[Olsr-dev] Improving SPF with binary heaps
Diogo Gonçalves
(spam-protected)
Fri Aug 21 02:30:27 CEST 2015
Hi,
I'm finishing my patch, I'll send it to you soon.
For now, I just have some issues about how to measure the performance of
the priority queues in olsrd. I'm using olsr switch to test my code and I
did not find a good way to scale my network and measure the performance. I
have some results outside the olsrd(see attachments) using kcachegrind and
other tools to do this and now I'm trying to measure the performance into
the olsrd too.
Is olsr switch the best way to do this?
2015-08-20 6:24 GMT-03:00 Henning Rogge <(spam-protected)>:
> Hi,
>
> any status update on your work?
>
> We are still waiting for the initial merge of your code into the new
> branch.
>
> Henning Rogge
>
>
> On Mon, Aug 3, 2015 at 12:25 PM, Ferry Huberts <(spam-protected)> wrote:
>
>> 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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150820/35ca8885/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: cycles_in_SPF.pdf
Type: application/pdf
Size: 6461 bytes
Desc: not available
URL: <http://lists.olsr.org/pipermail/olsr-dev/attachments/20150820/35ca8885/attachment.pdf>
More information about the Olsr-dev
mailing list