I recently tried my hand at writing a ray tracer (something I haven't done
for 15 years!) and, in particular, I to write the shortest possible ray
tracer which was still comprehensible and interesting. The initial result
was a 222-line OCaml program which incrementally renders a sphere-flake via
OpenGL:

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

I then cut this program down to a 66-line OCaml program and ported it into a
97-line C++ program. These programs are compared on this page:

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

The cut-down versions don't do reflections, color or such a pretty
sphere-flake and output a greyscale PGM but they do still use hierarchical
spherical bounding volumes to accelerate rendering enough that they can
render scenes containing millions of spheres.

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

Great work.  What is default floating point type used by OCaml
compiler?  I got running time of about 36s for scene level 3 on
Pentium3 machine and running time of about 25s when all references to
"double" type in C++ code changed to "float" (and float is usually
"good enough" for ray tracing)...

Regards,
Alex

Is that comparison supposed to be fair in any way whatsoever?

Somewhere on an opteron 146 running debian64:
# g++ -g -O3 ray.cpp -o ray
# time ./ray >tt

real    0m13.959s
user    0m13.946s
sys     0m0.009s

# objdump -x ray
[2mn later]
# diff ray_orig.cpp ray.cpp
12,16c12,18
< Vec operator+(Vec a, Vec b) { return Vec(a.x + b.x, a.y + b.y, a.z +
b.z); }
< Vec operator-(Vec a, Vec b) { return Vec(a.x - b.x, a.y - b.y, a.z -
b.z); }
< Vec operator*(double a, Vec b) { return Vec(a * b.x, a * b.y, a *
b.z); }
< double dot(Vec a, Vec b) { return a.x*b.x + a.y*b.y + a.z*b.z; }
< Vec unitise(Vec a) { return (1 / sqrt(dot(a, a))) * a; }
---

b.x, a.y + b.y, a.z + b.z); }
b.x, a.y - b.y, a.z - b.z); }
b.x, a * b.y, a * b.z); }
a.y*b.y + a.z*b.z; }
# g++ -g -O3 ray.cpp -o ray
# time ./ray >tt

real    0m10.493s
user    0m10.483s
sys     0m0.005s

If your point was to show how to write unbelievably inneficient code in
C++, you've succeeded.
Can't wait for a C++ vs Java comparison.

I think the point was to have some fun and to make a little demo that shows
how a functional language like OCaml can give rise to nice short expressive
programs while still delivering competitive performance.  And for those
goals, the OP succeeded!

Note also that he mentions on his web page that he's doing this for "the
computer language shootout benchmarks", http://shootout.alioth.debian.org/.
That page clearly points out all the caveats around benchmarks like these
(to the point that they can be effectively meaningless in  the real world.)

Specifically:

I've at least had some fun looking at his implementation!

-matt
--
Matt Pharr    m...@pharr.org    <URL:http://graphics.stanford.edu/~mmp>
=======================================================================
In a cruel and evil world, being cynical can allow you to get some
entertainment out of it. --Daniel Waters

You've missed the point.
a) he's telling the OCaml compiler to inline everything it can while
not giving its c++ counterpart opportunities to do so; fairness?
b) more importantly he's passing large structures by _value_ and i've
turned them into _references_.

In fact if you do the same for other hotpath functions as in:
19c21
<   virtual void intersect(double &, Vec &, Ray) = 0;
---

26c28
<   double ray_sphere(Ray ray) { // Intersection of a ray with a sphere
---
sphere
35c37
<   void intersect(double &lambda, Vec &normal, Ray ray) {
---
50c52
<   void intersect(double &lambda, Vec &normal, Ray ray) {
---

then the c++ version becomes 50% faster than originally (and in fact,
unconditionally faster than the OCaml version), without adding a single
line.

You'll notice i haven't even fixed the gratitious use of virtual
functions, and other details that force standard compliant c++
compilers to pessimize a lot when facing such... hmm.. source.

I'm sure OCaml is a wonderful & expressive language, but crafting such
a fishy c++ equivalent to make it shine (because you have an agenda) is
a despicable practice.

http://shootout.alioth.debian.org/.
world.)
I have nothing against such benchmarks when they are not clearly
rigged.

But i guess the main point of the whole operation wasn't fair
benchmarking, education, or fun but selling books: "This program has
demonstrated some of the ways that OCaml improves upon C++. For a
thorough introduction to OCaml, read our book "Objective CAML for
Scientists".

Or put another way, that's a sad PR stunt.

Have a nice day.

My post is more about clarity and less about performance. Your proposed
alterations make the C++ implementation significantly longer and more
obfuscated and your littering of the source code with "inline" actually
slows the program down on my Athlon t-bird.

Moreover, your choices of initial optimisation are decidedly suboptimal. I'd
have gone for:

1. Terminating the intersection of shadow rays when the first intersection
is found (instead of finding the closest intersection).

2. Use an implicit scene, to avoid storing it explicitly.

3. Use single-precision storage (or no storage at all).

Both of these optimisations will give much bigger performance improvements
when averaged over different platforms and architectures.

As it happens, I had already implemented all of your optimisations and all
of these optimisations to both implementations before I made my original
post. None of them add anything new. Sometimes C++ is faster, sometimes
OCaml is faster. OCaml is always much more succinct. You can keep doing
this until you are blue in the face but I don't think you'll learn much of
interest.

Both ocamlopt and g++ were allowed to inline code.

As OCaml is for symbolic use, it performs no inlining by default (unlike
g++) so it is common to ask OCaml to do some inlining on numerical code.
Thus, specifying "-inline 100" actually makes for a fairer comparison.

Both implementations use pass by value as this is clearer, shorter and (as a
consequence) more common in real code.

If you want a fair comparison then you should also make equivalent changes
to the OCaml implementation.

You are trying to compare optimised C++ against unoptimised OCaml, which
would be unfair. More worryingly, you seem to have skipped the part of the
experiment where you actually measure something.

When restricted to 80 columns, your optimisations add several lines. Indeed,
they push the C++ program over 100 LOC limit imposed by the creators of the
shootout.

In fact, I'd already implemented your optimisations (and many more effective
optimisations) and had to throw them out because of this limit. Note that
the OCaml has 30 more lines with which to optimise. My optimised <100 LOC
OCaml program is much faster than my optimised <100 LOC C++ on all
platforms.

What would you recommend instead?

I chose an inheritance hierarchy because this is the closest C++ equivalent
to a variant type which I see in typical C++ programs.

Another optimisation that I made was to replace inheritance with a single
Scene struct which represented a group of child scenes or a sphere when it
had no children. I threw this out as well because it is not a fair
equivalent to OCaml's variant type. For example, you could not specify a
colour for each sphere without also specifying colours for all bounding
volumes.

Can you elaborate on these other "details"?

Manually implementing pass constant by reference is both obfuscating and
error-prone whilst being theoretically unnecessary. The fact that the OCaml
compiler does this optimisation for you when the GNU C++ compiler does not
might interest some people.

Everyone will be free to contribute to the shootout version of the ray
tracer. Perhaps you would like to contribute a less "fishy" C++
implementation?

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

Double precision.

I agree that single precision is usually good enough for ray tracing.
However, when I tried the same optimisation I found that it made the
program much faster on 32-bit x86 and much slower on 64-bit AMD64. I assume
this is a float alignment issue.

Also, it generates (numerically) different results, which makes it trickier
to validate against the OCaml.

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com

  Then your compiler is stupid. Get a better one.

  The keyword 'inline' is not a command for the compiler that says it must
inline the function or else it will be deleted immediately. And the other
way around, the lack of 'inline' keyword by no means stops the compiler
from inlining the function if it can and it estimates it would be useful.

  In *theory* 'inline' is a hint to the compiler. In practice it has nothing
to do with inlining. Most of the modern compilers will simply ignore that
keyword when they are estimating whether a function should be inlined or
not. In this context 'inline' is a no-op. It's like the 'register'
keyword which is nowadays obsolete and a no-op.

  What 'inline' *does* have some effect on is the linker. If a function
with an identical declaration is implemented in more than one place
then in normal circumstances the linker will give an error (because it
can't know which one of them it should use). However, if the functions
were declared 'inline', then the compiler will tell the linker that
all of those functions are actually one and the same, and then the linker
will just use one of them.

  And by the way, if you are afraid of "litter" in C++ code, then you
should switch to another programming language.
  That "litter", as you call it, is not useless junk as you seem to imply.
It has a reason and a significance.

  I hope you are not passing megabyte-sized vectors by value...

  If your opinion of "clearer" and "shorter" is that the & symbol should
not be used, then you might want to either check your priorities or
change your programming language (because C++ is not for you).

  You want to compare which programming language runs inefficient code
faster?

  Inheritance has no overhead in C++. Dynamic binding has.
  While virtual function calls are pretty fast they are still slightly
slower than regular function calls. If you want maximum speed you should
not make time-critical functions virtual unless you are really forced to.

  Inheritance causes no overhead. That kind of optimization is useless.

--
                                                          - Warp

proposed
Oh? Silly me, i thought it was a benchmark.

I've put explicit inlines because, ie for Vec operators, you've put
them outside of the class scope, hence screwing the common heuristic
saying that a member function declared & defined within the class body
should be inlined (and that's a much stronger hint than using an
'inline' directive).
Anyway, that's decoration compared to other issues in your source.

Hmm? I tinker with a handful of lines, cut the runtime in half and
that's suboptimal?
Interesting.

Your aproach & space partition (as presented) will never give runtime
performance worth the time it takes to implement efficiently.
Such a sphere flake should render in a blink of the eye on modern
platforms, see the SPD for reference.
Or this: http://www.uni-koblenz.de/~cg/publikationen/cp_raytrace.pdf
I've merely fixed the most glaring flaws in your implementation.
Period.

I've never contested that OCaml is more succint, expressive or elegant.
I'm just saying that, given the horrible c++ implementation you've
presented, you have absolutely no authority or qualification to say
anything about the relative merit of c++ & OCaml performance wise.

It's all about exposing oportunities to do so.

comparison.
No. You've used none of the c++ idiom that actually helps a c++
compiler to guess what to inline or not.
Know your compiler (or in that case, your language).

Absolute non sense.
I can't beleive you really think that, but if that's the case, then you
should get back to your homework.

You're the one trying to sell books about OCaml...

I've provided patches. See for yourself.

You want to fit in those artificial constraints? Shorten names or
define some macros.
What was the fuss about already?

Sure. I mean you've shown such a level of C++ wizardry that we're
supposed to take your word for it?

Not using virtual functions in the hotpath.
Primo, that's uncalled for as your "hierarchy" doesn't mix types at a
given level, each object's type is known upfront.
Secundo, virtual functions are expensive because they forbid inlining
and are implemented as indirect branches , like:
  401c83:       callq  *0x8(%rax)
It doesn't make sense to use an expensive feature in the hotpath if you
can avoid it.
And you definitely can.

That's totally orthogonal.
Please do yourself a favor and read a good book about C++.

Strictly speaking of your implementation details (and not algorithm or
anything), you've also failed the const correctness test for example.
But i suppose you're going to say say that it's cruft or obfuscation.

I think you've just discovered that OCaml & C++ are two different
language that require the programmer to express things in a totally
different way.
And before you propose ways to improve C++ you should learn the
language first.

I don't have books to sell.
If/When i write a raytracer, i choose a path that at least has some
chances to perform decently.
See Wald & Havran.