Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 2014-12-24 13:58:41 -0600, Jim Nasby wrote: This surprises me given that SMHasher shows XXH to be 50% faster than Spooky for 20 byte keys. Note that there's quite some differences in how smhasher and postgres use the hash functions. The former nearly exclusively exercises the hash function while postgres also executes a lot of other code. Which means that the instruction cache and branch prediction is much less likely to contain relevant entries. And that can change the performance characteristics noticeably. Additionally there's differences in how much pipelining can be employed - the likelihood the CPU is able to do so in tight loops is much higher. Also note that in many cases in which you can see tag_hash/hash_any in workloads a part of the cost won't actually be the computation of the hashes themselves but the cache misses triggered by the hash computation accessing the data. 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
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 2014-12-24 00:27:39 -0600, Jim Nasby wrote: pgbench -S -T10 -c 4 -j 4 master: tps = 9556.356145 (excluding connections establishing) tps = 9897.324917 (excluding connections establishing) tps = 9287.286907 (excluding connections establishing) tps = 10210.130833 (excluding connections establishing) XXH32: tps = 32462.754437 (excluding connections establishing) tps = 33232.144511 (excluding connections establishing) tps = 33082.436760 (excluding connections establishing) tps = 33597.904532 (excluding connections establishing) FWIW, I don't believe these results for one second. It's quite plausible that there's a noticeable performance benefit, but a factor of three is completely unrealistic... Could you please recheck? 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
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
Andres Freund and...@2ndquadrant.com writes: On 2014-12-24 00:27:39 -0600, Jim Nasby wrote: pgbench -S -T10 -c 4 -j 4 master: tps = 9556.356145 (excluding connections establishing) tps = 9897.324917 (excluding connections establishing) tps = 9287.286907 (excluding connections establishing) tps = 10210.130833 (excluding connections establishing) XXH32: tps = 32462.754437 (excluding connections establishing) tps = 33232.144511 (excluding connections establishing) tps = 33082.436760 (excluding connections establishing) tps = 33597.904532 (excluding connections establishing) FWIW, I don't believe these results for one second. It's quite plausible that there's a noticeable performance benefit, but a factor of three is completely unrealistic... Could you please recheck? A possible theory is that the hash change moved some locks into different partitions causing a large reduction in contention, but even then 3X seems unlikely. And of course if that was the mechanism, the result is still pure luck; other examples might get worse by the same amount. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 12/24/14, 10:58 AM, Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: On 2014-12-24 00:27:39 -0600, Jim Nasby wrote: pgbench -S -T10 -c 4 -j 4 master: tps = 9556.356145 (excluding connections establishing) tps = 9897.324917 (excluding connections establishing) tps = 9287.286907 (excluding connections establishing) tps = 10210.130833 (excluding connections establishing) XXH32: tps = 32462.754437 (excluding connections establishing) tps = 33232.144511 (excluding connections establishing) tps = 33082.436760 (excluding connections establishing) tps = 33597.904532 (excluding connections establishing) FWIW, I don't believe these results for one second. It's quite plausible that there's a noticeable performance benefit, but a factor of three is completely unrealistic... Could you please recheck? A possible theory is that the hash change moved some locks into different partitions causing a large reduction in contention, but even then 3X seems unlikely. And of course if that was the mechanism, the result is still pure luck; other examples might get worse by the same amount. I must have screwed something up, because if anything I see a small loss for XXH now (but my laptop isn't consistent enough to be sure). This surprises me given that SMHasher shows XXH to be 50% faster than Spooky for 20 byte keys. -- Jim Nasby, Data Architect, Blue Treble Consulting Data in Trouble? Get it in Treble! http://BlueTreble.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
Jim Nasby jim.na...@bluetreble.com writes: On 12/24/14, 10:58 AM, Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: FWIW, I don't believe these results for one second. It's quite plausible that there's a noticeable performance benefit, but a factor of three is completely unrealistic... Could you please recheck? A possible theory is that the hash change moved some locks into different partitions causing a large reduction in contention, but even then 3X seems unlikely. And of course if that was the mechanism, the result is still pure luck; other examples might get worse by the same amount. I must have screwed something up, because if anything I see a small loss for XXH now (but my laptop isn't consistent enough to be sure). This surprises me given that SMHasher shows XXH to be 50% faster than Spooky for 20 byte keys. The speed of the hash calculation itself is unlikely to move the needle as much as 1% either direction, because I've seldom seen any profile in which hash_any accounted for more than a percent or so of total runtime. What is far more likely to be causing visible performance changes is downstream effects, ie changes in the distribution of entries across hash buckets, causing changes in bucket list search times and/or changes in contention (for shared memory tables that are locked on a hash-partition basis). But even then it's hard to credit 3X. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 12/20/14, 2:13 PM, Jim Nasby wrote: On 12/20/14, 11:51 AM, Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: On 2014-12-19 22:03:55 -0600, Jim Nasby wrote: What I am thinking is not using all of those fields in their raw form to calculate the hash value. IE: something analogous to: hash_any(SharedBufHash, (rot(forkNum, 2) | dbNode) ^ relNode) 32 | blockNum) perhaps that actual code wouldn't work, but I don't see why we couldn't do something similar... am I missing something? I don't think that'd improve anything. Jenkin's hash does have a quite mixing properties, I don't believe that the above would improve the quality of the hash. I think what Jim is suggesting is to intentionally degrade the quality of the hash in order to let it be calculated a tad faster. We could do that but I doubt it would be a win, especially in systems with lots of buffers. IIRC, when we put in Jenkins hashing to replace the older homebrew hash function, it improved performance even though the hash itself was slower. Right. Now that you mention it, I vaguely recall the discussions about changing the hash function to reduce collisions. I'll still take a look at fash-hash, but it's looking like there may not be anything we can do here unless we change how we identify relation files (combining dbid, tablespace id, fork number and file id, at least for searching). If we had 64bit hash support then maybe that'd be a significant win, since you wouldn't need to hash at all. But that certainly doesn't seem to be low-hanging fruit to me... I've taken a look at a number of different hash algorithms, testing them with initially with SMHasher [1] and then with pgbench. It's worth noting that a lot of work has been done in the area of hash algo's since we last updated the hash_any algorithm in 2009 [2]. It's probably worth revisiting this every other release or so. Most of my SMHasher results are at [3]. I suspect SpookyHash is close to what we currently have, so that's what I used for a baseline. I determined that fash-hash (called superfast in results) was faster than Spooky, but not as fast as CityHash64[4] or xxhash[5]. CityHash and xxhash had similar performance, but xxhash seems to have slightly better characteristics according to SMHasher, and more important, it's in C, not C++. However, CityHash has been replaced by farmhash[7], which might be faster than xxhash. I did a quick hack at using xxhash ONLY for shared buffer lookup [6]. I've attached the full patch, as well as a version that omits the new files. Note that currently xxhash is setup in such a way that we'd get different results depending on endian-ness, so we couldn't just drop this in as-is across the board. Of course, there's also the question of if we'd want to force a REINDEX on hash indexes. pgbench results are below. Select-only testing was done first, then read-write. There were several select-only runs on both to warm shared_buffers (set to 512MB for this test, and fsync is off). Database initialized with bin/pgbench -i -F 100 -s 10. pgbench -S -T10 -c 4 -j 4 master: tps = 9556.356145 (excluding connections establishing) tps = 9897.324917 (excluding connections establishing) tps = 9287.286907 (excluding connections establishing) tps = 10210.130833 (excluding connections establishing) XXH32: tps = 32462.754437 (excluding connections establishing) tps = 33232.144511 (excluding connections establishing) tps = 33082.436760 (excluding connections establishing) tps = 33597.904532 (excluding connections establishing) pgbench -T10 -c 4 -j 4 master: tps = 2299.314145 (excluding connections establishing) tps = 2029.956749 (excluding connections establishing) tps = 2067.462362 (excluding connections establishing) XXH32: tps = 2653.919321 (excluding connections establishing) tps = 2615.764370 (excluding connections establishing) tps = 2952.144461 (excluding connections establishing) Questions: Do we want to do what we've previously done and cut/paste/modify this code into our repo? Given how rapidly hash algorithms seem to be changing I'm inclined to minimize the amount of effort required to pull a new one in... Can someone with a big-endian CPU see what the impact of XXH_FORCE_NATIVE_FORMAT 1 vs 0? If there's a notable difference we might want to do different things for on-disk vs in-memory hashes. For that matter, assuming we adopt this, do we want to replace the index hash functions too? SMHasher shows that CityHash is ~50% faster than XXHash for 262144 byte keys. Even SpookyHash is about 17% faster on that key size. So if we want to do something with hash indexes, we'd probably be better off with City or Farm hash than XXHash. [1] https://code.google.com/p/smhasher/ [2] https://github.com/postgres/postgres/commit/8205258fa675115439017b626c4932d5fefe2ea8 [3] https://github.com/decibel/hash_testing/tree/master/results [4] https://code.google.com/p/cityhash/ [5] https://code.google.com/p/xxhash/ [6]
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 12/24/14, 12:27 AM, Jim Nasby wrote: There were several select-only runs on both to warm shared_buffers (set to 512MB for this test, and fsync is off). BTW, presumably this ~380M database isn't big enough to show any problems with hash collisions, and I'm guessing you'd need way more memory than what I have on this laptop. Might be worth looking into that on a machine with a serious amount of memory. -- Jim Nasby, Data Architect, Blue Treble Consulting Data in Trouble? Get it in Treble! http://BlueTreble.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
Andres Freund and...@2ndquadrant.com writes: On 2014-12-19 22:03:55 -0600, Jim Nasby wrote: What I am thinking is not using all of those fields in their raw form to calculate the hash value. IE: something analogous to: hash_any(SharedBufHash, (rot(forkNum, 2) | dbNode) ^ relNode) 32 | blockNum) perhaps that actual code wouldn't work, but I don't see why we couldn't do something similar... am I missing something? I don't think that'd improve anything. Jenkin's hash does have a quite mixing properties, I don't believe that the above would improve the quality of the hash. I think what Jim is suggesting is to intentionally degrade the quality of the hash in order to let it be calculated a tad faster. We could do that but I doubt it would be a win, especially in systems with lots of buffers. IIRC, when we put in Jenkins hashing to replace the older homebrew hash function, it improved performance even though the hash itself was slower. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 12/20/14, 11:51 AM, Tom Lane wrote: Andres Freund and...@2ndquadrant.com writes: On 2014-12-19 22:03:55 -0600, Jim Nasby wrote: What I am thinking is not using all of those fields in their raw form to calculate the hash value. IE: something analogous to: hash_any(SharedBufHash, (rot(forkNum, 2) | dbNode) ^ relNode) 32 | blockNum) perhaps that actual code wouldn't work, but I don't see why we couldn't do something similar... am I missing something? I don't think that'd improve anything. Jenkin's hash does have a quite mixing properties, I don't believe that the above would improve the quality of the hash. I think what Jim is suggesting is to intentionally degrade the quality of the hash in order to let it be calculated a tad faster. We could do that but I doubt it would be a win, especially in systems with lots of buffers. IIRC, when we put in Jenkins hashing to replace the older homebrew hash function, it improved performance even though the hash itself was slower. Right. Now that you mention it, I vaguely recall the discussions about changing the hash function to reduce collisions. I'll still take a look at fash-hash, but it's looking like there may not be anything we can do here unless we change how we identify relation files (combining dbid, tablespace id, fork number and file id, at least for searching). If we had 64bit hash support then maybe that'd be a significant win, since you wouldn't need to hash at all. But that certainly doesn't seem to be low-hanging fruit to me... -- Jim Nasby, Data Architect, Blue Treble Consulting Data in Trouble? Get it in Treble! http://BlueTreble.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 12/18/14, 5:00 PM, Jim Nasby wrote: 2201582 20 -- Mostly LOCALLOCK and Shared Buffer Started looking into this; perhaps https://code.google.com/p/fast-hash/ would be worth looking at, though it requires uint64. It also occurs to me that we're needlessly shoving a lot of 0's into the hash input by using RelFileNode and ForkNumber. RelFileNode includes the tablespace Oid, which is pointless here because relid is unique per-database. We also have very few forks and typically care about very few databases. If we crammed dbid and ForkNum together that gets us down to 12 bytes, which at minimum saves us the trip through the case logic. I suspect it also means we could eliminate one of the mix() calls. But I wonder if we could still do better, because we typically also won't have that many relations. Is there some fast way we could combine dbid, forkNum and relid into a uint32? That gets us down to 8 bytes, which means we could use fash-hash, or a stripped down mix(). Unfortunately I don't know much about hash algorithms, so I don't know how practical any of this actually is, or what a good method for combining those fields would be. My current idea is something like (rot(forkNum, 2) | dbid) ^ relid, but if you got unlucky with your oid values you could end up with a lot of collissions from that. I can put some effort into this, but I'd like some guidance. -- Jim Nasby, Data Architect, Blue Treble Consulting Data in Trouble? Get it in Treble! http://BlueTreble.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
Jim Nasby jim.na...@bluetreble.com writes: On 12/18/14, 5:00 PM, Jim Nasby wrote: 2201582 20 -- Mostly LOCALLOCK and Shared Buffer Started looking into this; perhaps https://code.google.com/p/fast-hash/ would be worth looking at, though it requires uint64. It also occurs to me that we're needlessly shoving a lot of 0's into the hash input by using RelFileNode and ForkNumber. RelFileNode includes the tablespace Oid, which is pointless here because relid is unique per-database. We also have very few forks and typically care about very few databases. If we crammed dbid and ForkNum together that gets us down to 12 bytes, which at minimum saves us the trip through the case logic. I suspect it also means we could eliminate one of the mix() calls. I don't see this working. The lock table in shared memory can surely take no such shortcuts. We could make a backend's locallock table omit fields that are predictable within the set of objects that backend could ever lock, but (1) this doesn't help unless we can reduce the tag size for all LockTagTypes, which we probably can't, and (2) having the locallock's tag be different from the corresponding shared tag would be a mess too. I think dealing with (2) might easily eat all the cycles we could hope to save from a smaller hash tag ... and that's not even considering the added logical complexity and potential for bugs. Switching to a different hash algorithm could be feasible, perhaps. I think we're likely stuck with Jenkins hashing for hashes that go to disk, but hashes for dynahash tables don't do that. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On Fri, Dec 19, 2014 at 04:41:51PM -0600, Jim Nasby wrote: On 12/18/14, 5:00 PM, Jim Nasby wrote: 2201582 20 -- Mostly LOCALLOCK and Shared Buffer Started looking into this; perhaps https://code.google.com/p/fast-hash/ would be worth looking at, though it requires uint64. It also occurs to me that we're needlessly shoving a lot of 0's into the hash input by using RelFileNode and ForkNumber. RelFileNode includes the tablespace Oid, which is pointless here because relid is unique per-database. We also have very few forks and typically care about very few databases. If we crammed dbid and ForkNum together that gets us down to 12 bytes, which at minimum saves us the trip through the case logic. I suspect it also means we could eliminate one of the mix() calls. But I wonder if we could still do better, because we typically also won't have that many relations. Is there some fast way we could combine dbid, forkNum and relid into a uint32? That gets us down to 8 bytes, which means we could use fash-hash, or a stripped down mix(). Unfortunately I don't know much about hash algorithms, so I don't know how practical any of this actually is, or what a good method for combining those fields would be. My current idea is something like (rot(forkNum, 2) | dbid) ^ relid, but if you got unlucky with your oid values you could end up with a lot of collissions from that. I can put some effort into this, but I'd like some guidance. -- Jim Nasby, Data Architect, Blue Treble Consulting Data in Trouble? Get it in Treble! http://BlueTreble.com Hi, If we are going to consider changing the hash function, we should consider something like xxhash which runs at 13.8GB/s on a 2.7GHz x86_64 for the XXH64 variant and 6.8GB/s for the XXH32 variant which is double the speed of fast-hash according to the page running on a 3GHz x86_64. In addition, something like that could be used a checksum instead of the current CRC32, although some work has already gone into speeding it up, as is. Otherwise, it probably makes sense to just stick with creating the fastpath 8-byte analogously to the 4-byte fastpath that was just added. Is calculating the hash the bottle-neck? Regards, Ken -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
k...@rice.edu k...@rice.edu writes: If we are going to consider changing the hash function, we should consider something like xxhash which runs at 13.8GB/s on a 2.7GHz x86_64 for the XXH64 variant and 6.8GB/s for the XXH32 variant which is double the speed of fast-hash according to the page running on a 3GHz x86_64. Well, as the google page points out, raw speed is not the only figure of merit; otherwise we'd just xor all the bytes and call it good. We need the hash function to spread out the hash values well, or else we lose more cycles chasing inordinately-long hash chains than we saved with a cheap hash function. Google claims their fast-hash is actually better on this point than Jenkins, which if true would be very nice indeed. Keep in mind also that very very few of our hash keys are longer than about 20 bytes, so that speed-per-byte is not that exciting anyway. Longer setup/finish times could easily swamp any per-byte advantages, for example. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 12/19/14, 5:13 PM, Tom Lane wrote: Jim Nasby jim.na...@bluetreble.com writes: On 12/18/14, 5:00 PM, Jim Nasby wrote: 2201582 20 -- Mostly LOCALLOCK and Shared Buffer Started looking into this; perhaps https://code.google.com/p/fast-hash/ would be worth looking at, though it requires uint64. It also occurs to me that we're needlessly shoving a lot of 0's into the hash input by using RelFileNode and ForkNumber. RelFileNode includes the tablespace Oid, which is pointless here because relid is unique per-database. We also have very few forks and typically care about very few databases. If we crammed dbid and ForkNum together that gets us down to 12 bytes, which at minimum saves us the trip through the case logic. I suspect it also means we could eliminate one of the mix() calls. I don't see this working. The lock table in shared memory can surely take no such shortcuts. We could make a backend's locallock table omit fields that are predictable within the set of objects that backend could ever lock, but (1) this doesn't help unless we can reduce the tag size for all LockTagTypes, which we probably can't, and (2) having the locallock's tag be different from the corresponding shared tag would be a mess too. I think dealing with (2) might easily eat all the cycles we could hope to save from a smaller hash tag ... and that's not even considering the added logical complexity and potential for bugs. I think we may be thinking different things here... I'm not suggesting we change BufferTag or BufferLookupEnt; clearly we can't simply throw away any of the fields I was talking about (well, except possibly tablespace ID. AFAICT that's completely redundant for searching because relid is UNIQUE). What I am thinking is not using all of those fields in their raw form to calculate the hash value. IE: something analogous to: hash_any(SharedBufHash, (rot(forkNum, 2) | dbNode) ^ relNode) 32 | blockNum) perhaps that actual code wouldn't work, but I don't see why we couldn't do something similar... am I missing something? Switching to a different hash algorithm could be feasible, perhaps. I think we're likely stuck with Jenkins hashing for hashes that go to disk, but hashes for dynahash tables don't do that. Yeah, I plan on testing the performance of fash-hash for HASH_BLOBS just to see how it compares. Why would we be stuck with Jenkins hashing for on-disk data? pg_upgrade, or something else? -- Jim Nasby, Data Architect, Blue Treble Consulting Data in Trouble? Get it in Treble! http://BlueTreble.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 2014-12-19 22:03:55 -0600, Jim Nasby wrote: I'm not suggesting we change BufferTag or BufferLookupEnt; clearly we can't simply throw away any of the fields I was talking about (well, except possibly tablespace ID. AFAICT that's completely redundant for searching because relid is UNIQUE). It's actually not. BufferTag's contain relnodes via RelFileNode - that's not the relation's oid, but the filenode. And that's *not* guranteed unique across database unfortunately. What I am thinking is not using all of those fields in their raw form to calculate the hash value. IE: something analogous to: hash_any(SharedBufHash, (rot(forkNum, 2) | dbNode) ^ relNode) 32 | blockNum) perhaps that actual code wouldn't work, but I don't see why we couldn't do something similar... am I missing something? I don't think that'd improve anything. Jenkin's hash does have a quite mixing properties, I don't believe that the above would improve the quality of the hash. 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
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
I wrote: Here's a proposed patch along this line. I left in oid_hash (in the form of a macro) so that this does not cause any API break for existing third-party modules. However, no callers in our own code directly refer to tag_hash or oid_hash anymore. Committed that version after some further comment wordsmithing. On Teodor's original test cases, I see about 8% speedup compared to the 4%-ish numbers he originally reported. This may be random variation or it might mean that we got a win someplace else besides tidbitmap.c. I've not tried to sleuth it down exactly. I am wondering though if this suggests that it'd be worth our while to add a similar fast path for 8-byte hash keys. That would be quite painless to add now (with the exception of actually coding the fast hash function, perhaps). regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: hash_create API changes (was Re: [HACKERS] speedup tidbitmap patch: hash BlockNumber)
On 12/18/14, 12:48 PM, Tom Lane wrote: I wrote: Here's a proposed patch along this line. I left in oid_hash (in the form of a macro) so that this does not cause any API break for existing third-party modules. However, no callers in our own code directly refer to tag_hash or oid_hash anymore. Committed that version after some further comment wordsmithing. On Teodor's original test cases, I see about 8% speedup compared to the 4%-ish numbers he originally reported. This may be random variation or it might mean that we got a win someplace else besides tidbitmap.c. I've not tried to sleuth it down exactly. I am wondering though if this suggests that it'd be worth our while to add a similar fast path for 8-byte hash keys. That would be quite painless to add now (with the exception of actually coding the fast hash function, perhaps). I stuck an elog in to report when a hash wasn't found, and came up with these results (first number is how many times a hash wasn't found, second is keysize). I don't see a lot of 8's in there... Second set of numbers is the same thing, except counting every time we looked for the hash value, regardless of result. (Both cases generated by running make check.) BTW, as part of this I found some hash values were hit over 30k times in the first case. I don't know if that means a boatload of collisions or something else. Command to generate that data is: $egrep '^LOG: Hashtable ' src/test/regress/log/postmaster.log |cut -d\| -f2,4|sort|uniq -c|cut -d' ' -f1|sort -n|tail Before hitting the raw data, here is a summary of hash searches by key size (generated by patch 1): 43 48 327 256 1411 416 9321 136 12436 12 31270 64 107017 8 203127 16 628107 4 2201582 20 -- Mostly LOCALLOCK and Shared Buffer egrep '^LOG: Hashtable ' src/test/regress/log/postmaster.log |cut -d\| -f2,6|sort|uniq -c (patch 2) 581 Analyzed elements table|8 1141 Analyzed lexemes table|16 46 Array distinct element count table|4 167 Attopt cache|8 26 Btree proof lookup cache|8 95 CFuncHash|4 2387 Combo CIDs|8 99 Databases hash|4 22 Event Trigger Cache|4 85 JoinRelHashTable|8 460690 LOCALLOCK hash|20 1 LOCALLOCK hash|LOCALLOCK hash 49608 LOCK hash|16 951 Local Buffer Lookup Table|20 5 Local predicate lock|16 581 Operator class cache|4 1658 Operator lookup cache|136 301 PLpgSQL function cache|416 5 PREDICATELOCK hash|16 14 PREDICATELOCKTARGET hash|16 52278 PROCLOCK hash|16 1064 Pending Ops Table|12 14790 Per-database table|4 15297 Portal hash|64 21 Prepared Queries|64 126 PrivateRefCount|4 4 RI compare cache|8 55 RI constraint cache|4 90 RI query cache|8 72 Record information cache|64 24040 Relcache by OID|4 742 RelfilenodeMap cache|8 21 Rendezvous variable hash|64 4 Rewrite / Old to new tid map|12 49 Rewrite / Unresolved ctids|12 5 SERIALIZABLEXID hash|4 60 Sequence values|4 9603 Shared Buffer Lookup Table|20 43 ShmemIndex|48 5335 TIDBitmap|4 138 TableSpace cache|4 16516 Temporary table of OIDs|4 169 Timezones|256 6 Tsearch configuration cache|4 4 Tsearch dictionary cache|4 1 Tsearch parser cache|4 11550 TupleHashTable|8 327 Type information cache|4 59 json object hashtable|64 17430 smgr relation table|16 egrep '^LOG: Hashtable ' src/test/regress/log/postmaster.log |cut -d\| -f2,6|sort|uniq -c (patch 1) 2250 Analyzed elements table|8 28817 Analyzed lexemes table|16 428 Array distinct element count table|4 447 Attopt cache|8 224 Btree proof lookup cache|8 1363 CFuncHash|4 5219 Combo CIDs|8 2415 Databases hash|4 12063 Event Trigger Cache|4 178 JoinRelHashTable|8 990753 LOCALLOCK hash|20 72129 LOCK hash|16 19858 Local Buffer Lookup Table|20 2 Local Buffer Lookup Table|LOG: Hashtable 7 Local predicate lock|16 4557 Operator class cache|4 9321 Operator lookup cache|136 1 Operator lookup cache|136LOG: Hashtable 1411 PLpgSQL function cache|416 8 PREDICATELOCK hash|16 106 PREDICATELOCKTARGET hash|16 73102 PROCLOCK hash|16 10929 Pending Ops Table|12 23534 Per-database table|4 29502 Portal hash|64 233 Prepared Queries|64 689 PrivateRefCount|4 91 RI compare cache|8 310 RI constraint cache|4 289 RI query cache|8 1471 Record information cache|64 1 Record information cache|64LOG: Hashtable 1 Record information cache|6LOG: Hashtable 426050 Relcache by OID|4 1308 RelfilenodeMap cache|8 12 Rendezvous variable hash|64 24 Rewrite / Old to new tid map|12 1483 Rewrite / Unresolved ctids|12 12 SERIALIZABLEXID hash|4 263 Sequence values|4 1190971 Shared Buffer Lookup Table|20 30 Shared Buffer Lookup Table|20LOG: Hashtable 20 Shared Buffer Lookup Table|2LOG: Hashtable 1 Shared Buffer Lookup Table|Event Trigger Cache 27 Shared Buffer Lookup Table|LOCALLOCK hash 2 Shared Buffer Lookup Table|LOCK hash 14 Shared Buffer Lookup Table|LOG: Hashtable 9 Shared Buffer Lookup Table|PROCLOCK hash 10 Shared Buffer Lookup Table|Relcache by OID 20 Shared Buffer Lookup Table|Shared Buffer Lookup
