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).
[ Parent
| on HN ]
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.