Optimization flag for unchecked fixnums in SBCL?

[Paul Rubin]

I looked in the manual and didn't see a way to do this. The following
Haskell code (Euler problem 14) takes about 0.5 seconds on my old laptop:

cl :: Int -> Int
cl n = if odd n then 3*n+1 else n`quot`2
dl n = (1+) . length . takeWhile (/= 1) . iterate cl $ n
main = print . maximum $ [(dl n, n) | n <- [1..1000000]]

Int is Haskell's built-in fixnum type. Integer is bignums and that
version takes about 7 seconds.

The below CL version takes 5 seconds (this is chopped down from a
memoized version that takes about 0.2 seconds). I tried a few different
ways to tell the compiler that `collatz' should take and return fixnums,
but I didn't find the right way. Any help? Thanks.

(defun collatz (n)
(cond ((oddp n) (1+ (* 3 n)))
(t (floor n 2))))

(defun clen (n)
(cond ((= n 1) 1)
((<= n 0) 'crash)
(t (1+ (clen (collatz n))))))

(defun run (&optional (n 1) (mi 0) (ma 0))
(if (> n 1000000)
(list mi ma)
(let ((a (clen n))
(nn (1+ n)))
(if (> a ma)
(run nn n a)
(run nn mi ma)))))
(print (run))
(terpri)

[Jeff Barnett]

Post by Paul Rubin
I looked in the manual and didn't see a way to do this. The following
cl :: Int -> Int
cl n = if odd n then 3*n+1 else n`quot`2
dl n = (1+) . length . takeWhile (/= 1) . iterate cl $ n
main = print . maximum $ [(dl n, n) | n <- [1..1000000]]
Int is Haskell's built-in fixnum type. Integer is bignums and that
version takes about 7 seconds.
The below CL version takes 5 seconds (this is chopped down from a
memoized version that takes about 0.2 seconds). I tried a few different
ways to tell the compiler that `collatz' should take and return fixnums,
but I didn't find the right way. Any help? Thanks.
(defun collatz (n)
(cond ((oddp n) (1+ (* 3 n)))
(t (floor n 2))))
(defun clen (n)
(cond ((= n 1) 1)
((<= n 0) 'crash)
(t (1+ (clen (collatz n))))))
(defun run (&optional (n 1) (mi 0) (ma 0))
(if (> n 1000000)
(list mi ma)
(let ((a (clen n))
(nn (1+ n)))
(if (> a ma)
(run nn n a)
(run nn mi ma)))))
(print (run))
(terpri)

As a start, did you you try defining collatz and clen with defsubst? Did
you try using declarations and their cousins? And did your CL system
provide a decent, declaration-sensitive compiler?

In other words I'm not sure how and what you told the compiler or what
compiler you were telling. What I recall about this muddle is that what
a compiler (and system) did with declaration type things was highly
implementation dependent so wouldn't be quite sure what to advise you.

Other than use defsubst. That should open code most anything in most any
CL compiler-based system.

[Kaz Kylheku]

Post by Jeff Barnett
As a start, did you you try defining collatz and clen with defsubst? Did
you try using declarations and their cousins? And did your CL system
provide a decent, declaration-sensitive compiler?

defsubst is some Emacs Lisp thing for inline functions.

In Common Lisp, it's (declaim (inline ...)).

[Jeff Barnett]

Post by Kaz Kylheku

Post by Jeff Barnett
As a start, did you you try defining collatz and clen with defsubst? Did
you try using declarations and their cousins? And did your CL system
provide a decent, declaration-sensitive compiler?

defsubst is some Emacs Lisp thing for inline functions.
In Common Lisp, it's (declaim (inline ...)).

I thought that defsubst was in both the Symbolics' implementation of CL
and Allegro's. It's been a while so I might have misremembered. Thanks
for correction.

[Paul Rubin]

Post by Jeff Barnett
As a start, did you you try defining collatz and clen with defsubst?
Did you try using declarations and their cousins? And did your CL
system provide a decent, declaration-sensitive compiler?

I didn't try defsubst. I did try some declarations but didn't get them
to work. I think that means I didn't use them properly, rather than
that they don't work. Yes, SBCL is a serious optimizing compiler. If
not the premier compiler, it is one of them.

Post by Jeff Barnett
Other than use defsubst. That should open code most anything in most
any CL compiler-based system.

I think the issue is not funcall overhead, but rather, the slowness of
bignum arithmetic compared to just hoping that everything fits in a
fixnum. The "trick" of this Euler problem is that a few (only a few) of
the intermediate values will overflow a 32 bit word. But, everyone uses
64 bit machines these days, so that part works anyway.

[David De La Harpe Golden]

Post by Paul Rubin
The "trick" of this Euler problem is that a few (only a few) of
the intermediate values will overflow a 32 bit word. But, everyone uses
64 bit machines these days, so that part works anyway.

Ah, good point. (erm, last (signed-byte 29) part my prev post probably
only worked because - at (safety 0) - it was indeed generating code
using unchecked >32-bit signed arithmetic ops on my 64-bit machine anyway)

Worth noting in context that if you use sbcl with (safety 3) ON and use
(signed-byte 32) say, though, then the type-declarations-as-assertions
nicely catches the problem (at runtime with dynamic check)

$ head -n2 collatz-signed-byte-32-inline-safe.lisp
(declaim (optimize (speed 0) (safety 3) (debug 3)))
(declaim (ftype (function ((signed-byte 32)) (values (signed-byte
32) &optional)) collatz))


$ sbcl --control-stack-size 1024 --dynamic-space-size 65536
* (compile-file "collatz-signed-byte-32-inline-safe.lisp")
[...]
* (load "collatz-signed-byte-32-inline-safe.fasl")

debugger invoked on a TYPE-ERROR @535D60FF in thread
#<THREAD "main thread" RUNNING {1001348003}>:
The value
2482111348
is not of type
(SIGNED-BYTE 32)
from the function type declaration.

Type HELP for debugger help, or (SB-EXT:EXIT) to exit from SBCL.

restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.

(COLLATZ 827370449)


Playing about for n 1000000, apparently (signed-byte 37) enough...


$ sbcl --control-stack-size 2048 --dynamic-space-size 65536
--script collatz-signed-byte-36-inline-safe.lisp
Unhandled TYPE-ERROR in thread #<SB-THREAD:THREAD "main thread" RUNNING
{1001348003}>:
The value
34988856874
is not of type
(SIGNED-BYTE 36)
from the function type declaration.
[...]


$ sbcl --control-stack-size 2048 --dynamic-space-size 65536
--script collatz-signed-byte-37-inline-safe.lisp

(837799 525)

[David De La Harpe Golden]

Post by Paul Rubin
The below CL version takes 5 seconds (this is chopped down from a
memoized version that takes about 0.2 seconds). I tried a few different
ways to tell the compiler that `collatz' should take and return fixnums,
but I didn't find the right way. Any help? Thanks.

Perhaps showing what you tried would have been good, but see link [1]
below for typical ways to declare types of function arguments anyway.

Also bear in mind safety settings - sbcl trusting type decls to unsafe
levels is at (safety 0), see [2], though do think twice before doing that...

While the Common Lisp HyperSpec is a reference specification, it's a
relatively readable one, and documents type specifiers in general, see [3]

Also worth bearing in mind the SBCL originally forked from CMUCL with
its declarations-as-assertions, so both SBCL and CMUCL docs may be of
interest (while bearing in mind they're not actually the same lisp impls
or there'd be no point in having both), see [4] - Note per that link you
might favor a more careful integer range type choice over classic fixnum
(a haskell Int is defined as only at least -2^29..2^29-1, see [5], and
there's a (signed-byte 29) possible in lisp...)

(aside: the CMUCL lisp compiler was/is itself called Python, entirely
coincidentally - rather before the popular language of the same name,
somethign to bear in mind when reading SBCL and CMUCL docs)

with your code, with debian packaged sbcl 2.2.9:

$ time (for i in {1..100}; do sbcl --script collatz.lisp >/dev/null
; done)

real 3m35.656s
user 3m34.878s
sys 0m0.715s


add some declarations at the top - more adjustments to decls and code in
general may well be possible in this case, but this is an example.
This post is not intended as some exhaustive examination of possible
optimizations.

$ head -n3 collatz-fixnum-noopt.lisp
(declaim (ftype (function (fixnum) fixnum) collatz))
(declaim (ftype (function (fixnum) (or fixnum symbol)) clen))
(declaim (ftype (function (&optional fixnum fixnum fixnum) list) run))

$ time (for i in {1..100}; do sbcl --script
collatz-fixnum-noopt.lisp >/dev/null ; done)

real 1m46.481s
user 1m45.735s
sys 0m0.695s


*** Unsafe optimizations are, well, unsafe, but measurably faster in
this case. DON'T be too hasty to do such things, though, the gain may
not be as much as you think for throwing away safety - a dynamic check
can allow a good compiler to assume things are already checked /
specialized further "down" ***

$ head -n4 collatz-fixnum-unsafeopt.lisp
(declaim (optimize (speed 3) (safety 0) (debug 0)))
(declaim (ftype (function (fixnum) fixnum) collatz))
(declaim (ftype (function (fixnum) (or fixnum symbol)) clen))
(declaim (ftype (function (&optional fixnum fixnum fixnum) list) run))

$ time (for i in {1..100}; do sbcl --script
collatz-fixnum-unsafeopt.lisp >/dev/null ; done)

real 1m19.539s
user 1m18.873s
sys 0m0.636s


Another poster mentioned defsubst, but while no doubt possibly still
present in some Common Lisp impls, that's more likely to be seen in
Emacs Lisp code these days. You can declare functions inline in a CL
way, see [6] for sbcl though.

$ head -n6 collatz-fixnum-inline-unsafeopt.lisp
(declaim (optimize (speed 3) (safety 0) (debug 0)))
(declaim (ftype (function (fixnum) fixnum) collatz))
(declaim (ftype (function (fixnum) (or fixnum symbol)) clen))
(declaim (ftype (function (&optional fixnum fixnum fixnum) list) run))
(declaim (inline collatz))
(declaim (inline clen))

$ time (for i in {1..100}; do sbcl --script
collatz-fixnum-inline-unsafeopt.lisp >/dev/null ; done)

real 1m2.662s
user 0m58.448s
sys 0m4.174s


using (signed-byte 29) over fixnum in obvious fashion - and all prior
decls - apparently actually faster, if only slightly (fixnum is 2^62
range on 64-bit x86-64 sbcl, various ops on two fixnums won't always
result in a fixnum)

$ time (for i in {1..100}; do sbcl --script
collatz-signed-byte-29-inline-unsafeopt.lisp >/dev/null ; done)

real 0m58.247s
user 0m53.990s
sys 0m4.209s



Running with an outer bash shell time around it like the above of course
includes entire sbcl script mode startup overhead over and over again
though, mind...

At the SBCL REPL you can (compile-file "file.lisp") and read compiler
messages that may indicate further opportunities for changes, and load
the file and e.g. (disassemble #'collatz) etc. to see what native code
the compiler generated, can also help see where further declarations may
be useful.


$ sbcl

* (compile-file "collatz-signed-byte-29-inline-unsafeopt.lisp")

[... some messages ...]

* (load "collatz-signed-byte-29-inline-unsafeopt.fasl")

(837799 525)
T

* (time (dotimes (i 100) (run)))
Evaluation took:
22.592 seconds of real time
22.588946 seconds of total run time (22.588519 user, 0.000427 system)
99.99% CPU
87,953,286,681 processor cycles
0 bytes consed




links:

[1]
lispcookbook.github.io/cl-cookbook/type.html#declaring-the-input-and-output-types-of-functions

[2] www.sbcl.org/manual/#Declarations-as-Assertions

[3] www.lispworks.com/documentation/HyperSpec/Body/04_bc.htm

[4] cmucl.org/docs/cmu-user/html/Fixnums.html

[5]
stackoverflow.com/questions/73106581/why-is-the-standard-guaranteed-range-for-int-in-haskell-exactly-229-229

[6] www.lispworks.com/documentation/HyperSpec/Body/d_inline.htm#inline

[steve g]

Post by Paul Rubin
I looked in the manual and didn't see a way to do this. The following
cl :: Int -> Int
cl n = if odd n then 3*n+1 else n`quot`2
dl n = (1+) . length . takeWhile (/= 1) . iterate cl $ n
main = print . maximum $ [(dl n, n) | n <- [1..1000000]]
Int is Haskell's built-in fixnum type. Integer is bignums and that
version takes about 7 seconds.
The below CL version takes 5 seconds (this is chopped down from a
memoized version that takes about 0.2 seconds). I tried a few different
ways to tell the compiler that `collatz' should take and return fixnums,
but I didn't find the right way. Any help? Thanks.
(defun collatz (n)
(cond ((oddp n) (1+ (* 3 n)))
(t (floor n 2))))
(defun clen (n)
(cond ((= n 1) 1)
((<= n 0) 'crash)
(t (1+ (clen (collatz n))))))
(defun run (&optional (n 1) (mi 0) (ma 0))
(if (> n 1000000)
(list mi ma)
(let ((a (clen n))
(nn (1+ n)))
(if (> a ma)
(run nn n a)
(run nn mi ma)))))
(print (run))
(terpri)

I don't understand the math but here is a quick change that shaves it
down some.

CL-USER> (time (run))
Evaluation took:
2.054 seconds of real time
2.052833 seconds of total run time (2.052229 user, 0.000604 system)
99.95% CPU
4,733,868,882 processor cycles
0 bytes consed

(837799 525)

WARNING: redefining COMMON-LISP-USER::COLLATZ in DEFUN
COLLATZ
CL-USER> (compile 'collatz)
COLLATZ
NIL
NIL
CL-USER> (time (run))
Evaluation took:
1.626 seconds of real time
1.625390 seconds of total run time (1.625332 user, 0.000058 system)
99.94% CPU
3,748,148,144 processor cycles
0 bytes consed

(837799 525)
CL-USER>


Here is an assist. you are getting killed with clen. i don't understand
the math well; but this should help.

(defun collatz (n)
;; declare the type N to number
(declare (type number n)
(optimize (speed 3) (space 0) (safety 0)))
;; this ensures N is < 32-bits wide and zeros out the rest of the bits.
(setq n (mask-field (byte 32 0) n))
;; the compiler can assume N has enough space for simple arithmetic as
;; opposed to generic functions.
(cond ((oddp n)
(1+ (* 3 n)))
(t
;; this will ensure that only one value is returned from floor.
;; Normally floor returns 2 values - here we tell the compiler that
;; we only want the first value.
(nth-value 0 (floor n 2)))))


your problem with clen is the generic+ at the end of your cond
statement. I'm going to try this in C. What haskell compiler do you use?

anyway this should help (i think).

[Paul Rubin]

Post by steve g
your problem with clen is the generic+ at the end of your cond
statement. I'm going to try this in C. What haskell compiler do you use?

Currently ghc 8.8.4 which is kind of old. I could try with a newer
compiler. I have a C++ version that is drastically faster but has
memoization. The maybe weird-looking recursive implementation of clen
in the Lisp version lingers from ripping out the memoization from an
earlier version that I posted. I guess I could fix it to be tail
recursive if that sounds likely to help.

For specification of the problem, see:

https://projecteuler.net/problem=14

Thanks, and also the same to David De La Harpe Golden, for help with
these declarations.