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