[Shootout-list] Ray tracer

[Jon Harrop]

On Friday 17 June 2005 19:14, Brent Fulgham wrote:
> --- Jon Harrop <jon@ffconsultancy.com> wrote:
> > I think we should compare the fastest
> > implementations under 100 LOC, anything
> > goes.
>
> Dr. Harrop -- as a trained scientist I would think
> you would see the value in trying to control for as
> many variables as possible!  Do you really think an
> "Anything Goes" attitude is correct when trying to
> maintain some minimal level of objectivity?

As a trained scientist, I do, absolutely, yes. :-)

Ultimately: Trying to enforce your own subjective belief of equivalence will 
detract from the objectivity of the shootout, not add to it.

I propose that the objectivity is dictated solely by the soft LOC limit and 
the requirement that the code must produce the correct output for a given 
input (i.e. the same output as the 57-line OCaml from which all other 
programs were derived). Style is fairly subjective. The equivalence of 
implementations in terms of data structures and algorithms is very subjective 
because we don't know what the compilers are doing.

For example, what would you consider to be the C equivalent of the scene tree? 
I chose to use malloc in the same way that the C++ version uses the linked 
list allocator. However, the latter is really filling an array. What if 
someone submitted a C implementation which called malloc once? If you allow 
it then half of your critics will be outraged that the C implemented uses an 
array where the C++ is "clearly" using a linked list. If you disallow it then 
half of your critics (curiously this is often the same half ;-) will be 
outraged that you're letting C++ "hide" the array in its standard library.

> > I have found that the optimisations are very
> > language-dependent. For example, making the scene
> > tree implicit (computing it on-the-fly) made the
> > OCaml much faster and the MLton much slower. So I
> > think the diverse results will be of
> > greater interest than a set of equivalently-naively
> > written implementations.
>
> I agree that the results would be interesting, but
> won't it be difficult to know what we are really
> measuring?

Simple: This will measure how efficiently each language can solve the given 
task in practice.

The only valid objection that I can see is "but your most optimised ray tracer 
happens to fit neatly into 100 LOC where all the other implementations 
don't". This is an entirely valid criticism and the solution is to implement 
several benchmarks of varying complexity, all with the same "anything goes" 
attitude. Those where all implementations fit into 100 LOC represent simple 
tasks that can be completely optimised in practice. Those where no 
implementations fit into 100 LOC represent tasks so complex that it is 
impossible to completely optimise them in practice, even in the most 
expressive and concise languages.

For the small tasks (like Ackermann) there is another caveat. Specifically, 
unless the tasks are carefully set (in the way that Skaller described a while 
ago) you'll start to see implementations which hardcode the answer, or 
precompute it at compile time. Coincidentally, that's just happened. :-)

> If two different algorithms (and two  
> different data structures, etc.) are compared, how
> can we determine what amount of the delta in
> performance is due to algorithms versus the compiler
> implementation?

Users can profile the implementations to determine where the time is actually 
spent.

I appreciate the desire to compare seemingly equivalent programs but this is 
simply not possible in general and, consequently, must be dismissed.

> You may not be privy to the regular scalding reviews
> of the shootout in terms of measurement techniques
> and 'fairness' (and so are perhaps not as sensitive
> to these issues).  I think taking an 'Anything Goes'
> approach will lead to more problems.

You can tell them to "bring it on" from me. :-)

> > Having had a long debate on comp.lang.functional
> > about this, I'd be interested to hear what others
> > think about the code style on the shootout. Should
> > we use Stephen's style, which is more representative
> > of typical SML code, or should we use my style,
> > which is more representative of the brevity of SML's
> >
> > grammar but arguably less comprehensible?
>
> One great benefit of the shootout is as a collection
> of (often nontrivial) program implementations in a
> wide range of languages.  I think we should accept
> some level of 'noblesse oblige' and try to display
> implementations that follow the coding style and
> practices that are typical for the language in
> question.  So, the short answer is "Use Stephen's
> Style."

The problem here is that a couple of similarly experienced (to Stephen, not 
me!) SML programmers said they thought his style was overly spaced out.

> > I think it would be best to use my style as,
> > otherwise, both the performance and the LOC of MLton
> > will suffer unrepresentatively if we adopt the
> > "fastest under 100 LOC" approach.
>
> This is not the obfuscated SML shootout.  We are not
> trying to cram an interpreter for BASIC in a single
> line of code!  I'd suggest extending the 100 LOC
> guideline, but I recognize that that would only
> raise the bar (not resolve the issue).  So, all I
> can propose is that we try to follow Doug's original
> guidelines and ask that people code their programs
> as if LOC was not being measured.
>
> And of course, I could always wave a dictatorial
> wand and start reformatting files.... :-(

Had I not been coding for the shootout, the programs would have been laid out 
like this:

OCaml - the same
MLton - slightly more verbose (<10LOC more)
C++ - the same
Java - probably the same although I don't use Java

I agree with you entirely though, and am not an experienced SML programmer. 
However, I do think it will be a shame to see MLton appear bloated when, in 
fact, it is almost as concise as OCaml. Would it be easy to count words and 
bytes too?

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