util/set: Pull out loop-invariant computations
authorConnor Abbott <cwabbott0@gmail.com>
Mon, 20 May 2019 12:58:06 +0000 (14:58 +0200)
committerConnor Abbott <cwabbott0@gmail.com>
Fri, 31 May 2019 17:14:04 +0000 (19:14 +0200)
commitf7ff6856492e8437ad78bb6a853a681afd3fc98c
tree496d0522d8b9e68fefb53fd3e0159dd5c57c3b36
parent3bd073301182b4bb2dae28bee6175ebe78184f3d
util/set: Pull out loop-invariant computations

Unfortunately GCC can't do this for us, probably because we call the key
comparison function which GCC can't prove won't modify arbitrary memory.
This is a pretty hot function, so do the optimization manually to be
sure the compiler will get it right.

While we're here, make the computation of the new probe address use a
single conditional subtract instead of a modulo, since we know that it
won't ever get as big as 2 * ht->size before the modulo. Modulos tend to
be pretty expensive operations.

shader-db compile time results for my database:

Difference at 95.0% confidence
-2.24934 +/- 0.69897
-0.516296% +/- 0.159993%
(Student's t, pooled s = 0.983684)

Reviewed-by: Eric Anholt <eric@anholt.net>
Acked-by: Jason Ekstrand <jason@jlekstrand.net>
src/util/set.c