5 ms·

The link to the main github page, for the curious: https://github.com/TeamSPoon/wam_common_lisp https://github.com/TeamSPoon/wam_common_lisp Is SWI-Prolog real

The link to the main github page, for the curious: https://github.com/TeamSPoon/wam_common_lisp https://github.com/TeamSPoon/wam_common_lisp Is SWI-Prolog really faster than CLisp? I had no idea. Prolog seems like a language that would be pretty slow by default, but maybe you can do some pretty novel optimizations

YeGoblynQueenne 9y ago
The github page makes it pretty clear that it's "an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp". At least for the time being- it took a week to write that implementation, according to the Google group.
- PeachPlum 9y ago
  That is quoting Greenspun's tenth rule "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule
zmonx 9y ago
Why should Prolog be slower than CLisp? It is true, there is some overhead that is inherent to Prolog programs, mostly due to logical variables. But this is a rather small overhead, and if you need this feature, you would pay a comparable price also in other languages. Also, SWI-Prolog is among the slower Prolog systems: There are much faster Prolog systems available. See for example the following benchmarks: http://www.picat-lang.org/bprolog/performance.htm http://www.picat-lang.org/bprolog/performance.htm
- fasquoika 9y ago
  >Why should Prolog be slower than CLisp? In general, declarative programming tends to rely on having a sufficiently smart implementation. Maybe Prolog is simply more efficient than I would've guessed
  - yorwba 9y ago
    Prolog may be a "declarative" language, but you can still write imperative programs that rely heavily on resolution order, cuts and whatnot. So the natural solution in Prolog may be slower, but that doesn't mean you can't make it faster.
    - fusiongyro 9y ago
      In my experience, it is hard to avoid factoring in the resolution order. Cuts are still gross as hell though. Often you can follow Bird's advice for Haskell and make an inefficient program that is obviously right as a base. Prolog programs often have a generate-and-test flavor; once you have a good base, you can start refining inefficiencies in one side or the other. Maybe it's easier to make your generator produce better-qualified candidates, maybe it's easier to make your test faster. Prolog also sometimes has surprising abilities owing to the unification process itself. For example, difference lists give you singly-linked lists with O(1) append to the tail. Data structures with "holes" are a generalization of that idea. There's also a whole book devoted to making Prolog programs efficient: The Craft of Prolog by Richard O'Keefe.
  - fusiongyro 9y ago
    Most things that were considered shockingly inefficient in the 70s are faster than things we consider merely harmlessly inefficient today. :) In practice, Prolog requires the programmer to have some understanding of how it's going to be executed. This is in contrast to SQL, which is intentionally high-level to allow the database to figure out the best strategy and does require a lot more in the backend. Mercury also finds this abhorrent, but Mercury is another sufficiently-smart situation and a bit more obtuse.
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 ago
  In 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 ago

YeGoblynQueenne 9y ago

The github page makes it pretty clear that it's "an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp". At least for the time being- it took a week to write that implementation, according to the Google group.

PeachPlum 9y ago
That is quoting Greenspun's tenth rule "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp." https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

zmonx 9y ago

Why should Prolog be slower than CLisp? It is true, there is some overhead that is inherent to Prolog programs, mostly due to logical variables. But this is a rather small overhead, and if you need this feature, you would pay a comparable price also in other languages. Also, SWI-Prolog is among the slower Prolog systems: There are much faster Prolog systems available. See for example the following benchmarks: http://www.picat-lang.org/bprolog/performance.htm http://www.picat-lang.org/bprolog/performance.htm

fasquoika 9y ago
>Why should Prolog be slower than CLisp? In general, declarative programming tends to rely on having a sufficiently smart implementation. Maybe Prolog is simply more efficient than I would've guessed
- yorwba 9y ago
  Prolog may be a "declarative" language, but you can still write imperative programs that rely heavily on resolution order, cuts and whatnot. So the natural solution in Prolog may be slower, but that doesn't mean you can't make it faster.
  - fusiongyro 9y ago
    In my experience, it is hard to avoid factoring in the resolution order. Cuts are still gross as hell though. Often you can follow Bird's advice for Haskell and make an inefficient program that is obviously right as a base. Prolog programs often have a generate-and-test flavor; once you have a good base, you can start refining inefficiencies in one side or the other. Maybe it's easier to make your generator produce better-qualified candidates, maybe it's easier to make your test faster. Prolog also sometimes has surprising abilities owing to the unification process itself. For example, difference lists give you singly-linked lists with O(1) append to the tail. Data structures with "holes" are a generalization of that idea. There's also a whole book devoted to making Prolog programs efficient: The Craft of Prolog by Richard O'Keefe.
- fusiongyro 9y ago
  Most things that were considered shockingly inefficient in the 70s are faster than things we consider merely harmlessly inefficient today. :) In practice, Prolog requires the programmer to have some understanding of how it's going to be executed. This is in contrast to SQL, which is intentionally high-level to allow the database to figure out the best strategy and does require a lot more in the backend. Mercury also finds this abhorrent, but Mercury is another sufficiently-smart situation and a bit more obtuse.

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 ago
In 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 ago