Ray tracer language comparison

Ray tracer language comparison

[Jon Harrop]

I've updated my language comparison with four implementations in Scheme and 
one in Lisp:

  http://www.ffconsultancy.com/free/ray_tracer/languages.html

In short, Stalin's run-time performance is excellent (36% faster than 
ocamlopt) but its compile times are poor (2,000x slower than ocamlopt!) and 
SBCL-compiled Lisp is 6x slower than ocamlopt. Both Scheme and Lisp are >2x 
as verbose as OCaml.

Juho Snellman posted an interesting Lisp variant that used a macro to factor 
out unboxing, greatly reducing the stress on the GC and improving Lisp's 
performance to that of OCaml. Applying the same optimisation to the OCaml 
implementations makes them much faster again but I have yet to factor this 
out into a camlp4 macro.

This raises two interesting questions:

1. Can a camlp4 macro be written to factor out this unboxing transformation:

  let v = center -| orig in
  let b = dot v dir in
  let disc = b *. b -. dot v v +. radius *. radius in

where "+|" denotes vector addition and "*|" denotes scalar*vector 
multiplication. Transformed to:

  let vx = center.x -. orig.x in
  let vy = center.y -. orig.y in
  let vz = center.z -. orig.z in
  let b = vx *. dir.x +. vy *. dir.y +. vz *. dir.z in
  let vv = vx *. vx +. vy *. vy +. vz *. vz in
  let disc = b *. b -. vv +. radius *. radius in

So the intermediate vectors are not allocated and collected.

2. Manually inlining the code gives a huge performance improvement but using 
-inline does not appear to give this improvement. I assume ocamlopt can 
inline this but will not remove the boxing and subsequent unboxing. Is that 
right?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Ray tracer language comparison

[Thomas Fischbacher]

On Tue, 4 Oct 2005, Jon Harrop wrote:

> 
> I've updated my language comparison with four implementations in Scheme and 
> one in Lisp:
> 
>   http://www.ffconsultancy.com/free/ray_tracer/languages.html

I think this analysis is quite seriously flawed:

(1) You are mostly comparing implementations, not languages, yet call this 
a "language comparison".

(2) Just having a glance at in particular at the Lisp implementation 
immediately reveals trivial but relevant further optimizations that one 
would like to include. For example, just adding a further entry 
(:type (vector double-float)) to (defstruct vec ...) reduces run time by 
more than 20%. I did not take a closer look yet, but my impression is that 
this is not even a comparison of implementations, but just a comparison of 
various snippets of code for various languages, written by people with 
quite different proficiency with the individual languages and 
implementations. So, I wonder whether the data may indeed be quite 
seriously flawed.

(3) Unless I missed some interesting development, Stalin by no means is a 
"Scheme", at least for any of the official definitions of the term 
"Scheme" (IEEE, RnRS). Of course, it is easy to optimize towards using 
machine integers (instead of "proper numbers") if the system just does not 
support the Scheme numerical tower.

(4) You are just looking at one single example application, which in 
addition is not especially large. So, if Lisp's metasyntactic capabilities
really are a great boon, as many people like to claim, this clearly will 
not show in a ~100 lines example. And this is just one example of a small 
"benchmark" program not really allowing any conclusions for real world 
applicability. So, okay, OCaml is a great system for writing a 
primitive raytracer in ~60 lines, but I would not dare to extrapolate any 
conclusion about other programs from this.

(5) Some statements are just plain outright wrong, such as this:
"In practice, SBCL is very poor at inferring types and it is necessary to 
litter the source code with type declarations, as we have done here."

While SBCL/CMUCL are not Hindley-Milner, their type inference does know 
more tricks than one might suppose. If you declare a number to be an 
integer in the range (0..100) (which you can do), it will know that its 
square is in the range (0..10000). If you declare a number x to be a 
fixnum, then it will know that (+ 1 x) will not necessarily be a fixnum, 
and hence generate generic addition code (which it has to - to maintain 
correctness).

So it is more an issue of the programmer expecting different things from 
the system than it provides. Please do not spread such un-informed 
comments that just contribute to the general confusion and 
misunderstanding.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] Ray tracer language comparison

[Thomas Fischbacher]

On Tue, 4 Oct 2005, Jon Harrop wrote:

> 
> I've updated my language comparison with four implementations in Scheme and 
> one in Lisp:
> 
>   http://www.ffconsultancy.com/free/ray_tracer/languages.html
> 
> In short, Stalin's run-time performance is excellent (36% faster than 
> ocamlopt) but its compile times are poor (2,000x slower than ocamlopt!) and 
> SBCL-compiled Lisp is 6x slower than ocamlopt. Both Scheme and Lisp are >2x 
> as verbose as OCaml.

As you may have seen from my initial reply to that posting, I originally 
was quite sceptical. However, I had a somewhat lengthy PM conversation 
with Dr. Jon Harrop where he kindly and patiently explained to me his 
methodology and findings, and eventually, this inspired me to contribute 
another benchmark (which I did of my own) to this comparison. As this 
issue created a lot of traffic on comp.lang.functional, comp.lang.scheme, 
comp.lang.java.programmer, and some other newsgroups, this could even be 
of interest to a broader audience.

It's here:

http://www.cip.physik.uni-muenchen.de/~tf/raytracer/

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] Re: Ray tracer language comparison

[Gerd Stolpmann]

Am Sonntag, den 09.10.2005, 10:53 -0400 schrieb Vincenzo Ciancia:
> Thomas Fischbacher wrote:
> 
> > 
> > As you may have seen from my initial reply to that posting, I originally
> > was quite sceptical. However, I had a somewhat lengthy PM conversation
> > with Dr. Jon Harrop where he kindly and patiently explained to me his
> > methodology and findings, and eventually, this inspired me to contribute
> > another benchmark (which I did of my own) to this comparison.
> 
> What is the difference, that you mention in your webpage, between "OCaml"
> and "Objective Caml"? It's not clear to me what your benchmark is about at
> all :)

I guess it's a joke. OCaml = the speed-optimized version; Objective Caml
= the version optimized for readability (which I don't agree with).

Gerd
-- 
------------------------------------------------------------
Gerd Stolpmann * Viktoriastr. 45 * 64293 Darmstadt * Germany 
gerd@gerd-stolpmann.de          http://www.gerd-stolpmann.de
Telefon: 06151/153855                  Telefax: 06151/997714
------------------------------------------------------------

Re: [Caml-list] Ray tracer language comparison

[Yaron Minsky]

It seems like on the whole a more fitting riposte might have been to
provide a version of the SBCL implementation that was 8x faster than
Jon's, rather than to provide a crippled version of Jon's that was 8x
slower.  But to each his own, I suppose....

y

Re: [Caml-list] Re: Ray tracer language comparison

[sejourne_kevin]

Gerd Stolpmann a écrit :
> Am Sonntag, den 09.10.2005, 10:53 -0400 schrieb Vincenzo Ciancia:
> 
>>Thomas Fischbacher wrote:
>>
>>
>>>As you may have seen from my initial reply to that posting, I originally
>>>was quite sceptical. However, I had a somewhat lengthy PM conversation
>>>with Dr. Jon Harrop where he kindly and patiently explained to me his
>>>methodology and findings, and eventually, this inspired me to contribute
>>>another benchmark (which I did of my own) to this comparison.
>>
>>What is the difference, that you mention in your webpage, between "OCaml"
>>and "Objective Caml"? It's not clear to me what your benchmark is about at
>>all :)
> 
> 
> I guess it's a joke. OCaml = the speed-optimized version; Objective Caml
> = the version optimized for readability (which I don't agree with).
Without colors, it is the same for the two programs... unreadable at all.

	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com

Re: [Caml-list] Ray tracer language comparison

[Thomas Fischbacher]

On Sun, 9 Oct 2005, Yaron Minsky wrote:

> It seems like on the whole a more fitting riposte might have been to
> provide a version of the SBCL implementation that was 8x faster than
> Jon's, rather than to provide a crippled version of Jon's that was 8x
> slower.  But to each his own, I suppose....

What? You call that elegant use of higher order functions "crippled"? 
What a Blasphemy. I am really, truly outraged.

...on the other hand... 

[wicked thinking]
[most evil sniggering]
[pictures of the great evil genius playing the organ]
[more of all the above]
[ *clickediclick* ]

Bring that man to be, he shalt be served as well!

I just extended my analysis by another implementation in yet another 
language. This time, it's "Steel Bank Common Lisp". As this is a Lisp as 
well, I will be concerned primarily with comparing it against SBCL, but it 
may also be nice to compare it with OCaml, or Objective Caml.

There it is:

http://www.cip.physik.uni-muenchen.de/~tf/raytracer/#sbcl

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: Ray tracer language comparison

[Vincenzo Ciancia]

Thomas Fischbacher wrote:

> 
> As you may have seen from my initial reply to that posting, I originally
> was quite sceptical. However, I had a somewhat lengthy PM conversation
> with Dr. Jon Harrop where he kindly and patiently explained to me his
> methodology and findings, and eventually, this inspired me to contribute
> another benchmark (which I did of my own) to this comparison.

What is the difference, that you mention in your webpage, between "OCaml"
and "Objective Caml"? It's not clear to me what your benchmark is about at
all :)

V.

-- 
Please note that I do not read the e-mail address used in the from field but
I read vincenzo_ml at yahoo dot it
Attenzione: non leggo l'indirizzo di posta usato nel campo from, ma leggo
vincenzo_ml at yahoo dot it

Re: [Caml-list] Ray tracer language comparison

[Jon Harrop]

On Sunday 09 October 2005 06:26, you wrote:
> http://www.cip.physik.uni-muenchen.de/~tf/raytracer/

I reformatted your code with tuareg indentation and 80-char columns to conform 
with the other implementations for fair comparison, corrected the bug in a 
call to printf and removed the superfluous parentheses. Your code is then 1 
line shorter and 8x slower than the previous implementation on my site. I 
then rewrote it to be both shorter and faster.

For anyone who is interested, the main performance degradation introduced by 
Thomas came from the use of polymorphic HOFs (particularly Array.init) to 
perform vector arithmetic that appears in the inner loops of the ray tracer.

Here is my implementation that is both 17% shorter in LOC (and shorter in both 
words and bytes) and 4.7x faster than Thomas':

let ( *| ) s (x, y, z) = s *. x, s *. y, s *. z
let ( +| ) (x1, y1, z1) (x2, y2, z2) = x1 +. x2, y1 +. y2, z1 +. z2
let ( -| ) (x1, y1, z1) (x2, y2, z2) = x1 -. x2, y1 -. y2, z1 -. z2
let dot (x1, y1, z1) (x2, y2, z2) = x1 *. x2 +. y1 *. y2 +. z1 *. z2
let unitise r = (1. /. sqrt (dot r r)) *| r

let ray_sphere orig dir center radius =
  let v = center -| orig in
  let b = dot v dir in
  let disc = sqrt(b *. b -. dot v v +. radius *. radius) in
  if disc <> disc || b +. disc < 0. then infinity else
    if b -. disc > 0. then b -. disc else b +. disc

let rec intersect orig dir ((lambda, _) as hit) (center, radius, children) =
  let lambda' = ray_sphere orig dir center radius in
  if lambda' >= lambda then hit else match children with
    | `List [] -> lambda', unitise (orig +| lambda' *| dir -| center)
    | `List children -> List.fold_left (intersect orig dir) hit children

let intersect orig dir = intersect orig dir (infinity, (0., 0., 0.))

let neg_light = unitise (1., 3., -2.) and ss = 4

let rec ray_trace orig dir scene =
  let lambda, normal = intersect orig dir scene in
  if lambda = infinity then 0. else
    let g = max 0. (dot normal neg_light) in
    let p = orig +| lambda *| dir +| sqrt epsilon_float *| normal in
    if g = 0. || fst (intersect p neg_light scene) < infinity then 0. else g

let rec create level c r =
  let obj = c, r, `List [] and a = 3. *. r /. sqrt 12. in
  if level = 1 then obj else
    let f x' z' = create (level-1) (c +| (x', a, z')) (0.5 *. r) in
    c, 3. *. r, `List [obj; f (-.a) (-.a); f a (-.a); f (-.a) a; f a a]

let n, scene = match Sys.argv with
    [| _; l; n|] -> int_of_string n, create (int_of_string l) (0., -1., 4.) 1.
  | _ -> 512, create 9 (0., -1., 4.) 1.;;

Printf.printf "P5\n%d %d\n255\n" n n;;
for y = n - 1 downto 0 do
  for x = 0 to n - 1 do
    let g = ref 0. in
    for dx = 0 to ss - 1 do
      for dy = 0 to ss - 1 do
	let aux x d = float x -. float n /. 2. +. float d /. float ss in
	let dir = unitise (aux x dx, aux y dy, float n) in
	g := !g +. ray_trace (0., 0., 0.) dir scene
      done
    done;
    let g = 0.5 +. 255. *. !g /. float (ss*ss) in
    Printf.printf "%c" (char_of_int (int_of_float g))
  done
done

The main source of performance degradation in this implementation is probably 
the use of tuples to represent vectors rather than records. With ocamlopt, 
the floats in records of floats are unboxed but the floats in tuples of 
floats are not. Thus, this implementations places extra burden on the 
allocator and GC.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Ray tracer language comparison

[Thomas Fischbacher]

On Sun, 9 Oct 2005, Jon Harrop wrote:

> On Sunday 09 October 2005 06:26, you wrote:
> > http://www.cip.physik.uni-muenchen.de/~tf/raytracer/
> 
> I reformatted your code with tuareg indentation and 80-char columns to conform 
> with the other implementations for fair comparison,

The longest line in your original code has 79 columns. So does the longest 
line in my code. I do not use any indentation and formatting techniques 
which are not present in your original code as well.

> corrected the bug in a 
> call to printf and removed the superfluous parentheses.

Yes, I was notified of this as well and corrected it in the source. 
Concerning teh extra parens: I like them. Let's just consider this 
artisitc freedom, okay?

> Your code is then 1 
> line shorter and 8x slower than the previous implementation on my site.

What do you mean, "previous implementation"? You provide data for OCaml, 
and I suggested you should include Objective Caml into the comparison as 
well.

> I then rewrote it to be both shorter and faster.

Let us see:

> Printf.printf "P5\n%d %d\n255\n" n n;;
> for y = n - 1 downto 0 do
>   for x = 0 to n - 1 do
>     let g = ref 0. in
>     for dx = 0 to ss - 1 do

Ah. You eliminated the main function. Nice move. I suppose one could 
easily do this for the other implementations as well.



As some people out there seem to wonder what this is all about: 
I maintain the following claim.

- While Jon does not clearly state this on his web page, his main 
  criterion for a valid submission is that it must be impossible to 
  improve by making it both shorter and faster.

- The problem with this methodology is that it does not satisfy even 
  the most fundamental principle one would like to see in a proper comparison:

  If we take a product X, and a product Y, which in fact just again is 
  X, but let us pretend for now and threat them as if they were different,
  then it must not be possible to make a submission for X and a submission 
  for Y that both are valid under all the criteria applied, which lead to
  the conclusion that X is considerably better than Y.

Okay, Jon, you just managed to produce an Objective Caml implementation 
which shows that I am completely wrong, and indeed, Objective Caml is even 
much more succinct than OCaml, while being only about 50% slower than 
OCaml. Why don't you include that important result on your web page?

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

Re: [Caml-list] Ray tracer language comparison

[Florian Weimer]

* Thomas Fischbacher:

> I just extended my analysis by another implementation in yet another 
> language. This time, it's "Steel Bank Common Lisp".

Is this some kind of elaborate hoax?  If it is, I don't get it?

"OCaml" vs. "Objective Caml", "SBCL" vs. "Steel Bank Common Lisp",
"1/8" vs. "1/10" -- all these comparisons are a bit strange.

Re: [Caml-list] Ray tracer language comparison

[Thomas Fischbacher]

On Sun, 9 Oct 2005, Florian Weimer wrote:

> * Thomas Fischbacher:
> 
> > I just extended my analysis by another implementation in yet another 
> > language. This time, it's "Steel Bank Common Lisp".
> 
> Is this some kind of elaborate hoax?  If it is, I don't get it?
> 
> "OCaml" vs. "Objective Caml", "SBCL" vs. "Steel Bank Common Lisp",
> "1/8" vs. "1/10" -- all these comparisons are a bit strange.

All the numbers and measurements on my page are for real. As well as all 
statements concerning my testing environment. And I am using precisely the 
same diligence with my studies as Jon does with his.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)