🚀 go-pugleaf

(Dan Bernstein) writes:
>(Nick Rothwell) writes:
>> (Dan Bernstein) writes:
>> >Piercarlo is entirely correct. If you care about ``information hiding''
>> >and the ``purity'' of your code more than efficiency, you can't expect
>> >fast code. If you can't bear to put your original code in comments and
>> >write an efficient version with temporary variables, you don't deserve
>> >fast code.
>> 
>> This is rubbish, check out the performance of New Jersey ML
>> (high-level functional language, efficient optimised native code
>> generation).
>
>Are you saying that your compiler is smarter than you are or just that
>it's not as lazy?
>
>Can it figure out, say, Knuth's algorithm for computing the delta2 table
>in Boyer-Moore string searching, starting from a dumb algorithm for the
>same job?
>
After some discussion with my colleague Norbert V\"olker (who doesn't
read news), I can come up with the following reply:

- first, Knuth's algorithm as published in [1] is *WRONG*. This already
shows that not even DEK, who is an *extremely* competent programmer, to my
knowledge, was able to come up with the algorithm. See [2] for the
improved algorithm.

- second, N. V\"olker is currently working on a (transformational) derivation
of the delta-algorithm for BM pattern matching (with H. Partsch). Their
version of the algorithm is going to be different from the delta2
algorithm in [2], it uses more space and less time.
It is Norbert's feeling, however, that in the future compilers will be
able to come up with the delta2 algorithm, since all that is involved in
a derivation by hand is finite differencing (aka strength reduction).
The reason that current compilers are not able to do this is that they
do not ``know'' what lists (strings, sequences, or whatever) *are*. Cf.
[3] for the basic laws about strings.

My view of this whole issue is the following:
- there are two kinds of optimisations:
  routine ones and smart ones.
  Routine optimisations are:
  strength reduction, code motion, loop merging, (`bout everything you
  heard about in your course on Optimizing Compilers)
  Smart optimisations are inventions of new algorithms, like the BM
  pattern matching algorithm *itself*, the non-trivial sorting
  algorithms (cf. Darlington's paper `A Synthesis of Several Sorting
  Algorithms')
  The only problem I don't know for sure how to place is register
  allocation.
- the routine optimisations can be done (eventually) by a compiler; all
the examples of things that `you'd better do yourself because your
compiler is too stupid' mentioned so far fall in this class.
- the smart optimisations can only be done by humans because they
involve ``eureka's'' and design decisions; it is, however, possible
to limit the number of eureka's by inventing strategies (cf. some work
by D.R.Smith and A.Pettorossi) and by gaining knowledge about your
problem domain first (e.g. lists, cf. [3]).

References:
[1] Knuth, Morris, Pratt: Fast Pattern Matching in Strings, Siam J.
Comput. 6, 1977.
[2] Rytter: A correct preprocessing algorithm for Boyer-Moore
string-searching, Siam J. Comput. 9, 1980.
[3] R.S. Bird: An introduction to the theory of lists, in: M.Broy (ed.):
Logic of Programming and Calculi of Discrete Design, ASI Series Vol.
F36, Berlin:Springer 1987.

I'm very sorry for you, mr. Bernstein, that you chose an example that
proves my (and Nick Rothwell's) point.


Eerke Boiten, Department of Informatics, K.U.Nijmegen
Toernooiveld, 6525 AD Nijmegen, The Netherlands.
Tel. +31-80-612236.     eerke@cs.kun.nl