On Wednesday 04 April 2007 17:55, Seth Arnold wrote: > I understand part of the reason is that the 2.6 kernel has far more > datastructures indexed by hash tables. The hash tables waste a > certain amount of memory, and may be sized incorrectly for your > machine. This should speed up the kernel on moderate-sized machines, > but both large and small machines could use more effective > datastructures.
Done right and used where appropriate, there are few indexing schemes more efficient than hashing. The classic mistake made by most implementors, however, is to use chaining to handle hash collisions. This represents a waste of memory. The better approach is double-hashing (using a secondary hash to skip entries when a collision occurs) and a hash table size that is a prime number. Then take the memory that would have been used for link storage in chained collision handling and allocate it to the hash table itself. I don't know how the Linux kernel implements hashing. > .... -- To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
