latvianlinuxgirl: Adventures in GSOC

Google Code Jam 2009

2009-07-21T19:20:00.003-04:00

Just got to know that Google Code Jam is on this year too. Definitely will participate. Last year I got past Qualification round. This year I will have to practice more and hopefully will get past Round 1.

OSCON 2009

2009-07-20T14:27:00.003-04:00

Just wanted to say that I am excited to be at OSCON 2009 conference. :) Also excited to meet other GSOC students at BoF session.

Profiling code: Breadth first search surprise

2009-06-28T22:51:00.004-04:00

At this point in the project I am almost done with writing parser so I did some profiling of the code.

My system is Ubuntu 9.04, ruby 1.8.7 [i486-linux], Intel Core 2 Duo P8600 @2.4GHz

I created test_phyloxml_big.rb test file. It has test_next_tree method which calls next_tree on the phyloxml file until end of file is reached. Here follow results on the ncbi_taxonomy_mollusca.xml file which is 1.5MB large with 5632 external nodes.

It takes around 7.5min to finish test_phyloxml_big.rb test.
(Finished in 443.231507 seconds.
Finished in 457.255576 seconds. )

output of the top:

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
21222 diana 20 0 29020 25m 1928 R 95 0.9 5:32.92 ruby

So it looks like memory footprint is small ~ 25MBs. CPU usage is 95% (i have two processors, so it is completely using one of them).

I did the same thing for tol_life_xml but it took forever to finish. (more than 3 hours)

For curiosity I created a method next_tree_dummy. All it does is to reader.read from file until it reaches element.

tree of life xml (file size: 45.1MB) - Finished in 3.177743 seconds.

mollusca xml (1.5MB) - Finished in 0.252993 seconds.

metazoa xml (32.3MB) - Finished in 3.393467 seconds.

I think this shows that libxml is really fast.

I also did profiling with ruby-prof on ncbi mollusca taxonomy file.

Here is partial output:


diana@diana-ubuntu:~/bioruby$ ruby-prof -p graph test/unit/bio/db/test_phyloxml_big.rb
Loaded suite /usr/bin/ruby-prof
Started
.
Finished in 1345.4039 seconds.

1 tests, 0 assertions, 0 failures, 0 errors
Thread ID: 3084157360
Total Time: 1257.6

[..]
-------------------------------------------------------------------------------
                   1257.56      0.60      0.00   1256.96              2/2     Bio::TestPhyloXMLBig#test_next_tree
 100.00%   0.05%   1257.56      0.60      0.00   1256.96                2     Bio::PhyloXML#next_tree
                      0.08      0.03      0.00      0.05       8107/16210     Bio::PhyloXML#parse_attributes
                      0.00      0.00      0.00      0.00         1/243188     String#==
                      0.00      0.00      0.00      0.00       8104/24322     LibXML::XML::Reader#[]
                      6.18      0.97      0.00      5.21      48616/48616     Bio::PhyloXML#parse_clade_elements
                      0.14      0.14      0.00      0.00      48623/97244     LibXML::XML::Reader#read
                      0.27      0.17      0.00      0.10     48644/875134     Bio::PhyloXML#is_element?
                      0.11      0.04      0.00      0.07      16206/32442     Class#new
                      0.04      0.04      0.00      0.00     16206/116034     Kernel#==
                      0.00      0.00      0.00      0.00          4/72929     Bio::PhyloXML#parse_simple_elements
                      0.07      0.01      0.00      0.06        8102/8102     Bio::Tree#add_node
                      0.44      0.31      0.00      0.13     97243/137758     Bio::PhyloXML#is_end_element?
                   1249.05      0.02      0.00   1249.03        8102/8102     Bio::Tree#parent
                      0.58      0.07      0.00      0.51        8102/8102     Bio::Tree#add_edge
-----------------------------------------------------------------------------
                   1249.05      0.02      0.00   1249.03        8102/8102     Bio::PhyloXML#next_tree
  99.32%   0.00%   1249.05      0.02      0.00   1249.03             8102     Bio::Tree#parent
                   1249.03      0.13      0.00   1248.90        8102/8102     Bio::Tree#path
                      0.00      0.00      0.00      0.00       8102/72975     Array#[]
--------------------------------------------------------------------------------
                   1249.03      0.13      0.00   1248.90        8102/8102     Bio::Tree#parent
  99.32%   0.01%   1249.03      0.13      0.00   1248.90             8102     Bio::Tree#path
                      0.04      0.01      0.00      0.03  16204/164638052     Hash#[]
                   1248.82      0.27      0.00   1248.55        8102/8102     Bio::Pathway#bfs_shortest_path
                      0.03      0.03      0.00      0.00     24306/116034     Kernel#==
                      0.01      0.01      0.00      0.00      16204/72975     Array#[]
--------------------------------------------------------------------------------
                   1248.82      0.27      0.00   1248.55        8102/8102     Bio::Tree#path
  99.30%   0.02%   1248.82      0.27      0.00   1248.55             8102     Bio::Pathway#bfs_shortest_path
                      0.26      0.19      0.00      0.07 142736/164638052     Hash#[]
                      0.07      0.07      0.00      0.00     75419/116034     Kernel#==
                   1248.18    115.50      0.00   1132.68        8102/8102     Bio::Pathway#breadth_first_search
                      0.04      0.04      0.00      0.00      67317/67330     Array#unshift
--------------------------------------------------------------------------------
                   1248.18    115.50      0.00   1132.68        8102/8102     Bio::Pathway#bfs_shortest_path
  99.25%   9.18%   1248.18    115.50      0.00   1132.68             8102     Bio::Pathway#breadth_first_search
                    136.52     92.65      0.00     43.8765785140/164638052     Hash#[]
                     22.53     22.53      0.00      0.0032900672/32900681     Array#shift
                    973.59    324.56      0.00    649.0332892570/32892570     Hash#each_key
                      0.04      0.03      0.00      0.01   24306/98702064     Hash#[]=
[..]

99.32% of the total time is spent in Bio::Tree#parent method and the methods it calls.
Bio::Tree#parent calls Bio::Tree#path which calls Bio::Pathways#bfs_shortest_path which in turn calls Bio::Pathway#breadth_first_search (99.25% of total time is spent in this method and its sub calls).

This was a huge surprise for me. Why would breadth first search be needed if I just want to know the parent node of the current node.

The reason I am using Bio::Tree#parent is because I have to keep track of the current node I am parsing. When I have reached element i set the current_node to the parent of the node I just parsed.

I see here two options.

1) Keep track of the current node myself (by putting references in an array and pushing and poping accordingly). Thus I won't have to call the Bio::Tree#parent method.

2) Update Bio::Tree/ Bio::Node class so that nodes contain references to their parents. (thus not needing to call breadth first search).

What do you think?

(Code is available at github )

A quote about Microsoft

2009-06-15T11:52:00.002-04:00

I somehow ended up reading this site and read this awesome quote:

"The day Microsoft makes something that doesn't suck is probably the day they start making vacuum cleaners." -Ernst Jan Plugge

No offense to anybody, but it is funny!

Calling method from string in Ruby

2009-05-31T19:09:00.009-04:00

A week and a little bit has passed since the beginning of coding for Google Summer of Code 2009. I am getting more and more excited since I am learning more of advanced Ruby programming.

So I am parsing XML into objects using LibXML::XML::Reader. I had this code:

 1     def parse_events()
 2       events = Events.new
 3       @reader.read #go to next element
 4       #read while have reached end of events
 5       while not(is_end_element?('events')) do
 6         if is_element?('type')
 7           @reader.read
 8           events.type = @reader.value
 9           @reader.read
10           has_reached_end_tag?('type')
11         end
12         if is_element?('duplications')
13           @reader.read
14           events.duplications = @reader.value.to_i
15           @reader.read
16           has_reached_end_tag?('duplications')
17         end
18         if is_element?('speciations')
19           @reader.read
20           events.speciations = @reader.value.to_i
21           @reader.read
22           has_reached_end_tag?('speciations')
23         end
24         if is_element?('losses')
25           @reader.read
26           events.losses = @reader.value.to_i
27           @reader.read
28           has_reached_end_tag?('losses')
29         end
30         if is_element?('confidence')
31           events.confidence = parse_confidence
32         end
33         @reader.read
34       end
35       return events
36     end #parse_events

This was too much of code duplication, but the problem was that each time different method of the events object is called.

After some searching on interwebs, luckily, I found out that ruby has a method send, which invokes the method identified by symbol and passes any arguments.

So I created such method:


  def parse_simple_element(object, name)
    if is_element?(name)
      @reader.read
      object.send("#{name}=", @reader.value)
      @reader.read
      has_reached_end_tag?(name)
    end
  end

So now the method parse_events() can be rewritten like this:


   def parse_events()
     events = Events.new
     @reader.read #go to next element
     while not(is_end_element?('events')) do
       ['type', 'duplications', 'speciations', 'losses'].each { |elmt|
         parse_simple_element(events, elmt)
       }
       if is_element?('confidence')
         events.confidence = parse_confidence
       end
       @reader.read
     end
     return events
   end #parse_events

Much shorter!! Now I run the unit tests and it works! No worries that I broke something while refactoring code. In cases like this I really appreciate the power of unit testing.

Hello World!

2009-05-25T22:12:00.000-04:00

I wanted to have a blog for quite a long time, and now I have a good reason to start it: Google Summer of Code 2009.

My project is to implement phyloXML support in BioRuby and I am working for NESCent organization.

Here is the project abstract:

Phylogenetic trees are used in important applications, including phylogenomics, phylogeography, gene function prediction, cladistics and the study of molecular evolution. In order to foster successful analysis, exchange, storage and reuse of phylogenetic trees and associated data, the phyloXML format was developed. It can store all necessary information about the phylogenetic tree, like clade, sequence, name and distance. The goal of this project is to implement support for phyloXML in BioRuby.

My project page is: https://www.nescent.org/wg_phyloinformatics/PhyloSoC:PhyloXML_support_in_BioRuby

The source code is on GitHub: http://github.com/rozziite/bioruby/tree/master

I have been using Open Source software for quite a long time already and I am now excited to contribute back to community.