From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00, REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news3.google.com!feeder1-2.proxad.net!proxad.net!feeder2-2.proxad.net!newsfeed.arcor.de!newsspool3.arcor-online.net!news.arcor.de.POSTED!not-for-mail Date: Tue, 11 Aug 2009 01:34:05 +0200 From: Georg Bauhaus Reply-To: rm.tsoh+bauhaus@maps.futureapps.de User-Agent: Thunderbird 2.0.0.22 (Windows/20090605) MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: GNAT's stack checking in Ubuntu 9.04 (and Shootout regex-dna) References: <4a776a94$0$31878$9b4e6d93@newsspool3.arcor-online.net> <4a7f1fc5$0$31344$9b4e6d93@newsspool4.arcor-online.net> <9adb4985-582c-4cbf-906c-3afa7dcd31f6@g1g2000vbr.googlegroups.com> In-Reply-To: <9adb4985-582c-4cbf-906c-3afa7dcd31f6@g1g2000vbr.googlegroups.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Message-ID: <4a80ae6e$0$31877$9b4e6d93@newsspool3.arcor-online.net> Organization: Arcor NNTP-Posting-Date: 11 Aug 2009 01:34:06 CEST NNTP-Posting-Host: 40ba35df.newsspool3.arcor-online.net X-Trace: DXC=0fB_T0Co;MW\9P[:DUn00QMcF=Q^Z^V3X4Fo<]lROoRQ^YC2XCjHcbYbiGi;SFJC@WKQDKiQ7h 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.