Re: Optimization flag for unchecked fixnums in SBCL?

On 07/08/2024 20:42, Paul Rubin wrote:
 > 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