Opened 9 years ago
Closed 8 years ago
#12615 closed enhancement (fixed)
sign(integer) is horribly slow
Reported by: | zimmerma | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-5.7 |
Component: | basic arithmetic | Keywords: | |
Cc: | jpflori, was, kcrisman, robertwb | Merged in: | sage-5.7.beta1 |
Authors: | Robert Bradshaw | Reviewers: | Paul Zimmermann |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Noticed in Sage 4.8:
sage: a=-17 sage: %timeit s = sign(a) 125 loops, best of 3: 757 µs per loop sage: %timeit s = a//abs(a) 625 loops, best of 3: 246 ns per loop
thus computing sign(a)
with a//abs(a)
is 3000 faster!!!
Attachments (1)
Change History (19)
comment:1 Changed 9 years ago by
- Cc kcrisman added
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
Try it out and see what the speedup is. I'd be happy to review something like that.
comment:4 Changed 9 years ago by
Hmmm. Well, it helps, but you still lose a lot going from something(sign) to sign(something):
# unpatched sage: %timeit s = sign(2) 5 loops, best of 3: 427 µs per loop
# with .sign() using mpz_sgn sage: %timeit s = sign(2) 625 loops, best of 3: 47.4 µs per loop sage: %timeit s = 2.sign() 625 loops, best of 3: 352 ns per loop
Function calls are slow. :-/
comment:5 Changed 9 years ago by
Well, to be clear, it's not function call overhead itself, it's BuiltinFunction?-related.
comment:6 Changed 9 years ago by
regarding comment 4, I don't understand since for abs
we get similar
timings, and even abs(something) is faster:
sage: %timeit s = abs(2) 625 loops, best of 3: 201 ns per loop sage: %timeit s = 2.abs() 625 loops, best of 3: 456 ns per loop
Paul
comment:8 Changed 8 years ago by
- Status changed from new to needs_review
Attached a patch to add sign() methods to QQ and ZZ. The sign(x) function is still really slow because
sage: sign.__call__?? def __call__(self, *args, coerce=True, hold=False): """ Evaluates this function at the given arguments. We coerce the arguments into symbolic expressions if coerce=True, then call the Pynac evaluation method, which in turn passes the arguments to a custom automatic evaluation method if ``_eval_()`` is defined.
in other words, it creates SR(x) and a ginac representation of the call before finally calling x.sign(). Ugh, I've filed #13933.
comment:9 Changed 8 years ago by
- Status changed from needs_review to needs_info
Robert, thanks, I see a speedup of a factor of more than 10 on my example:
sage: a=-17 sage: %timeit s = sign(a) 625 loops, best of 3: 41 µs per loop sage: %timeit s = a//abs(a) 625 loops, best of 3: 257 ns per loop
However I wonder about the need of the "pool" cache for integers in [-5,100], since the speedup is "only" about 20%:
sage: a=100 sage: %timeit s = sign(a) 625 loops, best of 3: 34.7 µs per loop sage: a=101 sage: %timeit s = sign(a) 625 loops, best of 3: 41.5 µs per loop
Paul
comment:10 follow-up: ↓ 13 Changed 8 years ago by
- Status changed from needs_info to needs_review
Oops, there was an error in this patch. Yeah, the pool doesn't make a big difference here, but it can be used more genrally as well so I think it's worth including.
comment:11 Changed 8 years ago by
I don't think that sign(x) can be made much faster than in #13933 (vs. abs, which is a builtin function), but a.sign() is *much* faster now. It also scales better :)
sage: a = 3^2^20 sage: %timeit a//abs(a) 625 loops, best of 3: 129 µs per loop
comment:12 Changed 8 years ago by
- Reviewers set to Paul Zimmermann
- Status changed from needs_review to positive_review
good work, thanks Robert!
Paul
comment:13 in reply to: ↑ 10 ; follow-up: ↓ 14 Changed 8 years ago by
- Status changed from positive_review to needs_work
Replying to robertwb:
Yeah, the pool doesn't make a big difference here, but it can be used more genrally as well so I think it's worth including.
Sorry, but allocating 103 integers just because somebody might possibly write a patch in the future to use them is silly. For this patch, could we stick just with the integers that we actually use? Your hypothetical futute patch can still enlarge the pool.
comment:14 in reply to: ↑ 13 Changed 8 years ago by
- Status changed from needs_work to needs_review
Replying to jdemeyer:
Replying to robertwb:
Yeah, the pool doesn't make a big difference here, but it can be used more genrally as well so I think it's worth including.
Sorry, but allocating 103 integers just because somebody might possibly write a patch in the future to use them is silly. For this patch, could we stick just with the integers that we actually use? Your hypothetical futute patch can still enlarge the pool.
Done.
comment:15 Changed 8 years ago by
See also #13981
comment:16 Changed 8 years ago by
- Status changed from needs_review to positive_review
thank you Robert for the new patch.
Paul
comment:17 Changed 8 years ago by
- Milestone changed from sage-5.6 to sage-5.7
comment:18 Changed 8 years ago by
- Merged in set to sage-5.7.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
The fall-through into constructing a ComplexIntervalField? is expensive. Maybe it makes sense to give the obvious suspects (ZZ, QQ, RR, etc.) a .sign() method.