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:  sage9.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: 
Description
Example:
sage: p = 2^5211 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/CastryckDecruSageMath#speedingsagemathupusingacache
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
Status:  new → needs_review 

comment:2 Changed 2 months ago by
Commit:  94af055c1a9b792ff00cdbd371657a7112be904c → b5f2eac416f30607c1e72e32c2a4745101fd74c3 

comment:3 Changed 2 months ago by
Cc:  k3w1k0d3r added 

Reviewers:  → Julien Grijalva 
comment:4 Changed 2 months ago by
Status:  needs_review → positive_review 

comment:5 Changed 2 months ago by
Status:  positive_review → needs_work 

comment:6 Changed 2 months ago by
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.
comment:7 Changed 2 months ago by
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
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
Commit:  b5f2eac416f30607c1e72e32c2a4745101fd74c3 → c6772ddbddf7ce66c9956aff3e0915f35507f33c 

Branch pushed to git repo; I updated commit sha1. New commits:
c6772dd  remove incorrect(?) sig_on/sig_off

comment:10 Changed 8 weeks ago by
Status:  needs_work → needs_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
Commit:  c6772ddbddf7ce66c9956aff3e0915f35507f33c → 0b9db49a459b78c018f610f23ec9c79562e56b62 

Branch pushed to git repo; I updated commit sha1. New commits:
0b9db49  avoid failing code path by passing tuple to GF constructor

comment:12 Changed 8 weeks ago by
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
Patchbot is morally green; I've seen the remaining failure in other (totally unrelated) tickets before.
comment:14 Changed 8 weeks ago by
Status:  needs_review → positive_review 

comment:15 Changed 5 weeks ago by
Branch:  public/defer_primality_testing_in_cached_GF_constructor → 0b9db49a459b78c018f610f23ec9c79562e56b62 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
update doctest outputs