On 10-10-15 21:01, nextg...@freenetproject.org wrote: > Oi! > > Given > https://github.com/freenet/fred/blob/next/src/freenet/node/PeerManager.java#L1049 > > We seem to get our peers location and their peer's location... > Iterate over the whole lot (150^2 entries max) > ... > And then for each of them, ensure that they haven't been routed to before by > iterating over a list of locations we've already routed to (18 is the max HTL) > ... > That's 18*150^2 => 405k iterations in the worst case ... on the hot-path > (each request we route will go through it)!
Nice find! One more thing: you forgot the recentlyFailed case, where it recurses twice (line 1173 and 1183), leading to a total of 1.2M iterations worst case (however this case is extremely unlikely to occur). > It seems very naive. > > How can we do better? Locations are double, what's the best data-structure > here? > I'm rusty: is a TreeMap with a custom comparator (NavigableMap) what we want? At least keeping FOAF peers locations sorted would allow for binary search, i.e. O(log n) instead of O(n) search, at the cost of an initial O(n log n) sort. That would however require reworking PeerNode.getPeersLocation() to return (and maintain) a sorted array. If one would then also keep the routedTo (of size m) sorted by location, we can find the FOAF (assuming peer count n for ourself and all of our peers) closest to the target location not in routedTo in O(log n + m) time for each of our peers, and when done intelligently, find our peer with the FOAF closest to the target O(n log n + nm + m log m) for *all* of our peers. That would bring the iteration count down around 100-fold from the current situation. For any further optimization, the hardest part would be to figure out all the corner cases present in the current spaghetti. ☺ — Bert
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
