3 ms·
> Is SWI-Prolog really faster than CLisp? Naive Fibonacci isn't exactly representative. Especially not if you mess up the implementation: As given, the Lisp ve
by tom_mellior 9y ago
> Is SWI-Prolog really faster than CLisp?
Naive Fibonacci isn't exactly representative. Especially not if you mess up the implementation: As given, the Lisp version
(defun fib (n) (if (<= (1- n) 0) n (the fixnum (+ (fib (- n 1)) (fib (- n 2))))))
computes 39088169 for (fib 38) (on my machine, in 64 seconds in CLisp), whereas the hand-written Prolog version computes 63245986. Oops. Changing the Lisp version to a version equivalent to the Prolog version:
(defun fib (n) (if (<= n 1) 1 (the fixnum (+ (fib (- n 1)) (fib (- n 2))))))
computes the correct result. With this I get:
[3]> (time (fib 38))
Real time: 59.298958 sec.
Run time: 59.3 sec.
Space: 1011935760 Bytes
GC: 1157, GC time: 1.168 sec.
63245986
And on SWI-Prolog:
?- time(fibp2(38, O)).
% 379,475,913 inferences, 20.021 CPU in 20.022 seconds (100% CPU, 18953864 Lips)
O = 63245986.
?- statistics.
% [...]
% 33,858 garbage collections gained 2,529,839,696 bytes in 0.851 seconds.
Both allocate a whole lot of memory but (if the numbers are to be trusted) GC is not the reason CLisp is so much slower. All the numbers involved here fit well into SWI's range for tagged integers, so arithmetic on them should be pretty efficient.
EDIT: You can further improve the CLisp version by removing the THE which was presumably meant to aid optimization, but apparently didn't:
[1]> (defun fib (n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))
FIB
[2]> (time (fib 38))
Real time: 42.21966 sec.
Run time: 42.216 sec.
Space: 0 Bytes
63245986
That's more like it... (With the author's DECLAIM flags for maximum speed, I get a further improvement of about 2 seconds, to 40 seconds. Launching SWI-Prolog with -O, though, improves it in turn to 10 seconds, with only 1 GB allocated instead of 2.5. Benchmarking is fun!)
- lispm 9y agoIn the range of available Lisp implementations, CLisp not really the speed demon. on my 1.2Ghz Core Macbook: SBCL * (time (fib 38)) Evaluation took: 1.640 seconds of real time 1.635822 seconds of total run time (1.631918 user, 0.003904 system) 99.76% CPU 1,968,285,540 processor cycles 0 bytes consed LispWorks CL-USER 6 > (time (fib 38)) Timing the evaluation of (FIB 38) User time = 0.567 System time = 0.002 Elapsed time = 0.554 Allocation = 136848 bytes 29 Page faults 63245986
- kazinator 9y agoCLISP doesn't compile functions input at the REPL or loaded from source files with LOAD. If you don't do (compile 'fib), you're testing AST interpretation, not byte code.
- tom_mellior 9y agoHa, excellent point. Thanks.
- tom_mellior 9y agoOK, so now we are ready to answer the great-great-grandparent's question: > Is SWI-Prolog really faster than CLisp? No. At least not on naive Fibonacci. [1]> (defun fib (n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))))) FIB [2]> (compile 'fib) FIB ; NIL ; NIL [3]> (time (fib 38)) Real time: 6.730412 sec. Run time: 6.732 sec. Space: 0 Bytes 63245986 The project's GitHub page makes pretty much all the mistakes you can make when benchmarking: Comparing programs that are not equivalent and with wildly uncomparable optimization settings. There is an almost incomprehensible blurb at the end of https://github.com/TeamSPoon/wam_common_lisp https://github.com/TeamSPoon/wam_common_lisp that (I think) tries to argue that you should not turn on optimization in Lisp because it costs more than you gain. I disagree.
- zmonx 9y agoThank you for these benchmarks! For a fair comparison, one should however also take into account that SWI-Prolog is among the slower Prolog systems. I therefore recommend to also use a faster Prolog system. For example, I used the following Prolog translation of your code and ran it in GNU Prolog: n_fib(N0, F) :- ( N0 =< 1 -> F = 1 ; N1 is N0 - 1, N2 is N0 - 2, n_fib(N1, F1), n_fib(N2, F2), F is F1 + F2 ). On my machine configuration, GNU Prolog is more than thrice as fast as SWI-Prolog (even with -O) for: | ?- n_fib(38, F). F = 63245986 GNU Prolog in fact compiles to native code. You can test this by putting the code into a file, say fib.pl, and compiling it with the GNU Prolog compiler using: $ gplc fib.pl You can then run it with ./fib and invoke the above query.