@simon_brooke @vashti Only if it doesn’t also need to be fast.
Discussion
Loading...
Post
@alwayscurious @vashti define fast. I can compute the factorial of 1,000 in under one millisecond on an ordinary laptop in several different #Lisp dialects, without optimisation.
Is that not fast enough for you?
https://gist.github.com/simon-brooke/fcb59705950c5ad515e18fba065510ae
Agreed. #CommonLisp on Android ( #cl_repl) is capable and plenty fast enough on a Pixel 8a running your factorial code. 😎
You can make CL faster than the C/C++ used by NumPy: https://stewart123579.github.io/blog/posts/code/calculating-a-dot-product/#python-vs-dot-r-vs-dot-lisp-timing
![Partial screenshot with the following text:
QML-USER [1]
(defun fact (n) "Compute the factorial o...
real time : 0.000 secs
run time : 0.000 secs
gc count : 1 times
consed : 654512 bytes](https://cdn.fosstodon.org/media_attachments/files/115/771/823/878/357/887/original/3374a426f3cc16d6.png)
@svw @alwayscurious @vashti from the cons space usage I'm guessing that was the recursive algorithm? If so, the more impressive. Small #Lisp imlementations tend not to have dynamic stack. But allocating and deallocating stack frames on a dynamic stack is a time cost.
@svw
Sorry, could you time the
(mytime naïve-dot-v2 "naïve loop v2"
(loop for x across aa
for y across ab
summing (* x y)))
idiom instead?
Thinking about it, I'm not sure how to write DO for this. I have been interested in DO recently.
@simon_brooke @alwayscurious @vashti
@screwlisp Right, what arguments do you want me to test?
@simon_brooke could you do something comparable to svw. but with
(loop for x fixnum across arrayx for y fixnum across arrayy summing (* x y) into z fixnum finally (return z))
and
(do ((x (pop listx) (pop listx)) (y (pop listy) (pop listy)) (z 0))
((null listx) (incf z (* x y)))
(declare (fixnum x y z))
(incf z (* x y)))
which are my swing at fast forms closely analogous to svw's fast lisp blogging. I'm also interested in how similar performance gains and losses are between lisps.
@screwlisp aye, but arguments! What arguments to these functions would it be useful to you for me to test?
~12 more replies (not shown)
@simon_brooke svw above was using
(loop for i below 10000000 collect (random 1.0))
. I used a much smaller example on my old computing laptop. If my use of pop is a better operation than loop for .. in, I guess the larger the example the better the pop one would seem. So I am not really sure what values to choose, other than using the same one on the same machine.
How did you choose 1000 for your factorial benchmarks?
@screwlisp on the Xerox 1108 (Interlisp-D) on which I was first able to compute (recursively) bignum factorials, factorial 1000 took just over twenty minutes. I therefore didn't even think of trying to compute anything larger. It's been my standard benchmark of Lisp stack performance ever since!
My Acorn A440, in 1987, could do it in 4 seconds (Cambridge Lisp); a TI Explorer I tested in 1989 could do it in 0.3 seconds; these days, my laptop can do it in 0.000064 seconds of wall clock time.
@screwlisp there's a lot to like about the Interlisp spaghetti stack — it seems to me the most natural native multi-tasking implementation in Lisp I've seen, at least until #Clojure — but it was not fast!
@screwlisp (TI Explorer was running Common Lisp, but I don't know whose; on my laptop I was using SBCL)
@screwlisp OK, get this:
CL-USER[10]: (time (fact 10000))
Evaluation took:
0.008 seconds of real time
0.010394 seconds of total run time (0.010327 user, 0.000067 system)
[ Real times consist of 0.004 seconds GC time, and 0.004 seconds non-GC time. ]
125.00% CPU
36,355,445 processor cycles
69,741,184 bytes consed
For reality check, there are fewer than 1*10^82 atoms in the observable universe; factorial of 10,000 is larger than 1*10^35,660.
These are BIG numbers.
@screwlisp (fact 100000) blows the stack on SBCL in its standard configuration. Whether it's possible to configure SBCL to handle a larger stack I don't know. But the fact that we can compute (and compute with) numbers of the magnitude of 10,000! just blows my mind.
Computers have come such a LONG WAY in my lifetime.
@simon_brooke now the differences between
(declaim (optimize speed))
(defun fact (n)
"Compute the factorial of `n`, expected to be a natural number."
(cond ((= n 1) 1)
(t (* n (fact (- n 1))))))
(defun dofact (n)
(do
((result 1 (* result n))
(n n (- n 1)))
((= n 1) result)))
(prog1 nil
(time (fact 1000))
(time (dofact 1000)))
are eating at me actually.
@svw
Though, based on my laptop,
(defun doot2 (a b)
(do ((z 0)
(x (pop a) (pop a))
(y (pop b) (pop b)))
((null a) (incf z (* x y)))
(declare (fixnum x y z))
(incf z (* x y))))
consistently beats
(defun loopdot (a b)
(loop :for x fixnum :in a
:for y fixnum :in b
:summing (* x y) :into z fixnum
:finally (return z)))
@simon_brooke @alwayscurious @vashti
@alwayscurious @vashti however, I'm grateful to you for raising that issue, because it prompted me to find out how fast it would run in Portable Standard #Lisp, so I've spent a happy couple of hours trying to debug bootstrapping problems in Blake McBride's version of the PSL compiler. I don't have it working yet, but I have made progress. Will it be faster than SBCL? Don't know, but I suspect so.
BT Free Social
BT Free is a non-profit organization founded by @ozoned@btfree.social . It's goal is for digital privacy rights, advocacy and consulting. This goal will be attained by hosting open platforms to allow others to seamlessly join the Fediverse on moderated instances or by helping others join the Fediverse.
Automatic federation enabled