Some time ago we noticed that the function Orbit(G,S,OnSets) can be
hopelessly slow when |S| and in particular the length of the resulting orbit
are big enough.
We tested Orbit() using Profile,
we found that the largest amount of CPU time is consumed by AddSet.
One may see looking at the appropriate C code that the time taken by AddSet
to add a new element to the set of length N is proportional to N.
It is not quite clear why faster ways to handle sets, such that the addition
of a new element takes only O(log(N)) operations, are not used in the GAP
implementation. For instance, a
program using one such way finds the orbit on sets more
than 100 times faster the GAP function.
I'm sure that there are other functions whose performance can be greatly
improved by handling sets properly.
Dept. of Mathematics,
Univ. of Western Australia, Nedlands WA 6009, Australia