Opened 10 years ago
Closed 10 years ago
#6118 closed defect (fixed)
[with (new) second patch, positive review] integer shifting slow
Reported by: | robertwb | Owned by: | somebody |
---|---|---|---|
Priority: | major | Milestone: | sage-4.2 |
Component: | basic arithmetic | Keywords: | |
Cc: | Merged in: | sage-4.2.alpha0 | |
Authors: | Robert Bradshaw, Craig Citro | Reviewers: | Mike Hansen, Craig Citro |
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Attachments (2)
Change History (15)
Changed 10 years ago by
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
- Summary changed from integer shifting slow to [with patch, needs review] integer shifting slow
comment:3 Changed 10 years ago by
Thumbs up from me. The patch successfully applied to my 4.0 install and the tests in integer.pyx pass.
This patch is important for mpmath performance (#6196). Time for sage.libs.mpmath.all.runtests() without patch = 63.66 seconds, with patch = 51.88 seconds.
comment:4 Changed 10 years ago by
- Summary changed from [with patch, needs review] integer shifting slow to [with second patch, needs review] integer shifting slow
I'm definitely happy with this patch. As Robert points out in the patch, there are a few inconsistencies in some of the integer.pyx
code -- for instance, there are the incongruously named _lshift
and _rshift_
, which are basically the same and are barely used. I've removed them, cleaned up the bits of code that used them, and made one or two (morally) small changes to Robert's _shift_helper
code, such as some comments and more error checking.
Interestingly, I'm having some funny results using timeit
vs. %timeit
, namely that timeit
tends to be inconsistent on timings this tiny:
sage: a = 123 ; b = 11 sage: timeit("a << b") 625 loops, best of 3: 200 ns per loop sage: timeit("a << b") 625 loops, best of 3: 323 ns per loop sage: timeit("a << b") 625 loops, best of 3: 371 ns per loop sage: timeit("a << b") 625 loops, best of 3: 360 ns per loop sage: timeit("a << b") 625 loops, best of 3: 360 ns per loop sage: timeit("a << b") 625 loops, best of 3: 370 ns per loop sage: timeit("a << b") 625 loops, best of 3: 368 ns per loop sage: timeit("a << b") 625 loops, best of 3: 418 ns per loop
As you can see, it's generally around 368 ns
, but the timings have several outliers. But IPython %timeit
thinks the fast outlier is the correct value!
sage: %timeit a << b 10000000 loops, best of 3: 188 ns per loop sage: %timeit a << b 10000000 loops, best of 3: 187 ns per loop
I tend to trust it, because it's running a ton of loops -- maybe the fact that my computer is doing several things at once is disturbing timeit
?
Anyway, new patch attached. Robert, if you could look over the changes, I'd say this is a positive review. It seems to give me a nominally faster (around 5%
) timing than the previous version, but that's probably just my computer being weird.
comment:5 Changed 10 years ago by
I just realized this touched integer.pxd, so some comments first. We care about shifting by ints a lot because library code (especially mpmath) does a lot of stuff like "x << 1". I think the patch may make that path slower. Also, the error checking and cpdefing may make it slower too (I'll test, might be negligible).
Also, why do
if n < 0: n *= -1 sign *= -1
rather than
n *= sign
comment:6 Changed 10 years ago by
Here's after just the first patch:
sage: a = 5; b = 6; c = 6r sage: %timeit a << b 10000000 loops, best of 3: 195 ns per loop sage: %timeit a >> b 1000000 loops, best of 3: 218 ns per loop sage: %timeit a << c 10000000 loops, best of 3: 188 ns per loop sage: %timeit a >> c 1000000 loops, best of 3: 217 ns per loop sage: b = -6; c = -6r sage: %timeit a << b 1000000 loops, best of 3: 204 ns per loop sage: %timeit a >> b 10000000 loops, best of 3: 196 ns per loop sage: %timeit a >> c 10000000 loops, best of 3: 190 ns per loop sage: %timeit a << c 1000000 loops, best of 3: 222 ns per loop
and after the second patch
sage: sage: a = 5; b = 6; c = 6r sage: sage: %timeit a << b 1000000 loops, best of 3: 192 ns per loop sage: sage: %timeit a >> b 1000000 loops, best of 3: 204 ns per loop sage: sage: %timeit a << c 1000000 loops, best of 3: 203 ns per loop sage: sage: %timeit a >> c 1000000 loops, best of 3: 217 ns per loop sage: sage: sage: b = -6; c = -6r sage: sage: %timeit a << b 1000000 loops, best of 3: 206 ns per loop sage: sage: %timeit a >> b 1000000 loops, best of 3: 197 ns per loop sage: sage: %timeit a >> c 1000000 loops, best of 3: 203 ns per loop sage: sage: %timeit a << c 1000000 loops, best of 3: 222 ns per loop
With repeated timings, the variance seems to be about 5 or so ns. The only significant differences are that Integer >> Integer is a bit faster with the second patch, and Integer << int and Integer >> int are faster with the first.
I'm (pleasantly) surprised making it a cpdef function didn't slow it down. I don't think shift_helper
needs to do error checking, and it seems odd to introduce a new auxiliary variable normalize_Integer
.
Changed 10 years ago by
comment:7 Changed 10 years ago by
- Summary changed from [with second patch, needs review] integer shifting slow to [with (new) second patch, needs review] integer shifting slow
I've added a new version of the second patch, which mostly just adds comments and removes the inconsistencies with things like _lshift
and _rshift_
.
In particular, I've come around to Robert's point that we want to speed up the Integer << int
and Integer >> int
cases the most -- I just did a search_src('>>')
, and there seems to be a lot of code that shifts by literals (which will be Python int
s). I also removed the one extra error check in _shift_helper
and made a note about it.
One last question, though -- do we really need the case where y = ZZ(y)
raises a ValueError
? Looking at the Integer
constructor, this seems to only happen when we're given a string in a base larger than 36; in this case, the code in the except
clause won't work, anyway. So are there other cases where this is used that I'm not thinking of? (It's obviously not too important, but I'm curious.)
comment:8 Changed 10 years ago by
- Reviewers set to Mike Hansen, Craig Citro
- Summary changed from [with (new) second patch, needs review] integer shifting slow to [with (new) second patch, positive review] integer shifting slow
I think that Craig's patch looks good, and his question shouldn't really hold this up. I'll open a new ticket for that so that these can go in.
comment:9 Changed 10 years ago by
- Summary changed from [with (new) second patch, positive review] integer shifting slow to [with (new) second patch, needs rebase] integer shifting slow
I got some hunk failures when applying trac-6118-pt2.patch
:
[mvngu@sage sage-main]$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/6118/trac-6118-pt2.patch && hg qpush adding trac-6118-pt2.patch to series file applying trac-6118-pt2.patch patching file sage/rings/integer.pxd Hunk #1 FAILED at 15 1 out of 1 hunks FAILED -- saving rejects to file sage/rings/integer.pxd.rej patching file sage/rings/integer.pyx Hunk #1 FAILED at 4363 Hunk #2 FAILED at 4405 Hunk #3 FAILED at 4417 Hunk #4 FAILED at 4434 Hunk #5 FAILED at 4443 5 out of 5 hunks FAILED -- saving rejects to file sage/rings/integer.pyx.rej patch failed, unable to continue (try -v) patch failed, rejects left in working dir Errors during apply, please fix and refresh trac-6118-pt2.patch
This needs a rebase against Sage 4.1.2.alpha1 or a later version.
comment:10 Changed 10 years ago by
Minh, were you applying both patches? The second applies on top of the first.
comment:11 Changed 10 years ago by
mhansen -- what's up? a bunch of us are at the HUB working on Sage...
comment:12 Changed 10 years ago by
- Summary changed from [with (new) second patch, needs rebase] integer shifting slow to [with (new) second patch, positive review] integer shifting slow
Both patches should be applied -- not just the last one.
comment:13 Changed 10 years ago by
- Merged in set to sage-4.2.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
Before
After