Opened 9 years ago
Closed 9 years ago
#658 closed enhancement (fixed)
Object churn in XORComparator
Reported by: | Zlatin Balevsky | Owned by: | zzz |
---|---|---|---|
Priority: | trivial | Milestone: | 0.9.1 |
Component: | router/netdb | Version: | 0.9 |
Keywords: | garbage collection allocation memory | Cc: | |
Parent Tickets: | Sensitive: | no |
Description
Profiling my node for several hours found that ~18% of the garbage collected objects are created by the XORComparator. It's probably worse for large, busy nodes. The following suggestion fixes that:
# # old_revision [5b24a07e8a843d03ea45e664c59b93937c5efc42] # # patch "router/java/src/net/i2p/router/networkdb/kademlia/XORComparator.java" # from [69b66a2b5abeb85c7e837dd19f96dba6374172b3] # to [dbbf214e3f60c5e1b177ee59ced463e870332bb7] # ============================================================ --- router/java/src/net/i2p/router/networkdb/kademlia/XORComparator.java 69b66a2b5abeb85c7e837dd19f96dba6374172b3 +++ router/java/src/net/i2p/router/networkdb/kademlia/XORComparator.java dbbf214e3f60c5e1b177ee59ced463e870332bb7 @@ -11,17 +11,27 @@ class XORComparator implements Comparato */ class XORComparator implements Comparator<Hash> { private final byte[] _base; + private final byte[] _lhsTemp, _rhsTemp; /** * @param target key to compare distances with */ public XORComparator(Hash target) { _base = target.getData(); + _lhsTemp = new byte[_base.length]; + _rhsTemp = new byte[_base.length]; } public int compare(Hash lhs, Hash rhs) { - byte lhsDelta[] = DataHelper.xor(lhs.getData(), _base); - byte rhsDelta[] = DataHelper.xor(rhs.getData(), _base); - return DataHelper.compareTo(lhsDelta, rhsDelta); + byte [] lhsData = lhs.getData(); + byte [] rhsData = rhs.getData(); + if (lhsData == null || rhsData == null || + ( lhsData.length != rhsData.length) || + ( lhsData.length != _base.length)) + return DataHelper.compareTo(lhsData,rhsData); + + DataHelper.xor(lhsData, 0, _base, 0, _lhsTemp, 0, _lhsTemp.length); + DataHelper.xor(rhsData, 0, _base, 0, _rhsTemp, 0, _rhsTemp.length); + return DataHelper.compareTo(_lhsTemp, _rhsTemp); } }
Subtickets
Change History (5)
comment:1 Changed 9 years ago by
Milestone: | → 0.9.1 |
---|---|
Status: | new → accepted |
comment:2 follow-up: 3 Changed 9 years ago by
We used this datastructure in LimeWire to store our Kademlia nodes and perform lookups: https://code.google.com/p/patricia-trie/
It works very well for IP filter as well.
Right now it's Apache 2.0 although we were GPLv2.. I guess Roger decided he could change the license on his own. Oh well, assume it's Apache if that works better.
comment:3 Changed 9 years ago by
I just checked with them, they did officially "donate" it with the Apache license. So it's all clear to use as Apache 2.0.
Replying to zab:
We used this datastructure in LimeWire to store our Kademlia nodes and perform lookups: https://code.google.com/p/patricia-trie/
It works very well for IP filter as well.
Right now it's Apache 2.0 although we were GPLv2.. I guess Roger decided he could change the license on his own. Oh well, assume it's Apache if that works better.
comment:4 Changed 9 years ago by
Interesting. That looks like nice code.
As of now, my year-long plan for Kad is as follows:
1) Write a BEP 5 (DHT) implementation for i2psnark with a 'fake' kad (hash map)
2) Pull the netdb kad out into a separate lib, rewrite it, make it generic for SHA256/SHA1
3) plug the new kad into dht snark, replacing the hashmap
4) merge dht snark into trunk
5) test, bugfixes, enable by default, …
6) plug the new kad into netdb
7) use the new kad routing table instead of sorting the floodfills all the time
8) merge into trunk
1-3 are done and 4-8 will probably take another year
all that subject to change, and of course research of alternatives like patricia trie.
comment:5 Changed 9 years ago by
Resolution: | → fixed |
---|---|
Status: | accepted → closed |
XORComparator fixed up similar to the patch above, after 0.9-21 but didn't bother bumping to -22.
I like it.
Sadly, it's a symptom of a much larger problem, that we sort the netdb way too much since we don't use a real Kademlia routing table. But a fix for that is several releases out.
In the meantime I'll happily fix up XORComparator as you've suggested.