[Mesa-dev] [PATCH 4/8] util: Change util/set to use quadratic probing

[Thomas Helland]

Less code, and gives a small speedup due to
avoiding the extra modulo operation.
Also less memory footprint since rehash gets dropped.

Results from oprofile on a shader-db run:
set_add	                2.80 ---> 2.70
set_search              2.86 ---> 2.74
runtime	                162  ---> 165
---
 src/util/set.c | 81 +++++++++++++++++++++++++++-------------------------------
 src/util/set.h |  1 -
 2 files changed, 38 insertions(+), 44 deletions(-)

diff --git a/src/util/set.c b/src/util/set.c
index f01f869..f350c1e 100644
--- a/src/util/set.c
+++ b/src/util/set.c
@@ -49,39 +49,39 @@ uint32_t deleted_key_value;
 const void *deleted_key = &deleted_key_value;
 
 static const struct {
-   uint32_t max_entries, size, rehash;
+   uint32_t max_entries, size;
 } hash_sizes[] = {
-   { 2,            5,            3            },
-   { 4,            7,            5            },
-   { 8,            13,           11           },
-   { 16,           19,           17           },
-   { 32,           43,           41           },
-   { 64,           73,           71           },
-   { 128,          151,          149          },
-   { 256,          283,          281          },
-   { 512,          571,          569          },
-   { 1024,         1153,         1151         },
-   { 2048,         2269,         2267         },
-   { 4096,         4519,         4517         },
-   { 8192,         9013,         9011         },
-   { 16384,        18043,        18041        },
-   { 32768,        36109,        36107        },
-   { 65536,        72091,        72089        },
-   { 131072,       144409,       144407       },
-   { 262144,       288361,       288359       },
-   { 524288,       576883,       576881       },
-   { 1048576,      1153459,      1153457      },
-   { 2097152,      2307163,      2307161      },
-   { 4194304,      4613893,      4613891      },
-   { 8388608,      9227641,      9227639      },
-   { 16777216,     18455029,     18455027     },
-   { 33554432,     36911011,     36911009     },
-   { 67108864,     73819861,     73819859     },
-   { 134217728,    147639589,    147639587    },
-   { 268435456,    295279081,    295279079    },
-   { 536870912,    590559793,    590559791    },
-   { 1073741824,   1181116273,   1181116271   },
-   { 2147483648ul, 2362232233ul, 2362232231ul }
+   { 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 }
 };
 
 static int
@@ -116,7 +116,6 @@ _mesa_set_create(void *mem_ctx,
 
    ht->size_index = 0;
    ht->size = hash_sizes[ht->size_index].size;
-   ht->rehash = hash_sizes[ht->size_index].rehash;
    ht->max_entries = hash_sizes[ht->size_index].max_entries;
    ht->key_hash_function = key_hash_function;
    ht->key_equals_function = key_equals_function;
@@ -164,11 +163,11 @@ static struct set_entry *
 set_search(const struct set *ht, uint32_t hash, const void *key)
 {
    uint32_t hash_address;
+   uint32_t quad_hash;
 
+   quad_hash = 1;
    hash_address = hash % ht->size;
    do {
-      uint32_t double_hash;
-
       struct set_entry *entry = ht->table + hash_address;
 
       if (entry_is_free(entry)) {
@@ -179,9 +178,7 @@ set_search(const struct set *ht, uint32_t hash, const void *key)
          }
       }
 
-      double_hash = 1 + hash % ht->rehash;
-
-      hash_address = (hash_address + double_hash) % ht->size;
+      hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
    } while (hash_address != hash % ht->size);
 
    return NULL;
@@ -225,7 +222,6 @@ set_rehash(struct set *ht, unsigned new_size_index)
    ht->table = table;
    ht->size_index = new_size_index;
    ht->size = hash_sizes[ht->size_index].size;
-   ht->rehash = hash_sizes[ht->size_index].rehash;
    ht->max_entries = hash_sizes[ht->size_index].max_entries;
    ht->entries = 0;
    ht->deleted_entries = 0;
@@ -251,6 +247,7 @@ static struct set_entry *
 set_add(struct set *ht, uint32_t hash, const void *key)
 {
    uint32_t hash_address;
+   uint32_t quad_hash;
    struct set_entry *available_entry = NULL;
 
    if (ht->entries >= ht->max_entries) {
@@ -259,10 +256,10 @@ set_add(struct set *ht, uint32_t hash, const void *key)
       set_rehash(ht, ht->size_index);
    }
 
+   quad_hash = 1;
    hash_address = hash % ht->size;
    do {
       struct set_entry *entry = ht->table + hash_address;
-      uint32_t double_hash;
 
       if (!entry_is_present(entry)) {
          /* Stash the first available entry we find */
@@ -288,9 +285,7 @@ set_add(struct set *ht, uint32_t hash, const void *key)
          return entry;
       }
 
-      double_hash = 1 + hash % ht->rehash;
-
-      hash_address = (hash_address + double_hash) % ht->size;
+      hash_address = (hash_address + quad_hash*quad_hash) % ht->size;
    } while (hash_address != hash % ht->size);
 
    if (available_entry) {
diff --git a/src/util/set.h b/src/util/set.h
index 9acd2c2..5a1097c 100644
--- a/src/util/set.h
+++ b/src/util/set.h
@@ -46,7 +46,6 @@ struct set {
    uint32_t (*key_hash_function)(const void *key);
    bool (*key_equals_function)(const void *a, const void *b);
    uint32_t size;
-   uint32_t rehash;
    uint32_t max_entries;
    uint32_t size_index;
    uint32_t entries;
-- 
2.2.1