[Olsr-dev] Improving SPF with binary heaps
Ferry Huberts
(spam-protected)
Mon Aug 3 12:25:18 CEST 2015
Ok.
There now is a branch 'dijkstra-binary-heap' on the olsrd repo.
The setting in the configuration file is 'DijkstraBinaryHeap', which
adjusts the setting 'olsr_cnf->dijkstra_binary_heap' (which is false by
default).
Please follow the plan and when done, notify us.
And I still want to see performance numbers to justify pulling in these
changes to the core of olsrd.
Ferry
On 01/08/15 01:52, Diogo Gonçalves wrote:
> Hi,
>
> Thanks for trusting in my work.
> This plan is fine to me, I will work on it. I just suggest to rename the
> configuration setting 'dijkstraHeapBinary' to 'dijkstraBinaryHeap'.
>
> Diogo.
>
> 2015-07-31 7:43 GMT-03:00 Ferry Huberts <(spam-protected)
> <mailto:(spam-protected)>>:
>
> Ok guys.
>
> Henning and I talked about this and we're willing to merge the work.
>
> However, don't cheer to soon because we do have a few demands that
> must be met before we actually merge it.
>
> The plan:
> 1- I'll create a new branch 'dijkstra-binary-heap' next week
> 2- On that branch I'll put patches that create a new configuration
> setting 'dijkstraHeapBinary'.
> 3- You will rebase your branch on the new branch.
> 4- You will rework your patches such that:
> - they are reviewable (see )
> - the configuration setting 'dijkstraHeapBinary' determines
> whether the current heap code is used or your code.
>
> If your rework is complete, we'll review it again.
>
>
> How is that for a plan?
> Please let us know.
>
>
> Ferry & Henning
>
> PS. Henning would like to pick up your work for olsrd v2 once complete.
>
> On 31/07/15 08:48, Diogo Gonçalves wrote:
>
> ohh, you are right, thank you!
>
> If all node's pointers are NULL, the node isn't in the heap, but
> there
> is one special case for root node, this node doesn't point to
> another one.
>
> I already fixed it in the function. Thank you again.
>
> Diogo
>
> 2015-07-31 3:02 GMT-03:00 Henning Rogge <(spam-protected)
> <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>>:
>
> No,
>
> I think we are mostly fine...
>
> Just a last question about the new "heap_is_node_added"
> inline... are
> you sure about the second return command? I think it will
> only return
> "true" if all three fields in the heap are NULL.
>
> What are you trying to test, are ALL of these fields
> initialized
> normally or just a few of them?
>
> If all of them are !NULL I would suggest replacing the if()
> condition
> and the both return with:
> > return node && node->parent && node->left && node->right;
>
> if just one of them should be !NULL, maybe this will work:
> > return node && (node->parent || node->left || node->right);
>
> Henning
>
> On Fri, Jul 31, 2015 at 7:55 AM, Diogo Gonçalves
> <(spam-protected)
> <mailto:(spam-protected)>
> <mailto:(spam-protected)
> <mailto:(spam-protected)>>> wrote:
> > Hi,
> >
> > I updated my binary heap lib in the olsrd [1] with some
> static
> functions. Is
> > there something else that I can do?
> >
> > [1]https://github.com/diogomg/olsrd
> >
> > 2015-07-30 9:22 GMT-03:00 Henning Rogge
> <(spam-protected) <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>>:
> >>
> >> Hi,
> >>
> >> I lost a bit track of this while away at the IETF in
> Prague...
> >>
> >> Can you send a new patch with the current version of
> the code to the
> >> list? I think we can clean up the rest inside the
> olsr.org <http://olsr.org>
> <http://olsr.org> repository.
> >>
> >> Is the github code still "up to date" in terms of the
> head.[ch]
> code?
> >> If yes I will give it a try to use it in the olsrd2
> Dijkstra too.
> >>
> >> Henning Rogge
> >>
> >> On Tue, Jul 14, 2015 at 9:27 PM, Henning Rogge
> <(spam-protected) <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>> wrote:
> >> > Yes,
> >> >
> >> > that looks better... always a good idea to keep the
> internal
> functions
> >> > hidden.
> >> >
> >> > Henning
> >> >
> >> > On Tue, Jul 14, 2015 at 5:19 PM, Diogo Gonçalves
> >> > <(spam-protected)
> <mailto:(spam-protected)>
> <mailto:(spam-protected)
> <mailto:(spam-protected)>>> wrote:
> >> >> HI,
> >> >>
> >> >> I cleaned up my heap.h[1], leaving only functions
> for the
> users, as you
> >> >> asked me. I hope i'm on right way but I know that
> there are
> >> >> improvements to
> >> >> do, so if you have something else to suggest you can
> ask me.
> >> >>
> >> >>
> >> >> [1] https://github.com/diogomg/olsrd
> >> >>
> >> >> 2015-07-13 14:10 GMT-03:00 Henning Rogge
> <(spam-protected) <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>>:
> >> >>>
> >> >>> Hi,
> >> >>>
> >> >>> since we have some people to ask when we have questions
> about it, I
> >> >>> think it will be good to merge.
> >> >>>
> >> >>> But I would also like someone of you to look after
> it when I
> build it
> >> >>> into the olsrd2 dijkstra. If you can clean up the
> "heap.h"
> file so
> >> >>> that it only contains the necessary functions for
> an user
> (and not the
> >> >>> internal ones), it should be easy to supply a few good
> accessor macros
> >> >>> (similar to list.h and avl.h in OONF).
> >> >>>
> >> >>> Henning
> >> >>>
> >> >>> On Mon, Jul 13, 2015 at 7:07 PM, Saulo Queiroz
> <(spam-protected) <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>>
> >> >>> wrote:
> >> >>> > Ferry and Henning, ok.
> >> >>> > We have just to care about real routing metrics,
> like ETX
> >> >>> > since the priority queue will be arranged based
> on such
> >> >>> > real value. What you think?
> >> >>> >
> >> >>> >
> >> >>> > On 13 July 2015 at 13:47, Henning Rogge
> <(spam-protected) <mailto:(spam-protected)>
> <mailto:(spam-protected) <mailto:(spam-protected)>>> wrote:
> >> >>> >>
> >> >>> >> On Mon, Jul 13, 2015 at 6:01 PM, Saulo Queiroz
> >> >>> >> <(spam-protected)
> <mailto:(spam-protected)> <mailto:(spam-protected)
> <mailto:(spam-protected)>>>
> >> >>> >> wrote:
> >> >>> >> > Yes,
> >> >>> >> > something like 1/priority_value (for instance)
> might work.
> >> >>> >>
> >> >>> >> I thought more about (UINT32_MAX-value)
> >> >>> >>
> >> >>> >> Henning
> >> >>> >
> >> >>> >
> >> >>> >
> >> >>> >
> >> >>> > --
> >> >>> > Saulo Jorge bq
> >> >>> > -
> >> >>> > "In theory, there is no difference between
> practice and
> theory, in
> >> >>> > practice
> >> >>> > there is"
> >> >>> > -- Someone
> >> >>
> >> >>
> >
> >
>
>
>
>
>
> --
> Ferry Huberts
>
>
--
Ferry Huberts
More information about the Olsr-dev
mailing list