## Optimizing speed and fixnum literal

Discussion of Common Lisp

### Optimizing speed and fixnum literal

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

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))`

Kompottkin

Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany

### Re: Optimizing speed and fixnum literal

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

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

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

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.

Kompottkin

Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany

### Re: Optimizing speed and fixnum literal

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

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