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/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? 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. > Florent
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
