Opened 11 years ago
Closed 8 years ago
#9887 closed defect (worksforme)
slow coercion from integer ring to integer mod ring
Reported by: | dmharvey | Owned by: | tbd |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | performance | Keywords: | sd51 |
Cc: | Merged in: | ||
Authors: | Reviewers: | Alex Ghitza | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Sage 4.5.3, 2.6GHz Opteron, Linux
sage: R = Integers(3^20) sage: u = Integer(2) sage: timeit("z = R(u)") 625 loops, best of 3: 6.84 µs per loop
Why does it take 18000 cycles to convert a tiny integer to an element of R?
Attachments (3)
Change History (18)
comment:1 Changed 11 years ago by
- Status changed from new to needs_review
comment:2 Changed 11 years ago by
Oops, the top of the dependencies got cut off, and there are newer versions of some of these patches. It should read:
8333_parent_init.patch 8333_finite_fields_to_new_coercion.2.patch 7883_ideals.patch 7883_fixes.patch 7585_9_1_frac_and_coerce_updates.patch 8334_residue_fields-rebased_for_8446.patch 7585_12_1_fixes.patch.2 9814-2.patch
Note that you can find 7585_12_1_fixes.patch
and 7585_9_1_frac_and_coerce_updates.patch
at #8334.
comment:3 Changed 11 years ago by
- Milestone set to sage-4.6
I tried the test cases from tickets #9882-#9887 under 4.5.3, under 4.6.alpha2 without this patch, and with this patch. Apologies for the crappy ASCII-art table.
------------------------------- | 4.5.3 | 4.6.a2 | + patch | ------------------------------------- #9882 | 19.8 µs | 15.9 µs | 3.87 µs | #9883 | 4.25 ms | 133 µs | 21.5 µs | #9884 | 1.04 ms | 385 µs | 18 µs | #9885 | 1.23 µs | 1.24 µs | 1.34 µs | #9886 | 33.7 µs | 32.5 µs | 32.9 µs | #9887 | 6.54 µs | 966 ns | 992 ns | -------------------------------------
So it looks like David's other finite rings patches have already made a dramatic speed improvement to several of these, and the patch on this ticket further improves some of them. The fact that #9885 actually slowed down marginally as a result of the patch is slightly worrying; it might just be random noise, but I did several more runs and the slight slowdowns in #9885 and (to a lesser extent) #9887 seemed quite consistent. It might be a price worth paying for the dramatic speedups elsewhere, but it would be nice if we could avoid it.
I'd be interested to see corresponding timings on other systems.
comment:4 Changed 11 years ago by
I'm not sure why there are slight slowdowns for #9885 and #9887. But I did figure out why #9886 was unexpectedly slow: see #10130.
Here are timings on my Macbook Pro (+ patch includes the patch at #10130):
------------------------------- | 4.3.rc0 | 4.6.a2 | + patch | ------------------------------------- #9882 | 19.9 µs | 15 µs | 3.71 µs | #9883 | 4.34 ms | 117 µs | 20.2 µs | #9884 | 3.79 ms | 314 µs | 30.7 µs | #9885 | 1.22 µs | 850 ns | 938 ns | #9886 | 9.99 µs | 33.4 µs | 264 ns | #9887 | ? µs | 787 ns | 814 ns | -------------------------------------
I got a range of values for #9885 in the middle column, from 835ns to 1.07µs.
I wanted to check 9.99µs in the first column in a different branch, so rebuilt only to discover that that copy of sage was built when I had an earlier version of OS X and was thus running 32 bit...
comment:5 Changed 10 years ago by
- Status changed from needs_review to needs_work
This patch fails to apply against 4.7:
cd "/home/kedlaya/Downloads/sage-4.7/devel/sage" && hg import "/home/kedlaya/Downloads/9887.patch" applying /home/kedlaya/Downloads/9887.patch patching file sage/rings/finite_rings/integer_mod.pxd Hunk #1 succeeded at 12 with fuzz 1 (offset 0 lines). patching file sage/rings/polynomial/polynomial_ring.py Hunk #7 FAILED at 1246 1 out of 13 hunks FAILED -- saving rejects to file sage/rings/polynomial/polynomial_ring.py.rej abort: patch failed to apply
Changed 10 years ago by
comment:6 Changed 10 years ago by
- Status changed from needs_work to needs_review
It should apply against 4.7.1.alpha4.
comment:7 Changed 10 years ago by
For patchbot (and others working against 4.7), apply 9887_vs_47.patch only.
comment:8 Changed 10 years ago by
What is the status of this patch now? It looks like it could easily bit-rot (if it hasn't already).
comment:9 Changed 10 years ago by
Apply only 9887_vs_48a2.patch
comment:10 Changed 10 years ago by
- Dependencies set to 11900
- Reviewers set to PatchBot
- Status changed from needs_review to needs_work
- Work issues set to needs rebase
comment:11 Changed 10 years ago by
- Dependencies changed from 11900 to #11900
comment:12 Changed 9 years ago by
- Status changed from needs_work to needs_info
There is at least some partial work on this done in 5.7.beta3
:
sage: R = Integers(3^20) sage: u = Integer(2) sage: %timeit z = R(u) 100000 loops, best of 3: 1.48 us per loop sage: %timeit z = R(u) 1000000 loops, best of 3: 1.74 us per loop
So should we close this ticket?
Edit - I'm running this test on my Ubuntu VM while video chatting on Skype in my Host OS.
comment:13 Changed 8 years ago by
- Dependencies #11900 deleted
- Keywords sd51 added
- Reviewers PatchBot deleted
- Status changed from needs_info to positive_review
- Work issues needs rebase deleted
I second the request to close the ticket. On sage-5.10:
sage: R = Integers(3^20) sage: u = Integer(2) sage: %timeit("z = R(u)") 10000000 loops, best of 3: 24.6 ns per loop sage: %timeit("z = ZZ(u)") 10000000 loops, best of 3: 24.5 ns per loop
In other words, putting u into R takes the same time as putting u into ZZ (where it is already). It shouldn't be possible to do any better.
I'll tag this as "positive review" to bring it to the release manager's attention.
comment:14 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-duplicate/invalid/wontfix
- Reviewers set to Alex Ghitza
comment:15 Changed 8 years ago by
- Resolution set to worksforme
- Status changed from positive_review to closed
This depends on #7883, #8333, #8334 and #9814. In particular, you first need to apply
from those tickets.
On the other hand, it also addresses the speed issues in #9885, #9884, #9883 and #9882. It should also fix #9886: the timings indicate that
ZZ.convert_map_from(R)
is getting called each time, rather than the morphism being found in theconvert_from_hash,
and I don't know why this would be the case.