Non-readonly types in HPCGAP causing slowdowns about gap HOT 9 CLOSED

Results as of today (with #1326 merged in May) for GAP (started with -A):

gap> stat:=function() return [NEW_TYPE_CACHE_HIT,NEW_TYPE_CACHE_MISS,NEW_TYPE_NEXT_ID]; end;;
gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
3326
[ 221451, 1826, 3392 ]
gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
3219
[ 220754, 1045, 1100 ]
gap> 3392+1100;
4492

For HPC-GAP:

gap> stat:=function() return [NEW_TYPE_CACHE_HIT,NEW_TYPE_CACHE_MISS,NEW_TYPE_NEXT_ID]; end;;
gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
5061
[ 220797, 2484, 4042 ]
gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
5098
[ 221096, 718, 778 ]
gap> 4042+778;
4820

So the example is still considerably slower in HPC-GAP than in GAP, but it clearly is not due to type cache misses -- indeed, the numbers are slightly better in HPC-GAP than they are in GAP.

So while we still have a performance issue, I am pretty sure it's not due to non-readonly types anymore. Closing.

from gap.

I’m working on this. I think it can be fixed by a little code reorganisation

Specifically adding an argument to NEW_TYPE which allows the post-processing done in Subtype* to be done inside NEW_TYPE before the type is made readonly.

from gap.

Good find, Chris!

For reference (and to link this issue with the relevant PR), it seems Steve's PR #129 is meant to address this.

from gap.

Actually, I cannot reproduce Chris' findings at all?! With master, I get this:

gap> NEW_TYPE_CACHE_HIT; NEW_TYPE_CACHE_MISS;
242
40
gap> g:=WreathProduct(MathieuGroup(9),Group((1,2)));; time;
7
gap> NEW_TYPE_CACHE_HIT; NEW_TYPE_CACHE_MISS;
243
51
gap> ConjugacyClassesSubgroups(g);; time;
3186
gap> NEW_TYPE_CACHE_HIT; NEW_TYPE_CACHE_MISS;
214162
2386

But with hpcgap-default rev 9ec2afe (so without Steve's PR), I get this:

gap> NEW_TYPE_CACHE_HIT; NEW_TYPE_CACHE_MISS;
71
13
gap> g:=WreathProduct(MathieuGroup(9),Group((1,2)));; time;
9
gap> NEW_TYPE_CACHE_HIT; NEW_TYPE_CACHE_MISS;
71
14
gap> ConjugacyClassesSubgroups(g);; time;
7537
gap> NEW_TYPE_CACHE_HIT; NEW_TYPE_CACHE_MISS;
52378
96

So there are overall a lot fewer NEW_TYPE calls to start with, and also considerably fewer cache misses. Considering that Subtype is so exotic, and certainly not used when computing in permutation groups, that's perhaps not very surprising... ?!

from gap.

The problem is that in the troublesome case (_NEW_TYPE_READONLY is false), neither of those variables is incremented. Look at how NEW_TYPE_NEXT_ID changes to see how many new types are actually being created.

from gap.

Subtype is not exotic. It is used whenever an object discovers that it has a new filter -- so whenever an attribute is computed.

from gap.

Note that PR #326 (and also #142, #291, #295) attempt to deal with this issue.

from gap.

We merged #326 some time ago. I now get these numbers (on the same laptop as with the previous ones, but with a new OS version, and of course the most recent GAP / HPC-GAP versions). I executed

gap> ConjugacyClassesSubgroups(WreathProduct(MathieuGroup(9),Group((1,2))));; time;

several tiems in each. In GAP, the time fluctuated around 3.4 seconds (so a bit slower than what I reported above), while in HPC-GAP, it varied around 5.25 seconds. While that is still quite a bit slower, it certainly is a noticable improvement compared to what I got earlier.

To get a somewhat more accurate idea of the impacte of #326, I also measured this in the merge commit 6576369, and the commit 539383e right before the merge. Before the merge, I get times around 6.4 seconds, right after the merge it's about 5.3 seconds.

Nice! But still some work left to be done.

from gap.

To update this, I now get these results, using this helper function recording the number of type cache hits/misses and types created:

stat:=function() return [NEW_TYPE_CACHE_HIT,NEW_TYPE_CACHE_MISS,NEW_TYPE_NEXT_ID]; end;;

Results for GAP:

gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
3218
[ 218079, 997, 2532 ]
gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
3151
[ 216761, 812, 864 ]

Results for HPC-GAP:

gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
6579
[ 182171, 36834, 38436 ]
gap> old:=stat();; g:=WreathProduct(MathieuGroup(9),Group((1,2)));; ConjugacyClassesSubgroups(g);; time; stat() - old;
6412
[ 181780, 35794, 35870 ]

As you can see, runtime in HPC-GAP regressed a bit again (and it takes 2x as long as GAP). The number of new types being generated is lower for both GAP and HPC-GAP, but it still is MUCH higher for HPC-GAP. So there is still room for improvement.

from gap.