4 ms·
Found the CMU grad! I think this is very different from a splay tree, though. Open-address tables take advantage of the cache by removing linked lists from th
by dlbucci 10y ago
Found the CMU grad! I think this is very different from a splay tree, though. Open-address tables take advantage of the cache by removing linked lists from the data structure, which is why I think they tend to have good real-world performance.
Splay trees, on the other hand, can only really be implemented using pointers and a linked structure (splaying a tree that's been implemented with an array sounds absolutely miserable). They don't have good cache usage, which is why they generally perform poorly outside of big-O notation.
- stcredzero 10y agoFound the CMU grad! Nope! Didn't go there. I think this is very different from a splay tree, though. Open-address tables take advantage of the cache Well, duh! That's why I said it's analogous. Of course something built on an array is likely going to have better cache behavior! My point is that you're using amortized work to shorten the average amount of work it takes to retrieve your data. My point was to talk about the generalized meta-strategy. Lose a point for poor reading comprehension because you so-badly-wanted-to-correct-someone.
- AustinScript 10y agoDial it back man.
- jabl 10y agoAlso, 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).
- stcredzero 10y agoBinary 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.