| |||||||||||||
Worst case performance and "impossibly unlikely" conditionsWorst case performance and "impossibly unlikely" conditionsPosted Jan 12, 2012 1:26 UTC (Thu) by cmccabe (guest, #60281)In reply to: Worst case performance and "impossibly unlikely" conditions by nix Parent article: Denial of service via hash collisions
Based on some things I've read, splay trees may not be the best way to go on modern hardware. The problem is that they turn what would normally be read-only operations into read+write operations. That means cache lines get dirty, If your program has multiple threads working on multiple CPUs, the overhead of cache line invalidation can really start to hurt.
There was a post about this in 2010 on the freebsd list:
Basically, it was a great idea in the 1980s, but I'm not sure how well it works these days.
(Log in to post comments)
Worst case performance and "impossibly unlikely" conditions Posted Jan 12, 2012 1:52 UTC (Thu) by wahern (subscriber, #37304) [Link] It's easy enough to test. NetBSD, FreeBSD, and OpenBSD all have <sys/tree.h>, containing preprocessor based splay and red-black tree implementations which, other than the algorithm, are implemented almost identically. It's self contained, so you can download the single header file. man 3 tree for the API. Those kernels tend to rely on RB trees fairly heavily. OpenBSD uses <sys/tree.h> for almost everything, including PF and the VM. It's perhaps not as fast as the radix, etc., trees in Linux, but it's simple and is unlikely to create any surprises in the future. I wrote a left-leaning RB tree variant which is a drop-in replacement, except the prefix is LLRB instead of RB. LLRBs have a simpler algorithm, so it's easier to hack on if necessary.
Worst case performance and "impossibly unlikely" conditions Posted Jan 12, 2012 21:42 UTC (Thu) by cmccabe (guest, #60281) [Link]
Yeah, sys/tree.h is useful. I tend to avoid the splay tree parts, though. To be fair, I've been too lazy to actually benchmark the two implementations.
Worst case performance and "impossibly unlikely" conditions Posted Jan 13, 2012 13:52 UTC (Fri) by nix (subscriber, #2304) [Link]
Indeed that is a downside. If your hash is often accessed from many different threads, and particularly if it is often randomly accessed, a splay tree may be a bad choice of implementation. However, if access is concentrated in a few threads (as is common for the vast majority of data structures but not e.g. for a hash tracking all memory in a multithreaded kernel), *or* if your access patterns exhibit strong locality of reference (so that item percolation to the top of the tree is worthwhile), *or* if your overheads are elsewhere such that you don't care about a bit of cache overhead (true everywhere but in hot paths), a splay tree is either OK or downright good.
And I contend that in the vast majority of applications this is true. This site has a focus on kernel development, but most programs are not the kernel and most data structures are not randomly accessed on a large number of CPUs in a very hot path. And you need all of those things to be true at once before a splay tree's disadvantages become substantial. (That is not to say that it always has advantages over other implementations: I would only bother with a splay tree if I expected to be populating large hashes and then only using bits of them most of the time. But for some very common applications -- e.g. caching -- this is true.)
Worst case performance and "impossibly unlikely" conditions Posted Jan 18, 2012 23:36 UTC (Wed) by cmccabe (guest, #60281) [Link]
This seems like the kind of thing where benchmarking is your friend. Luckily, it's fairly easy to go back and forth between red-black trees and splay trees.
I'm still wary of splay trees because they generate dirty cache lines which need to be written back to main memory at some point. That eats into the available memory bandwidth. And of course, even if all of your accesses are single-threaded, there's always the possibility of false sharing.
|
|||||||||||||