Ok, I have looked at the example that was the slowest: 5 times slower than gcc.

k-nucleitide: http://shootout.alioth.debian.org/u32/benchmark.php?test=knucleotide&lang=all

The C++ code is giving me headaches from only am
still not sure what the hell they have done (or cheated) to reach this speed. Looking at the Python example explains what the benchmark actually does in less than a screenpage.

I am trying to implement a completely new Pascal version. Below is what I have already, it will be about 50% faster than the previous Pascal example. I am cheating too. Instead of a hash table in the commonly known sense my "hash table" is implemented as a trie.

It still does what the hash table would be supposed to do, and therefore does not violate the spirit of this benchmark, it will hold key-value pairs, the key is the DNA fragment (string) and the value is its count. in a wider sense this could be seen as just a different way to implement a hash table, to the outside it is behaving like one.

The main goal is to first count the occurrences of fragments of several sizes and store the count for each of them in a hash table (I store them in a trie because I think it is about storing an looking up vast amounts of key-value pairs and not how exactly this hash table is internally implemented). Then in the second step use this to look up and print a few of them.

'GTCA' or 'gtca', when you shr 1 and $03 each char you end up with numbers from 0..3, so the first thing I do is transform the entire thing into a string of numbers 0..3. Then my alphabet has only 4 letters. Each node in my trie has an array of 4 sub nodes for the possible next letter of the key. I am counting all the frequencies all at once, each time a node is missing I insert it and if it is already there I increase its count. This will give me all counts of all fragments of all lengths from 1..18 with one pass.

Then I look up and print the required ones.

The sorted output of 'aa'..'tt' sorted by frequency is still missing. I don't have much time for this today anymore, I will continue later. Also I doubt they will ever accept it. I only wanted to know why on earth the C++ version can be so fast and why the existing Pascal version is so slow and how fast this problem can be

Mmm..
4.45s to complete and log all make actions (C++ gnu g++) 0.11s to complete and log all make actions (Pascal Free Pascal)

we _are_ _compiling_ it faster ;)

and
132,656 kB vs 127,684 kB memory, we're actually _better_ than them ;) and 2383 vs 2106 code length (well they're better here).

Maybe
/usr/local/src/fpc-2.4.2.i386-linux/bin/fpc -FuInclude/fpascal -XXs -Oppentiumm -Cppentiumm -O3 -Cfsse2 -oFPASCAL_RUN knucleotide.fpascal-2.pas

the command line also is the answer ? (is the Q6600 64bit ?) also c++ code sports things like cpu affinity, while we don't... or they try to _parallelize_ it behind the machines' back ?

Hard to say.

(Not that I know much about c++ generally)
:)
Lukasz
[...]

Bernd

Oh yeah, look:

(c++ code)
Queue workQueue;
  Worker *workers = new Worker[cpus.count];
  for ( u32 i = 0; i < cpus.count; i++ )
    workers[i].start( &workQueue, block );
  for ( u32 i = 0; i < cpus.count; i++ )
    workers[i].join();

They do it in workqueues...

also they read 4 bytes characters input

void addline( const char *buffer, int bytes )
[...]
u8 *out = (u8 *)( data + count / 4 );
// 00000dd0:00000cc0-00000bb0:00000aa0 -> ddccbbaa

-> they take advantage of unicode or whatever mcbs the shell makes them do ?

I think we spend too much time&effort adding data to buffer

(procedure main)
[...]
  while not eof do begin
     readln(s);
     if (s[1]  '>') and (s[1]  ';') then begin
       len:=length(s);
       if (bufferptr+len+1)>buffersize then  begin
         inc(buffersize,buffersize);
         reallocmem(buffer,buffersize);
       end;
       move (s[1],buffer[bufferptr],len);
       inc(bufferptr,len);
     end;
   end;
instead of getting it processed on the fly;

(this just 5 min I had to spare, now I have to go ;) L.