On 18-10-15 21:08, 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/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
Our locations should in the end use the full 256 bit locations or an exact prefix of that, immediately implying a circular keyspace (add one to the max, end up in 0 again). There is no need to use BigDecimals here, locations don't get arbitrarily large and we don't need to do arithmetic except for change / distance calculation. Apart from that, what's the idea behind the Double.MIN_VALUE after all? If that's intended to capture minuscule calculation errors, it won't work: Double.MIN_VALUE is somewhere around 1e-150, while the distance between two consecutive double values in the range [0.5, 1.0) is somewhere around 1e-16 (or equal to Math.ulp(0.5)), i.e. Math.abs(x - y) where x and y are in the range of [0.5, 1.0) will never return a value as small as Double.MIN_VALUE. Also, Math.abs is guaranteed never to return negative zero, so checking for that would be pointless too. >> >> 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. Why not map the range [0.0, 1.0) to [0L, 0xFFFFFFFFFFFFFFFFL]? Then we'd just use a 64 bit prefix of the 256 bit location. Just ignore the signedness of the longs, we don't do arbitrary arithmetic anyhow. There still is my location-as-object branch[0] that rewrites the entire location logic into an object-oriented approach where locations are immutable objects. The branch is somewhat outdated, but you get the idea. Once that's in, it would be trivial to switch implementations to actually use any internal representation. [0] https://github.com/freenet/fred/compare/next...bertm:location-as-object — Bert
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
