On Tue, 2015-10-13 at 22:26 +0200, Bert Massop wrote: > On 10-10-15 21:01, nextg...@freenetproject.org wrote: > > Oi! > > > > Given https://github.com/freenet/fred/blob/next/src/freenet/node/Pe > > erManager.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. ☺ >
That'd work nicely if we weren't doing the operations modulo Double.MIN_VALUE. Is there any reason why our locations doubles and not BigDecimals? http://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html Toad? Any objection to that being changed? Florent
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
