Another Potential CPU Optimization For Mesa: Quadratic Probing

Mesa developer Thomas Helland is looking at reviving an old set of Mesa patches that could help out in some CPU-bound scenarios.

Helland re-discovered some old Mesa patches from April 2015 for implementing quadratic probing in hash tables for being faster rather than the linear re-probing hash table as is used currently. Helland explained further in the patch, "This will allow us to remove the large static table and use a power of two hash table size that we can compute on the fly. We can use bitmasking instead of modulo to fit our hash in the table, and it's less code. By using the algorithm hash = sh + i/2 + i*i/2 we are guaranteed that all retries from the quad probing are distinct, and so we should be able to completely fill the table."

When re-basing these patches and testing against Mesa master, from looking at the perf analysis on shader-db he found the hash table operations indeed were reduced. The overall impact was about a 10% reduction in the shader-db run-time. That's promising, but he's looking for feedback if he should continue exploring this potential "win" and also how it affects the performance for real hardware with real games. In particular, with how it affects the Borderlands 2 Linux performance with that being a CPU-heavy game, as outlined with the call for Mesa GL threading.

Helland's comments in RFC: Quadratic probing for the win.