`On Fri, Mar 08, 2002 at 01:22:39AM +0100, Andrea Arcangeli wrote:> -	"i" is the random not predictable input> -	"i" is generated by dropping the non random bits of the "page"> 		with a cute trick that drops the bit with> 		a shiftright with an immediate argument, it's not a> 		division so it's faster it could been> 		"page/sizeof(struct page)" but it would been slower> -	s(i) takes into account not just the last "wait_table->shift" bytes> 	of the random information in "i", but also the next "shift"> 	bytes, so it's more random even if some of those lower or higher> 	bits is generating patterns for whatever reason> -	finally you mask out the resulting random information s(i) with> 	size-1, so you fit into the wait_table->head memory.> The result is that it exploits most of the random input, and physically> consecutive pages are liekly to use the same cacheline in case there is> some pattern. That looks a good algorithm to me.I'm sorry, this reasoning is too flawed to address in detail. I'm aprogrammer, not a schoolteacher. I'll drop a hint: "randomness" is notthe right word to use. The way to make a meaningful statement is astatistical measurement of how close the resulting bucket distributionsare to uniform, as uniform distributions across buckets minimize collisions.I suggest the usual chi^2 and Kolmogorov-Smirnov (and variants) tests.The results of these tests are simple: they will compute theprobability that the difference between the measured distribution and atrue uniform distribution could not have occurred by chance (i.e.whether its difference from the uniform distribution is statisticallysignificant). With these things in hand you should be able to make moremeaningful assertions about your hashing algorithms.Cheers,BillP.S.:	The quality (or lack thereof) of this hash function is already	visible in histograms of the pagecache bucket distribution on	larger systems. Statistical measurements of its quality reflect	this very clearly as well. Someone needs to move the stable out	of the Sahara and closer to a lake.	http://www.samba.org/~anton/linux/pagecache/pagecache_before.png	is a histogram of the pagecache hash function's bucket distribution	on an SMP ppc64 machine after some benchmark run.	http://www.samba.org/~anton/linux/pagecache/pagecache_after.png	has a histogram of a Fibonacci hashing hash function's bucket	distribution on the same machine after an identical benchmark run.	(There is more to come from the hash table analysis front.)-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`