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

[jonathan <johnscpg@googlemail.com>]

On Aug 20, 12:50 am, Georg Bauhaus <rm.tsoh.plus-
bug.bauh...@maps.futureapps.de> wrote:

> Since a fixed buffer size makes the program
> fail when inputs grow, I think the temporary Unbounded_String
> is reasonable.
>
> There are only a few calls to Unbounded.* anyway.
> Get_Line seems to be the dominating subprogram here.


I agree. These timings mean that overhead from unbounded
strings is insignificant.

Unfortunately I got my timings a bit wrong.  Fortunately the
conclusion remains the same.  (I redid everything
carefully.)  IO is consistently ~11% running time on
my machine, so no great source of inefficiency.

I also measured the benefit of the 64 Megabyte buffer
more carefully:

      procedure Read_Section is
         ...
         Local_Buffer : String_Access;
      begin
         Local_Buffer := new String (1 .. 1024 * 1024 * 64);

I would now recommend

         Local_Buffer := new String (1 .. 1024 * 1024 * 16);

Its only .25 sec slower.

Finally, I found one last useful optimization, which
consistently shaves 6% off the running time on my machine.
(I was unpleasantly surprised that it wasn't better.)

The 125 Meg array (Buffer) is read through from beginning
to end numerous times and and each time about 125 million
substrings are written to string Key.Data:

  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:

 Key.Last            := Length;
 Key.Data(2..Length) := Buffer (1..Length-1);--new essential init.

 for I in Length .. Buffer'Last loop

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

    -- New. Use loop not sliding, (and -funroll-all-loops):
    for j in 1 .. Length-1 loop
       Key.Data(j) := Key.Data(j+1);
    end loop;
    Key.Data(Length) := Buffer (I);

    declare
       Element : constant Element_Access := Table.Get (Key);
    ...



Jonathan