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=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,ccd04b355056eb04
X-Google-Attributes: gid103376,public
From: geert@fozzie.sun3.iaf.nl (Geert Bosch)
Subject: Re: performance tuning with gnat
Date: 1996/05/14
Message-ID: <4na3ii$1oo@fozzie.sun3.iaf.nl>#1/1
X-Deja-AN: 154824872
distribution: world
references: <4mvkq1$nr4@cville-srv.wam.umd.edu> <4n069g$rrf@eri1.erinet.com>
organization: La Calandre Infortunee
newsgroups: comp.lang.ada
Date: 1996-05-14T00:00:00+00:00
List-Id: <comp.lang.ada>


James E. Hopper (jhopper@erinet.com) wrote:
   [About what causes most slowdown]
`` 2.  Unconstrained Arrays are REAL slow [...] ''

I've found this too, but for most places where this mattered it's
possible to gain a large speed-up by tuning a small piece of code using
pointer operations.  While rewriting a regular expression matching
library for Ada I found that at first the performance was really bad
(2-3 times as slow as the original C version), but after changing a few
lines the speed came close (20% slower) to that of the C-version..

Since most time was spend in a simple routine that searches the first
occurrence of a character in a string, I've rewritten that routine
using a character pointer, which is incremented after each comparison.
The function still works on arguments of the standard type String, but
is several times faster. 

Hopefully GNAT will be able to make this conversion itself in a future
version, as it's possible to calculate the bounds only once before
entering the loop. BTW: is there some program that makes it possible
to have a readable assembly output where addresses are symbolic and
assembly lines are mixed with Ada source lines. (Like those Turbo
Pascal days.) It would make debugging GNAT code generation problems
(both performance and correctness) much easier.

Of course these 12 lines are "ugly" and need unchecked conversion
and/or Address_To_Access_Conversions, but the original "clean" Ada
version is left in the code as an alternative for programs where safety
is more important than speed.

The main point in writing an Ada version of the regexp library was to
see what the performance difference would be when going from an
implementation using dynamically allocated memory (at least for the
regexp finite state machine), only uncheckable pointer operations and
"printf" on detecting errors to an implementation requiring no dynamic
memory allocation (the FSM is an unconstrained type), just one place
with pointer operations and raising exceptions on (expression) errors.

The results really surprised me. The "literally converted" regexp
library generated code that was nearly exactly the same speed (as
expected), and the code without any unchecked conversions or pointer
operations was only 2-3 times as slow. The compromise that I prefer has
just 1% "ugly" code and performs just slightly slower thant the C
version on my test cases.  (The differences will be bigger when the FSM
will make many transitions without doing much more character matches
and some other uncommon cases.)

It's worth noting that declaring new types and packages, instantiating
and using Unchecked_Conversions are all essentially free in terms of
execution speed.  So, it often pays off to declare new types and do
unchecked conversions to/from them when those types are more efficient
in some function and speed is really critical.

Especially when it's possible to convert loops that process small (8-
or 16-bit) data values to loops that process 32-64 bit data values
(depending on the architecture) at once can make large speedups
possible, since each loop iteration 2 - 8 data items can be processed
instead of 1 and on some RISC machines processing 32- or 64-bit data is
faster than processing 8-bit data.

Regards,
   Geert
-- 
E-Mail: geert@sun3.iaf.nl     *** The moon may be smaller than ***
 Phone: +31-53-4303054        ** Earth,  but it's further away. **