Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On 11.10.2013 13:42, Huchev wrote:
gettimeofday(start, NULL);
for (i = 0; i VALUES; i++) {
state = XXH32_init(result);
XXH32_update(state, i, 4);
XXH32_digest(state);
}
gettimeofday(end, NULL);
This code is using the update variant, which is only useful when dealing
with very large amount of data which can't fit into a single block of
memory. This is obviously overkill for a 4-bytes-only test. 3 functions
calls, a malloc, intermediate data book keeping, etc.
To hash a single block of data, it's better to use the simpler (and faster)
variant XXH32() :
gettimeofday(start, NULL);
for (i = 0; i VALUES; i++) { XXH32(i, 4, result); }
gettimeofday(end, NULL);
You'll probably get better results by an order of magnitude. For better
results, you could even inline it (yes, for such short loop with almost no
work to do, it makes a very sensible difference).
Not really. Even with this change it's slightly slower than crc32, at
least with the 32-bit integers. With 64-bit integers it's about 2x as
fast. But even then it's like ~1% of the total runtime, so any
improvements here are not really changing anything.
The inlining is not a good idea IMHO, because that'd be very different
from the actual usage (there won't be such tight loop). OTOH I'm not
sure if the compiler does not already inline that as an optimization.
That being said, it's true that these advanced hash algorithms only
shine with big enough amount of data to hash. Hashing a 4-bytes
value into a 4-bytes hash is a bit limited exercise. There is no
pigeon hole issue. A simple multiplication by a 32-bits prime would
fare good enough and result in zero collision.
Agreed. I'll revisit this if/when I'll need to support larger data types
in this aggregate.
Tomas
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
gettimeofday(start, NULL);
for (i = 0; i VALUES; i++) {
state = XXH32_init(result);
XXH32_update(state, i, 4);
XXH32_digest(state);
}
gettimeofday(end, NULL);
This code is using the update variant, which is only useful when dealing
with very large amount of data which can't fit into a single block of
memory. This is obviously overkill for a 4-bytes-only test. 3 functions
calls, a malloc, intermediate data book keeping, etc.
To hash a single block of data, it's better to use the simpler (and faster)
variant XXH32() :
gettimeofday(start, NULL);
for (i = 0; i VALUES; i++) { XXH32(i, 4, result); }
gettimeofday(end, NULL);
You'll probably get better results by an order of magnitude. For better
results, you could even inline it (yes, for such short loop with almost no
work to do, it makes a very sensible difference).
That being said, it's true that these advanced hash algorithms only shine
with big enough amount of data to hash. Hashing a 4-bytes value into a
4-bytes hash is a bit limited exercise. There is no pigeon hole issue. A
simple multiplication by a 32-bits prime would fare good enough and result
in zero collision.
--
View this message in context:
http://postgresql.1045698.n5.nabble.com/custom-hash-based-COUNT-DISTINCT-aggregate-unexpectedly-high-memory-consumption-tp5773463p5774264.html
Sent from the PostgreSQL - hackers mailing list archive at Nabble.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: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
Sent from my iPad On 08-Oct-2013, at 10:41, Claudio Freire klaussfre...@gmail.com wrote: On Tue, Oct 8, 2013 at 1:23 AM, Atri Sharma atri.j...@gmail.com wrote: Consider the aspects associated with open addressing.Open addressing can quickly lead to growth in the main table.Also, chaining is a much cleaner way of collision resolution,IMHO. What do you mean by growth in the main table? Sorry, I should have been more verbose. AFAIK, Open addressing can be slower with a load factor approaching 1 as compared to chaining. Also, I feel that implementation of open addressing can be more complicated as we have to deal with deletes etc. Deletes for a hash aggregate? Yeah, that doesn't apply here.I was just listing out the demerits of open addressing :) My point is, it is not wise to unnecessarily complicate matters by shifting to open addressing. If we want, we could look at changing the data structure used for chaining, but chaining is better for our requirements IMHO. Regards, Atri -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On 8 Říjen 2013, 6:23, Atri Sharma wrote: Hi Tomas, Consider the aspects associated with open addressing.Open addressing can quickly lead to growth in the main table.Also, chaining is a much cleaner way of collision resolution,IMHO. What do you mean by growth in the main table? Sorry, I should have been more verbose. AFAIK, Open addressing can be slower with a load factor approaching 1 as compared to chaining. Also, I feel that implementation of open addressing can be more complicated as we have to deal with deletes etc. I feel we can redesign our current chaining mechanism to have skip lists instead of singly linked lists. I experimented with it sometime back and I feel that it gives a stable performance with higher loads. Regards, Atri OK, thanks for the explanation. I've spent some time hacking this yesterday, the results are available in a separate branch: https://github.com/tvondra/count_distinct/tree/open-addressing The complexity of the implementation is pretty much comparable to chaining. I assume it would get much more complex with handling deletes etc., but that's not really necessary here. However I'm unable to make it at least comparable to chaining. The trick is that the hash table performs reasonably only until it's ~ 65-70% full, it gets really slow after that. So to maintain performance comparable to chaining, I'd have to keep the table below this threshold, effectively wasting ~30% of memory. And the topic of this thread was about decreasing the memory consumptions, so it seems to me open-addressing is not a good match here. I'll try a few more things but I don't think it's going to fly. I've made some significant improvements in the chaining version (in the master branch), now getting about the memory consumption I've estimated. Tomas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
Sent from my iPad However I'm unable to make it at least comparable to chaining. The trick is that the hash table performs reasonably only until it's ~ 65-70% full, it gets really slow after that. So to maintain performance comparable to chaining, I'd have to keep the table below this threshold, effectively wasting ~30% of memory. I expected that. AFAIK, open addressing gets slow when the load factor approaches 1. I feel this is what is happening here. And the topic of this thread was about decreasing the memory consumptions, so it seems to me open-addressing is not a good match here. I'll try a few more things but I don't think it's going to fly. Yeah, I also feel that open addressing isn't the way to go for the problem here. I've made some significant improvements in the chaining version (in the master branch), now getting about the memory consumption I've estimated. I agree, we can hope to reduce the memory consumption by making changes in the current chaining implementation. I would like to look into changing the data structure used for chaining from singly linked list to maybe skip list or something else. Regards, Atri -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On 8 Říjen 2013, 11:42, Atri Sharma wrote: I've made some significant improvements in the chaining version (in the master branch), now getting about the memory consumption I've estimated. I agree, we can hope to reduce the memory consumption by making changes in the current chaining implementation. I would like to look into changing the data structure used for chaining from singly linked list to maybe skip list or something else. Just to be sure - I haven't been messing with the HashAggregate implementation directly, but with a custom aggregate. But feel free to tweak the built-in hash table ;-) Tomas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On Tue, Oct 8, 2013 at 4:15 PM, Tomas Vondra t...@fuzzy.cz wrote: On 8 Říjen 2013, 11:42, Atri Sharma wrote: I've made some significant improvements in the chaining version (in the master branch), now getting about the memory consumption I've estimated. I agree, we can hope to reduce the memory consumption by making changes in the current chaining implementation. I would like to look into changing the data structure used for chaining from singly linked list to maybe skip list or something else. Just to be sure - I haven't been messing with the HashAggregate implementation directly, but with a custom aggregate. But feel free to tweak the built-in hash table ;-) Tomas Heh. Do you mind if I try it out on the custom agg you built? I assume it is on the github repo link you shared? Regards, Atri -- Regards, Atri l'apprenant -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On 8 Říjen 2013, 13:52, Atri Sharma wrote: On Tue, Oct 8, 2013 at 4:15 PM, Tomas Vondra t...@fuzzy.cz wrote: On 8 Říjen 2013, 11:42, Atri Sharma wrote: I've made some significant improvements in the chaining version (in the master branch), now getting about the memory consumption I've estimated. I agree, we can hope to reduce the memory consumption by making changes in the current chaining implementation. I would like to look into changing the data structure used for chaining from singly linked list to maybe skip list or something else. Just to be sure - I haven't been messing with the HashAggregate implementation directly, but with a custom aggregate. But feel free to tweak the built-in hash table ;-) Tomas Heh. Do you mind if I try it out on the custom agg you built? I assume it is on the github repo link you shared? Not at all, that's why I pushed that into a public repo. The master branch contains the regular chained hash table, the open addressing is in a separate branch (also in the repo). Tomas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On Mon, Oct 07, 2013 at 12:41:58AM +0200, Tomas Vondra wrote: 2. Consider using a simpler/faster hash function, like FNV[1] or Jenkins[2]. For fun, try not hashing those ints at all and see how that performs (that, I think, is what you get from HashSetint in Java/C#). I've used crc32 mostly because it's easily available in the code (i.e. I'm lazy), but I've done some quick research / primitive benchmarking too. For example hashing 2e9 integers takes this much time: FNV-1 = 11.9 FNV-1a = 11.9 jenkins = 38.8 crc32 = 32.0 So it's not really slow and the uniformity seems to be rather good. I'll try FNV in the future, however I don't think that's the main issue right now. Hi Tomas, If you are going to use a function that is not currently in the code, please consider xxhash: http://code.google.com/p/xxhash/ Here are some benchmarks for some of the faster hash functions: NameSpeed Q.Score Author xxHash 5.4 GB/s 10 MumurHash 3a2.7 GB/s 10 Austin Appleby SpookyHash 2.0 GB/s 10 Bob Jenkins SBox1.4 GB/s 9 Bret Mulvey Lookup3 1.2 GB/s 9 Bob Jenkins CityHash64 1.05 GB/s10 Pike Alakuijala FNV 0.55 GB/s 5 Fowler, Noll, Vo CRC32 0.43 GB/s 9 MD5-32 0.33 GB/s10 Ronald L. Rivest SHA1-32 0.28 GB/s10 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: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
Sent from my iPad On 07-Oct-2013, at 4:11, Tomas Vondra t...@fuzzy.cz wrote: On 6.10.2013 20:37, Tomáš Janoušek wrote: Hi, On Sat, Oct 05, 2013 at 08:22:54PM +0200, Tomas Vondra wrote: I'm on 64-bit architecture and the example works with int32, which means the sizes should be about this: hash_element_t = 20B hash_bucket_t = 4B + (20B * items in the bucket [in steps of 5]) hash_table_t = 4B + space for buckets In the example above, there's ~20k unique values in each group. The threshold is 20 items per bucket on average, so that's 1024 buckets, and the buckets are almost full. So for single group, the hash table size is about 4B + 1024 * (4B + 20 * 20B) = 413700B = ~ 400 kB There are 4000 groups, so the total estimate is ~1.6GB in total. However when executed (9.2, 9.3 and HEAD behave exactly the same), the query consumes almost ~5GB of RAM (excluding shared buffers). I think the missing thing is the memory allocator bookkeeping overhead. You're assuming that hash_element_t.value takes 8B for the pointer and 4B for the value itself, but using malloc it takes another at least 20 bytes, and from a quick glance at backend/utils/mmgr/aset.c it seems that palloc is certainly not without its overhead either. Also, each additional level of pointers adds execution overhead and increases the likelihood of cache misses. I'd suggest a few improvements, if I may: 1. Drop hash_element_t altogether, store length in hash_bucket_t and alloc hash_bucket_t.items of size nitems * length bytes. I doubt that storing the hash values has a benefit worth the storage and code complexity overhead (you're storing fixed-size ints, not large blobs that are expensive to compare and hash). Good idea - I'll move the length to the hash table. You're right that keeping the hash for int32/64 values is probably useless, however I planned to eventually extend the code to support larger values (possibly even varlena types, i.e. text/bytea). So I'll keep this for now, but I'll keep this as a possible optimization. 2. Consider using a simpler/faster hash function, like FNV[1] or Jenkins[2]. For fun, try not hashing those ints at all and see how that performs (that, I think, is what you get from HashSetint in Java/C#). I've used crc32 mostly because it's easily available in the code (i.e. I'm lazy), but I've done some quick research / primitive benchmarking too. For example hashing 2e9 integers takes this much time: FNV-1 = 11.9 FNV-1a = 11.9 jenkins = 38.8 crc32 = 32.0 So it's not really slow and the uniformity seems to be rather good. I'll try FNV in the future, however I don't think that's the main issue right now. 3. Consider dropping buckets in favor of open addressing (linear probing, quadratic, whatever). This avoids another level of pointer indirection. OK, this sounds really interesting. It should be fairly straightforward for fixed-length data types (in that case I can get rid of the pointers altogether). Consider the aspects associated with open addressing.Open addressing can quickly lead to growth in the main table.Also, chaining is a much cleaner way of collision resolution,IMHO. It's been a few years since I've done stuff this low level, so I won't go into suggesting a different data structure -- I have honestly no idea what's the best way to count the number of distinct integers in a list. Thanks for the hints! Tomas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On 7.10.2013 14:50, k...@rice.edu wrote: On Mon, Oct 07, 2013 at 12:41:58AM +0200, Tomas Vondra wrote: 2. Consider using a simpler/faster hash function, like FNV[1] or Jenkins[2]. For fun, try not hashing those ints at all and see how that performs (that, I think, is what you get from HashSetint in Java/C#). I've used crc32 mostly because it's easily available in the code (i.e. I'm lazy), but I've done some quick research / primitive benchmarking too. For example hashing 2e9 integers takes this much time: FNV-1 = 11.9 FNV-1a = 11.9 jenkins = 38.8 crc32 = 32.0 So it's not really slow and the uniformity seems to be rather good. I'll try FNV in the future, however I don't think that's the main issue right now. Hi Tomas, If you are going to use a function that is not currently in the code, please consider xxhash: http://code.google.com/p/xxhash/ Here are some benchmarks for some of the faster hash functions: NameSpeed Q.Score Author xxHash 5.4 GB/s 10 MumurHash 3a2.7 GB/s 10 Austin Appleby SpookyHash 2.0 GB/s 10 Bob Jenkins SBox1.4 GB/s 9 Bret Mulvey Lookup3 1.2 GB/s 9 Bob Jenkins CityHash64 1.05 GB/s10 Pike Alakuijala FNV 0.55 GB/s 5 Fowler, Noll, Vo CRC32 0.43 GB/s 9 MD5-32 0.33 GB/s10 Ronald L. Rivest SHA1-32 0.28 GB/s10 Hi, thanks for the link. I repeated the simple benchmark (code is here: http://pastebin.com/e9BS03MA) with these results: FNV duration= 9.821 FNVa duration= 9.753 jenkins duration = 37.658 crc32 duration = 7.127 xxhash duration = 68.814 The only difference is that this time I added -O3 (which I forgot last time). That's probably the reason why CRC32 even faster than FNV. Anyway, xxhash seems to be much slower than the other functions, at least in this particular case. I don't think the poor results necessarily contradict the table of results you've posted, because that's on a large block of random data while I'm hashing very short amounts of data (4B / 8B). So my guess is xxhash init takes much more time than the other algorithms. Chances are it'd be faster on large amounts of data, but that's not really useful. Maybe I'll revisit it in the future if I'll decide to add support for varlena types. Until then I'll stick with crc32 which is fast and has much better Quality score than FNV. Tomas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
Hi Atri! On 7.10.2013 16:56, Atri Sharma wrote: 3. Consider dropping buckets in favor of open addressing (linear probing, quadratic, whatever). This avoids another level of pointer indirection. OK, this sounds really interesting. It should be fairly straightforward for fixed-length data types (in that case I can get rid of the pointers altogether). Consider the aspects associated with open addressing.Open addressing can quickly lead to growth in the main table.Also, chaining is a much cleaner way of collision resolution,IMHO. What do you mean by growth in the main table? Tomas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
Hi Tomas, Consider the aspects associated with open addressing.Open addressing can quickly lead to growth in the main table.Also, chaining is a much cleaner way of collision resolution,IMHO. What do you mean by growth in the main table? Sorry, I should have been more verbose. AFAIK, Open addressing can be slower with a load factor approaching 1 as compared to chaining. Also, I feel that implementation of open addressing can be more complicated as we have to deal with deletes etc. I feel we can redesign our current chaining mechanism to have skip lists instead of singly linked lists. I experimented with it sometime back and I feel that it gives a stable performance with higher loads. Regards, Atri -- Regards, Atri l'apprenant -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On Tue, Oct 8, 2013 at 1:23 AM, Atri Sharma atri.j...@gmail.com wrote: Consider the aspects associated with open addressing.Open addressing can quickly lead to growth in the main table.Also, chaining is a much cleaner way of collision resolution,IMHO. What do you mean by growth in the main table? Sorry, I should have been more verbose. AFAIK, Open addressing can be slower with a load factor approaching 1 as compared to chaining. Also, I feel that implementation of open addressing can be more complicated as we have to deal with deletes etc. Deletes for a hash aggregate? -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
Hi, On Sat, Oct 05, 2013 at 08:22:54PM +0200, Tomas Vondra wrote: I'm on 64-bit architecture and the example works with int32, which means the sizes should be about this: hash_element_t = 20B hash_bucket_t = 4B + (20B * items in the bucket [in steps of 5]) hash_table_t = 4B + space for buckets In the example above, there's ~20k unique values in each group. The threshold is 20 items per bucket on average, so that's 1024 buckets, and the buckets are almost full. So for single group, the hash table size is about 4B + 1024 * (4B + 20 * 20B) = 413700B = ~ 400 kB There are 4000 groups, so the total estimate is ~1.6GB in total. However when executed (9.2, 9.3 and HEAD behave exactly the same), the query consumes almost ~5GB of RAM (excluding shared buffers). I think the missing thing is the memory allocator bookkeeping overhead. You're assuming that hash_element_t.value takes 8B for the pointer and 4B for the value itself, but using malloc it takes another at least 20 bytes, and from a quick glance at backend/utils/mmgr/aset.c it seems that palloc is certainly not without its overhead either. Also, each additional level of pointers adds execution overhead and increases the likelihood of cache misses. I'd suggest a few improvements, if I may: 1. Drop hash_element_t altogether, store length in hash_bucket_t and alloc hash_bucket_t.items of size nitems * length bytes. I doubt that storing the hash values has a benefit worth the storage and code complexity overhead (you're storing fixed-size ints, not large blobs that are expensive to compare and hash). 2. Consider using a simpler/faster hash function, like FNV[1] or Jenkins[2]. For fun, try not hashing those ints at all and see how that performs (that, I think, is what you get from HashSetint in Java/C#). 3. Consider dropping buckets in favor of open addressing (linear probing, quadratic, whatever). This avoids another level of pointer indirection. It's been a few years since I've done stuff this low level, so I won't go into suggesting a different data structure -- I have honestly no idea what's the best way to count the number of distinct integers in a list. [1] http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash [2] http://en.wikipedia.org/wiki/Jenkins_hash_function Best regards, -- Tomáš Janoušek, a.k.a. Liskni_si, http://work.lisk.in/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Re: custom hash-based COUNT(DISTINCT) aggregate - unexpectedly high memory consumption
On 6.10.2013 20:37, Tomáš Janoušek wrote: Hi, On Sat, Oct 05, 2013 at 08:22:54PM +0200, Tomas Vondra wrote: I'm on 64-bit architecture and the example works with int32, which means the sizes should be about this: hash_element_t = 20B hash_bucket_t = 4B + (20B * items in the bucket [in steps of 5]) hash_table_t = 4B + space for buckets In the example above, there's ~20k unique values in each group. The threshold is 20 items per bucket on average, so that's 1024 buckets, and the buckets are almost full. So for single group, the hash table size is about 4B + 1024 * (4B + 20 * 20B) = 413700B = ~ 400 kB There are 4000 groups, so the total estimate is ~1.6GB in total. However when executed (9.2, 9.3 and HEAD behave exactly the same), the query consumes almost ~5GB of RAM (excluding shared buffers). I think the missing thing is the memory allocator bookkeeping overhead. You're assuming that hash_element_t.value takes 8B for the pointer and 4B for the value itself, but using malloc it takes another at least 20 bytes, and from a quick glance at backend/utils/mmgr/aset.c it seems that palloc is certainly not without its overhead either. Also, each additional level of pointers adds execution overhead and increases the likelihood of cache misses. I'd suggest a few improvements, if I may: 1. Drop hash_element_t altogether, store length in hash_bucket_t and alloc hash_bucket_t.items of size nitems * length bytes. I doubt that storing the hash values has a benefit worth the storage and code complexity overhead (you're storing fixed-size ints, not large blobs that are expensive to compare and hash). Good idea - I'll move the length to the hash table. You're right that keeping the hash for int32/64 values is probably useless, however I planned to eventually extend the code to support larger values (possibly even varlena types, i.e. text/bytea). So I'll keep this for now, but I'll keep this as a possible optimization. 2. Consider using a simpler/faster hash function, like FNV[1] or Jenkins[2]. For fun, try not hashing those ints at all and see how that performs (that, I think, is what you get from HashSetint in Java/C#). I've used crc32 mostly because it's easily available in the code (i.e. I'm lazy), but I've done some quick research / primitive benchmarking too. For example hashing 2e9 integers takes this much time: FNV-1 = 11.9 FNV-1a = 11.9 jenkins = 38.8 crc32 = 32.0 So it's not really slow and the uniformity seems to be rather good. I'll try FNV in the future, however I don't think that's the main issue right now. 3. Consider dropping buckets in favor of open addressing (linear probing, quadratic, whatever). This avoids another level of pointer indirection. OK, this sounds really interesting. It should be fairly straightforward for fixed-length data types (in that case I can get rid of the pointers altogether). It's been a few years since I've done stuff this low level, so I won't go into suggesting a different data structure -- I have honestly no idea what's the best way to count the number of distinct integers in a list. Thanks for the hints! Tomas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
