[BioRuby] Benchmarking FASTA file parsing
Tomoaki NISHIYAMA
tomoakin at kenroku.kanazawa-u.ac.jp
Sat Aug 14 10:52:57 EDT 2010
Hi,
> Subparsing of the defline should not be done for generic parsing,
> but rather when needed.
To my understanding, the subparsing of the definition occurs only
when needed, ie when entry_id, identifiers, gi, etc. is called, in
current code.
If only definition is called, it is not further parsed.
> Without any experience I think that disabling GC sounds like a bad
> idea.
Yes, completely disabling GC is generally a bad idea.
A code running with 6 Gbytes mem could eat 60 Gbytes or more...
(Yes it seems two or three-fold faster if there is enough memory,
but this trade-off is too extreme).
But since the GC dominates the running time,
it is an important target for optimization.
http://en.wikibooks.org/wiki/Ruby_Programming/Reference/Objects/GC
A more moderate reduction of GC frequency will surely speedup the
process 30~50%.
Admittedly, explicit GC.disable, GC.start make the code ugly.
Trial on tweaking the parameters in gc.c did only a minor (~5%)
improvement.
Careful coding to reduce object creation might contribute to speed up.
One of questionable variable is
@entry_overrun
Is this variable and attr_reader :entry_overrun
really required yet or is just a trace of older code? > Goto-San
Since there is only two other variables, which is apparently essential,
this third variable might account significant speed reduction.
A tests suggested again removing 3 lines can improve 5%.
(Unfortunately not 50%)
diff --git a/lib/bio/db/fasta.rb b/lib/bio/db/fasta.rb
index 7ea668e..95f3be4 100644
--- a/lib/bio/db/fasta.rb
+++ b/lib/bio/db/fasta.rb
@@ -111,7 +111,7 @@ module Bio
# The seuqnce lines in text.
attr_accessor :data
- attr_reader :entry_overrun
+# attr_reader :entry_overrun
# Stores the comment and sequence information from one entry of
the
# FASTA format string. If the argument contains more than one
@@ -119,8 +119,8 @@ module Bio
def initialize(str)
@definition = str[/.*/].sub(/^>/, '').strip # 1st line
@data = str.sub(/.*/, '') # rests
- @data.sub!(/^>.*/m, '') # remove trailing entries for sure
- @entry_overrun = $&
+# @data.sub!(/^>.*/m, '') # remove trailing entries for sure
+# @entry_overrun = $&
end
# Returns the stored one entry as a FASTA format. (same as to_s)
--
Tomoaki NISHIYAMA
Advanced Science Research Center,
Kanazawa University,
13-1 Takara-machi,
Kanazawa, 920-0934, Japan
On 2010/08/14, at 17:21, Martin Asser Hansen wrote:
> I was hoping for an easy to use generic FASTA parser in bioruby. I
> think it would be confusing with two flavors of parsers for short/
> long entries. Also, I think that with a minor effort the existing
> parser could be optimized a fair bit. Subparsing of the defline
> should not be done for generic parsing, but rather when needed.
> Without any experience I think that disabling GC sounds like a bad
> idea. Of cause C is always faster, but Ruby is nicer.
>
>
> Cheers,
>
>
> Martin
>
>
>
>
> On Sat, Aug 14, 2010 at 5:42 AM, Tomoaki NISHIYAMA
> <tomoakin at kenroku.kanazawa-u.ac.jp> wrote:
> Hi,
>
>> Mind you that the Benchmark is performed on StringIO data, and
>> that the script does not touch the disk!
>> In a real test, it will be much slower!
>
> My initial thought was :- That's true, and therefore the pure
> parser part which runs fairly fast with O(N)
> is not the primary problem. If you push the entries into a hash it
> will be much more time consuming.
>
> But realized that its two orders slower... (due to the benchmark
> code as pointed out by goto-san)
> 20 min for 100 M could be painful.
>
>> I have been trying to get an overview of the code in
>> Bio::FastaFormat,
>> but I find it hard to read (that could be because I am not used to
>> Ruby, or OO for that matter).
>
>
> For one thing, the Bio::FastaFormat is designed to work with
> Bio::FlatFile.
> If you write a dedicated fasta parser that could run much faster.
>
> # I would write C codes for a very simple operation on NGS data.
> # That will run 100 times faster.
> # When the necessary operation is a bit more complex, I would use
> ruby. much much more time consuming....
>
> Perhaps the target is to process about 20 ~ 1000 M reads with each of
> them having 25 to 150 nt for the time being.
> Thats quite different situation compared to process the
> ~ 0.1 M entry of 50-10000 aa residues or nucleotides in a genome.
> The relative cost for the entry separation becomes higher compared
> with the sequence
> processing within the entry.
>
> So, it may worth to write NGS dedicated parser rather than sticking
> on FlatFile.
>
> Playing around the benchmark, about the half of execution time is
> for garbage collection,
> and the order of execution is somewhat relevant to get the number.
> If you can suppress unnecessary object generation to the minimum
> and disable GC, that will
> perhaps make it run much faster.
>
> $ diff -u benchfasta benchfasta-hash-GC-b
> --- benchfasta 2010-08-13 21:45:21.000000000 +0900
> +++ benchfasta-hash-GC-b 2010-08-14 11:53:20.000000000 +0900
> @@ -34,6 +34,9 @@
> end
> end
>
> +count = ARGV.shift.to_i
> +count = 2 if count == nil
> +
> data = <<DATA
> >5_gECOjxwXsN1/1
> AACGNTACTATCGTGACATGCGTGCAGGATTACAC
> @@ -57,12 +60,23 @@
> TTATGATGCGCGTGGCGAACGTGAACGCGTTAAAC
> DATA
>
> -io1 = StringIO.new(data)
> -io2 = StringIO.new(data)
> +io0 = StringIO.new(data * count)
> +io1 = StringIO.new(data * count)
> +io2 = StringIO.new(data * count)
> +fasta0 = Fasta.new(io0)
> fasta1 = Fasta.new(io1)
> fasta2 = Bio::FastaFormat.open(io2)
>
> -Benchmark.bm(5) do |timer|
> - timer.report('Hack') { 10_000_000.times { fasta1.each { |
> entry1| } } }
> - timer.report('Bio') { 10_000_000.times { fasta2.each { |
> entry2| } } }
> +hash0=Hash.new
> +hash1=Hash.new
> +hash2=Hash.new
> +
> +Benchmark.bm(8) do |timer|
> + GC.enable;GC.start;GC.disable;
> + timer.report('Bio') { i=0; fasta2.each { |entry2| i+=1; hash2
> [entry2.definition + i.to_s] = entry2.seq[2..25]} }
> + hash2 = nil; GC.enable;GC.start;GC.disable;
> + timer.report('Hack') { i=0; fasta0.each { |entry1| i+=1; hash0
> [entry1[:seq_name] + i.to_s] = entry1[:seq][2..25]} }
> + hash0 = nil; GC.enable;GC.start;GC.disable;
> + timer.report('Hack-seq') { i=0; fasta1.each { |entry1| i+=1;
> hash1[entry1[:seq_name] + i.to_s] = Bio::Sequence::NA.new(entry1
> [:seq])[2..25]} }
> + hash1 = nil; GC.enable;GC.start;GC.disable;
> end
>
>
>
>
>
>
> --
> Tomoaki NISHIYAMA
>
> Advanced Science Research Center,
> Kanazawa University,
> 13-1 Takara-machi,
> Kanazawa, 920-0934, Japan
>
>
> On 2010/08/13, at 23:51, Martin Asser Hansen wrote:
>
>>
>> As you stated 3 times faster with the hack, you may be already
>> using ruby 1.9.
>>
>>
>> I am using ruby 1.9.1, and I am using a fairly fast computer, but
>> I am actually questioning the quality of the code.
>>
>> Anyway, I think 13 or 18 seconds for 100 M entry is fast enough
>> and this
>> part will not be the bottle neck of any application.
>> How fast do you need it be?
>>
>> Mind you that the Benchmark is performed on StringIO data, and
>> that the script does not touch the disk! In a real test, it will
>> be much slower! I did not test on real data and more speed issues
>> may surface (I have no idea how Ruby's file buffering compares to
>> Perl's, performance-wise).
>>
>> I was contemplating porting some Biopieces (www.biopieces.org)
>> from Perl to Ruby. Biopieces are used for everyday slicing and
>> dicing of all sorts of biological data in a very simple and
>> flexible manner. While Biopieces are not as fast as dedicated
>> scripts, they are fast enough for convenient analysis of NGS data,
>> but I will not accept a +300% speed penalty (i.e. read_fasta).
>>
>> I have been trying to get an overview of the code in
>> Bio::FastaFormat, but I find it hard to read (that could be
>> because I am not used to Ruby, or OO for that matter). It strikes
>> me that the FastaFormat class does a number of irrelevant things
>> like subparsing comments when not strictly necessary. In fact, the
>> FASTA format actually don't use comments prefixed with #
>> (semicolon can be used, but I will strongly advice against it
>> since most software don't deal with it). Also, parsing is
>> dependent on the record separator being '\n' - that could be
>> considered a bug. There seem to be an overuse of substitutions,
>> transliterations and regex matching. How about keeping it nice an
>> tight? ala:
>>
>> SEP = $/
>> FASTA_REGEX = /\s*>?([^#{SEP}]+)#{SEP}(.+)>?$/
>>
>> def get_entry
>> block = @io.gets(SEP + ">")
>> return nil if block.nil?
>>
>> if block =~ FASTA_REGEX
>> seq_name = $1
>> seq = $2
>> else
>> raise "Bad FASTA entry->#{block}"
>> end
>>
>> seq.gsub!(/\s/, "")
>> end
>>
>>
>> Cheers,
>>
>>
>> Martin
>>
>> --
>> Tomoaki NISHIYAMA
>>
>> Advanced Science Research Center,
>> Kanazawa University,
>> 13-1 Takara-machi,
>> Kanazawa, 920-0934, Japan
>>
>>
>
>
More information about the BioRuby
mailing list