D

Moar Languagez! GC content in Python, D, FPC, C++ and C (and now Go)

My two previous blog posts (this one and this one) on comparing the performance of a number of languages for a simple but very typical bioinformatics problem, spurred a whole bunch of people to suggest improvements. Nice! :) Many of the comments can be read in the comments on those posts, as well as in the G+ thread, while I got improvements sent by mail from Thomas Hume (thomas.hume -at- labri.fr) and Daniel Spångberg.

Anyway, here comes an updated post, with a whole array of improvements, and a few added languages.

One suggestion I got (by Thomas Koch, I think), was applicable to all the code examples that I got sent to me, namely to count GC, and AT separately, and add to the total sum only in the end. It basically cut a few percent of all execution times, so I went through all the code variants and added it. It did improve the speed in a simipar way for all the codes.

Many people suggested to read the whole file in once instead of reading line by line though. This can cause problems with the many very large files in bioinformatics, so I have divided the results below in solutions that read line by line, and those that read more than that.

Among the code examples I got, was "our own" Daniel Spångberg of UPPMAX, who wrote a whole bunch of C variants, even including an OpenMP parallelized variant, which takes the absolute lead. Nice! :)

More credits in the explanation of the codes, under each of the results sections.

Ok, so let's go to the results:

Performance results

Reading line by line

Here are first the codes that read only line by line. I wanted to present them first, to give a fair comparison.

Python1.692
Cython1.684
Go (8g)1.241
Go (gcc)0.883
Go Tbl (gcc)0.785
Go Tbl (8g)0.767
PyPy0.612
FPC (MiSchi)0.597
D (GDC)0.589
FPC0.586
FPC (leledumbo)0.567
D (DMD)0.54
D Tbl (DMD)0.492
D (LDC)0.479
C++ (HA)0.385
D Tbl (GDC)0.356
Go Tbl (RP) (8g)0.337
Go Tbl (RP) Ptr (8g)0.319
D Tbl (LDC)0.317
C (DS)0.276
C (TH)0.252
C (DS Tbl)0.183

Explanation of code, with links

All of the below codes have have been modified to benefit from the tip from Thomas Koch (thomas -at- koch.ro), to cound AC and GC separately in the inner loop, and sum up only in the end.

Click the language code to see the code!

  • Python: My code, with improvents from lelledumbo (here on the blog).
  • Cython: Same as "Python", compiled to C with Cython, with statically typed integers.
  • Go (8g): Go code compiled with inbuilt Go compiler.
  • Go (gcc): Go code compiled with GCC.
  • Go Tbl (gcc): Go code, table optimized, and compiled with GCC.
  • Go Tbl (8g): Go code, table optimized, and compiled with inbuilt Go compiler.
  • PyPy: My python code compiled with PyPy (1.9.0 with GCC 4.7.0)
  • FPC (MiSchi): FreePascal version improved by MiSchi (Tonne Schindler)
  • D (GDC): My D code, with many improvements suggested from the folks in the G+ thread. Compiled with GDC.
  • FPC: My FPC code
  • FPC (leledumbo): FreePascal version improved by Leledumbo (leledumbo_cool -at- yahoo.co.id)
  • D Tbl (DMD): My table optimized D code, compiled with DMD.
  • D (DMD): My D code, compiled with DMD.
  • D Tbl (GDC): My table optimized D code, compiled with GDC.
  • D (LDC): My D code, compiled with LDC.
  • C++ (HA): Harald Aschiz's C++ code.
  • Go Tbl (RP) (8g): Roger Peppe's optimized Go code, omitting string conversion and using range.
  • Go Tbl (RP) Ptr (8g): Roger Peppe's optimized Go code, additionally using pointers for the table opt.
  • D Tbl (LDC): My table optimized D code, compiled with LDC.
  • C (DS): Daniel Spångberg's C code (See his even faster ones in the next section!)
  • C (TH): Thomas Hume's C code.
  • C (DS Tbl): Daniel Spångberg's line-by-line version, with table optimization.

Reading more lines, or whole file

Here are the codes that don't keep themselves to reading line by line, but do more than so. For example Gerdus van Zyl's pypy-optimized code reads a bunch of lines at a time (1k seems optimal), before processing them, while still allowing to process in a line-by-line fashion. Then there is Daniel Spångberg's exercise in C performance, where by reading the file in at once, and applying some smart C tricks, and even doing some OpenMP-parallelization, cuts down the execution time under 100 ms, and that is for a 1million line file, on a rather slow MacBook air. Quite impressive!

PyPy (GvZ) PyPy PyPy (GvZ) + Opt C (DS Whole) C (DS Whole Tbl) C (DS Whole Tbl Par) C (DS Whole Tbl 16bit) C (DS Whole Tbl Par 16bit) C (DS Whole Tbl Par 16bit Unroll)
0.862s 0.626s 0.551s 0.178s 0.114s 0.095s 0.084s 0.070s 0.066s

Explanation of code, with links

Note: All of the below codes have been modified to benefit from the tip from Thomas Koch (thomas -at- koch.ro), to cound AC and GC separately in the inner loop, and sum up only in the end.

Conclusions

I think there are a number of conclusions one can draw from this:

  • C is in it's own class, when it comes to speed, which is seen in both of the categories above.
  • C++ is also fast, but D with the right compiler is not far behind.
  • Generally D and FPC is very close!
  • Pure python is not near the compiled ones, but surprisingly (for me), by using PyPy, it becomes totally comparable with compiled languages!
  • If you look both at the speed, and the compactness and readability of code at the same time, I find D to be a very strong competitor in this game, but at the same time, Go is very close, and already has a [code.google.com/p/biogo/ bioinformatics package (biogo)]!

What do you think?


Update May 11: Daniel Spångberg now provided a few even more optimized versions: DS Tbl: a table optimized version of the line-by-line reading, as well as optimized versions of the ones that read the whole file at once. On the fastest one, I also tried with -funroll-all-loops to gcc, to see how far we could get. The result (for a 58MB text file): 66 milliseconds!

Update May 16: Thanks to Franzivan Bezerra's post here, I now got some Go code here as well. I modified Francivan's gode a bit, to comply with our latest optimizations here, as well as created a table optimized version (similar to Daniel Spångberg's Table optimized C code). To give a fair comparison of table optimization, I also added a table optimized D version, compiled with DMD, GDC and LDC. Find the results in the first graph below.

Update II, May 16: The link to the input file, used in the examples, got lost. It can be downloaded here!

Update III, May 16: Thanks to Roger Peppe, suggesting some improved versions in this thread on G+, we now got two more, very fast Go versions, clocking even slightly below the idiomatic C++ code. Have a look in the first graph and table below!

Update IV, May 16: Now applied equivalent optimizations like Roger's ones for Go mentioned above, to the "D Tbl" versions (re-use the "line" var as buffer to readln(), and use foreach instead of for loop). Result: D and Go gets extremely similar numbers: 0.317 and 0.319 was the best I could get for D and Go, respectively. See updated graphs below.

Update May 17: See this post on how Francivan Bezerra acheived same performance as C with D, beating the other two (Go and Java) in the comparison. (Direct link to GDoc)

GC content continued: Python vs D vs C++ vs Free Pascal

My previous blog post, comparing a simple character counting algorithm between python and D, created an interesting discussion on Google+, with many tuning tips for the D version, and finally we also had a C++ version (kindly provided by Harald Achitz).

Then I could not resist to try out something I've been thinking about for a while (comparing D with Free Pascal (FPC)), so I went away and jotted down an FPC version as well (my first FPC code ever, I think).

Anyway, I now just wanted to summarize a comparison between all of these! I have added below the python code, the faster of the two D versions in my previous post, as well as the new additions: Harald's C++ version and my FPC version.

Performance results

PythonD (DMD)D (GDC)D (LDC)C++FPC
7.904s0.652s0.668s0.538s0.399s0.629s

Numbers are execution time in seconds, for counting the fraction of "G" and "C" characters compared to "A", "T", "C" and "T" in a 58 MB text file of nearly 1 million lines of text. And so, why not plot it as well:

My comments

Not surprising maybe that C++ is the fastest. I find it interesting though that both D and FPC perform in the same ballpark at least, with code written by a novice user (although with some minor tweaking).

For me personally, I also got a first answer on the question I've been wondering about for a while: Will D or FreePascal be faster, given that Pascal is an older and more mature language, and doesn't use a Garbage collector, while D on the other hand have better compiler support, which it can benefit from (like LLVM).

Since I've been betting the most on D lately, I find it interesting to see that still, D can perform better, at least with the right compiler. Still I'm impressed that FPC is totally on par with D, and beaten only when D is compiled with the LLVM backed LDC.

On another note though, I tend to like the compactness of the D code. It's not really that far from the python version, if omitting the closing curly brackets, no? Not bad for a statically compiled high performance language! :) (That is, while FreePascal has it's merits from using mostly natural language words, over quirky symbols, which IMO can enhance readability a bit).

The code

Python version

import re
import string
 
def main():
    file = open("Homo_sapiens.GRCh37.67.dna_rm.chromosome.Y.fa","r")
    gcCount = 0
    totalBaseCount = 0
    for line in file:
        line = line.strip("\n")
        if not line.startswith(">"):
            gcCount += len(re.findall("[GC]", line))
            totalBaseCount += len(re.findall("[GCTA]", line))
    gcFraction = float(gcCount) / totalBaseCount
    print( gcFraction * 100 )
 
 
if __name__ == '__main__':
    main()

D version

import std.stdio;
import std.string;
import std.algorithm;
import std.regex;
 
void main() {
    File file = File("Homo_sapiens.GRCh37.67.dna_rm.chromosome.Y.fa","r");
    int gcCount = 0;
    int totalBaseCount = 0;
    string line;
    char c;
    while (!file.eof()) {
        line = file.readln();
        if (line.length > 0 && !startsWith(line, ">")) {
            for(uint i = 0; i < line.length; i++) {
                c = line[i];
                if (c == 'C' || c == 'T' || c == 'G' || c == 'A') {
                    totalBaseCount++;
                    if ( c == 'G' || c == 'C' ) {
                        gcCount++;
                    }
                }   
            }
        }
    }
    float gcFraction = ( cast(float)gcCount / cast(float)totalBaseCount );
    writeln( gcFraction * 100 );
}

C++ version

(Kindly shared by Harald Achitz!)

#include <string>
#include <fstream>
#include <iostream>
 
int main() {
 
    std::fstream fs("Homo_sapiens.GRCh37.67.dna_rm.chromosome.Y.fa", std::ios::in);
 
    int gcCount = 0;
    int totalBaseCount = 0;
 
    if ( fs.is_open() )  {
        std::string line;
        while (std::getline(fs, line)) {
            if(*(line.begin()) != '>') {
                for(std::string::const_iterator pos = line.begin(); pos!=line.end() ; ++pos){
                     switch (*pos){
                       case 'A' :
                         totalBaseCount++;
                         break;
 
                       case 'C' :
                         gcCount++;
                         totalBaseCount++;
                         break;
 
                       case 'G' :
                         gcCount++;
                         totalBaseCount++;
                         break;
 
                       case  'T' :
                         totalBaseCount++;
                         break;
 
                       default:
                         break;
                     }
                }
          }
    }
    //std::cout << "gcCount: " << gcCount << " / totalBaseCount: "<< totalBaseCount << " = " ;
    std::cout << ( (float)gcCount / (float)totalBaseCount ) * 100 << std::endl ;
  } else {
    std::cout << "can't open file" ;
  }
  return 0 ;
}

Free Pascal (FPC)

program gc;
{$mode objfpc} // Do not forget this ever
 
uses
    Sysutils;
 
var
    FastaFile: TextFile;
    CurrentLine: String;
    GCCount: Integer;
    TotalBaseCount: Integer;
    i: Integer;
    c: Char;
    GCFraction: Single;
 
begin
    GCCount := 0;
    TotalBaseCount := 0;
 
    AssignFile(FastaFile, 'Homo_sapiens.GRCh37.67.dna_rm.chromosome.Y.fa'); 
    {$I+} //use exceptions
    try  
        Reset(FastaFile);
        repeat
            Readln(FastaFile, CurrentLine); 
            i := 0;
            while i < Length(CurrentLine) do
            begin
                c := CurrentLine[i];
                if (c = 'A') or (c = 'G') or (c = 'C') or (c = 'T')  then
                begin
                    TotalBaseCount := TotalBaseCount + 1;
                    if (c = 'G') or (c = 'C') then
                        GCCount := GCCount + 1;
                end;
                i := i + 1;
            end;
        until(EOF(FastaFile)); 
        CloseFile(FastaFile);
    except
        on E: EInOutError do
        begin
            Writeln('File handling error occurred. Details: '+E.ClassName+'/'+E.Message);
        end;    
    end;
    GCFraction := GCCount / TotalBaseCount;
    Writeln(FormatFloat('00.0000', GCFraction * 100));
end.

Compile flags

I used the following compile commands / flags for the test above (from the Makefile):

d:
        dmd -ofgc_d_dmd -O -release -inline gc.d
        gdmd -ofgc_d_gdc -O -release -inline gc.d
        ldmd2 -ofgc_d_ldc -O -release -inline gc.d
cpp:
        g++ -ogc_cpp -O3 gc.cpp
 
fpc:
        fpc -ogc_fpc -Ur -O3 -TLINUX gc.pas

Let me know if there is other flags that should be used, for some of the above compilers!

Impressions from the first D Coders Stockholm meetup

The first meetup of the D Coders Stockholm meetup.com group is just finished.(and the first meetup.com D meetup ever, as far as we know! :) ). I thought to share some impressions from the meetup.

I was pleasantly surprised that just a couple of weeks after the group started we gathered a group of five D coders for a real meetup, in relatively "small" city like Stockholm. Additionally, theoretically we could have doubled the number, based on the ten members of the D Coders Stockholm meetup group already.

So, what did we do or talk about? A good part of the meeting consisted of doing rounds and sharing each of ours experiences with D coding in different aspects.

At the end, Oscar and Daniel Brynolf (brothers) showed off some quite veru impressive work they have done on a game engine. I'll leave it to them selves to how much they want to talk about it, and not tell too much about it here though.

Anyways, the group turned out to be committed to contiuing with meetups small and large, and we were discussing various ways this could be done.

The main ideas circled around a combination of show-off meetings where we can show stuff we have done and discuss and share experiences, hackathons, as well as simpler "just meetups" over a beer/coffee" type of meetups.

In terms of interest areas, many in the group were interested in game development, but most also seemed to have also a general interest for all things D. One concrete idea for a "hackathon" subject, for example, was to create a group website in vibe.d (promising web framework in D).

Practically we concluded to try to collect ideas for meetup/hackathon topics in an "idea bucket", in the D Coders Stockholm meetup group forum, and when enough topics are gathered, turn it into a concrete meetup. So, let the ideas come! Looking forward to seeing more D in Stockholm/Sweden in the future! :)

Top D programming language links

Although there are numerous resources out there about the D programming language, they don't seem that easy to find. Here I'm trying to gather a top-list of resources for aspirind D coders:

UPDATE Mar 4, 2013: Implemented suggestions by Simen Endsjø

UPDATE Mar 5, 2013: Implemented suggestions by Xinok

D is great for small utility programs

Look how little code is needed to read from stdin, and do something with eash line of the output, in the D programming language:
import std.stdio;
 
void main() {
  foreach(line; stdin.byLine()) {
    writeln("Got input line: ", line);
  }
}
Compile the above code with:
dmd dtest.d -of"dtest"
... and pipe some output to the newly created binary:
ls -l | ./dtest

This should make D a perfect language for creating small utility apps for parsing text, that you can pipe to!

How to correctly compile with curl support in D

For some reason, dmd produces a linking command that puts curl and phobos2 in the wrong order (it is strange that it is order sensitive), which can be seen with "dmd -v". Phobos has to be linked before curl. In order to fix this when compiling, you can do:

dmd [filename] -L-lphobos2 -L-lcurl

Inside the .d file, use:

import std.net.curl;

For further discussion, see:

Tags:

Execute an external command in D

import std.stdio;
import std.process;
 
void main() {
  string output = shell("ls -l");
  write(output);
}

Compile it with the D2.0 dmd compiler:
dmd dls.d

... and the run the compiled binary:
./dls

(See also this question on StackOverflow, where I documented this first).