Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Why is my program so slow even though I've used hashes?

by Angharad (Pilgrim)
on May 28, 2009 at 16:17 UTC ( #766687=perlquestion: print w/replies, xml ) Need Help??

Angharad has asked for the wisdom of the Perl Monks concerning the following question:

The files that the script uses are enormous so I cant really post them here which I know makes live slightly difficult but I'm hoping people will see the flaws in the structure of the program and give me ideas as to how I can improve it. Knowing that storing data in arrays would make for a very slow program, I implemented hashes instead. But its still impossibly slow. It works but its too slow to be usable. Any tips much appreciated. Heres the code.

#!/usr/local/bin/perl # this script finds the residue numbers that are associated # with a particular domain and retrieves the catalytic site # residues for that domain use strict; use English; use Data::Dumper; use UNIVERSAL qw(isa); use FileHandle; # declare some variables my $domain; my $fsg; # this is the directory that the domain files are stored my $dir = "<my directory>"; # this is a file containing the domains of interest. my $domFile = shift; # we are going to go through this file one domain structure at a time # so we can pull out the appropriate CSA data # this is a file containing CSA data (from the website my $csafile = shift; my %csa_hash; my %dom_hash; # lets open the CSA data file open(CSAFILE, "$csafile") or die "unable to open $csafile: $!\n"; # ok lets get CSA information into a hash lookup while(<CSAFILE>) { my @csa_data = split(/\,/, $_); my $pdb = $csa_data[0]; my $chain = $csa_data[3]; my $res = $csa_data[4]; # i need to concatenate the three for now to obtain # a unique key for the hash my $csa_record = "$pdb" . "." . "$chain" . "." . "$res"; # now lets place all the contents in a hash $csa_hash{$csa_record} = 1; } # lets close the CSA file close(CSAFILE); # test printing the array containing the CSA data #print Dumper(%csa_hash); looks good # lets open the domFile file open(DOMFILE, "$domFile") || die "ERROR: Unable to open $domFile for r +eading: $!\n"; # we can go though the file using a while loop # we want to get all the residues in the domain # in a hash while(<DOMFILE>) { my @data = split(/\s+/, $_); $domain = $data[0]; #$fsg = $data[1]; # now to get the residue list of the # domain # we want this in a hash # open structure file for reading open(FILE, "$dir$domain") || die "Sorry, unable to open $dir$domai +n for reading\n"; while (my $line = <FILE>) { chomp $line; my @ff = split /\s+/,$line; my $number = $ff[5]; my $CA = $ff[2]; # looking just for CA atoms of pdb file if("$CA" eq "CA") { $dom_hash{$domain}{$number} = 1; } } } # ok, now we have both the CSA and domain information in hashes # it should be easy to compare them for my $protein_dom ( keys %dom_hash ) { for my $residue (keys %{ $dom_hash{$protein_dom} } ) { # in order to compare the domain data and the # CSA data I need to extract the chain data my $domchain = substr($protein_dom, 0, 5); # ok, now we just check if the same information # can be found in the CSA hash while ((my $key, my $value) = each(%csa_hash)) { #print "$key\n"; # ok we now need to split up the key in the hash my $pdb = substr($key, 0, 4); my $chain = substr($key, 5, 1); my $res = substr($key, 7, 6); $res =~/\S/g; # getting rid of excess white space #print "$pdb $chain $res\n"; # works great. using subst +ring as I dont really want to create an array my $pdbchain = "$pdb" . "$chain"; # concatenate together so to + compare with domain data # print "$pdbchain\n"; # works fine # lets be on the safe side and remove white space # for domchain and pdbchain $domchain =~/\S/g; $pdbchain =~/\S/g; chomp($domchain); chomp($pdbchain); # lets find CSA data for a particular domain if("$domchain" eq "$pdbchain") { # print off residues that are common # to both if("$res" eq "$residue") { print "$domchain $pdbchain $residue $res\n"; } } } } }

Replies are listed 'Best First'.
Re: Why is my program so slow even though I've used hashes?
by moritz (Cardinal) on May 28, 2009 at 16:30 UTC
    Well, programs don't run faster magically just because you use hashes. They only give you speed if you don't have to loop over the whole hash, but look up the values by key.

    So instead of using your current keys for storage, use the value that is called $pdbchain in your program as a hash key. Then you can replace whole while (($key, $value) = each %hash) { if ($a eq $b) { ... } } with a single hash lookup, which should improve the performance.

Re: Why is my program so slow even though I've used hashes?
by ikegami (Patriarch) on May 28, 2009 at 17:31 UTC

    Bug: The following do anything (useful):

    $res =~/\S/g; $domchain =~/\S/g; $pdbchain =~/\S/g;

    You want:

    $res =~ s/\s//g; $domchain =~ s/\s//g; $pdbchain =~ s/\s//g;

    Also, all over you have "$var" which needlessly makes a copy of $var. Drop the quotes. You want just $var. For example,

    if("$domchain" eq "$pdbchain")
    should be
    if($domchain eq $pdbchain)

Re: Why is my program so slow even though I've used hashes?
by akho (Hermit) on May 28, 2009 at 16:55 UTC
    As an addition to what moritz said (which is the most important thing here):
    • use English makes your regular expressions dramatically slower (see English).
    • Since you don't use English names for punctuation variables—it is unnecessary anyway. So are use UNIVERSAL qw(isa) (which should not be used as a function anyway) and use FileHandle. However, use warnings would be nice.
Re: Why is my program so slow even though I've used hashes?
by jettero (Monsignor) on May 28, 2009 at 16:49 UTC

    In the olden days English was known to slow down all your regular expressions. (I think they fixed that in 5.10?) That could be part of the problem.

    Which part of your program is slow?

    -Paul

      I think its ok until I get to the bit where I'm going though the %dom_hash hash.
Re: Why is my program so slow even though I've used hashes?
by DStaal (Chaplain) on May 28, 2009 at 17:13 UTC

    In addition to what everyone else has said: Whenever you hear/think/say 'why is my code slow', profile!

      Given the simplicity of the program (two nested loops), profiling won't tell you much ("the nested content is slow") until you've done some high-level analysis.

      If the nested loops can be eliminated or sped up, improvements will ensue. For example, if it's possible for $domain to have the same value for two rows of DOMFILE, a file is being read more often than it needs to be.

      And then there's the three-deep loop at the bottom. Efforts should be placed into flattening those.

      Once that's done, profiling could be used to do some micro-optimisations.

      Update: That one part of the program is IO-bound and the other is CPU-bound is noteworthy. Maybe parallelisation is an option.

        I'm of the opinion that the added understanding gained by profiling is worth it even in simple cases. At the point where you are trying to speed it up, even educated guessing is often wrong. And Devel::NYTProf (which I linked to above) does both line-level and block-level profiling, so it would directly say that the problem is that you are running these loops too often. (Leading the optimizer to start looking for ways to run them less, hopefully.)

        When looking at profile output, there is a temptation to focus on individual lines I'll admit; but it can and does help just as much on a broader scale, as long as the programmer resists that temptation.

Re: Why is my program so slow even though I've used hashes?
by Angharad (Pilgrim) on May 28, 2009 at 18:25 UTC
    Thanks very much for all your comments so far. With that in mind, I changed some of my code as follows
    foreach my $key (sort keys %csa_hash) { #print "$key\n"; # ok we now need to split up the key in the hash my $pdb = substr($key, 0, 4); my $chain = substr($key, 5, 1); my $res = substr($key, 7, 6); #print "$pdb $chain $res\n"; # works great. using substring as I d +ont really want to create an array my $pdbchain = "$pdb" . "$chain"; # concatenate together so to com +pare with domain data # print "$pdbchain\n"; # works fine # lets be on the safe side and remove white space # for domchain and pdbchain $res =~ s/\s//g; #$domchain =~ s/\s//g; $pdbchain =~ s/\s//g; #chomp($domchain); chomp($pdbchain); if($dom_hash{$pdbchain}{$res}) { print "$pdbchain $res\n"; } }
    And now it runs in seconds. I'm no longer looping over %dom_hash, I'm simply using it as a look up table.
Re: Why is my program so slow even though I've used hashes?
by Marshall (Canon) on May 28, 2009 at 19:54 UTC
    I don't have any sample data to work with, and I might be wrong, but even if I am, perhaps you will get some new ideas...

    I think the problem starts with how the CSA_hash is built. You have 3 values: $pdb,$chain,$res that are concatenated together to form one key and the value of that key is always 1. That is all well and good if the main thing is that this combination of things is only counted once. Maybe you need to do that, I don't know. BUT later on in the most performance critical part of the code, what you really want to know is what $res's correspond to the $pdb,$chain combination. So another idea for CSA_hash, would be like this:

    die "some usage error msg" if (@ARGV !=2); my ($domFile,$csafile)= @ARGV; open(CSAFILE, "$csafile") or die "unable to open $csafile: $!"; my %csa_hash; my %dom_hash; my $domain_dir = "<my directory>"; while(<CSAFILE>) { chomp; s/\s+//g; #keep things simple, delete spaces my ($pdb,$chain,$res) = (split(/,/, $_))[0,3,4]; push (@{$csa_hash{"$pdb;$chain"}},$res}); }
    This is a HoL, Hash of List. Maybe there can be duplicate $res values for each "$pdb;$chain" combo? I don't know. If there are, then it is not hard to fix that.

    Where all of this is headed is to the 3rd loop level:

    while ((my $key, my $value) = each(%csa_hash)) {....}
    note that $value here is irrelevant (it is always 1). %csa_hash is being used like a list NOT a hash! This is actually the worst possible case of a search: it is linear and it always access all N items in the list. If there are a lot of keys in %csa_hash, this will bog things down quite a bit! I think this is a very key statement:

    if("$domchain" eq "$pdbchain"){....}
    This $domchain is a function of just the stuff that was used to create the csa_hash! Or actually the modified version above. A hash is a horrible thing to waste...or so the saying goes... So I recommend created the csa_hash with keys that are easy for the inner most loop to access. This routine is going to get "hit a lot", but you want fast answer, not a N*keys(csa_hash) answer.

    One thing that I think is noteworthy is that if a string can work in a print statement, it will work as a hash key, eg. $somehash{"$pdb;$chain"}= $res; If the ";" is not a valid value inside of the $parm vars, then this works great. If you have a multi-value key, you can do a split on ";".

    hope this helps.

Re: Why is my program so slow even though I've used hashes?
by akho (Hermit) on May 28, 2009 at 18:05 UTC
    What could
    $domchain =~/\S/g; $pdbchain =~/\S/g; chomp($domchain); chomp($pdbchain);
    possibly accomplish?

    I tried to fix some things in the code below, but, naturally, I could't try to run it (as I don't have the files).

    use strict; use warnings FATAL => 'all'; use autodie; my $dir = "<my directory>"; my ( $dom_file_name, $csa_file_name ) = @ARGV; my %csa_hash; my %dom_hash; open my $csa_file, '<', $csa_file_name; while ( my $csa = <$csa_file> ) { my @csa_data = split( /\,/, $csa ); $csa_hash{ $csa_data[0] . $csa_data[3] } = $csa_data[4]; } close($csa_file); open my $dom_file, '<', $dom_file_name; while ( my $dom = <$dom_file> ) { my @dom_data = split /\s+/, $dom; my $domain = $dom_data[0]; next if exists $dom_hash{$domain}; open my $ind_dom_file, '<', $dir . $domain; while ( my $line = <$ind_dom_file> ) { chomp $line; my @ff = split /\s+/, $line; my $number = $ff[5]; my $CA = $ff[2]; push @{ $dom_hash{$domain} }, $number if $CA eq 'CA'; } close $ind_dom_file; } close $dom_file; while ( my ( $protein_dom, $residues_ref ) = each %dom_hash ) { for my $residue ( @{$residues_ref} ) { my $dom_chain = substr( $protein_dom, 0, 5 ); if ( $residue eq $csa_hash{$dom_chain} ) { print "$dom_chain $residue\n"; } } }

    The idea was that it does the same thing as your code, but faster.

Re: Why is my program so slow even though I've used hashes?
by bichonfrise74 (Vicar) on May 28, 2009 at 18:26 UTC
    Try using Devel::DProf to profile your code. It will show you which subroutines are taking a long time to finish.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://766687]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2023-02-05 23:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (33 votes). Check out past polls.

    Notices?