.opt files

[Ralph Becket]

The same friend who has asked me to give a presentation on why systems
people should be interested in Mercury has also thrown down the
gauntlet: the bet is that a Mercury implementation of the SPECINT
129.compress algorithm (LZW using double hashing) will not run more
than six times slower that the C implementation; the wager is for
about ten pints of beer or a couple of good nights down the pub.
A stake worth playing for.  [Just for the record, my friend would like
to lose this bet, but is highly skeptical about the efficiency of
declarative languages...]

I've had a look at the C source and the heart of the algorithm is a
fairly tightly coded pair of nested loops, the outer one calculating
the first hash and the inner one probing on the second hash.  Both are
generated by some fairly straightforward bit twiddling.  The hash
table itself is represented as a pair of 69,001 element arrays of long
int's.

Clearly Mercury's mutable array library (array.m) is what is called
for here.  Looking at array.opt (which I presume is basically for
inlining optimisations) I see that various procedures including
array__lookup/3 exist there, but not array__set/4.  While
array__lookup/3 will be much more heavily used in the Mercury
implementation of 129.compress, having array__set/4 inlined would also
be a big help.

My first question is, what crietera are used to decide which
procedures end up in the .opt file?  In the case of array__set/4, the
C code is almost identical to that of array__lookup/3.  If both were
in the .opt file, a procedure doing nothing more than array lookup's
and set's stands a good chance of having the indirections through the
array structure to get at the size and elements members moved outside
the inner loops.  Without it, I doubt that the compiler could do this
in all safety since it has no idea what array__set/4 is going to do
the the array structure.

My second question is, if the compiler could be encouraged to include
array__set/4 in the .opt file, is gcc smart enough to elide the
out-of-range tests (it can be deduced from the code, by a human at any
rate, that this error cannot occur)?

Cheers,

Ralph

-- 
Ralph Becket  |  rwab1 at cam.sri.com  |  http://www.cam.sri.com/people/becket.html