WAM-CL: Common Lisp in Prolog | Hacker News Reader

WAM-CL: Common Lisp in Prolog

groups.google.com

67 pointslispm16 comments

The link to the main github page, for the curious: 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

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

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

Ha, excellent point. Thanks.

OK, 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 that (I think) tries to argue that you should not turn on optimization in Lisp because it costs more than you gain. I disagree.

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

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

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

>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

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.

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.

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.

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.

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

>The main purpose is this impl is it to run prolog-in-lisp 1000x faster than the fastest lisps (like SBCL)

This is very interesting. I thought that the prolog implementations done in Common Lisp were fast!

So now you can have not only Prolog in Lisp, but also Lisp in Prolog. Wonderful.

Here's a much older demo of a similar idea:

https://www.metalevel.at/lisprolog/

At 160 lines, it's short enough and readable enough to give a hint of the kinds of things Prolog is good at.

Reply on news.ycombinator.com