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)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 8/7/2024 1:42 PM, Paul Rubin wrote:

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)

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.
--
Jeff Barnett

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 2024-08-08, Jeff Barnett <jbb@notatt.com> wrote:

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

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 8/8/2024 1:19 PM, Kaz Kylheku wrote:

On 2024-08-08, Jeff Barnett <jbb@notatt.com> wrote:

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.
--
Jeff Barnett

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Jeff Barnett <jbb@notatt.com> writes:

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.

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On 10/08/2024 04:00, Paul Rubin wrote:

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)

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

steve g <sgonedes1977@gmail.com> writes:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)