Should GHCI be faster?

Hi everyone,

finally I came back to write after a little break (I’m having rough time writing my thesis). A thing I really like is to implement project Euler’s problems with several languages, just to performs same silly benchmarks. A long time ago I’ve coded the solution of  Problem # 5 in Common Lisp (although you can search and find, within this site, implementations in Racket and Clojure). It run in about 10 seconds with SBCL:

(defun div1-x-p (divisor num)
  "Checks if num is evenly divisible for all number below divisor"
  (cond
    ((= 1 divisor) t)
    ((/= 0 (mod num divisor)) nil)
    (t (and t (div1-x-p (1- divisor) num)))))

(defun project-euler-5-solver (acc)
  (if (div1-x-p 20 acc)
      acc
      (project-euler-5-solver (1+ acc))))

It’s a bit naive, but I’m not going to focusing on this, while I report an optimized version user knobo posted between article’s comments:

(defun solver ()
	(declare (optimize (speed 3) (space 0) (safety 0) (debug 0)))
	(loop for num of-type fixnum from 1
		until (loop for divisor of-type fixnum from 20 downto 1
		always (zerop (mod num divisor)))
		finally (return num)))

You can even compile this after having loaded it inside SBCL:

(load "euler5.lisp")
(sb-ext:save-lisp-and-die "euler5" :executable t :toplevel 'solver))

This version run in about 3.8 seconds, since there is not much difference between the compiled and interpreted version. The version which uses lcm as fast as the Haskell one, instead:

(reduce 'lcm (loop for div of-type fixnum from 20 downto 1 collect div))

Since I’ve been wondering for a while how Haskell would perform in this particular problem, I’ve written a simple solution of the same problem:

import Data.List

solver :: Maybe Integer
solver = find (\x -> divPred x) [20,40..]

divPred :: (Integral a) => a -> Bool
divPred x = all (\y -> x `mod` y == 0) [20,19..2]

main :: IO ()
main = do
  putStrLn $ show solver

Ok, what about this? The compiled version is obviously blazing fast, and it took only about 1.8 second on my machine. Nevertheless the interpreted version is really slow: it takes about 57 seconds!! (Although you can type :set -fobject-code just before loading the script, and ghci will compile it under the hood as a .o file. Thanks to Svein Ove for the tip).
For the sake of completeness, you can try this outstanding solution for the problem gave me from the user Hammar:

solver = foldl1 lcm [1..20]

main :: IO ()
main = do
  putStrLn $ show solver

And these are the execution times:

alfredodinapoli$ time euler5
232792560

real	0m0.006s
user	0m0.001s
sys	0m0.003s

Pretty impressive, aren’t they? But for now, we will concentrate only on the naive implementation.

As you can imagine, I’m bit disappointed on the fact that my current favorite functional programming language is so slow, for this particular tasks, if interpreted.

Life is full of ladders

Some days ago, for accident I stumbled upon this interesting (and famous) benchmark, comparing several programming languages. As you can see, Haskell is one of the fastest languages, even though Scala is some step upper into the main score. I’ve decided, just for completeness and curiosity, to implement the problem #5 even in Scala, with a big disclaimer: I hadn’t written a single line of Scala until this afternoon, and this is the result:

def divPred(x : Int): Boolean =
	{
	    Range(20,1,-1).forall(x % _ == 0)
	}

	def solver(): Option[Int] =
	{
		Range(20,1000000000,20).find(divPred _)
	}

	def timeIt()
	{
		val start = System.currentTimeMillis()
		printf(solver().toString())
		val end = System.currentTimeMillis()
		println((end - start).asInstanceOf[Float] + " msecs")
	}

This took about 3 seconds interpreted and more or less the same time even compiled, so there is not a big different but, I mean, it took 3 seconds even interpreted!

Conclusions, thoughts, open questions

Now, despite I think Scala is a nice piece of software, I can’t stand the fact that is Java based. But the point is not “Scala is better then Haskell”, because Haskell can be compiled with -O2 and everything is blazing fast. The point is: Why Haskell can be blazing fast even compiled but Scala can? I suspect there are several reasons behind it, like the JIT compiling and other sharp optimization Scala and Java do in the background… Yes, but why not Haskell?

This is not a troll post, is a reflection and an input to other Haskellers out there to improve again and again Haskell to make it the perfect functional language. And just before you will post “cutting-edge” solutions, I will advice you: The main point of this post is not to demonstrate that a super-optimized Haskell program can lower the execution time, because I have written the two implementation acting just as a guy who try the languages “out-the-box”: everyone coming from a functional background should be able to:

1. Search the main documentation library for “famous” functions like “all, any, filter, map, etc”
2. Be able to implement a simple and naive problem only with this construct
3. Compare the execution times

This obviously stands for every language.That’s my opinion. And yours?

Cheers,

Alfredo