Zbr's days.

About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Sun, 14 May 2006

Compared Jenkins hash with XOR hash used in TCP socket selection code.

Tests were performed to determine how fair is hashed results distribution.
I've create simple TCP server simulator, which runs bound to single IP address and port. Simulator has 64k entry array, each entry contains hit counter. There were 100*64k runs, so ideal hash would result in 64k entries with 100 hits each.
There are two types of hashes used for tests - Jenkins hash: 

	u32 ports;
	unsigned int h;

	ports = lport;
	ports <<= 16;
	ports |= fport;

	h = jhash_2words(faddr, laddr, ports);
	h ^= h >> 16;
	h ^= h >> 8;

	return h;
and standard XOR hash, which is used in Linux TCP socket selection code:
	unsigned int h = (laddr ^ lport) ^ (faddr ^ fport);
	h ^= h >> 16;
	h ^= h >> 8;
	return h;

Tests were run for different set of remote addresses and ports:
  • random remote IP, random remote ports
  • random remote IP, linear remote ports
  • random remote IP, const remote ports
  • const remote IP, random remote ports
  • const remote IP, linear remote ports

Horizontal axis contains number of hits, and vertical one shows how many elements of array(64k elements total) have given hit counter.

For random remote IP address distribution and different remote source distribution (first three cases above) both XOR and Jenkins hashes show the same fairness.
But for constant remote IP (the latter two cases above) Jenkins hash shows strange artefacts, which are unacceptible for socket hash function.
So I decided to use simple one-dimensional array with XOR hash for netchannel hash table.

/devel/other :: Link / Comments ()