Opened 14 years ago
Closed 8 years ago
#864 closed enhancement (fixed)
Asymptotically slow PARI --> Python long conversions
Reported by: | craigcitro | Owned by: | craigcitro |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.13 |
Component: | performance | Keywords: | pari |
Cc: | Merged in: | sage-5.13.beta2 | |
Authors: | Peter Bruin | Reviewers: | Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This is really a leftover from ticket #467, split because I wanted the first half of the fix to make it into 2.8.7. Here's a summary of the badness:
sage: x = 10^100000 sage: time y = pari(x) CPU times: user 1.18 s, sys: 0.01 s, total: 1.19 s Wall time: 1.26 sage: time z = Integer(y) CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s Wall time: 0.02 sage: time u = int(y) CPU times: user 1.94 s, sys: 1.33 s, total: 3.27 s Wall time: 3.58 sage: time u = int(Integer(y)) CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s Wall time: 0.03 sage: x = 10^1000000 sage: time y = pari(x) CPU times: user 105.12 s, sys: 1.26 s, total: 106.38 s Wall time: 121.86 sage: time z = Integer(y) CPU times: user 0.03 s, sys: 0.02 s, total: 0.05 s Wall time: 0.09 sage: time u = int(y) CPU times: user 188.17 s, sys: 145.12 s, total: 333.28 s Wall time: 364.80 sage: time u = int(Integer(y)) CPU times: user 0.04 s, sys: 0.02 s, total: 0.06 s Wall time: 0.07
And here's the state of affairs after the first patch:
sage: x = 10^100000 sage: time y = pari(x) CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 sage: time z = Integer(y) CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 sage: time u = int(y) CPU times: user 1.64 s, sys: 1.09 s, total: 2.73 s Wall time: 2.79 sage: time u = int(Integer(y)) CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 sage: x = 10^1000000 sage: time y = pari(x) CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 sage: time z = Integer(y) CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s Wall time: 0.00 sage: time u = int(y) CPU times: user 220.90 s, sys: 137.34 s, total: 358.24 s Wall time: 408.11 sage: time u = int(Integer(y)) CPU times: user 0.00 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01
Clearly that third function call needs to be fixed; this is done by the attached patch.
Attachments (2)
Change History (12)
comment:1 Changed 14 years ago by
- Status changed from new to assigned
comment:2 Changed 12 years ago by
comment:3 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:4 follow-up: ↓ 5 Changed 8 years ago by
- Component changed from interfaces to performance
- Report Upstream set to N/A
- Status changed from new to needs_review
- Summary changed from Asymptotically slow pari <--> python long conversions to Asymptotically slow PARI --> Python long conversions
I am uploading a patch that implements conversion from PARI t_INT
to Python long via an intermediate mpz_t
, so long(y)
essentially does long(Integer(y))
.
Some timings:
sage: x = 10^1000000 sage: %timeit y=pari(x) 10000 loops, best of 3: 197 us per loop sage: %timeit z=Integer(y) 100 loops, best of 3: 4.11 ms per loop sage: %timeit u=long(y) 100 loops, best of 3: 13 ms per loop sage: %timeit u=long(Integer(y)) 100 loops, best of 3: 13.8 ms per loop sage: x = 10^10000000 sage: %timeit y=pari(x) 100 loops, best of 3: 5.57 ms per loop sage: %timeit z=Integer(y) 100 loops, best of 3: 2.94 ms per loop sage: %timeit u=long(y) 100 loops, best of 3: 13.9 ms per loop sage: %timeit u=long(Integer(y)) 100 loops, best of 3: 13.8 ms per loop
Changed 8 years ago by
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 7 Changed 8 years ago by
Replying to pbruin:
so
long(y)
essentially doeslong(Integer(y))
.
Why not literally do long(Integer(y))
then and save many lines of code?
comment:6 Changed 8 years ago by
Note that this works:
sage: Integer(pari("Mod(2,7)")) 2
so you would get these cases for free...
comment:7 in reply to: ↑ 5 Changed 8 years ago by
Replying to jdemeyer:
Replying to pbruin:
so
long(y)
essentially doeslong(Integer(y))
.Why not literally do
long(Integer(y))
then and save many lines of code?
I thought that the penalty for creating an Integer
was quite heavy in some cases; for example, with the current patch applied, I get
sage: y=pari(10^10000) sage: %timeit -c -r 1 u=long(y) 100000 loops, best of 1: 12.2 us per loop sage: %timeit -c -r 1 u=long(Integer(y)) 10000 loops, best of 1: 19.6 us per loop
However, I just tried implementing gen.__long__(self)
as return long(Integer(self))
, and it is just as fast, thanks to Cython I guess. I also agree that long(pari("Mod(2,7)"))
is nice to get for free. New patch coming soon.
comment:8 Changed 8 years ago by
- Reviewers set to Jeroen Demeyer
- Status changed from needs_review to needs_work
Changed 8 years ago by
comment:9 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
apply trac_864-pari_int_long_conversion.patch
comment:10 Changed 8 years ago by
- Merged in set to sage-5.13.beta2
- Resolution set to fixed
- Status changed from needs_review to closed
Looks good!
Hi Craig,
this has been open a while. The current timings from sage.math: