rewrite comparison Qi, Lisp OCaml - results now on www
Mark Tarver
http://www.lambdassociates.org/studies/study10.htm
Some small changes. The final tests were run with 10^7 (not
10^6)iterations for a better picture. Garbage collection was done
before each run.
I could not (as of 13/07/07) get my OCaml compiler to compile Jon's
program, though it runs in interpreted mode. By taking the ratio of
the compiled performance on Jon's machine to his interpreted
performance I was able to infer a projected figure for my machine.
This figure is consistent with Jon's
"Although Lisp's fastest time [Nathan] is only 3x slower than the
OCaml (using Nathan's hand-optimised pattern match) ....."
The results show Nathan's Lisp and Qi Turbo-E to be the fastest Lisp
based solutions and to be within 4% of each other and by my projection
about 2.5 times slower than the short OCaml solution.
All the solutions are there, including the object code from Turbo-E
which can be run under Lisp.
If I get the OCaml compiler to do its stuff I'll post any change up
here.
Thanks to
Nathan Froyd
Andre Thieme
Pascal Constanza
Dan Bensen
for providing code
Jon Harrop (for both providing code and providing motivation to
develop Turbo-E)
Marcus Breing (for correcting my first run)
Mark
Daniel Janus
> I've now placed the results and the code on
>
> http://www.lambdassociates.org/studies/study10.htm
> I could not (as of 13/07/07) get my OCaml compiler to compile Jon's
> program, though it runs in interpreted mode. By taking the ratio of
> the compiled performance on Jon's machine to his interpreted
> performance I was able to infer a projected figure for my machine.
You might try this version (I fixed some typos and replaced
polymorphic variants with standard variants for a little speedup):
http://korpus.pl/~nathell/foo.ml
(Compile it with ocamlopt foo.ml -o foo.)
I also fine-tuned by hand the output of Qi Turbo-E, removing
SBCL warnings about inability to optimize:
http://korpus.pl/~nathell/foo.lisp
Here are the timings on my Celeron 2.4GHz with 512 MB RAM running
Arch Linux:
OCaml 3.09.3:
[nathell@chamsin ~]$ time ./a.out
real 0m1.705s
user 0m1.496s
sys 0m0.012s
Qi/SBCL 1.0.6:
* (tt 10000000)
Evaluation took:
3.813 seconds of real time
3.248203 seconds of user run time
0.064004 seconds of system run time
[Run times include 0.064 seconds GC run time.]
0 calls to %EVAL
0 page faults and
479,998,536 bytes consed.
--
Daniel 'Nathell' Janus, GG #1631668, przesu...@nathell.korpus.pl
create_initial_thread(initial_function);
lose("CATS. CATS ARE NICE.\n");
-- Steel Bank Common Lisp, sbcl/runtime/runtime.c:425
Jeronimo Pellegrini
On 2007-07-13, Mark Tarver <dr.mt...@ukonline.co.uk> wrote:
> I've now placed the results and the code on
>
> http://www.lambdassociates.org/studies/study10.htm
>
> Some small changes. The final tests were run with 10^7 (not
> 10^6)iterations for a better picture. Garbage collection was done
> before each run.
>
> I could not (as of 13/07/07) get my OCaml compiler to compile Jon's
> program, though it runs in interpreted mode. By taking the ratio of
> the compiled performance on Jon's machine to his interpreted
> performance I was able to infer a projected figure for my machine.
I'd like to reproduce this, and maybe run the compiled OCaml code.
Could you provide a Lisp function with all the inputs to the Lisp
implementations, so I could time them on my own machine?
Also, I don't know OCaml, but I'd like to know how you would do the
timing in it (if I get the whole program, with the timing code included,
I'll just compile and run it).
Thanks,
J.
Mark Tarver
> Dnia 13.07.2007 Mark Tarver <dr.mtar...@ukonline.co.uk> napisa³/a:
> create_initial_thread(initial_function);
> lose("CATS. CATS ARE NICE.\n");
> -- Steel Bank Common Lisp, sbcl/runtime/runtime.c:425
I get the same speed in your hand-edited Turbo-E version as my old
version - using Windows. Your time ratios between Turbo-E and OCaml
are pretty much in line with my projected results :) - OCaml slightly
more than twice as fast.
Good stuff.
Mark
Nathan Froyd
> I've now placed the results and the code on
>
> http://www.lambdassociates.org/studies/study10.htm
>
> Some small changes. The final tests were run with 10^7 (not
> 10^6)iterations for a better picture. Garbage collection was done
> before each run.
FWIW, I went back and optimized my code a bit more. Perversely,
turning off (OPTIMIZE (SPEED 3)) for both your version and my
version improved performance dramatically. (This is a fault of
the current SBCL implementation and it only shows up because of
recursive calls to local functions, which this benchmark makes
quite a lot of. For interested SBCL hackers, this is because
with (SPEED 3), we use a JMP/RET for local calls; otherwise we
use CALL/RET, which gives much better performance on modern
processors, even though we have to do the full call.)
Timings on my x86-64 machine (Intel Xeon 3.6GHz, best of four):
Mark's original: 3.4s
My original: 3.5s
Mark's "optimized": 2.6s
My "optimized": 2.1s
"optimized" for Mark's code means removing (OPTIMIZE (SPEED 3))
and changing NUMBERP checks to INTEGERP; my optimized code is
given below:
(defun simplify-froydnj (xexpr)
(if (atom xexpr)
xexpr
(let* ((op (first xexpr))
(t1 (rest xexpr))
(z (first t1))
(t2 (rest t1))
(y (first t2)))
(let* ((f (simplify-froydnj z))
(g (simplify-froydnj y)))
(tagbody
START
(if (eq '+ op) (go OPTIMIZE-PLUS) (go TEST-MULTIPLY))
OPTIMIZE-PLUS
(when (eql f 0) (return-from simplify-froydnj g))
(when (eql g 0) (return-from simplify-froydnj f))
(when (and (integerp f) (integerp g)) (return-from
simplify-froydnj (+ f g)))
(go REARRANGE-EXPR)
TEST-MULTIPLY
(unless (eq '* op) (go REARRANGE-EXPR))
OPTIMIZE-MULTIPLY
(when (or (eql f 0) (eql g 0)) (return-from simplify-
froydnj 0))
(when (eql f 1) (return-from simplify-froydnj g))
(when (eql g 1) (return-from simplify-froydnj f))
(when (and (integerp f) (integerp g)) (return-from
simplify-froydnj (* f g)))
REARRANGE-EXPR
(when (and (listp g) (eq op (first g)))
(let* ((t1 (rest g))
(u (first t1))
(v (second t1)))
(return-from simplify-froydnj
(simplify-froydnj (list op (list op f u) v)))))
MAYBE-CONS-EXPR
(if (and (eq f z) (eq g y))
(return-from simplify-froydnj xexpr)
(return-from simplify-froydnj (list op f g))))))))
The big wins were turning off (SPEED 3) and using INTEGERP. The
trickery with T{1,2} in the LETs above probably doesn't have much
of an effect, but I didn't feel like timing the effects precisely.
I don't know what the O'Caml code would clock in at. Based on the
timings from the above page, I'd imagine somewhere between 1.5s and
2s.
-Nathan
Dan Bensen
> | `Int n, `Int m -> `Int (n +/ m)
> | `Int (Int 0), e | e, `Int (Int 0) -> e
> let rec ( *: ) f g = match f, g with
> | `Int n, `Int m -> `Int (n */ m)
> | `Int (Int 0), e | e, `Int (Int 0) -> `Int (Int 0)
> | `Int (Int 1), e | e, `Int (Int 1) -> e
Does Int cover rationals, or is it just a num?
type num =
| Int of int
| Big_int of Big_int.big_int
| Ratio of Ratio.ratio
Ben Bacarisse
> Dnia 13.07.2007 Mark Tarver <dr.mt...@ukonline.co.uk> napisał/a:
>> I've now placed the results and the code on
>>
>> http://www.lambdassociates.org/studies/study10.htm
>
>> I could not (as of 13/07/07) get my OCaml compiler to compile Jon's
>> program, though it runs in interpreted mode. By taking the ratio of
>> the compiled performance on Jon's machine to his interpreted
>> performance I was able to infer a projected figure for my machine.
>
> You might try this version (I fixed some typos and replaced
> polymorphic variants with standard variants for a little speedup):
>
> http://korpus.pl/~nathell/foo.ml
>
> (Compile it with ocamlopt foo.ml -o foo.)
Very useful. This enabled me to compare the OCaml and Haskell
versions (Haskell posted in anther thread -- it seems to have got
split). OCaml/Haskell ratio about 2.75 (1.1s vs 0.4s) on my machine
which I found rather surprising.
--
Ben.
Jon Harrop
Int is a misnoma and it does already cover rationals here. My bad.
--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?usenet
David Golden
CL-USER> (simplify '(+ 1 (+ 1 (+ y 1))))
(+ (+ 1 (+ 1 Y)) 1)
CL-USER> (simplify-froydnj '(+ 1 (+ 1 (+ y 1))))
(+ (+ 2 Y) 1)
Slightly amending the Qi version can make it do that, of course:
...
+ A [+ B C] -> (simplify [+ [+ A B] C])
...
* A [* B C] -> (simplify [* [* A B] C])
...
D Herring
> I've now placed the results and the code on
>
> http://www.lambdassociates.org/studies/study10.htm
I think the Lisp timings could be improved; on my machine
(time (dotimes (n 10000000) (simplify *expr*)))
is significantly (~5-10%) faster than
(defun test (n)
(cond ((zerop n) 0)
(t (simplify *expr*) (test (1- n)))))
(time (test 10000000))
Here's my solution:
(defparameter *expr* '(* x (+ (+ (* 12 0) (+ 23 8)) y)))
(defun simplify (expr)
(if (listp expr)
; simplify
(let ((a (simp (cadr expr)))
(b (simp (caddr expr))))
(if (eql '+ (car expr))
; + simplifications
(cond
((and (numberp a) (numberp b)) (+ a b))
((eql a 0) b)
((eql b 0) a)
((and (listp b) (eql '+ (car b)))
(list '+ (list '+ a (cadr b)) (caddr b)))
(t (list '+ a b)))
; * simplifications
(progn
(when (numberp a)
(cond
((numberp b) (return-from simp (* a b)))
((= a 0) (return-from simp 0))
((= a 1) (return-from simp b))))
(when (numberp b)
(cond
((= b 0) (return-from simp 0))
((= b 1) (return-from simp a))))
(if (and (listp b) (eql '* (car b)))
(list '* (list '* a (cadr b)) (caddr b))
(list '* a b)))
))
; return the atom
expr))
Later,
Daniel
Jon Harrop
> I've now placed the results and the code on
>
> http://www.lambdassociates.org/studies/study10.htm
Can you alter the benchmark to simplify one large randomly-generated
expression rather than the same trivial expression a million times?
Also, I got a considerable performance improvement in OCaml by splitting the
simplifier into the three functions that you see, i.e. matching over + and
* in separate functions. I note that your Lisp is not doing this.
Finally, let me know when I should start optimizing the OCaml. ;-)
Mark Tarver
Yes; right. Doing that and removing (optimize (speed 3)) gives
3.6s - faster because the compiler directive was slowing me down.
The new times for all the tests under the new compiler directives plus
my corrected code are up on the site.
Mark
Mark Tarver
Jon Harrop
> Also, I don't know OCaml, but I'd like to know how you would do the
> timing in it (if I get the whole program, with the timing code included,
> I'll just compile and run it).
Put this code into the file simplify.ml:
open Num;;
let int n = `Int(Int n);;
let ( +: ) f g = `Add(f, g) and ( *: ) f g = `Mul(f, g);;
let expr =
`Var "x" *: ((int 12 *: int 0 +: (int 23 +: int 8)) +: `Var "y");;
let time f x =
let t = Sys.time() in
let f_x = f x in
Printf.printf "Took %fs\n" (Sys.time() -. t);
f_x;;
let rec loop n f x = if n=1 then f x else (ignore(f x); loop (n-1) f x);;
let rec ( +: ) f g = match f, g with
| `Int n, `Int m -> `Int (n +/ m)
| `Int (Int 0), e | e, `Int (Int 0) -> e
| f, `Add(g, h) -> f +: g +: h
| f, g -> `Add(f, g);;
let rec ( *: ) f g = match f, g with
| `Int n, `Int m -> `Int (n */ m)
| `Int (Int 0), e | e, `Int (Int 0) -> `Int (Int 0)
| `Int (Int 1), e | e, `Int (Int 1) -> e
| f, `Mul(g, h) -> f *: g *: h
| f, g -> `Mul(f, g);;
let rec simplify = function
| `Int _ | `Var _ as f -> f
| `Add (f, g) -> simplify f +: simplify g
| `Mul (f, g) -> simplify f *: simplify g;;
time (loop 10000000 simplify) expr;;
type expr =
Q of num
| Var of string
| Add of expr * expr
| Mul of expr * expr
let ( +: ) f g = Add(f, g) and ( *: ) f g = Mul(f, g);;
let int n = Q(Int n);;
let expr =
Var "x" *: ((int 12 *: int 0 +: (int 23 +: int 8)) +: Var "y");;
let time f x =
let t = Sys.time() in
let f_x = f x in
Printf.printf "Took %fs\n" (Sys.time() -. t);
f_x;;
let rec loop n f x = if n=1 then f x else (ignore(f x); loop (n-1) f x);;
let rec ( +: ) f g = match f, g with
| Q (Int 0), e | e, Q (Int 0) -> e
| Q n, Q m -> Q (n +/ m)
| f, Add(g, h) -> f +: g +: h
| f, g -> Add(f, g);;
let rec ( *: ) f g = match f, g with
| Q (Int 0), e | e, Q (Int 0) -> Q (Int 0)
| Q (Int 1), e | e, Q (Int 1) -> e
| Q n, Q m -> Q (n */ m)
| f, Mul(g, h) -> f *: g *: h
| f, g -> Mul(f, g);;
let rec simplify = function
| Q _ | Var _ as f -> f
| Add (f, g) -> simplify f +: simplify g
| Mul (f, g) -> simplify f *: simplify g;;
time (loop 10000000 simplify) expr;;
Compile it with:
$ ocamlopt nums.cmxa simplify.ml -o simplify
Run it with:
$ ./simplify
Took 1.902710s
Took 0.802878s
The first time is for the OCaml that Mark is using. The second time is for a
slightly faster (and more conventional) implementation.
Dan Bensen
> Dan Bensen wrote:
>> > let rec ( +: ) f g = match f, g with
>> > | `Int n, `Int m -> `Int (n +/ m)
>> > | `Int (Int 0), e | e, `Int (Int 0) -> e
>>
>> > let rec ( *: ) f g = match f, g with
>> > | `Int n, `Int m -> `Int (n */ m)
>> > | `Int (Int 0), e | e, `Int (Int 0) -> `Int (Int 0)
>> > | `Int (Int 1), e | e, `Int (Int 1) -> e
>>
>> Does Int cover rationals, or is it just a num?
>> type num =
>> | Int of int
>> | Big_int of Big_int.big_int
>> | Ratio of Ratio.ratio
>
> Int is a misnoma and it does already cover rationals here. My bad.
Assuming you mean "misnomer", how is "Int" a misnomer for an integer?
And how are Ratios and Big_ints processed by matching Ints?
--
Dan
www.prairienet.org/~dsb/
Jeronimo Pellegrini
>> I'd like to reproduce this, and maybe run the compiled OCaml code.
>>
>> Could you provide a Lisp function with all the inputs to the Lisp
>> implementations, so I could time them on my own machine?
>>
>> Also, I don't know OCaml, but I'd like to know how you would do the
>> timing in it (if I get the whole program, with the timing code included,
>> I'll just compile and run it).
>>
>> Thanks,
>> J.
>
> You can download the code from the file
>
> http://www.lambdassociates.org/studies/benchmark.zip
Thank you. I ran all benchmarks on an Athlon with 1.3 GHz, and
1.1 Mb memory, and I got slightly different results, with OCaml in
second.
This is what I got on my system, running all files without
any modifications, except for fixing the function name in Pascal's
version (defines "simplify-pacal" but tries to use "simplify").
The method I used is explained after the time listing.
Qi-generated Lisp code:
5.529 seconds of real time
4.810269 seconds of user run time
0.057991 seconds of system run time
Nathan:
6.232 seconds of real time
5.090226 seconds of user run time
0.058991 seconds of system run time
OCaml:
6.343035s
Dan:
6.622 seconds of real time
5.45817 seconds of user run time
0.06499 seconds of system run time
Andre:
30.898 seconds of real time
25.950056 seconds of user run time
0.192971 seconds of system run time
Pascal:
19.336 seconds of real time
16.332518 seconds of user run time
0.157976 seconds of system run time
How I measured times:
For the Lisp versions, I just did
sbcl < andre.lisp
sbcl < pascal.lisp
...
(I added the call to (tt 10000000) in the files where it was missing)
For the OCaml version, I did:
ocamlc -o jon nums.cma jon\ \(ocaml\).ml
./jon2
J.
Jeronimo Pellegrini
> For the Lisp versions, I just did
>
> sbcl < andre.lisp
> sbcl < pascal.lisp
> ...
>
> (I added the call to (tt 10000000) in the files where it was missing)
>
> For the OCaml version, I did:
> ocamlc -o jon nums.cma jon\ \(ocaml\).ml
> ./jon2
Sorry, I forgot to mention:
SBCL 1.0.7
3.09.2
J.
Jeronimo Pellegrini
>> You can download the code from the file
>>
>> http://www.lambdassociates.org/studies/benchmark.zip
>
> Thank you. I ran all benchmarks on an Athlon with 1.3 GHz, and
> 1.1 Mb memory, and I got slightly different results, with OCaml in
> second.
>
> This is what I got on my system, running all files without
> any modifications, except for fixing the function name in Pascal's
> version (defines "simplify-pacal" but tries to use "simplify").
> The method I used is explained after the time listing.
>
> Qi-generated Lisp code:
> 5.529 seconds of real time
> 4.810269 seconds of user run time
> 0.057991 seconds of system run time
>
> Nathan:
> 6.232 seconds of real time
> 5.090226 seconds of user run time
> 0.058991 seconds of system run time
>
> OCaml:
> 6.343035s
I only saw Jon's post after I sent these results. Using ocamlopt instead
of ocamlc I get different results for OCaml:
OCaml:
0.235965s
For the Qi code, using
(time (dotimes (i 10000000) (simplify *expr*)))
Instead of the tt function gives slightly better results:
5.185 seconds of real time
4.545309 seconds of user run time
0.053992 seconds of system run time
J.
Mark Tarver
>
> - Show quoted text -
The O'Caml time is out by x10. Jon is running 10^6 iterations not the
10^7. Try the new upload with 10^7 - you should get about 2 seconds.
Mark
Ben Bacarisse
...and with good reason. The trouble with test like this in Haskell
is that the optimiser (and sometimes just the lazy evaluation) means
that it is hard to so repeated tests.
What I posted above was a red herring. Using this code:
data Expression
= I Int
| S String
| Add Expression Expression
| Mul Expression Expression
deriving Show
simplify :: Expression -> Expression
simplify e =
case e of
(Add a b) -> simp (Add (simplify a) (simplify b))
(Mul a b) -> simp (Mul (simplify a) (simplify b))
e -> e
where
simp :: Expression -> Expression
simp (Add (I x) (I y)) = I (x + y)
simp (Add (I 0) e) = e
simp (Add e (I 0)) = e
simp (Mul (I x) (I y)) = I (x * y)
simp (Mul (I 0) _) = I 0
simp (Mul _ (I 0)) = I 0
simp (Mul (I 1) e) = e
simp (Mul e (I 1)) = e
simp (Mul a (Mul b c)) = simplify (Mul (Mul a b) c)
simp (Add a (Add b c)) = simplify (Add (Add a b) c)
simp e = e
-- [* x [+ [+ [* 12 0] [+ 23 8]] y]].
test = (Mul (S "x") (Add (Add (Mul (I 12) (I 0)) (Add (I 23) (I 8))) (S "y")))
main = loop (10^7)
where loop 0 = return ()
loop n = do simplify2 test `seq` loop (n - 1)
the repetition is not compiled away. I get 5.6s now and a profile run
confirms that the simplification is happening 10^7 times. To compare
that to the OCaml times, Jon's revised code (with two versions in it)
gives 2s and 1s on the same machine. The time goes down 4.3s if I
unroll the simplification, which is what I think Jon's version 2 is
doing.
If I turn optimisation on in GHC, then the time goes right down --
because, again, the compiler spots the pointlessness of the loop!
I second a test with one big expression!
--
Ben.
Jon Harrop
The argument to the `Int constructor is an arbitrary-precision rational. So
I should have called it `Rational instead.
David Golden
Um. You could also take the attitude that Nathan's code may be
outside spec and should be "broken" into compliance: after all,
once you start "improving" the simplifier, that's a pretty big
can of worms.
Jon Harrop
> Um. You could also take the attitude that Nathan's code may be
> outside spec and should be "broken" into compliance: after all,
> once you start "improving" the simplifier, that's a pretty big
> can of worms.
My original code make + and * left associative, so I think this is correct.
The fact that Nathan's code produces a smaller expr is simply because
1+1->2 is one of the steps in this simplification. There is nothing
particularly fancy going on.
--
Dr Jon D Harrop, Flying Frog Consultancy
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?usenet
Markus E Leypold
> David Golden wrote:
>> Um. You could also take the attitude that Nathan's code may be
>> outside spec and should be "broken" into compliance: after all,
>> once you start "improving" the simplifier, that's a pretty big
>> can of worms.
>
> My original code make + and * left associative, so I think this is correct.
> The fact that Nathan's code produces a smaller expr is simply because
> 1+1->2 is one of the steps in this simplification. There is nothing
> particularly fancy going on.
Still -- code that does different things is not really comparable. One
should agree on the exact specification to obtain meaningful results
for the "benchmark".
Regards -- Markus
Jon Harrop
Absolutely. I was only commenting on the "breaking Nathan's code into
compliance" bit.
Having said that, it is tricky to define "does the same thing" in this
context because we're talking about redundant code that never gets run for
the test expression that Mark chose.
Andras Simon
>
> You can download the code from the file
>
> http://www.lambdassociates.org/studies/benchmark.zip
>
Curiously, if the input of JH's code uses rationals instead of
integers, there's a 20-fold slowdown. Needless to say, this doesn't
happen with the CL versions. I get 4.743 with SBCL for a Pascal-like
solution (and 7.709 with Pascal's) and 49.720441s with OCaml.
The changes to the OCaml code are:
let rat n m = `Int (Int n // Int m) ;;
(* there must be a better way to produce rationals *)
let expr =
`Var "x" *: ((rat 12 11 *: int 0 +: (rat 23 22 +: rat 8 7)) +: `Var "y");;
Andras
Jon Harrop
> The changes to the OCaml code are:
>
> let rat n m = `Int (Int n // Int m) ;;
> (* there must be a better way to produce rationals *)
>
> let expr =
> `Var "x" *: ((rat 12 11 *: int 0 +: (rat 23 22 +: rat 8 7)) +: `Var
> "y");;
Yes, I get 29.3s for OCaml. I suspect that adding a pair of rationals using
the Num library is an order of magnitude slower than the Lisp equivalent.