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