[Mesa-dev] [PATCH 5/8] util: Change set to use power-of-two sized table

[Thomas Helland]

Should be more efficient as we can use a bitmask
operation instead of an expensive modulo.

Results from oprofile on a shader-db run:
set_add	                2.70 ---> 1.69
set_search              2.74 ---> 2.11
runtime	                165  ---> 157
---
 src/util/set.c | 82 +++++++++++++++++++++++++++++++---------------------------
 1 file changed, 44 insertions(+), 38 deletions(-)

diff --git a/src/util/set.c b/src/util/set.c
index f350c1e..f231dd1 100644
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -48,40 +48,46 @@
 uint32_t deleted_key_value;
 const void *deleted_key = &deleted_key_value;
 
+/**
+ * We chose table sizes that's a power of two.
+ * This is computationally less expensive than primes.
+ * FNV-1a has good avalanche properties, so collision is not an issue.
+ * These tables are sized to have an extra 10% free to avoid
+ * exponential performance degradation as the hash table fills
+ */
 static const struct {
    uint32_t max_entries, size;
 } hash_sizes[] = {
-   { 2,            5            },
-   { 4,            7            },
-   { 8,            13           },
-   { 16,           19           },
-   { 32,           43           },
-   { 64,           73           },
-   { 128,          151          },
-   { 256,          283          },
-   { 512,          571          },
-   { 1024,         1153         },
-   { 2048,         2269         },
-   { 4096,         4519         },
-   { 8192,         9013         },
-   { 16384,        18043        },
-   { 32768,        36109        },
-   { 65536,        72091        },
-   { 131072,       144409       },
-   { 262144,       288361       },
-   { 524288,       576883       },
-   { 1048576,      1153459      },
-   { 2097152,      2307163      },
-   { 4194304,      4613893      },
-   { 8388608,      9227641      },
-   { 16777216,     18455029     },
-   { 33554432,     36911011     },
-   { 67108864,     73819861     },
-   { 134217728,    147639589    },
-   { 268435456,    295279081    },
-   { 536870912,    590559793    },
-   { 1073741824,   1181116273   },
-   { 2147483648ul, 2362232233ul }
+   { 3,            4            },
+   { 7,            8            },
+   { 14,           16           },
+   { 28,           32           },
+   { 57,           64           },
+   { 115,          128          },
+   { 230,          256          },
+   { 460,          512          },
+   { 921,          1024         },
+   { 1843,         2048         },
+   { 3686,         4096         },
+   { 7372,         8192         },
+   { 14745,        16384        },
+   { 29491,        32768        },
+   { 58982,        65536        },
+   { 117964,       131072       },
+   { 235929,       262144       },
+   { 471859,       524288       },
+   { 943718,       1048576      },
+   { 1887436,      2097152      },
+   { 3774873,      4194304      },
+   { 7549747,      8388608      },
+   { 15099494,     16777216     },
+   { 30198988,     33554432     },
+   { 60397977,     67108864     },
+   { 120795955,    134217728    },
+   { 241591910,    268435456    },
+   { 483183820,    536870912    },
+   { 966367641,    1073741824   },
+   { 1932735283ul, 2147483648ul }
 };
 
 static int
@@ -166,7 +172,7 @@ set_search(const struct set *ht, uint32_t hash, const void *key)
    uint32_t quad_hash;
 
    quad_hash = 1;
-   hash_address = hash % ht->size;
+   hash_address = hash & (ht->size -1);
    do {
       struct set_entry *entry = ht->table + hash_address;
 
@@ -178,8 +184,8 @@ set_search(const struct set *ht, uint32_t hash, const void *key)
          }
       }
 
-      hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
-   } while (hash_address != hash % ht->size);
+      hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
+   } while (hash_address != (hash & (ht->size -1)));
 
    return NULL;
 }
@@ -257,7 +263,7 @@ set_add(struct set *ht, uint32_t hash, const void *key)
    }
 
    quad_hash = 1;
-   hash_address = hash % ht->size;
+   hash_address = hash & (ht->size -1);
    do {
       struct set_entry *entry = ht->table + hash_address;
 
@@ -285,8 +291,8 @@ set_add(struct set *ht, uint32_t hash, const void *key)
          return entry;
       }
 
-      hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
-   } while (hash_address != hash % ht->size);
+      hash_address = (hash_address + quad_hash*quad_hash) & (ht->size -1);
+   } while (hash_address != (hash & (ht->size -1)));
 
    if (available_entry) {
       if (entry_is_deleted(available_entry))
@@ -363,7 +369,7 @@ _mesa_set_random_entry(struct set *ht,
                        int (*predicate)(struct set_entry *entry))
 {
    struct set_entry *entry;
-   uint32_t i = rand() % ht->size;
+   uint32_t i = rand() & (ht->size -1);
 
    if (ht->entries == 0)
       return NULL;
-- 
2.2.1