strange array performance

[tor]

I was happily coding on my little avl tree library.

The internal nodes look like this:

type Node{K, V} <: Avl{K, V}

     child :: Array{Avl{K, V}, 1}

     key :: K

     value :: V

     balance :: Int8

end

Everything seemed natural and reasonable to me.

I keep the children in a length 2 array so that I can select one with a bool:

function insert{K, V}(node :: Node{K, V}, key :: K, value :: V)

     side = (key > node.key) + 1

     node.child[side] = insert(node.child[side], key, value)

     … fix balance factors and return

end

This is for two reasons. The good reason is it makes the code much shorter. I need only half as much rotation and balance-factor fixing code. This means less debugging and maintainance. The other reason is to avoid one conditional branch each time a child is accessed.

However, I just recently discovered that code like this seems to be rather expensive. Inserting 100 values in a tree takes a noticable amount of time. 1000 elements is enough to choke up the terminal.

The question is WHY? Is this a bug? If not, what are these things you call arrays? How are they implemented?

The weird thing is that the slow code worked correctly. The objects in the arrays behaved just like references. E.g. one can insert, delete and rotate nodes. That wouldn't be possible if for instance the objects were pasted into the array as data (while copying stuff around to make space). And if they were, even that would hardly explain the awful performance.

If I change the code to this:

type Node{K, V} <: Avl{K, V}

     left :: Avl,

     right :: Avl

    …

end

the performance becomes as expected (very acceptable). But then I have to rewrite and practically double the size of the core routines.

What I want is a way to store two pointers to trees in a type (like one would in c), so that I can select between them with a variable in constant time (preferably without conditional branching).

Is there a way to do that? Tuples can't do it, because you can't assign to them.

[Jeff Bezanson]

If you send a pointer to the full code I will investigate. There
shouldn't be a major problem with arrays, except that this
representation entails an extra object per node. Each array will take
up around 64 bytes on a 64-bit system, but doubling the number of
objects is never good.

> --
>
>
>

[Tor Gausen]

I'm sorry, I was wrong (how very unusual for me). So far I've only played around with small trees while debugging. When I tried a big one, the terminal (konsole plug-in for kate editor) had problems printing it... :-P Why must I always be so rash?

Remembering not to print anything to the screen, things run a lot faster, yet not extremely fast. Before any epcial optimization it takes about 12 seconds to insert a million integer pairs.

I realize of course there is a branch or two when bounds checking the array, but I hoped this could be fixed somehow later. My plan is to eventually remove the recursion and as many as possible of the conditional branches. I think one should be left with 2-3 per iteration when inserting or deleting.

Here is a pastbin link anyway.

http://pastebin.com/1qtjGhne

Oh, and sorryyy...

2012/7/28 Jeff Bezanson <jeff.b...@gmail.com>

--

[Jeff Bezanson]

No problem, printing issues have caused confusion many times. Branches can matter in tight inner loops, but allocating memory is definitely worse. In some cases bounds checks have very little overhead.

--
 
 
 

[Tor Gausen]

Yea, bounds checks are always predictable, except that one time they are not, and then it doesn't matter much, because the program just crashed. But when working itself down a binary tree I cannot imagine a cpu can have much  chance guessing left from right or whether a rotation will happen or not.
And yes, all those little allocations are likely to dominate when inserting.  

2012/7/28 Jeff Bezanson <jeff.b...@gmail.com>

[Stefan Karpinski]

On Fri, Jul 27, 2012 at 10:36 PM, Tor Gausen <torg...@gmail.com> wrote:

Here is a pastbin link anyway.

http://pastebin.com/1qtjGhne

Btw, gist is a GitHub service that's similar to pastebin and has support for the Julia file type since GitHub itself support Julia syntax highlighting. E.g. here's a gist of your code:

https://gist.github.com/3194647