Re: Ada Shootout program for K-Nucleotide (patches)

[jonathan <johnscpg@googlemail.com>]

On Aug 20, 11:15 pm, Georg Bauhaus <rm.tsoh.plus-
bug.bauh...@maps.futureapps.de> wrote:
> jonathan wrote:
> >   Key.Data(1 .. Length) := Buffer (I-Length+1 .. I);
>
> > The string Key.Data already contains most of the desired
> > data. Since Buffer may be in slower memory, and Key.Data
> > in very fast memory, it makes sense to update
> > Key.Data from itself whenever possible:
>
> Maybe, then, it is worthwhile loading a page worth
> of characters from the big string for the next round
> of fill-up completions?  If this loading doesn't happen
> perfectly anyway, that is.
>
> Or if we are at it, we might experiment with slice renamings
> or pointer artihmetic; requires a rewrite, I'd think.
> If the rules permit this at all ;-)

I did make another attempt here.  I made the string:

   type Bounded_String is record
      Data  : String(1 .. Max_String_Length);
      First : Natural;
      Last  : Natural;
   end record;

Now make Max_String_Length large, and if you want to slide
array Data a distance Shift_Length all you have to do in most
cases is increment First and Last by Shift_Length.

This essentially removed all the overhead in sliding
array Data.  I was very pleased with myself. (And again
astonished at how much an Ada compiler can do to help you
get it right.)  Unfortunately, it slowed the program
down quite a bit.  I think it just made the string "="
more complicated and slower. SO I've happily dropped that
approach.

I'll be off-line for a few days, so let me summarize what
we have.  The program is in good shape and very fast.
Martin Krischik wrote a good program, and we've now added a
light-weight string, inlined a few things by hand, and
worked around a GNAT 4.3.3 problem by using unbound strings.

Here's a rough speed estimate, single-core version. My Intel
quad core is similar to the benchmarking machine, just more
MHz.  knucleotide.adb runs in ~33 sec on my machine (either
GNAT 4.3.2 or GNAT 4.3.4).  I would expect it to run a
bit above 40 sec on the benchmarking machine. On the
benchmarking machine the top entries have running times of:
  20 sec, 43 sec, 48 sec, and 55 sec.
Most entries are much slower. So knucleotide.adb is
very respectible by my estimate.

Here's how I made that speed estimate.  I took the
faster-than-light (20 second) entry and compiled it
on my quad-core:

g++ -O3 -I ../boost/boost_1_36_0 -fopenmp knucleotide.c++

It ran in 16 sec on my machine, 20 sec on the benchmarking
machine. If that ratio holds, knucleotide.adb runs in
40 sec on the benchmarking machine. (By the way, I can't
make head or tails of the source code of knucleotide.c++.
It doesn't help that I don't know c++;)
It seems to be designed to make good use of OpenMP
style multiprocessing, but resemblance to the original
benchmark is somewhat obscure.  Still I am very
impressed, and I wonder how it works so well.)

Anyone who wants to report bugs or offer improvements can
find my single-core only version (knucleotide_3.adb) at

   http://web.am.qub.ac.uk/users/j.parker/

in directory  bench_depository. Georg has given
his site in the 1st post in this thread.

Jonathan