Re: GNAT's stack checking in Ubuntu 9.04 (and Shootout regex-dna)

[Georg Bauhaus <rm.tsoh.plus-bug.bauhaus@maps.futureapps.de>]

jonathan wrote:

> I was going to give up on regexdna.adb, but I had to
> try one last thing. [...]
>    Stack_Size : constant Positive := 2000;
> 
> with
> 
>    Stack_Size : constant Positive := 129;
> 
> in GNAT_spitbol.patterns.

> The program running time (single-core) dropped [...]

Interesting.

Does regexdna-multi.ada work on your system?

On a dual core system it seems to be shortening
the running time by almost a third.

(The slowdown in general is in the match-replace part;
the (first) matching part seems to be performing well.)

> Last remark: someone with experience using the
> spitbol routines might be able to optimize
> further.  There are tricks using "anchors"
> mentioned in spec of GNAT.spitbol.patterns.

Yes, I went up and down all kinds of anchoring and
saving cursor positions and using a function pointer
whose function would replace behind the scene and then
return False (like in the Match case) thus advancing
without requiring the loop in the match-replace part
(relying on the backtracking mechanism which would not
trigger backtracking, since the function returned False).
I also tried a Match and Replace pair.
But the results always seemed to indicate this
issue with VString and replacements:

(1) the match-replace is dominated by VString
which is Unbounded_String which is slow replacing
string slices no matter how the replacement is done.
(See also Bob Duff's remarks on Unbounded_String
in this thread.)
Constructing a new VString, for example, using Append
did not help (I was hoping that no shifting of characters
would be necessary).

(2) the lines in the match-replace section are reasonably
short,  Any("A") is a correspondingly short linear search.
The captured match is exactly the one character that
is replaced.
While the search is restarted from the string's
beginning in every loop, anchoring didn't seem to
make things faster.  For example,
 Pos(Saved_Cursor)  -- saved after last match
  & Break("A")
  & Len(1)
  & Setcur(Saved_Cursor'Access)
will in general capture a span of characters not
to be replaced.  This then requires either copying
the saved parts or saving the cursor position and
calling the Replace procedure with a Match object.
Works, but has been invariably slower in both cases.

But there is no end to ideas using SPITBOL patterns,
so yes, maybe someone has another idea? :-)

SNOBOL-4:

There is a great implementation of SPITBOL by
Phil Budne at http://www.snobol4.org/

I learned about SNOBOL-4 some years ago through
the GNAT packages, and immediately wanted to learn it,
which I did.  A pleasant experience---if you can avoid
debugging patterns :-)  Tables, Lists, user defined
types, type conversions, CODE, computed goto,
multiple function entry points,  and all this accessible
everywhere including in patterns! :)
I liked the SNOBOL-4 introduction by Susan Hockey,
Gimpel's book is a SNOBOL-4 treasure trove.