Regression in ConstructAllGroups(2916) between stable-4.8 and master

[markuspf]

Observed behaviour

gap> ConstructAllGroups(2916);

Did not return a result in 3 days on master, finishes in about 4000 seconds on stable-4.8 on the same hardware.

Expected behaviour

Slightly more similar runtimes.

Copy and paste GAP banner (to tell us about your setup)

 ┌───────┐   GAP v4.8.1-60-g7fb6cc3 of 2016-01-15 11:05:44 (UTC)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
 Packages:   AClib 1.2, Alnuth 3.0.0, AtlasRep 1.5.0, AutPGrp 1.6, CRISP 1.4.3, 
             Cryst 4.1.12, CrystCat 1.1.6, CTblLib 1.2.2, FactInt 1.5.3, 
             FGA 1.3.1, GAPDoc 1.5.1, IRREDSOL 1.2.4, LAGUNA 3.7.0, Polenta 1.3.6, 
             Polycyclic 2.11, RadiRoot 2.7, ResClasses 4.4.2, Sophus 1.23, 
             SpinSym 1.5, TomLib 1.2.5, Utils 0.39

Is this maybe to do with the changes to group homomorphisms?

[markuspf]

I observe the same problem with ConstructAllGroups(9720), one commonality between the two is a "high" power of 3 in the prime factorisation (3^5 and 3^6 respectively).

[hulpke]

No, I think the homomorphisms seem to be harmless here. I suspect it has something to do with recent changes to lists, though I cannot point my finger on the place.

The calculation hangs in a normalizer calculation for a subgroup of order 2 whjich is specially treated by using an element centralizer.

A binary search through the master branch (it would be helpful if someone could check this in case I misused git) finds that commit

633aa9a [633aa9a]
Parents: 42f85eb, 1caf57c
Author: Markus Pfeiffer markus.pfeiffer@morphism.de
Date: May 10, 2016 at 7:45:50 AM MDT

Merge branch 'stable-4.8'

is still OK, but the subsequent commit

6c9b41d [6c9b41d]
Parents: 633aa9a, 6473f24
Author: Markus Pfeiffer markuspf@users.noreply.github.com
Date: May 10, 2016 at 7:49:01 AM MDT

Merge pull request #781 from frankluebeck/fl_fix_random_list

Several fixes for Random on long lists in 64-bit GAP

triggers the problem. To observe, apply the following patch to stbcbckt.gi:

2665c2665,2668
<     return RepOpElmTuplesPermGroup( false, G, E, E, L, L );
--    
> Print("NormalizerOrder2\n");
>     G:=RepOpElmTuplesPermGroup( false, G, E, E, L, L );
> Print("NormalizerOrder2Out\n");
>     return G;

If a line
NormalizerOrder2
is followed by a long wait, the error is is there.

[markuspf]

Thanks for the assessment, I will have a closer look at what's happening there. Cheers,

[hulpke]

Some further analysis of the change. If I revert the changes in random.gi in chunks
@@ -190,7 +198,7 @@
and
@@ -215,8 +223,9 @@
(i.e. the last two) of the patch (and keep the kernel function) the problem vanishes.

[markuspf]

For some reason the first method selection in the following takes a really long time:

gap> l := List([1..2^28 + 1], i -> i+1);;
gap> ApplicableMethod(Random, [GlobalMersenneTwister, l]);
function( rs, list ) ... end
gap> time;
2796

Trying to compute the type of the list by any chance? Digging further...

[frankluebeck]

On Tue, May 24, 2016 at 03:11:35PM -0700, Alexander Hulpke wrote:

Some further analysis of the change. If I revert the changes in random.gi in chunks
@@ -190,7 +198,7 @@
and
@@ -215,8 +223,9 @@
(i.e. the last two) of the patch (and keep the kernel function) the problem vanishes.

The first of these changes removed a buggy kernel function. This is
substituted by a method that does not involve the determination of the type
of lists. As far as I can see it may be at most a few percent slower than
the previous kernel function, if at all.

The second change avoids that in Random(l); the type of l is determined
twice, as was the case before. This should never be slower than before.
(In case of long lists l one should not use Random(l) but better directly
l[Random(1, Length(l))] as in the new method).

[ChrisJefferson]

Here is a (huge!) concrete example of a problem (I just extracted this from @hulpke's code). This takes 66ms in 4.7.8, and a long time in master.

G := Group([ (2,3), (1,2), (84,165)(85,166)(86,167)(87,168)(88,169)(89,170)(90,171)(91,172)(92,173)(93,174)(94,175)(95,176)(96,
    177)(97,178)(98,179)(99,180)(100,181)(101,182)(102,183)(103,184)(104,185)(105,186)(106,187)(107,188)(108,
    189)(109,190)(110,191)(111,192)(112,193)(113,194)(114,195)(115,196)(116,197)(117,198)(118,199)(119,200)(120,
    201)(121,202)(122,203)(123,204)(124,205)(125,206)(126,207)(127,208)(128,209)(129,210)(130,211)(131,212)(132,
    213)(133,214)(134,215)(135,216)(136,217)(137,218)(138,219)(139,220)(140,221)(141,222)(142,223)(143,224)(144,
    225)(145,226)(146,227)(147,228)(148,229)(149,230)(150,231)(151,232)(152,233)(153,234)(154,235)(155,236)(156,
    237)(157,238)(158,239)(159,240)(160,241)(161,242)(162,243)(163,244)(164,245), (4,9,12,57,84,166,92,178,164,43,
    243,203,62,105,211,38,177,158,34,189,122,142,28,45,228,221,170,107,214,56,204,77,114,103,199,20,69,156,31,171,
    95,223,191,125,160,55,207,68,141,22,36,174,140,7,27,39,219,167,89,187,137,124,163,46,234,230,224,188,134,133,
    136,127,154,73,153,67,144,13,63,93,220,173,98,241,218,44,240,212,35,186,131,115,109,208,74,150,76,117,94,226,
    182,152,79,135,121,145,19,72,147,58,90,175,146,16,81,120,139,10,18,66,138)(5,6,21,30,165,86,169,110,205,83,123,
    157,37,180,149,61,108,202,65,96,238,200,17,78,129,112,91,181,155,70,162,40,225,176,143,25,54,201,59,87,184,119,
    97,244,209,71,159,49,198,14,60,102,193,11,15,75,111,85,172,101,232,245,206,80,132,130,118,100,235,236,233,242,
    215,53,213,50,195,23,33,183,113,88,190,128,151,82,126,148,64,99,229,227,179,161,52,216,41,222,185,116,106,217,
    47,231,239,197,26,51,210,32,168,104,196,29,42,237,194,8,24,48,192) ]);;

  Eval := [ (4,5)(7,8)(10,11)(13,14)(16,17)(19,20)(22,23)(25,26)(28,29)(31,32)(34,35)(37,38)(40,41)(43,44)(46,47)(49,50)(52,
    53)(55,56)(58,59)(61,62)(64,65)(67,68)(70,71)(73,74)(76,77)(79,80)(82,83)(85,86)(88,89)(91,92)(94,95)(97,
    98)(100,101)(103,104)(106,107)(109,110)(112,113)(115,116)(118,119)(121,122)(124,125)(127,128)(130,131)(133,
    134)(136,137)(139,140)(142,143)(145,146)(148,149)(151,152)(154,155)(157,158)(160,161)(163,164)(166,167)(169,
    170)(172,173)(175,176)(178,179)(181,182)(184,185)(187,188)(190,191)(193,194)(196,197)(199,200)(202,203)(205,
    206)(208,209)(211,212)(214,215)(217,218)(220,221)(223,224)(226,227)(229,230)(232,233)(235,236)(238,239)(241,
    242)(244,245) ];;

   L := Group([ (4,5)(7,8)(10,11)(13,14)(16,17)(19,20)(22,23)(25,26)(28,29)(31,32)(34,35)(37,38)(40,41)(43,44)(46,47)(49,50)(52,
    53)(55,56)(58,59)(61,62)(64,65)(67,68)(70,71)(73,74)(76,77)(79,80)(82,83)(85,86)(88,89)(91,92)(94,95)(97,
    98)(100,101)(103,104)(106,107)(109,110)(112,113)(115,116)(118,119)(121,122)(124,125)(127,128)(130,131)(133,
    134)(136,137)(139,140)(142,143)(145,146)(148,149)(151,152)(154,155)(157,158)(160,161)(163,164)(166,167)(169,
    170)(172,173)(175,176)(178,179)(181,182)(184,185)(187,188)(190,191)(193,194)(196,197)(199,200)(202,203)(205,
    206)(208,209)(211,212)(214,215)(217,218)(220,221)(223,224)(226,227)(229,230)(232,233)(235,236)(238,239)(241,
    242)(244,245), (84,96,108)(85,97,109)(86,98,110)(87,99,102)(88,100,103)(89,101,104)(90,93,105)(91,94,106)(92,95,
    107)(111,123,135)(112,124,136)(113,125,137)(114,126,129)(115,127,130)(116,128,131)(117,120,132)(118,121,
    133)(119,122,134)(138,150,162)(139,151,163)(140,152,164)(141,153,156)(142,154,157)(143,155,158)(144,147,
    159)(145,148,160)(146,149,161)(165,189,177)(166,190,178)(167,191,179)(168,183,180)(169,184,181)(170,185,
    182)(171,186,174)(172,187,175)(173,188,176)(192,216,204)(193,217,205)(194,218,206)(195,210,207)(196,211,
    208)(197,212,209)(198,213,201)(199,214,202)(200,215,203)(219,243,231)(220,244,232)(221,245,233)(222,237,
    234)(223,238,235)(224,239,236)(225,240,228)(226,241,229)(227,242,230), (84,165)(85,166)(86,167)(87,168)(88,
    169)(89,170)(90,171)(91,172)(92,173)(93,174)(94,175)(95,176)(96,177)(97,178)(98,179)(99,180)(100,181)(101,
    182)(102,183)(103,184)(104,185)(105,186)(106,187)(107,188)(108,189)(109,190)(110,191)(111,192)(112,193)(113,
    194)(114,195)(115,196)(116,197)(117,198)(118,199)(119,200)(120,201)(121,202)(122,203)(123,204)(124,205)(125,
    206)(126,207)(127,208)(128,209)(129,210)(130,211)(131,212)(132,213)(133,214)(134,215)(135,216)(136,217)(137,
    218)(138,219)(139,220)(140,221)(141,222)(142,223)(143,224)(144,225)(145,226)(146,227)(147,228)(148,229)(149,
    230)(150,231)(151,232)(152,233)(153,234)(154,235)(155,236)(156,237)(157,238)(158,239)(159,240)(160,241)(161,
    242)(162,243)(163,244)(164,245), (2,3), (1,2) ]);;


   RepOpElmTuplesPermGroup( false, G, Eval, Eval, L, L );

[ChrisJefferson]

Continuing the dive:

newL := Group( [ (  4,  5)(  7,  8)( 10, 11)( 13, 14)( 16, 17)( 19, 20)( 22, 23)
    ( 25, 26)( 28, 29)( 31, 32)( 34, 35)( 37, 38)( 40, 41)( 43, 44)( 46, 47)
    ( 49, 50)( 52, 53)( 55, 56)( 58, 59)( 61, 62)( 64, 65)( 67, 68)( 70, 71)
    ( 73, 74)( 76, 77)( 79, 80)( 82, 83)( 85, 86)( 88, 89)( 91, 92)( 94, 95)
    ( 97, 98)(100,101)(103,104)(106,107)(109,110)(112,113)(115,116)(118,119)
    (121,122)(124,125)(127,128)(130,131)(133,134)(136,137)(139,140)(142,143)
    (145,146)(148,149)(151,152)(154,155)(157,158)(160,161)(163,164)(166,167)
    (169,170)(172,173)(175,176)(178,179)(181,182)(184,185)(187,188)(190,191)
    (193,194)(196,197)(199,200)(202,203)(205,206)(208,209)(211,212)(214,215)
    (217,218)(220,221)(223,224)(226,227)(229,230)(232,233)(235,236)(238,239)
    (241,242)(244,245), ( 84, 96,108)( 85, 97,109)( 86, 98,110)( 87, 99,102)
    ( 88,100,103)( 89,101,104)( 90, 93,105)( 91, 94,106)( 92, 95,107)
    (111,123,135)(112,124,136)(113,125,137)(114,126,129)(115,127,130)
    (116,128,131)(117,120,132)(118,121,133)(119,122,134)(138,150,162)
    (139,151,163)(140,152,164)(141,153,156)(142,154,157)(143,155,158)
    (144,147,159)(145,148,160)(146,149,161)(165,189,177)(166,190,178)
    (167,191,179)(168,183,180)(169,184,181)(170,185,182)(171,186,174)
    (172,187,175)(173,188,176)(192,216,204)(193,217,205)(194,218,206)
    (195,210,207)(196,211,208)(197,212,209)(198,213,201)(199,214,202)
    (200,215,203)(219,243,231)(220,244,232)(221,245,233)(222,237,234)
    (223,238,235)(224,239,236)(225,240,228)(226,241,229)(227,242,230),
  ( 84,165)( 85,166)( 86,167)( 87,168)( 88,169)( 89,170)( 90,171)( 91,172)
    ( 92,173)( 93,174)( 94,175)( 95,176)( 96,177)( 97,178)( 98,179)( 99,180)
    (100,181)(101,182)(102,183)(103,184)(104,185)(105,186)(106,187)(107,188)
    (108,189)(109,190)(110,191)(111,192)(112,193)(113,194)(114,195)(115,196)
    (116,197)(117,198)(118,199)(119,200)(120,201)(121,202)(122,203)(123,204)
    (124,205)(125,206)(126,207)(127,208)(128,209)(129,210)(130,211)(131,212)
    (132,213)(133,214)(134,215)(135,216)(136,217)(137,218)(138,219)(139,220)
    (140,221)(141,222)(142,223)(143,224)(144,225)(145,226)(146,227)(147,228)
    (148,229)(149,230)(150,231)(151,232)(152,233)(153,234)(154,235)(155,236)
    (156,237)(157,238)(158,239)(159,240)(160,241)(161,242)(162,243)(163,244)
    (164,245), (2,3), (1,2) ] );;

    base := [ 211, 241, 238, 235, 3, 2, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
  17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
  35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52,
  53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
  71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88,
  89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105,
  106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120,
  121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135,
  136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150,
  151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165,
  166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180,
  181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195,
  196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210,
  212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226,
  227, 228, 229, 230, 231, 232, 233, 234, 236, 237, 239, 240, 242, 243, 244,
  245 ];;

   StabChainOp(newL, rec(base := base, reduced := false));

[ChrisJefferson]

I get an entirely different target to blame -- SCRSift moving into the Kernel.

However, there is also something dodgy with random numbers going on in stbc, as it reaches into the old random number generator and manipulates it directly, which I can imagine would cause trouble! Continuing to investigate.

[ChrisJefferson]

This is fixed by #807. I think the random number change just happened to change the random order something is generated in, causing it to hit the bad case.

[hulpke]

@ChrisJefferson Thank you very much for fixing this (and cleaning up the RNG access)!

[markuspf]

Thanks for catching this @ChrisJefferson. I am just now rerunning the computation to find whether the regression is gone.

[markuspf]

Good news: the runtimes in stable-4.8 and master are now pretty much the same. I think we're good to merge #807