Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: A Simple GPU Hash Table

nosferalatu.com

Post reply on HN
Print view View original

11–18 of 18 posts

Re: Show HN: A Simple GPU Hash Table

#11

Post by sounds »

diegoperini wrote: post #5

I wonder if this technique can be used to implement order independent transparency on GPU in a performant manner. Really great algorithm regardless! Explanatory Edit: Visually correct alpha blending requires all blended pixels to be known at the blend time but the way real time graphic pipelines work is too lossy to achieve that. Intermediate pixel are lost on each fragment step. In current game engines, when a semi-…

Intel has a great set of papers; the idea is to store a few of the semi-transparent pixels in a texture, then overflow to a storage buffer as needed.

https://www.gdcvault.com/play/1014547/Adaptive-Order-Indepen...

Especially at around 15:06 they make a great argument that above a certain limit, the net effect of additional pixels is minimal (because they will be blended behind a significant fraction of the whole picture, so just mushing together a few semi-transparent pixels at the _back_ of the stack is reasonable).

The problem is getting each pixel's data as small as possible so the texture doesn't overflow the limits of texture sizes in GPUs - typically mobile devices have a limit of 128 bits per pixel in texture sizes. Also, mobile devices don't really have enough GPU RAM to do this kind of order independent transparency on the 4x anti-aliased framebuffer.

After solving the above problems you're ready to spill some pixels into the storage buffer (again, because most pixels on the screen don't have 8 semi-transparent pixels in them, so spilling to overflow for the few ones that do may be faster than trying to keep it all in the texture). Now you're ready to do something like this technique.

Re: Show HN: A Simple GPU Hash Table

#12

Post by amalcon »

dahart wrote: post #10

Awesome! > The table uses power-of-two sizes instead of prime numbers because pow2/AND masking is a fast single instruction and the modulo operator is much slower. I was under the impression that the idea of prime number hash table sizes being faster was shredded a couple decades ago? Maybe by Bob Jenkins?

The idea behind prime number sizes is that you can use a hash function with periodicity issues, which would normally cause collisions. E.g. in C++, it's totally standard-compliant for std::hash::operator() to be the identity function. The prime number of buckets will tend to mitigate this.

These days, the preferred solution to this is usually to just use a better hash function without periodicity issues, so the bucketing no longer matters.

Re: Show HN: A Simple GPU Hash Table

#13

Post by dahart »

amalcon wrote: post #12
dahart wrote: post #10

Awesome! > The table uses power-of-two sizes instead of prime numbers because pow2/AND masking is a fast single instruction and the modulo operator is much slower. I was under the impression that the idea of prime number hash table sizes being faster was shredded a couple decades ago? Maybe by Bob Jenkins?

The idea behind prime number sizes is that you can use a hash function with periodicity issues, which would normally cause collisions. E.g. in C++, it's totally standard-compliant for std::hash ::operator() to be the identity function. The prime number of buckets will tend to mitigate this. These days, the preferred solution to this is usually to just use a better hash function without periodicity issues, so the buck…

Exactly. Indeed - I found the link I was thinking of - Bob Jenkins wrote about that in his famous 1997 article on hashes in Dr Dobbs. Having learned in college that hash table sizes are ideally prime, reading this article was shocking at the time. Ironically, I learned that hash table sizes should be prime in college after 1997, and didn’t find this article until later. I guess best practice knowledge takes time to percolate.

“The best hash table sizes are powers of 2. There is no need to do mod a prime (mod is sooo slow!). If you need less than 32 bits, use a bitmask. For example, if you need only 10 bits, do h = (h & hashmask(10));”

https://burtleburtle.net/bob/hash/doobs.html

Re: Show HN: A Simple GPU Hash Table

#14

Post by senderista »

You might want to check out Bidirectional Linear Probing, which can handle load factor >90% with good performance. I implemented and benchmarked it here: https://github.com/senderista/hashtable-benchmarks. Storing integer keys as their hash values (using a reversible hash function) also helps performance. I implemented a dozen or so 32- and 64-bit reversible integer hash functions in the same repo.

Re: Show HN: A Simple GPU Hash Table

#15

Post by nosferalatu75 »

senderista wrote: post #14

You might want to check out Bidirectional Linear Probing, which can handle load factor >90% with good performance. I implemented and benchmarked it here: https://github.com/senderista/hashtable-benchmarks . Storing integer keys as their hash values (using a reversible hash function) also helps performance. I implemented a dozen or so 32- and 64-bit reversible integer hash functions in the same repo.

That's great work. Thanks! Using a reversible hash function is a good idea.

Re: Show HN: A Simple GPU Hash Table

#16

Post by senderista »

nosferalatu75 wrote: post #15
senderista wrote: post #14

You might want to check out Bidirectional Linear Probing, which can handle load factor >90% with good performance. I implemented and benchmarked it here: https://github.com/senderista/hashtable-benchmarks . Storing integer keys as their hash values (using a reversible hash function) also helps performance. I implemented a dozen or so 32- and 64-bit reversible integer hash functions in the same repo.

That's great work. Thanks! Using a reversible hash function is a good idea.

FYI here's a concurrent version of BLP (I haven't implemented it but I stole their simplified insert algorithm): https://pdfs.semanticscholar.org/6d6c/ca94c57d408c0b1164d6ff.... Also see a compact version (concurrent Cleary hash table) by the same authors: https://www.researchgate.net/profile/Alfons_Laarman/publicat....
Post reply on HN