Opened 11 years ago

Closed 10 years ago

#12615 closed enhancement (fixed)

sign(integer) is horribly slow

Reported by: Paul Zimmermann Owned by: Alex Ghitza
Priority: major Milestone: sage-5.7
Component: basic arithmetic Keywords:
Cc: Jean-Pierre Flori, William Stein, Karl-Dieter Crisman, Robert Bradshaw Merged in: sage-5.7.beta1
Authors: Robert Bradshaw Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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)

12615-slow-sign.v3.patch (2.5 KB) - added by Robert Bradshaw 10 years ago.
apply only this patch

Download all attachments as: .zip

Change History (19)

comment:1 Changed 11 years ago by Karl-Dieter Crisman

Cc: Karl-Dieter Crisman added

comment:2 Changed 11 years ago by D.S. McNeil

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.

comment:3 Changed 11 years ago by Karl-Dieter Crisman

Try it out and see what the speedup is. I'd be happy to review something like that.

comment:4 Changed 11 years ago by D.S. McNeil

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 11 years ago by D.S. McNeil

Well, to be clear, it's not function call overhead itself, it's BuiltinFunction?-related.

comment:6 Changed 11 years ago by Paul Zimmermann

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:7 Changed 10 years ago by Paul Zimmermann

Cc: Robert Bradshaw added

Robert, do you have a hint to solve this?

Paul

comment:8 Changed 10 years ago by Robert Bradshaw

Status: newneeds_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 10 years ago by Paul Zimmermann

Status: needs_reviewneeds_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 Changed 10 years ago by Robert Bradshaw

Status: needs_infoneeds_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 10 years ago by Robert Bradshaw

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 10 years ago by Paul Zimmermann

Authors: Robert Bradshaw
Reviewers: Paul Zimmermann
Status: needs_reviewpositive_review

good work, thanks Robert!

Paul

comment:13 in reply to:  10 ; Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_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.

Changed 10 years ago by Robert Bradshaw

Attachment: 12615-slow-sign.v3.patch added

apply only this patch

comment:14 in reply to:  13 Changed 10 years ago by Robert Bradshaw

Status: needs_workneeds_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 10 years ago by Robert Bradshaw

See also #13981

comment:16 Changed 10 years ago by Paul Zimmermann

Status: needs_reviewpositive_review

thank you Robert for the new patch.

Paul

comment:17 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-5.6sage-5.7

comment:18 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.7.beta1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.