fred
fred copied to clipboard
freenet
Eleriseth pending keys
[email protected] posted this patch set:
This is a respin of forgotten two year old branch, pending-keys (6b30ce888c66c9ecca9e019d870559950e2df5c1).
After two years of keeping using my variant, I finally decided that toad design was better :-), dropped my customized hashmap, and rewritten/rebased/reordered/shuffled toad branch on top of 1468.
Let's rehash it from the start:
When running massive USK subscription, and I noticed interesting entry in logs:
(freenet.client.async.KeyListenerTracker,
(XXX), NORMAL): Removed pending keys from freenet.client.async.KeyListenerTracker@XXX:SSK : size now 23837 : freenet.client.async.SingleKeyListener@XXX KeyListenerTracker keeps all key listeners on ArrayList, and search it linearly (O(n)) on each added/removed/tripped-on-passing-key.
This worked well with "few big file downloaders (each splitfile uses single KeyListener to watch over all contained keys and uses bloom filter to pre-select "interesting" ones) and some dozens bookmarks subscriptions", but deals very badly with more massive USK (or other ULPR) subscriptions case, when there are thousands of individual listeners, and each passing key triggers linear search over huge KeyListener array.
This patch series replaces linear array with better structures for single-key listeners.
Notes:
all multi-key (splitfile) listeners are kept in keyListener ArrayList, as before;
if KeyListener and HasKeyListeners watch for a single route key (for CHK) or pubkey hash (for SSK), they should provide getWantedKey() method.
Requirements:
a) KeyListener.getWantedKey() and corresponding KeyListener.getHasKeyListener().getWantedKey() must return same/equal (as in "Arrays.equal") arrays (including null==null case).
b) getWantedKey() must return same/equal arrays (including null case) when called multiple times for given {Has,}KeyListener object.
(idea about adding HasKeyListener.getWantedKey() was taken from toad's 8778bc3126fb4f8d7d6cd6b07680982e5613d615 and integrated to initial patch, to avoid dancing forward and backward over same code).
Patch series is run-tested and works well for me (though, of course, I could've missed something, my testing is not really comprehensive, etc; careful review suggested).
This change set is duplicating implementation logic of a multi-value map all over the place. I suggest to move that logic to a separate class (for it to be reusable), or at least an inner class of the KeyListenerTracker (for keeping the code simple).
What I still don't get after reading the code, is why we'd want to store CHKs in a salted HashMap and SSKs in an unsalted TreeMap. The latter seems superior here, given it is collision-free and it actually shrinks when items are removed.
Apart from the remarks above and the comments in the code, the gist of this looks rather sensible to me. Note that these commits don't seem to comply with the coding standards.
From Eleriseth (re duplicating logic): Exactly same trick with T/[] was used everywhere in freenet, and for a good reason (memory efficiency; given the number of KeyListener required for full WebOfTrust and Sone subscription is quite large, it applies here too). Generalizing and replacing them does not belong to this patch series.
I think the replies from Eleriseth address all comments, so from my side this is ready to merge.
@bertm do you agree with the argumentation (“does not belong in this patch”)?
My usual stance would be "you touch it, you fix it", but I think we can agree to disagree on this one. I can live with the proposed changes from a functional point of view, so lacking volunteers to address my comments, this has my ack.
the conflicts shouldn’t be too hard to solve, but require more testing than I could do in the time slot I have for that right now (it’s mostly just copying for loops into additional checks). It’s not obvious enough, though, that I would attempt it without knowing the reasons for the changes on both sides.