Object churn in XORComparator

[zab]

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.

[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.

[zab]

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.