Ada Shootout program for K-Nucleotide (patches)
in [ADA]
|
From: Georg Bauhaus on 4 Sep 2009 12:22 Ludovic Brenta schrieb: > 262,499,981 procedure Write > 8,251,549,172 => ???:system__secondary_stack__ss_mark (7x) > . (Nucleotide_Length : in Frequencies; > . Nucleotide_Fragment : in Fragment := > Fragments.Null_Bounded_String) > . is > > Apparently, passing unconstrained strings to procedure Write involves > allocations on the secondary stack which account for 20% of the entire > execution time. That's hot spot #1. Indeed, and this particular hot spot had been cooled down twice: Step 1 - we replaced Bounded_String with our own Bounded_String Step 2 - we replaced this new Bounded_String with plain constrained strings of suitable fixed length (using generics)
From: Georg Bauhaus on 4 Sep 2009 12:29 Georg Bauhaus schrieb: > Ludovic Brenta schrieb: >> Apparently, passing unconstrained strings to procedure Write involves >> allocations on the secondary stack which account for 20% of the entire >> execution time. That's hot spot #1. > > Indeed, and this particular hot spot had been cooled down twice: > > Step 1 - we replaced Bounded_String with our own Bounded_String > > Step 2 - we replaced this new Bounded_String with plain > constrained strings of suitable fixed length (using generics) I should add that the current program spends much of its time in equality comparison of fragment strings, and then some in the hash function. So not only are the bounded_strings gone; Jonathan has also contributed a highly efficient hashing function and a cute string equality function. (As mentioned, to actually see the effects (of the current program), String_Fragments."=" should be a renaming of Equals. Operator subprograms seem to confuse the profiling programs, or am I missing some setting?)
From: Ludovic Brenta on 4 Sep 2009 12:38 Georg Bauhaus wrote on comp.lang.ada: > Georg Bauhaus schrieb: > > > Ludovic Brenta schrieb: > >> Apparently, passing unconstrained strings to procedure Write involves > >> allocations on the secondary stack which account for 20% of the entire > >> execution time. That's hot spot #1. > > > Indeed, and this particular hot spot had been cooled down twice: > > > Step 1 - we replaced Bounded_String with our own Bounded_String > > > Step 2 - we replaced this new Bounded_String with plain > > constrained strings of suitable fixed length (using generics) > > I should add that the current program spends much of its time > in equality comparison of fragment strings, > and then some in the hash function. > So not only are the bounded_strings gone; > Jonathan has also contributed a highly efficient hashing > function and a cute string equality function. > > (As mentioned, to actually see the effects (of the current > program), String_Fragments."=" should be a renaming of Equals. > Operator subprograms seem to confuse the profiling programs, > or am I missing some setting?) So I gather that Olivier was profiling an old version of the program. Correct? -- Ludovic Brenta.
From: Martin on 4 Sep 2009 13:56 On Sep 4, 1:50 pm, Ludovic Brenta <ludo...(a)ludovic-brenta.org> wrote: > Olivier Scalbert wrote on comp.lang.ada: > > >http://scalbert.dyndns.org/ada/knucleotide/callgrind_out_14048.txt > > Let's see: > > 43,644,857,598 PROGRAM TOTALS > [...] > > . > ---------------------------------------------------------------------------- > . -- > . -- Calculate and write data - either a percentage > for all fragments found or - when > . -- Nucleotide_Fragment is given - the count for > that fragment. > . -- > 262,499,981 procedure Write > 8,251,549,172 => ???:system__secondary_stack__ss_mark (7x) > . (Nucleotide_Length : in Frequencies; > . Nucleotide_Fragment : in Fragment := > Fragments.Null_Bounded_String) > . is > > Apparently, passing unconstrained strings to procedure Write involves > allocations on the secondary stack which account for 20% of the entire > execution time. That's hot spot #1. I wonder whether it is feasible to > pass access values to the strings. > > -- > Ludovic Brenta. I'm not familiar with this tool but if 'big numbers' for innocuous looking code is to be checked then what about: . function Get_Key (E : Element_Access) return Fragment is . begin 1,395,255,084 return E.all.Key; Is there some accessibility check going on in this? Could a 'pragma Assert (E.all /= null);' help? Cheers -- Martin
From: Georg Bauhaus on 4 Sep 2009 13:58
Ludovic Brenta schrieb: > So I gather that Olivier was profiling an old version of the program. > Correct? Yes. It likely is the one that has the home made Bounded_String. But this one does not have the plain String generic yet. (And a few other improvements.) I haven't finished merging the new multitasking edition and all of the new patches yet. A final draft should be ready this evening. (Just drop the file name from the link then to see a scratch paper style "manifest" if you like.) Another possible improvement (maybe for regexdna, too) that I have been thinking about is this: Currently, the working tasks will themselves print their results, after having finished all their work. They do so in the required order with the help of a protected Printer. The printer features an entry family (effectively one member per task). Guarding is such that tasks can print only one after the other, in the required order. (Printing is the last small thing that the tasks perform before they can be terminated.) The option I have been thinking of is, in the regexdna case in particular, to allow some "future" work to be done while the shared variable is collecting results: There might be free CPU capacity because, say on a 4-core, one task hasn't finished, leaving two out of four cores idling until the next rush of tasks starts working on the second part of the program, e.g.. Miscellanea: Does the size of the entry family (18, some not used) matter much? (Most of the work is done by the tasks undisturbed.) Should we requeue instead? For K-Nucleotide all this didn't seem to matter much, at least on the machines to which we have access: Dropping the requirement of orderly printing is not a big win. But who knows. |