[Shootout-list] Binary trees

[Einar Karttunen]

Jon Harrop <jon@ffconsultancy.com> writes:
> This is not totally unlike a real program. In particular, this tree can be 
> empty (containing only one T object, Empty). The other implementations (e.g. 
> OCaml, MLton, Haskell) can't represent an empty tree. Does this make them 
> invalid?

The Haskell implementation which is currently the fastest has:
data Tree = Node  Int Tree Tree | Nil
which is perfectly capable of representing an empty tree. If the other
ones are not they should be fixed.

> A quick profile of the above code shows that 50% of the time is spent in 
> Node::~Node(), deallocating non-leaf nodes of the trees.

Yes, the test is memory intensive.

>   type int_tree = Empty of int | Node of int_tree * int * int_tree

Seems unfair to me.

> Now, this begs the question how far can I take this optimisation before Isaac 
> starts whining? I can hear Isaac saying that I must mimic the existing 
> implementations (i.e. use their broken representation of a tree).

Are you saying that measuring one datastructure cannot be done if there
exists a faster datastructure for the same purpose?

> Or how about this, I replace the tree data structure in OCaml with a recursive 
> closure? That won't even need to build the tree, there will be nothing to GC 
> and it will probably be orders of magnitude faster as a consequence. Even 
> better, it's subtle, and Isaac probably won't notice. ;-)

Or you could try to play nice so that whining wouldn't be required.

> For me, the propect of having Isaac throw a submission back in my face because 
> of a rule he just imagined is the strongest reason to not join in development 
> of the shootout. If people were free to submit their own crazy optimisations 
> in their favourite language then I think the shootout would be much more 
> popular (just look at the software texture mapping competitions in days of 
> old).

If you do something you suspect that people won't like, you can post to
the list first *asking* whether that is considered ok.

> Also, these problems with binarytrees will disappear if we follow Skaller's 
> advise for designing the tests. This test shouldn't state that you must use a 
> binary tree, it should simply require you to solve a problem that is best 
> attacked with a binary tree.

That sounds very hard. First we have a benchmark and people start
contributing to it. After half a year someone finds a faster algorithm
and now all the implementations need to be rewritten. This is especially
hard for the more exotic languages with few contributors and in the
meantime the languages with the most activic contributors seem to be
faster in the test.

- Einar Karttunen