Path: ...!3.eu.feeder.erje.net!feeder.erje.net!news.in-chemnitz.de!news.swapon.de!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: David De La Harpe Golden <david@harpegolden.net>
Newsgroups: comp.lang.lisp
Subject: Re: Optimization flag for unchecked fixnums in SBCL?
Date: Thu, 8 Aug 2024 15:47:53 +0100
Organization: A noiseless patient Spider
Lines: 159
Message-ID: <v92lqq$2077$1@dont-email.me>
References: <87h6bwrufd.fsf@nightsong.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 08 Aug 2024 16:47:54 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f955f2f0b6cc7aa322adcfae2729160c";
	logging-data="65767"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19ShjvAYMdgJZSz0Zs38vze8vtxCKr9T2z6MRKPLeghgw=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:pQAw6Ul7eamUNpbU9PbQgvF9HTs=
In-Reply-To: <87h6bwrufd.fsf@nightsong.com>
Content-Language: en-US
Bytes: 6904

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