I'm now convinced that the speed issues aren't a problem. The reason is that when we're computing an automorphism group we know that the stabilizer chain will be up to date below the current level, so we don't sift at all.
Just to make the argument convincing, I tested empty graphs (which have full symmetry group and would be most likely to show this problem if it were there):
sage: G = Graph(n)
sage: timeit('H = G.automorphism_group()')
The results, in milliseconds:
n: | 10 | 20 | 30 | 40 | 50 |
--------|-----|-----|-----|-----|-----|
BEFORE: | 148 | 313 | 480 | 645 | 809 |
AFTER: | 148 | 311 | 479 | 645 | 820 |
In other words, no change at all. For a more complicated graph of higher degree:
sage: G = graphs.HigmanSimsGraph()
sage: G.num_verts()
100
sage: G.num_edges()
1100
Before:
sage: timeit('H = G.automorphism_group()')
5 loops, best of 3: 274 ms per loop
After:
sage: timeit('H = G.automorphism_group()')
5 loops, best of 3: 267 ms per loop
So no significant changes. I'm going to ask Tom to re-review this patch, since it's been through a few changes since he gave it the thumbs up. Note that this patch applies cleanly to sage-4.7.alpha4.
