Object churn in XORComparator

[Zlatin Balevsky]

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);
     }
 }

[zzz]

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.

[Zlatin Balevsky]

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.

[Zlatin Balevsky]

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.

[zzz]

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.

[zzz]

XORComparator fixed up similar to the patch above, after 0.9-21 but didn't bother bumping to -22.