I thought I’d learn a bit of Haskell, so I started watching Graham Hutton’s online course. The first example is a generate-and-test solver for the “countdown” puzzle, and I thought “that’s something that Prolog can do both more compactly and faster”. I was right about the “more compactly” but terribly wrong about “faster” – on my machine, Haskell takes 0.3 seconds for all solutions (compiled; 4.2 seconds using the
ghci interpreter); but Prolog takes over 40 seconds. And, looking at my Prolog code, I don’t see an obvious way of speeding it up - the profiler shows almost all the time spent here:
16% expr/2 (14% expr_2/2, 7% op_primitive/3
One thing that doesn’t show is any first-argument indexing – I assume it’s there but
vm_list/1 doesn’t show anything. I was able to make the Prolog code run about 20% faster by changing some of the comparison operations; and the
-O option got another 20%; but to be competitive with the Haskell code, I’d need a 10x speedup, and I don’t see how to do that.
The Prolog code is in countdown.pl; the Haskell code is in pgp-countdown.hs and documented in https://www.cs.nott.ac.uk/~pszgmh/countdown.pdf ; I wrote a few notes in countdown-notes.md. The test problem is run by:
time(forall(solve([1,3,5,10,25,50], 999, Expr), writeln(Expr))).
Is this slow performance because SWI-Prolog is designed for nice development features with performance being secondary, or is there some fundamental difference between Prolog and Haskell that accounts for the speed difference? Or is my Prolog code just really bad?
I tried GNU-Prolog’s compiler – it ran in 18 .4 seconds, which is a definite improvement, but still not enough to compete with Haskell. (GNU-Prolog’s interpreter was nearly 4x slower than SWI-Prolog)
(I noticed that GNU-Prolog builds with
-O3 -fomit-frame-pointer -Wno-char-subscripts -funsigned-char but I haven’t tried that, and I suspect it wouldn’t make much difference.)
swipl with the GNU-Prolog compiler options and there was at most a few percent performance change. (In both cases, I used PGO)
I’ve improved the code, now in countdown2.pl – it’s now only 7x slower than interpreted Haskell. It’s hard to see where I can get more speed because the profiler shows it spending 50% of its time in is/2. (My speedup was by changing
is/2; the overall time is now split evenly between evaluation and generating candidate expressions.)
With compiled GNU-Prolog, I’m down to 18 seconds (almost twice as fast as SWI-Prolog), or roughly 4x slower than interpreted Haskell.
The Haskell code (as far as I can tell, because I’m not an expert Haskell programmer) generates a lazy list of permutations (whereas Prolog uses backtracking). The
apply functions presumably are faster than Prolog’s is/2 because the Haskell code doesn’t have to do any extra tag checking. But that accounts for at most of half the performance difference between the Haskell and Prolog programs.