On 19/10/15 10:37, Florent Daigniere wrote: > On Sun, 2015-10-18 at 20:08 +0100, Matthew Toseland wrote: >> On 18/10/15 14:33, Florent Daigniere wrote: >>> 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/nod >>>>> e/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? >> Originally speed. Of course we can look up nodes by a Double - but we >> need to look for >= and <=, so it's more complicated, and I don't >> recall >> whether the API allows it cheaply (you used to have to create a bunch >> of >> objects e.g. iterators etc to get next-key-after-target). I agree >> that >> being able to do an exact match might be useful for some >> optimisations. >>> Any objection to that being changed? >> How about using a long? More bits than a double, at least for the >> vast >> majority of the space. And we can map 0.5 to 0, so sign isn't a big >> deal. >> >> Note that we use locations in both routing and swapping, so it might >> affect more code. > I've written some code overnight: > https://github.com/nextgens/fred/blob/optimize-closerpeer/test/freenet/ > node/LocationTest.java > https://github.com/nextgens/fred/blob/optimize-closerpeer/src/freenet/n > ode/Location.java > > It sort-of-works; the exclusion list is matched exactly as opposed to > modulo Double.MIN_VALUE... is that good enough? And the exclusion list is a set of peers' peers which we assume we've already routed to?
I still think you should separate optimising routing (trees of all locations etc, long's instead of doubles) from changing behaviour (ignoring FOAF peers if they were also the peers of a node we've already visited). Does our FOAF locations-of-peers announcement include nodes which are backed off for long periods? Nodes which are disconnected? I guess there's no real security issue at least - FOAF can already capture traffic easily, and solutions to this rely on either arbitrary proportional thresholds or clustering - therefore probably not applicable for long links/local traffic. > Florent
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
