gap-packages / recog

The GAP package recog to collect methods for constructive recognition
https://gap-packages.github.io/recog/
GNU General Public License v3.0
6 stars 14 forks source link

Remove TODO: is storing random elms quicker? #281

Closed ssiccha closed 3 years ago

ssiccha commented 3 years ago

The first commit fixes a bug in RandomElm. This fix is needed to call RandomElm on a group which does not store its random elements.

The second commit removes a TODO. The following is of course not a proper benchmark, but just a comparison of two runs of tst/testall.g. I think it's good enough to warrant that commit though. I originally wrote the comparison only for tst/testquick.g but using tst/testall.g gives the same overall picture.

Storing the random elements makes the whole test suite and most test files finish roughly 10% earlier than without storing random elements.

There are a few tests which run almost two times as fast with storing random elements enabled by default compared to without it being enabled.

There are a few test files where both approaches take roughly the same time.

Ignoring those test files which take less than 10ms to complete, PermLargeBasePrimitive is the only test file where not storing random elements is significantly faster, namely roughly 5%. Edit: With the slow and veryslow tests running too, veryslow/MatFDPM.tst is the only other test file where not storing random elements is significantly quicker for me: it takes 20s without storing random elements compared to 33.5s when storing random elements.

Here are timings from runs of tst/testquick.g on my machine. I ran the tests without storing random elements first to exclude the possibility that the whole speed difference came from heating up my CPU. I'm currently also running the full test suite on my machine.

With storing random elements

testing: /home/sergio/projects/pkg/recog/tst/working/quick/C3C5.tst
    5735 ms (131 ms GC) and 401MB allocated for quick/C3C5.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ClassicalNaturalNaming.tst
   60523 ms (1590 ms GC) and 4.32GB allocated for quick/ClassicalNaturalNaming.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/GenericSnAnUnknownDegree.tst
   72915 ms (10385 ms GC) and 7.33GB allocated for quick/GenericSnAnUnknownDegree.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/MatDiagonal.tst
    3331 ms (1206 ms GC) and 507MB allocated for quick/MatDiagonal.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/MatReducible.tst
     145 ms (8 ms GC) and 17.9MB allocated for quick/MatReducible.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/MatSn.tst
     903 ms (522 ms GC) and 47.5MB allocated for quick/MatSn.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/MatTrivial.tst
       5 ms (0 ms GC) and 542KB allocated for quick/MatTrivial.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/Methods.tst
       0 ms (0 ms GC) and 27.8KB allocated for quick/Methods.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/PermAllSubgroups.tst
     498 ms (18 ms GC) and 52.2MB allocated for quick/PermAllSubgroups.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/PermCycle.tst
       3 ms (0 ms GC) and 221KB allocated for quick/PermCycle.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/PermDirProd.tst
      15 ms (0 ms GC) and 2.25MB allocated for quick/PermDirProd.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/PermLargeBasePrimitive.tst
    4029 ms (1268 ms GC) and 2.09GB allocated for quick/PermLargeBasePrimitive.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/PermThrowAwayFixedPoints.tst
       5 ms (0 ms GC) and 632KB allocated for quick/PermThrowAwayFixedPoints.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/PermTrivial.tst
       1 ms (0 ms GC) and 180KB allocated for quick/PermTrivial.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjLowIndex.tst
     263 ms (9 ms GC) and 37.8MB allocated for quick/ProjLowIndex.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjLowIndex2.tst
    3793 ms (122 ms GC) and 348MB allocated for quick/ProjLowIndex2.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjNotAbsIrred.tst
     251 ms (11 ms GC) and 27.6MB allocated for quick/ProjNotAbsIrred.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjReducible.tst
     217 ms (9 ms GC) and 27.4MB allocated for quick/ProjReducible.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjStabChain.tst
    1396 ms (35 ms GC) and 113MB allocated for quick/ProjStabChain.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjSubfield.tst
     306 ms (10 ms GC) and 31.0MB allocated for quick/ProjSubfield.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjSubfield2.tst
     359 ms (12 ms GC) and 34.0MB allocated for quick/ProjSubfield2.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjSubfield3.tst
      67 ms (2 ms GC) and 4.85MB allocated for quick/ProjSubfield3.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjTensor.tst
    1771 ms (632 ms GC) and 87.7MB allocated for quick/ProjTensor.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjTensorInduced.tst
     765 ms (14 ms GC) and 68.9MB allocated for quick/ProjTensorInduced.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjThreeLargeElOrders.tst
     690 ms (14 ms GC) and 46.2MB allocated for quick/ProjThreeLargeElOrders.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/ProjTrivial.tst
       5 ms (0 ms GC) and 541KB allocated for quick/ProjTrivial.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/RecogMethod.tst
       1 ms (0 ms GC) and 59.8KB allocated for quick/RecogMethod.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/Sporadic.tst
   22736 ms (4961 ms GC) and 2.66GB allocated for quick/Sporadic.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/bugfix.tst
     223 ms (136 ms GC) and 10.4MB allocated for quick/bugfix.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/cgo1.tst
     929 ms (20 ms GC) and 57.6MB allocated for quick/cgo1.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/classical.tst
     947 ms (14 ms GC) and 57.0MB allocated for quick/classical.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/mixed.tst
       1 ms (0 ms GC) and 56.4KB allocated for quick/mixed.tst
testing: /home/sergio/projects/pkg/recog/tst/working/quick/sl3.tst
      71 ms (4 ms GC) and 11.8MB allocated for quick/sl3.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/MatAn.tst
    3442 ms (269 ms GC) and 625MB allocated for slow/MatAn.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/MatC3.tst
     257 ms (9 ms GC) and 26.0MB allocated for slow/MatC3.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/MatC3_2.tst
    6523 ms (247 ms GC) and 514MB allocated for slow/MatC3_2.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/MatHSmax5.tst
    3541 ms (327 ms GC) and 492MB allocated for slow/MatHSmax5.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/NonDeletedPermModuleRepOfSn.tst
    2278 ms (39 ms GC) and 143MB allocated for slow/NonDeletedPermModuleRepOfSn.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/ProjC6.tst
    7053 ms (276 ms GC) and 488MB allocated for slow/ProjC6.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/ProjDet.tst
   14815 ms (310 ms GC) and 625MB allocated for slow/ProjDet.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/Sporadic.tst
   19315 ms (2762 ms GC) and 1.72GB allocated for slow/Sporadic.tst
testing: /home/sergio/projects/pkg/recog/tst/working/slow/basic.tst
    6487 ms (1758 ms GC) and 1.05GB allocated for slow/basic.tst
testing: /home/sergio/projects/pkg/recog/tst/working/veryslow/ClassicalNatural.tst
   65668 ms (6614 ms GC) and 5.89GB allocated for veryslow/ClassicalNatural.tst
testing: /home/sergio/projects/pkg/recog/tst/working/veryslow/MatC6.tst
   35566 ms (1850 ms GC) and 2.44GB allocated for veryslow/MatC6.tst
testing: /home/sergio/projects/pkg/recog/tst/working/veryslow/MatFDPM.tst
   33503 ms (215 ms GC) and 775MB allocated for veryslow/MatFDPM.tst
testing: /home/sergio/projects/pkg/recog/tst/working/veryslow/PermSym10Subgroup.tst
   38105 ms (3168 ms GC) and 4.63GB allocated for veryslow/PermSym10Subgroup.tst
testing: /home/sergio/projects/pkg/recog/tst/working/veryslow/PermTrans16.tst
    7789 ms (729 ms GC) and 961MB allocated for veryslow/PermTrans16.tst
-----------------------------------
total    427241 ms (39706 ms GC) and 38.6GB allocated
              0 failures in 47 files

#I  No errors detected while testing

Without storing random elements

testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/C3C5.tst
    6019 ms (113 ms GC) and 387MB allocated for quick/C3C5.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ClassicalNaturalNaming.tst
   69404 ms (1474 ms GC) and 4.36GB allocated for quick/ClassicalNaturalNaming.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/GenericSnAnUnknownDegree.tst
   76174 ms (7684 ms GC) and 7.47GB allocated for quick/GenericSnAnUnknownDegree.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/MatDiagonal.tst
    3283 ms (1219 ms GC) and 576MB allocated for quick/MatDiagonal.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/MatReducible.tst
     154 ms (7 ms GC) and 19.1MB allocated for quick/MatReducible.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/MatSn.tst
     346 ms (13 ms GC) and 46.0MB allocated for quick/MatSn.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/MatTrivial.tst
       5 ms (0 ms GC) and 535KB allocated for quick/MatTrivial.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/Methods.tst
       0 ms (0 ms GC) and 27.8KB allocated for quick/Methods.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/PermAllSubgroups.tst
     499 ms (28 ms GC) and 51.1MB allocated for quick/PermAllSubgroups.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/PermCycle.tst
       3 ms (0 ms GC) and 211KB allocated for quick/PermCycle.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/PermDirProd.tst
      15 ms (0 ms GC) and 2.18MB allocated for quick/PermDirProd.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/PermLargeBasePrimitive.tst
    3050 ms (1303 ms GC) and 1.78GB allocated for quick/PermLargeBasePrimitive.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/PermThrowAwayFixedPoints.tst
       4 ms (0 ms GC) and 625KB allocated for quick/PermThrowAwayFixedPoints.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/PermTrivial.tst
       0 ms (0 ms GC) and 173KB allocated for quick/PermTrivial.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjLowIndex.tst
     250 ms (10 ms GC) and 38.2MB allocated for quick/ProjLowIndex.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjLowIndex2.tst
    7329 ms (462 ms GC) and 615MB allocated for quick/ProjLowIndex2.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjNotAbsIrred.tst
     277 ms (11 ms GC) and 30.7MB allocated for quick/ProjNotAbsIrred.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjReducible.tst
     186 ms (5 ms GC) and 23.5MB allocated for quick/ProjReducible.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjStabChain.tst
    1508 ms (38 ms GC) and 119MB allocated for quick/ProjStabChain.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjSubfield.tst
     311 ms (11 ms GC) and 28.9MB allocated for quick/ProjSubfield.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjSubfield2.tst
     322 ms (10 ms GC) and 31.3MB allocated for quick/ProjSubfield2.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjSubfield3.tst
      59 ms (4 ms GC) and 4.53MB allocated for quick/ProjSubfield3.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjTensor.tst
     899 ms (34 ms GC) and 75.3MB allocated for quick/ProjTensor.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjTensorInduced.tst
    1301 ms (298 ms GC) and 89.0MB allocated for quick/ProjTensorInduced.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjThreeLargeElOrders.tst
     744 ms (12 ms GC) and 48.9MB allocated for quick/ProjThreeLargeElOrders.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/ProjTrivial.tst
       8 ms (0 ms GC) and 536KB allocated for quick/ProjTrivial.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/RecogMethod.tst
       1 ms (0 ms GC) and 59.8KB allocated for quick/RecogMethod.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/Sporadic.tst
   29696 ms (10608 ms GC) and 2.66GB allocated for quick/Sporadic.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/bugfix.tst
     202 ms (87 ms GC) and 10.7MB allocated for quick/bugfix.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/cgo1.tst
    1572 ms (515 ms GC) and 61.2MB allocated for quick/cgo1.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/classical.tst
    1776 ms (475 ms GC) and 57.0MB allocated for quick/classical.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/mixed.tst
       0 ms (0 ms GC) and 55.7KB allocated for quick/mixed.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/quick/sl3.tst
      64 ms (0 ms GC) and 8.58MB allocated for quick/sl3.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/MatAn.tst
    5835 ms (2415 ms GC) and 646MB allocated for slow/MatAn.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/MatC3.tst
     249 ms (6 ms GC) and 25.4MB allocated for slow/MatC3.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/MatC3_2.tst
    7992 ms (436 ms GC) and 615MB allocated for slow/MatC3_2.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/MatHSmax5.tst
    3472 ms (213 ms GC) and 564MB allocated for slow/MatHSmax5.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/NonDeletedPermModuleRepOfSn.tst
    2885 ms (50 ms GC) and 172MB allocated for slow/NonDeletedPermModuleRepOfSn.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/ProjC6.tst
    9510 ms (400 ms GC) and 626MB allocated for slow/ProjC6.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/ProjDet.tst
   14917 ms (389 ms GC) and 582MB allocated for slow/ProjDet.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/Sporadic.tst
   22768 ms (5263 ms GC) and 1.73GB allocated for slow/Sporadic.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/slow/basic.tst
    6653 ms (2165 ms GC) and 1017MB allocated for slow/basic.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/veryslow/ClassicalNatural.tst
   66811 ms (6768 ms GC) and 6.00GB allocated for veryslow/ClassicalNatural.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/veryslow/MatC6.tst
   46430 ms (2203 ms GC) and 3.04GB allocated for veryslow/MatC6.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/veryslow/MatFDPM.tst
   20639 ms (460 ms GC) and 867MB allocated for veryslow/MatFDPM.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/veryslow/PermSym10Subgroup.tst
   39088 ms (3258 ms GC) and 4.57GB allocated for veryslow/PermSym10Subgroup.tst
testing: /home/sergio/projects/pkg/worktree-2-recog//tst/working/veryslow/PermTrans16.tst
    7576 ms (510 ms GC) and 948MB allocated for veryslow/PermTrans16.tst
-----------------------------------
total    460286 ms (48957 ms GC) and 39.8GB allocated
              0 failures in 47 files

#I  No errors detected while testing
codecov[bot] commented 3 years ago

Codecov Report

Merging #281 (76f7859) into master (c57a2be) will increase coverage by 0.02%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #281      +/-   ##
==========================================
+ Coverage   77.86%   77.88%   +0.02%     
==========================================
  Files          43       43              
  Lines       18389    18394       +5     
==========================================
+ Hits        14319    14327       +8     
+ Misses       4070     4067       -3     
Impacted Files Coverage Δ
gap/base/recognition.gi 69.02% <100.00%> (+0.23%) :arrow_up:
gap/perm/giant.gi 90.35% <0.00%> (+0.67%) :arrow_up: