[Olsr-dev] Improving SPF with binary heaps

[Diogo Gonçalves]

you are right, the remove operation is more expensive on heap than avl.

Removes the min node (leftmost) of an avl with n nodes can result in 0, 1,
2 ... or log n rotations. Removes the min node (root) of the heap always
result in log n rotations.

I can optimize the extract min operation of my heap, I wrote the code to be
clean and the performance may have been a little bit decreased.

The question is that insert operation is executed more times than remove on
dijkstra. The relax operation (_insert_into_working_tree) of avl can be a
avl_remove and a avl_insert. The relax on heap is just one, it has it own
relax operation. In those networks the difference of insert operation
between the priority queues is small but in large networks the avl
performance goes down.

2015-10-26 5:27 GMT-02:00 Henning Rogge <(spam-protected)>:

> On Mon, Oct 26, 2015 at 5:27 AM, Diogo Gonçalves
> <(spam-protected)> wrote:
> > Hi,
> >
> > I did some tests on core and I got a initial result by now. I built on
> core
> > a mesh network with 50, 100 and 150 nodes and 100, 200 and 300 links,
> > respectively. Unfortunately my hardware isn't able to run more nodes.
> >
> > The graph (attached) shows, as expected, that avl is a little bit better
> > than heap in those networks
>
> If I read this graph right, the remove_min operation of the HEAP is
> much more expensive than the remove operation of the AVL tree.
>
> And the "insert" operation of the AVL tree is only a little bit more
> expensive than the one of the HEAP.
>
> This doesn't look good, do you have an idea why "remove" is this expensive?
>
> Henning
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20151026/46a00d7f/attachment.html>