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

[jonathan <johnscpg@googlemail.com>]

On Aug 1, 1:21 pm, Georg Bauhaus <rm.tsoh.plus-
bug.bauh...@maps.futureapps.de> wrote:
> This is about the K-Nucleotide program at the
> Computer Language Benchmark Game,http://shootout.alioth.debian.org/u32/benchmark.php?test=knucleotide&...
> where some Ada programs have started to fail.

I took a 2nd look at your single core knucleotide.adb.

http://home.arcor.de/bauhaus/Ada/knucleotide.gnat

I was able to speed it up by 40% to 50% with one
change: I inlined the hashing function by hand.
Its not the prettiest code, but this is after
all an optimization exercise.

Running time under GNAT 4.3.2 went from 79 sec to
to 53 sec. Running time under GNAT 4.3.4 went from
70 sec to 50 sec. On both  GNAT 4.3.2, and
GNAT 4.3.4 (GPL 2009) the best compiler switches
I could find were:

   gnatmake -O3 -gnatp -march=native

Here is the original Hash function:

-- function Hash (Key : Fragment) return Hash_Type is
-- begin
--    return Hash_Function (Fragments_1.To_String (Key));
-- end Hash;

and here is the replacement:

 function Hash (Key : Fragment) return Hash_Type is
    type Uns_32 is mod 2**32;
    H : Uns_32 := 0;
    pragma Assert (Hash_Type'First = 0);
 begin
    for J in 1 .. Key.Last loop
      H := Character'Pos(Key.Data(J)) + H * 2**6 + H * 2**16 - H;
    end loop;
    return Hash_Type'Base (H mod Uns_32 (Hash_Type'Last + 1));
 end Hash;

A few more changes:

1. REMOVE:  pragma Restrictions (No_Finalization);
   Won't compile under GNAT 4.3.4, with mysterious
   error message. Could this be a problem on GNAT 4.3.3
   used at the shootout site? In any case, -gnatu
   says we're linking to storage pool routines, so
   this is probably an error.

2. I replaced:  type Hash_Type is range 0 .. 2**16;  with

      type Hash_Type is range 0 .. 2**17 - 1;

   Both work, but latter is a few % faster.

3. I moved  type Bounded_String  out of the private part
   and made it public so that function Hash could see it.
   (Just for convenience.)

      type Bounded_String is record
         Data : String(Frequencies);
         Last : Natural;
      end record;

4. The knucleotide.adb version that uses Ada.Containers is
   3 times slower than this new one, and seems to fail
   on the 250 Meg fasta text file used in the benchmark.

Final comment:

According to the shootout site, they're using
GNAT 4.3.3.  I wonder if this is the source of our
misery.  I can get GNAT 4.3.2 and  GNAT 4.3.4 (GPL)
the work very nicely on all machines I have access to.
The best optimation switches are often very different
on these 2 compilers, so I have no idea what GNAT 4.3.3
likes.

Jonathan