[Networkit] [review][patch] vertex diameter computation

Maximilian Vogel maximilian.vogel at student.kit.edu
Thu Sep 24 10:41:26 CEST 2015


Hi,

the current implementation as I see it[1] is purely sequential, 
therefore no races can occur.

I've compared the results and performance of the current state and your 
patch (but only on one graph with about 1.6M nodes 11M edges).
The results were the same, but Dev took about 130ms while your patch 
needed 350ms.

Your patch might result in more BFS searches than necessary (imagine the 
first BFS visits all nodes) and also introduces races as 
std::vector<bool> is not thread-safe when there are write accesses. I 
think it should be left as it is.

Best,
Max

[1]: 
https://algohub.iti.kit.edu/parco/NetworKit/NetworKit/files/9e0ca8a29cf191f437d8dc463dfb545e09a0452d/networkit/cpp/distance/Diameter.cpp#L192


On 24.09.2015 02:30, Matteo Riondato wrote:
> Hi all,
>
> The attached patch is meant to solve a potential race in writing to vd. Specifically, as the code is now in Dev, the following race can happen:
>
> Assume that at some point vd is 20, thread1 has maxDist + maxDist2 equal to 22, and thread2 has maxDist + maxDist2 equal to 21.
>
> Both thread1 and thread2 enter the block guarded by "if (maxDist + maxDist2 > vd)”.
> At this point, we may have that thread1 updates vd to 22, and then thread2 updates vd to 21.
> Hence the value stored in vd is not correct.
>
> The patch solve the issue by using a reduction on vd.
>
> I haven’t seen the race in practice, but I believe the patch is needed for correctness.
>
> I’d love a review before I commit it to Dev. Thanks in advance.
>
> Matteo
>
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150924/4915d4d3/attachment.html>


More information about the NetworKit mailing list