Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Performance regression related to Cayley digraphs #356

Closed
wilfwilson opened this issue Aug 15, 2017 · 3 comments
Closed

Performance regression related to Cayley digraphs #356

wilfwilson opened this issue Aug 15, 2017 · 3 comments
Assignees
@james-d-mitchell

Comments

@wilfwilson
Copy link
Collaborator 

M6 := Semigroup([
   Matrix(IsNTPMatrix, [[0, 0, 1], [0, 1, 0], [1, 1, 0]], 0, 6),
   Matrix(IsNTPMatrix, [[0, 0, 1], [0, 1, 0], [2, 0, 0]], 0, 6),
   Matrix(IsNTPMatrix, [[0, 0, 1], [0, 1, 1], [1, 0, 0]], 0, 6),
   Matrix(IsNTPMatrix, [[0, 0, 1], [0, 1, 0], [3, 0, 0]], 0, 6)]);
NrDClasses(M6);

The answer to this block of code is 16; M6 is the monoid consisting of all 3x3 matrices over Z/6Z.

Before PR #348 was merged (in v3.0.3, for instance), this computation took about 28 seconds. Afterwards (in the current version of master, for instance), it takes about 42 seconds.
@james-d-mitchell
Copy link
Collaborator

Just to double-check, everything is compiled the same way in both cases right?

@wilfwilson
Copy link
Collaborator Author

Yes. Michael and I used git bisect to change between Semigroups changesets; we used the released version of libsemigroups and ran make every time we checked out a new Semigroups changeset.

@james-d-mitchell james-d-mitchell self-assigned this Aug 23, 2017
james-d-mitchell pushed a commit to james-d-mitchell/Semigroups that referenced this issue Aug 23, 2017
fropin: fix performance of Left/RightCayleyDigraph
7c391dd 
Previously we did Digraph(EN_SEMI_RIGHT_CAYLEY_GRAPH(S)) which involved
copying the output of EN_SEMI_RIGHT_CAYLEY_GRAPH(S), and performing
checks that the output was valid. We make the output of
EN_SEMI_RIGHT_CAYLEY_GRAPH(S) immutable, and use DigraphNC to avoid
these unnecessary checks. This seems to resolve Issue semigroups#356.
@james-d-mitchell james-d-mitchell mentioned this issue Aug 23, 2017
Merged
@james-d-mitchell james-d-mitchell added 3.1 and removed 3.0 labels Aug 23, 2017
james-d-mitchell pushed a commit that referenced this issue Aug 23, 2017
fropin: fix performance of Left/RightCayleyDigraph
e6c8ffc 
Previously we did Digraph(EN_SEMI_RIGHT_CAYLEY_GRAPH(S)) which involved
copying the output of EN_SEMI_RIGHT_CAYLEY_GRAPH(S), and performing
checks that the output was valid. We make the output of
EN_SEMI_RIGHT_CAYLEY_GRAPH(S) immutable, and use DigraphNC to avoid
these unnecessary checks. This seems to resolve Issue #356.
wilfwilson added a commit that referenced this issue Aug 23, 2017
@wilfwilson
Merge pull request #360 from james-d-mitchell/fix-issue-356
c7ce4fb 
Fix issue #356
@mtorpey
Copy link
Collaborator

mtorpey commented Aug 31, 2017

This is now fixed, and the timing looks better than ever.

@mtorpey mtorpey closed this as completed Aug 31, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@james-d-mitchell james-d-mitchell

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@mtorpey @james-d-mitchell @wilfwilson