News for hackers. Stuff that matters.
Re:Robin Hood Hashing should be the default hash table imple... by jabl on Wednesday August 31, 2016 @02:35PM (#12400423)
Also, splay trees turn every read into several memory writes. Maybe not a good idea if the data structure is read by multiple threads (cacheline ownership bouncing back and forth all the time, rather than each core having it's own cached copy).
Re:Robin Hood Hashing should be the default hash table imple... by stcredzero on Thursday September 01, 2016 @01:57PM (#12407463)
Binary Trees are a bad idea from the POV of cache use, and from your analysis, Splay Trees are much worse. However, this has nothing to do with the generalized meta-strategy of continually reducing the amount of work it takes to fetch items. It has to do with why Binary Trees are bad from the POV of cache use.