Opened 2 months ago

Closed 5 weeks ago

#34281 closed enhancement (fixed)

defer primality and irreducibility testing in GF constructor until after caching

Reported by: Lorenz Panny Owned by:
Priority: major Milestone: sage-9.7
Component: performance Keywords:
Cc: k3w1k0d3r Merged in:
Authors: Lorenz Panny Reviewers: Julien Grijalva
Report Upstream: N/A Work issues:
Branch: 0b9db49 (Commits, GitHub, GitLab) Commit: 0b9db49a459b78c018f610f23ec9c79562e56b62
Dependencies: Stopgaps:

Status badges

Description

Example:

sage: p = 2^521-1
sage: F = GF(p)
sage: GF(p) is F  # field is cached
True
sage: %timeit GF(p)
521 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Note that the constructor tests primality each time even though the field is already cached! This was pointed out here:

https://github.com/jack4818/Castryck-Decru-SageMath#speeding-sagemath-up-using-a-cache

In this patch, we move the primality and irreducibility testing from FiniteFieldFactory.create_key_and_extra_args() to FiniteFieldFactory.create_object(), so that it isn't performed again for fields already present in the cache.

The result is a massive speedup for repeated invocations of GF(p):

78.6 µs ± 870 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Change History (15)

comment:1 Changed 2 months ago by Lorenz Panny

Status: newneeds_review

comment:2 Changed 2 months ago by git

Commit: 94af055c1a9b792ff00cdbd371657a7112be904cb5f2eac416f30607c1e72e32c2a4745101fd74c3

Branch pushed to git repo; I updated commit sha1. New commits:

b5f2eacupdate doctest outputs

comment:3 Changed 2 months ago by k3w1k0d3r

Cc: k3w1k0d3r added
Reviewers: Julien Grijalva

comment:4 Changed 2 months ago by k3w1k0d3r

Status: needs_reviewpositive_review

comment:5 Changed 2 months ago by k3w1k0d3r

Status: positive_reviewneeds_work

comment:6 Changed 2 months ago by k3w1k0d3r

patchbot failed a test, segfaulting when it reached the p, n = order.perfect_power() you added. I'm currently checking if I reproduce this locally.

Last edited 2 months ago by k3w1k0d3r (previous) (diff)

comment:7 Changed 2 months ago by Lorenz Panny

I suspect this is a consequence of the other doctest failures here (which I also see on the unpatched develop branch). I can't reproduce it in isolation.

comment:8 Changed 2 months ago by k3w1k0d3r

I am able to reproduce this behavior locally. It seems like a bug in the perfect_power method though. I'll investigate.

comment:9 Changed 8 weeks ago by git

Commit: b5f2eac416f30607c1e72e32c2a4745101fd74c3c6772ddbddf7ce66c9956aff3e0915f35507f33c

Branch pushed to git repo; I updated commit sha1. New commits:

c6772ddremove incorrect(?) sig_on/sig_off

comment:10 Changed 8 weeks ago by Lorenz Panny

Status: needs_workneeds_review

Setting to "needs review" to get the patchbot to run, but I suspect there are still problems.

comment:11 Changed 8 weeks ago by git

Commit: c6772ddbddf7ce66c9956aff3e0915f35507f33c0b9db49a459b78c018f610f23ec9c79562e56b62

Branch pushed to git repo; I updated commit sha1. New commits:

0b9db49avoid failing code path by passing tuple to GF constructor

comment:12 Changed 8 weeks ago by Lorenz Panny

With the most recent commit, I no longer see any failures on my machine. Still not sure what causes these crashes and why things only go wrong in pbori.pyx, but the workaround seems to, well, work around it.

comment:13 Changed 8 weeks ago by Lorenz Panny

Patchbot is morally green; I've seen the remaining failure in other (totally unrelated) tickets before.

comment:14 Changed 8 weeks ago by k3w1k0d3r

Status: needs_reviewpositive_review

comment:15 Changed 5 weeks ago by Volker Braun

Branch: public/defer_primality_testing_in_cached_GF_constructor0b9db49a459b78c018f610f23ec9c79562e56b62
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.