On 2014-10-14 09:30:58 -0400, Robert Haas wrote: > A few years ago I started working on a concurrent hash table for > PostgreSQL. The hash table part of it worked, but I never did > anything with it, really. Amit mentioned to me earlier this week that > he was seeing contention inside the dynahash machinery, which inspired > me to go back and update the patch.
Interestingly I've benchmarked similar loads, even on the same machine as Amit, and I do seem trememdous time spent in dynahash.c. It's nearly all cache misses in my tests though. > I took the basic infrastructure > from before and used it to replace the buffer table. Patch is > attached. That's pretty cool. The algorithm is complex enough that I haven't fully understood it yet, but it sounds sane on a first glance. > The key idea here is that lookups are done without any locks, only > memory barriers; and inserts and deletes are done using atomic ops. Hm. I quickly looked and I see that you use two full barriers for every lookup. That's pretty expensive. I think this should be doable using only read/write barriers on the lookup side? Even on architectures where read/write memory barriers have to be something but a compiler barrier, they're still usually a magnitude or so cheaper than full barriers. > The algorithm is not strictly lock-free for reasons explained in the > comments in chash.c, but it's a lot less locky than what we have now, > so in theory you might think that would be a good thing. I don't see much reason to strive for full lock-free ness. If the locks aren't noticeable in real world scenarios - who cares? > I haven't had time to do much performance testing yet, but it looks > like this may be slower at low client counts and faster at high client > counts. However, my results weren't real reproducible, and I haven't > done comprehensive testing yet. What was really bizarre is that I > couldn't really pin down the cause of the slowness at low client > counts; a quick perf profile showed overhead concentrated in > CHashBucketScan, basically memory access latency for walking the > bucket chain. But the table is built to have a load factor of 1, so I > can't see why that should amount to much, or why it should be > significantly worse than for dynahash. With regard for using a hash table for the buffer mapping lock I'm doubtful that any form of separate chaining is the right one. We currently have a quite noticeable problem with the number of cache misses in the buffer mapping hash (and also the heavyweight lock mgr) - if we stay with hashes that's only going to be fundamentally lower than dynahash if we change the type of hashing. I've had good, *preliminary*, results using an open addressing + linear probing approach. My guess is that the additional indirection via the arena explains the difference in cache misses? But I might be completely off here. It'd be quite interesting to see a perf stat -ddd of dynahash.c/chash employing builds for some comparable load. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers