In a letter of April 19 to the GAP-forum Frank Leonard wrote

"I have been attempting some constructions of finite groups in GAP as
defined by a presentation in abstract generators/relators. The
problem consists of applying a certain algorithm to construct a group
which I then attempt to identify. I also have access to the C.A.
package CAYLEY and have re-written the algorithm for CAYLEY. I have
found CAYLEY vastly superior (time wise) to GAP for this problem. I
assume that the fact that GAP programs/functions are interpreted would
be significant in explaining the discrepancies but I am curious if
there are any other factors which might be significant. Can you tell
me if there are any plans at present to write a compiler for GAP?"

In my reply I have made no attempt to hide my disappointment about
such unspecified but nevertheless very critical comment. On this I
have obtained a letter from Mr. Leonard which starts:

"The following is a personal message and is not intended for
submission to the GAP-forum."

I have to respect this. However I do not think that I break this
confidentiality if I report that after saying later on in his letter:
>"I have been deliberately vague about the details of my constructions
>in my submission as the material on which I have based my GAP program
>forms the basis of a paper..."
Mr. Leonard reports that he has used the GAP-function Size(g) on a
two-generator, two-relator presentation of the trivial group which he
then gives, thus allowing us to analyze the case. He states that it
took him approximately 20 sec using the GAP-command Size(g) and less
than a second in Cayley to find that the presentation does in fact
describe the trivial group.

We have repeated the calculations and found the statement correct, on
a DECstation Size(g) took 15 sec, Cayley took 0.5 sec. I only wished,
Mr. Leonhard had made this explicit statement in his first letter,
because this gives me a chance to explain the reasons and talk about
consequences of the observation.

Both programs use Todd-Coxeter coset enumeration methods. The one in
Cayley is implemented by George Havas in C, the one in GAP is written
by Martin Schoenert in the GAP-language with some time-critical parts
in C in the GAP kernel. There is a standalone version of Martin
Schoenert's program written by him totally in C and so the first step
is a comparison of this and the GAP function.

The respective time for Martin Schoenert's C program is 4.7 sec, as
stated above the time for the GAP function 15 sec. This factor is
rather typical, factors of 3 - 4 have also been observed with other
presentations. This factor is due to two reasons, the fact that GAP
is interpreted but also to the overhead time needed for the dynamic
storage allocation using indirections. We do not know exactly which
proportion of the factor is due to which of the reasons but it is
clear that even compilation would not remove the second reason. It is
also clear that both reasons hit in particular with programs in which
rather small data has to be accessed many times and Todd-Coxeter
methods are one of the worst cases for this phenomenon.

There remains quite a substantial factor to be explained. The first to
note is that there are several "strategies" for the Todd-Coxeter
method, which can have an enormous, unfortunately not completely a
priori predictable influence on the efficiency. There are some papers
investigating experimentally these various strategies, in particular

J.J. Cannon, L.A. Dimino, G. Havas, J.M. Watson : Implementation and
Analysis of the Todd-Coxeter Algorithm. Math. of Computation, 27,
(1973), 463 - 490.

G. Havas : Coset Enumeration Strategies. Proc. ISSAC 91.

and George Havas is carrying out further investigations.

Without going into details: There are two 'old' strategies, the
so-called Felsch strategy and the so-called HLT strategy (after
Haselgrove, Leech, and Trotter), of which 'in general' (such
statements always have exceptions, and Mr. Leonard's example is one)
the Felsch method tends to define fewer redundant coset numbers and
hence to need less space while the HLT method tends to be faster.
(Both have been improved by modifications, but this does not matter
too much here.) Now the times observed by Mr. Leonard are for the
default strategies in GAP and Cayley.

The very short time in Cayley is obtained by a HLT strategy, but as
George Havas, whom I want to thank for his help in investigating the
case, has pointed out, also with a bit of luck: If he just cyclically
permutes the relators, his program in CAYLEY takes 3 times longer
because it defines 3 times more coset numbers before collapsing the
coset table!! (maximal table size 69909 instead of 21860, 1.570 sec
instead of 0.530sec, times on his machine which I believe is a SUN)

The method used in GAP is basically a Felsch method, there is no GAP
implementatiom of a HLT based method yet. Modifications of the method
cause rather drastic changes in efficiency of a Felsch method, too, as
in particular George Havas has investigated. E.g. using the relators
also as subgroup generators in a Felsch strategy mode of George Havas'
program reduces the maximal table size from 27532 (which is the same
as in the GAP program) to 17012 and computing times from 2.29 sec to
1.40 sec. This is because in George's program subgroup generators are
scanned a la HLT. Using in addition a 'Preferred Definition List', a
strategy developped by George Havas, reduces the maximal table size
further to 9542 and the computing time 0.84 sec.

These figures make clear that the choice of the strategy is a delicate
matter and that the comparison made originally used defaults that were
particularly unlucky for the performance of GAP.

What are the consequences for us? For very large enumerations the
factor of 3 or 4 caused by indirection and interpretation is annoying.
We will therefore gratefully accept the offer of George Havas to
append his C-program, which at present probably represents the
greatest experience with the above mentioned delicate decisions, as a
share library to GAP. George will eventually provide us with the C
source code for the purpose, but he wants to polish the code first, so
we may first try to provide executables of his program for a few
computers. Using such a share library of course has the drawback
(which is the payment for some of its speed) that it is running on its
own piece of storage that is not administered by the GAP storage
management. Therefore we also intend to learn more from George's
experience and also try to improve the TC written in the GAP-language,
even if more or less intrinsicly we will loose that factor of 3 or 4
against a standalone C-program.

This has become a long letter, allow me nevertheless to mention
another case of an efficiency comparison. Both GAP 3.2 and CAYLEY have
programs for the computatipon of the subgroup lattice, which we are
allowed to compare even more since they have both been written in
Aachen. The CAYLEY program was written by Volkmar Felsch, originally
still in Fortran, then semiautomatically translated into C by John
Cannon. Volkmar Felsch is still helping to maintain this program, the
last such help was given only this Spring. The GAP program was
written by Juergen Mnich. Of course, when he had written it, we made
comparisons and were rather content with the results: For small groups
the two performed roughly equal while for big permutation groups (big
for this kind of program) such as the symmetric group S8 or the
Mathieu group M12 the new program was faster by a factor over 10,
which matters for these cases since absolute computing time is over
one hour for the new program for these cases. This was at least
partially due to the use of new functions for permutation groups. We
were rather surprised to learn from Ralf Dentzer that the performance
of the new program was not so satisfactory for medium size soluble
groups with thousands of classes of conjugate subgroups e.g. certain
groups of order 256 from Eamonn O'Brien's list for which the new
program performed by about the same factor of 10 *slower* than the old
one. Martin Schoenert has very briefly mentioned this fact in a reply
to a question in the GAP-forum recently and also mentioned that he has
written a still newer progam in GAP which seems to avoid these
deficiencies for medium size soluble groups while keeping the good
performance for the 'big' groups. This program will be put into GAP in
the not too far future.

I mention the second case after my report about the first in order to
make the point that in cases such as the computation of the subgroup
lattice of a 'big' permutation group the fact that GAP is interpreted
and the storage management uses indirections does not play such an
important role for the efficiency while on the other hand the
simplicity of programming in GAP makes it much more feasable to try a
mathematical variant of a method that can improve the efficiency.

Last not least however I want to emphazise that we do appreciate clear
and specific reports, such as given to us by Ralf Dentzer, about
deficiencies in GAP, deficiencies which we shall then try to remove as
much and as soon as our restricted manpower allows, and that the last
thing we want to do is to sweep such problems under the carpet.

Joachim Neubueser