On Mon, 2015-10-19 at 14:11 +0100, Matthew Toseland wrote: > 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.h > > > > tml > > > > > > > > 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/free > > net/ > > node/LocationTest.java > > https://github.com/nextgens/fred/blob/optimize-closerpeer/src/freen > > et/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? >
Yeah; that and both our current location and the previous one. > 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). That's what I'm trying to do here... I haven't done the last level of optimization where we combine all of them into a single structure (instead of iterating on each peer). It's still O(n)+ Here's how it's wired-in https://github.com/nextgens/fred/blob/optimize-closerpeer/src/freenet/n ode/PeerManager.java#L1054 As you can see, the logic is preserved, with the exception of how we handle what's in the exclude list... What I'm wondering is whether that new behaviour is fine or not. Do we need to compare what's in the exclude list modulo Double.MIN_VALUE (old behaviour) or is an exact match fine (new behaviour)? If it's not I just need more code to make it mirror the old one. > Does our FOAF locations-of-peers announcement include nodes > which are backed off for long periods? Nodes which are disconnected? It's complicated. There are several checks before and after; I'm not sure what the behaviour should be. > 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. It's clearly not about security here. Florent _______________________________________________ Devl mailing list Devl@freenetproject.org https://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
