Hash Functions for GPU Rendering – Nathan Reed’s coding blog

submited by

Style Pass

2021-05-22 07:30:09

Back in 2013, I wrote a somewhat popular article about pseudorandom number generation on the GPU. In the eight years since, a number of new PRNGs and hash functions have been developed; and a few months ago, an excellent paper on the topic appeared in JCGT: Hash Functions for GPU Rendering, by Mark Jarzynski and Marc Olano. I thought it was time to update my former post in light of this paper’s findings.

Jarzynski and Olano’s paper compares GPU implementations of a large number of different hash functions along dual axes of performance (measured by time to render a quad evaluating the hash at each pixel) and statistical quality (quantified by the count of failures of TESTU01 “Big Crush” tests). Naturally, there is quite a spread of results in both performance and quality. Jarzynski and Olano then identify the few hash functions that lie along the Pareto frontier—meaning they are the best choices along the whole spectrum of performance/quality trade-offs.

When choosing a hash function, we might sometimes prioritize performance, and other times might prefer to sacrifice performance in favor of higher quality (real-time versus offline applications, for example). The Pareto frontier provides the set of optimal choices for any point along that balance—ranging from LCGs at the extreme performance-oriented end, to some quite expensive but very high-quality hashes at the other end.