[Olsr-dev] Improving SPF with binary heaps

[Diogo Gonçalves]

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

On the basis of my study, binary heap is near to avl in small/medium-sized
mesh, however, from 800 nodes heap significantly outperform avl. My tests
on core weren't enough to prove this, I need to test it in a bigger mesh
network. I'll try to run core on one of the computers at my college's
computer lab.

I used valgrind/callgrind to get the functions' cpu cycles and I did a
graph with the cycles estimation per call. I can attach the callgrind files
if you want.

Best regards.

2015-10-22 4:55 GMT-02:00 Henning Rogge <(spam-protected)>:

> Hi,
>
> any feedback about the binary heap version of olsrd2?
>
> Henning
>
> On Fri, Oct 9, 2015 at 4:32 PM, Diogo Gonçalves
> <(spam-protected)> wrote:
> > Hi,
> >
> > Thank you so much, olsrd2 is running as I want.
> >
> > I'm starting the performance tests now.
> >
> > 2015-10-09 3:57 GMT-03:00 Henning Rogge <(spam-protected)>:
> >>
> >> On Fri, Oct 9, 2015 at 6:44 AM, Diogo Gonçalves
> >> <(spam-protected)> wrote:
> >> > Hi,
> >> >
> >> > Olsrd2 seems run but nothing is printed at terminal. Is it OK?
> >>
> >> Yes, default setting is only to print warnings to stderr... running
> >> quiet is expected unless you activate some debug/info logging sources.
> >>
> >> Henning
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20151026/270ab5dd/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: binheap_avl_core_graph.pdf
Type: application/pdf
Size: 5545 bytes
Desc: not available
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20151026/270ab5dd/attachment.pdf>