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

About these ads

23 thoughts on “Should GHCI be faster?

  1. @Edward: yes, more or less it is. I think that these ghci flags should be better documented, the one suggested by Svein is like a little pearl into the sea :)

    • Yes, I knew that SBCL was famous to be a very fast CL compiler, and yes, as you and Antoine noticed, it performs some tricks in background :)

    • From what I understand about SBCL, the difference between “Compiled” and “Interpreted” in this case is that running the code from the REPL actually invokes a compilation step first, whereas the pre-compiled version (via save-lisp-and-die) is actually pre-compiling the code. hence the ~6 second difference.

  2. A bit of a minor point, but note that you’re comparing apples to oranges here. The Scala code is using native integers, whereas the Haskell code is using bigints. Changing the type signatures to use Int (native) rather than Integer (bigint) results in an almost 2x speedup. Still slow compared to the Scala version, though.

    Also, foldl1 lcm [1..20] :)

    • The same point emerged on Haskell Reddit (perhaps you are the same person? :D ). Yes, it’s a little as comparing apples and oranges, but I think to have made my point: i’ve learned a bunch of interesting tricks and the comments gave me ideas of why the things are the way they are…
      Finally, about your code snippet I have to say… WOW!
      It’s blazing fast! The way to the enlightenment is to long… :D

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

    Could you time this on your computer also? Sorry for biting the “My language is faster then yours”-hook. But I thought it was a bit unfair that lisp got 10 seconds.

    • (defun my ()
      (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)))

      There… This one is a bit clearer :)

      • Thanks, but the point here is not “Lisp is worse”. A little disclaimer: i really like Lisp, so I’m happy to see that the computation could be improved (no doubt of that, after all). But the point here is “What can we do, out of the box, without knowing the most tricky features of a language?” Your code (as well as Hammar’s one) is not from a “Young Lisper”. Thank you for the snippet, though :)

      • As far as I can see. the point was “GHCI should be faster”.
        Anyway, I don’t use any advanced lisp features.
        1. (declare (optimize …)) is like haskell’s -O2
        2. of-type is like haskell’s :: Maybe Integer
        3. My version does not even have recursion (so it should be easy even for beginners)
        I’d still like to know how fast it runs compared to haskell. I’ve never really optimized lisp before like this. I never had to ;)

      • Give me a couple of hours (I’m pretty busy right know) and you will find your version with its timing as an article update :)

        Bye!
        Alfredo

      • I’ve tried it either interpreted (from SBCL loading and invoking your function) or compiled (with (sb-ext:save-lisp-and-die “euler5″ :executable t :toplevel ‘my)) and results are pretty the same, around 3.8 seconds :)

  4. I finally understood the fastest haskell version with lcm :)

    We can do that in lisp to:
    (reduce ‘lcm (loop for div of-type fixnum from 20 downto 1 collect div))

    I understand that I’m missing the point :) But now I can finally sleep with my parentheses again ;)
    At least I learned something, even though it’s kind of OT.

  5. SBCL does not use an interpreter. It uses a compiler. The REPL invokes the compiler, too.

    To time code execution without starting an executable, you can use the TIME macro.

    Also in your original code, what is the point of (and t foo)? That should be the same as just FOO.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...