[Mono-bugs] [Bug 59537][Nor] Changed - improve NameTable performance

[bugzilla-daemon@bugzilla.ximian.com]

Please do not reply to this email- if you want to comment on the bug, go to the
URL shown below and enter your comments there.

Changed by mono@bitfurnace.com.

http://bugzilla.ximian.com/show_bug.cgi?id=59537

--- shadow/59537	2004-09-16 01:53:08.000000000 -0400
+++ shadow/59537.tmp.28943	2004-09-16 02:01:38.000000000 -0400
@@ -502,6 +502,21 @@
 the very same randomness will make those cases exceedingly unlikely.
 In practise, linear probing with random hash multipliers is extremely
 fast and the worst case results are not seen.
 
 If worst-case results are a worry, we can rehash with a new multiplier
  when exceeding long probe lengths are encountered.
+
+------- Additional Comments From mono@bitfurnace.com  2004-09-16 02:01 -------
+Atsushi, I havent tried the unit tests (nor was I aware of them). I'll
+look into it and post here again when I can make the code pass the tests.
+
+The key to the performance improvement, in my opinion, is the memory
+efficiency of my approach. The main hashtable is an array of structs,
+each with only two fields. Everything is nice and compact and
+co-located in memory. A linear probing algorithm means that only
+consecutive memory locations need to be scanned to find matching
+hashtable entries. I found that my test was slower at 50% occupancy
+than 66% occupancy, so Im fairly sure that memory efficiency plays a role.
+
+In general less space equals more speed on modern processors, where a
+level 2 cache miss can result in 1000 instruction cycles being lost.