Opened 7 years ago

Closed 7 years ago

#658 closed enhancement (fixed)

Object churn in XORComparator

Reported by: zab Owned by: zzz
Priority: trivial Milestone: 0.9.1
Component: router/netdb Version: 0.9
Keywords: garbage collection allocation memory Cc:
Parent Tickets:

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 7 years ago by zzz

  • Milestone set to 0.9.1
  • Status changed from new to accepted

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.

comment:2 follow-up: Changed 7 years ago by 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:3 in reply to: ↑ 2 Changed 7 years ago by 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.

comment:4 Changed 7 years ago by 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.

comment:5 Changed 7 years ago by zzz

  • Resolution set to fixed
  • Status changed from accepted to closed

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

Note: See TracTickets for help on using tickets.