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

[jonathan <johnscpg@googlemail.com>]

On Aug 22, 11:35 pm, Georg Bauhaus <rm.tsoh.plus-
bug.bauh...@maps.futureapps.de> wrote:
> jonathan wrote:
> >> 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.  [...]
> > This essentially removed all the overhead in sliding
> > array Data.
>
> With the help of generics I have been able to further
> reduce string processing load.  Instances will adapt String
> to fragments, as needed.
> The result is another 20% speed-up.  A pleasant surprise,
> and fairly easy.  This allows using simple renames for
> key data. :-)
>


The program now runs in a splendid 23 sec on my
machine. For those who have not been paying
attention, we started some time ago with a program
that ran in > 72 sec.  Its now (I should think) quite
a bit faster than all but one at the benchmarking
site.

The string renaming turned out to be such a neat
trick, I'll write it out:

  Key(1 .. Length) := Buffer(I .. I + Length - 1);

(in its various forms) was replaced by

  Key : String renames Buffer(I .. I + Length - 1);

This combined with the smaller strings did the
trick.  On my machine execution fell from ~32 sec to
~23 sec from these 2 steps alone.

One useful feature of the new design is we can
explicitly "grow the hash table" as the rules
seem to specify, (although they accepted the static
sized table last time).  We now have the option
of changing Table_Size with each instantiation:

--Table_Size : constant Integer := 2 ** 17;
  Table_Size : constant Integer
           := 2 ** Integer'Min (Fragment'Last*4, 17);

  subtype Hash_Type is Integer range 0 .. Table_Size-1;

This is the form used by many other entries.  The new
table size does not change the speed in the slightest.
I prefer the static  2 ** 17 myself.


> I'd like to further merge the programs, following the
> comments so far.  In particular, there doesn't seem to be
> a real loss when using tasks on a single core machine,
> IIUC.  I'll try to confirm this some more.
> We could then submit just one program, if you agree.
>

To fuse single-core and multitasking version I tried
the following:

if Multitasking_Desired then
   Work_On_2.Writer.Set (Nucleotide_Length => 2);
   Work_On_18.Writer.Set (Fragment_18'Length, Fragment_18);
   Work_On_1.Writer.Set (Nucleotide_Length => 1);
   Work_On_12.Writer.Set (Fragment_12'Length, Fragment_12);
   Work_On_6.Writer.Set (Fragment_6'Length, Fragment_6);
   Work_On_4.Writer.Set (Fragment_4'Length, Fragment_4);
   Work_On_3.Writer.Set (Fragment_3'Length, Fragment_3);
else
   Work_On_1.Write (Nucleotide_Length => 1);
   Work_On_2.Write (Nucleotide_Length => 2);
   Work_On_3.Write (Fragment_3'Length, Fragment_3);
   Work_On_4.Write (Fragment_4'Length, Fragment_4);
   Work_On_6.Write (Fragment_6'Length, Fragment_6);
   Work_On_12.Write (Fragment_12'Length, Fragment_12);
   Work_On_18.Write (Fragment_18'Length, Fragment_18);
end if;

With Multitasking_Desired set to False, a typical
(good) timing might look like:

real    0m23.552s
user    0m23.141s
sys     0m0.404s

With Multitasking_Desired set to True, a typical
(good) timing might look like:

real    0m10.373s
user    0m23.625s
sys     0m0.432s

Fluctuations are not tiny; maybe .7 sec.
And remember, Linux in probably putting the 7 Work
tasks on 7 cores of the 8 available on my machine.

And there's a problem I can't solve.  One out of 5 to
20 runs gives this result:

real    0m15.691s
user    0m34.150s
sys     0m0.396s

Always the same ~16 seconds.
I can't tell if its a Linux hiccup, the phase of the
moon, or what, but I can't get rid of it.

That's one reason I am not sure it is a good idea
just yet to fuse the single-core version and the
tasking version. I'ld rather see the cleaner
single-core version polished up and submitted quick.

To make a task-free version I just directly
removed all the tasking from your latest. Works
well .. my versions are obsolete .. just an
option to consider.

Jonathan