Optimizing speed and fixnum literal

Discussion of Common Lisp

Optimizing speed and fixnum literal

Postby enderw88@gmail.com » Thu Feb 23, 2012 3:33 pm

Using sbcl and (optimize (speed 3)... I keep getting compiler notes that a literal integer is an integer not a fixnum so it can't optimize. the offending line is
Code: Select all
 (let* ((b (+ (- (* 3 m) a) c))
and the note is

Code: Select all
; note: forced to do GENERIC-- (cost 10)
;       unable to do inline fixnum arithmetic (cost 2) because:
;       The first argument is a (INTEGER 3 13835058055282163709), not a FIXNUM.
;       The result is a (VALUES
;                        (INTEGER -4611686018427387900 18446744073709551613)
;                        &OPTIONAL), not a (VALUES FIXNUM &REST T).
;       unable to do inline (signed-byte 64) arithmetic (cost 5) because:
;       The first argument is a (INTEGER 3 13835058055282163709), not a (SIGNED-BYTE
;                                                                        64).
;       The result is a (VALUES
;                        (INTEGER -4611686018427387900 18446744073709551613)
;                        &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T).
;       etc.



So how do I specify a fixnum literal?
enderw88@gmail.com
 
Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

Re: Optimizing speed and fixnum literal

Postby Kompottkin » Thu Feb 23, 2012 6:24 pm

The problem is not that the 3 itself, it's that (* 3 m) isn't guaranteed to be a fixnum if m is, because it's thrice as large as m. If you're certain that (* 3 m) will never exceed the fixnum range, you can annotate it by saying (the fixnum (* 3 m)).

Alternatively, you can specify a more restrictive type for m, like (integer -20 20) if that is the range that m is guaranteed to lie within. SBCL is smart enough to figure out that (* 3 m) is still in fixnum range in this case.

The same goes for all arithmetic operations, so if your types aren't restrictive enough, you're probably going to need to type-annotate every single intermediate step of the calculation. Thus,

Code: Select all
(the fixnum (+ (the fixnum (- (the fixnum (* 3 m)) a)) c))
User avatar
Kompottkin
 
Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany

Re: Optimizing speed and fixnum literal

Postby enderw88@gmail.com » Thu Feb 23, 2012 11:00 pm

Cool! Thanks, I didn't know I could do that.
enderw88@gmail.com
 
Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

Re: Optimizing speed and fixnum literal

Postby Ramarren » Fri Feb 24, 2012 12:20 am

Also see SBCLs modular arithmetic. The entry in the manual is I believe out of date, and the capabilities of the compiler in this case are actually greater than described. If you know that the result is going to be a positive fixnum then wrapping the whole computation with (logand most-positive-fixnum ...) often means that an operation can be optimized automatically, as long as it is reducible to addition, subtraction and bitwise operations.

For signed arithmetic this 2009 talk suggests using (sb-c::mask-signed-field (integer-length most-positive-fixnum) ...). I don't know if a more exposed interface has been made available since then (although it seems not), but it seems to compile without optimization notes on my system.
Ramarren
 
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

Re: Optimizing speed and fixnum literal

Postby gugamilare » Fri Feb 24, 2012 5:27 am

Kompottkin wrote:The problem is not that the 3 itself, it's that (* 3 m) isn't guaranteed to be a fixnum if m is, because it's thrice as large as m. If you're certain that (* 3 m) will never exceed the fixnum range, you can annotate it by saying (the fixnum (* 3 m)).


Actually, that is not quite accurate. If M was declared to be a fixnum, SBCL would still be able to optimize the call (* 3 m) (see the note that says that SBCL could optimize it if the first argument to - was a (SIGNED-BYTE 64).
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: Optimizing speed and fixnum literal

Postby Kompottkin » Fri Feb 24, 2012 8:50 am

gugamilare wrote:Actually, that is not quite accurate. If M was declared to be a fixnum, SBCL would still be able to optimize the call (* 3 m) (see the note that says that SBCL could optimize it if the first argument to - was a (SIGNED-BYTE 64).


AFAICT, fixnums are 63 bits wide on AMD64. (The SBCL internals wiki claims otherwise, but on my machine at least, MOST-POSITIVE-FIXNUM is 4611686018427387903, which is 2^62-1.). Thus, (* 3 m) is potentially outside the range of (SIGNED-BYTE 64) even for a fixnum m.

In fact, those messages emitted by SBCL indicate that m was inferred to be a (positive) fixnum.
User avatar
Kompottkin
 
Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany

Re: Optimizing speed and fixnum literal

Postby enderw88@gmail.com » Sat Feb 25, 2012 5:46 am

Ramarren wrote:Also see SBCLs modular arithmetic. The entry in the manual is I believe out of date, and the capabilities of the compiler in this case are actually greater than described. If you know that the result is going to be a positive fixnum then wrapping the whole computation with (logand most-positive-fixnum ...) often means that an operation can be optimized automatically, as long as it is reducible to addition, subtraction and bitwise operations.

For signed arithmetic this 2009 talk suggests using (sb-c::mask-signed-field (integer-length most-positive-fixnum) ...). I don't know if a more exposed interface has been made available since then (although it seems not), but it seems to compile without optimization notes on my system.


Thanks you his was very helpful. The 2009 presentation in particular. I wish the audio of that talk was available.
enderw88@gmail.com
 
Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

Re: Optimizing speed and fixnum literal

Postby gugamilare » Sat Feb 25, 2012 6:26 pm

Kompottkin wrote:AFAICT, fixnums are 63 bits wide on AMD64. (The SBCL internals wiki claims otherwise, but on my machine at least, MOST-POSITIVE-FIXNUM is 4611686018427387903, which is 2^62-1.). Thus, (* 3 m) is potentially outside the range of (SIGNED-BYTE 64) even for a fixnum m.

In fact, those messages emitted by SBCL indicate that m was inferred to be a (positive) fixnum.


Wow, I'm outdated. Last time I checked, fixnums were only 61 bits wide.
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 3 guests