util/set: Add specialized resizing add function
authorConnor Abbott <cwabbott0@gmail.com>
Mon, 20 May 2019 12:59:40 +0000 (14:59 +0200)
committerConnor Abbott <cwabbott0@gmail.com>
Fri, 31 May 2019 17:14:16 +0000 (19:14 +0200)
commit6f9beb28bb55ccf01445c8e57d3dca5216ec530f
tree784f9a24a071af2fa7b072347a6b1dff2dfc478f
parent451211741c894e7aea33f92a75fe9870fc5f1478
util/set: Add specialized resizing add function

A significant portion of the time spent in nir_opt_cse for the Dolphin
ubershaders was in resizing the set. When resizing a hash table, we know
in advance that each new element to be inserted will be different from
every other element, so we don't have to compare them, and there will be
no tombstone elements, so we don't have to worry about caching the
first-seen tombstone. We add a specialized add function which skips
these steps entirely, speeding up resizing.

Compile-time results from my shader-db database:

Difference at 95.0% confidence
-2.29143 +/- 0.845534
-0.529475% +/- 0.194767%
(Student's t, pooled s = 1.08807)

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