gap-system / gap

Main development repository for GAP - Groups, Algorithms, Programming, a System for Computational Discrete Algebra
https://www.gap-system.org
GNU General Public License v2.0
814 stars 161 forks source link

Faster `SwapMatrixRows` and `SwapMatrixColumns` for 8bit matrices #5838

Closed fingolfin closed 1 week ago

fingolfin commented 2 weeks ago

Before:

gap> mat:=IdentityMat(10,GF(5));; ConvertToMatrixRep(mat);; mat;
< mutable compressed matrix 10x10 over GF(5) >
gap> for i in [1..1000000] do SwapMatrixColumns(mat,1,2); od; time;
1308
gap> for i in [1..1000000] do SwapMatrixRows(mat,1,2); od; time;
125
gap> for i in [1..1000000] do tmp:=mat[1];mat[1]:=mat[2];mat[2]:=tmp; od; time;
92

After:

gap> mat:=IdentityMat(10,GF(5));; ConvertToMatrixRep(mat);; mat;
< mutable compressed matrix 10x10 over GF(5) >
gap> for i in [1..1000000] do SwapMatrixColumns(mat,1,2); od; time;
198
gap> for i in [1..1000000] do SwapMatrixRows(mat,1,2); od; time;
28
gap> for i in [1..1000000] do tmp:=mat[1];mat[1]:=mat[2];mat[2]:=tmp; od; time;
92

Please provide a short summary of this PR and its purpose here. E.g., does it add a new feature, and which? Does it fix a bug, and which? If there is an associated issue, please list it here.

Text for release notes

We track noteworthy changes as entries in the CHANGES.md file in the root directory of this repository. To help us decide whether and how to describe your PR, please do one of the following:

  1. If this PR shall not be mentioned in the release notes, write "none" here.
  2. If a brief note suffices, edit the title of this PR to be usable as entry in CHANGES.md, and write "see title" here (or if you have the required permissions, add the label release notes: use title to this PR and remove this section)
  3. If a longer note is needed, just write it here, ideally following the general style used in that file

Further details

If necessary, provide further details down here.