[Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.
Mesa's chaining hash table for object names is slow, and this should be much
faster. I namespaced the functions under _mesa_*, to avoid visibility
troubles that we may have had before with hash_table_* functions. The
hash_table.c file unfortunately lives in program/ still to avoid confusion
with automake's dependency files that would otherwise require a make distclean
across this change.
---
configure.ac |1 +
src/mesa/main/hash_table.h | 105 +
src/mesa/main/tests/Makefile.am|2 +
src/mesa/main/tests/hash_table/.gitignore | 10 +
src/mesa/main/tests/hash_table/Makefile.am | 42 ++
src/mesa/main/tests/hash_table/delete_and_lookup.c | 74
src/mesa/main/tests/hash_table/delete_management.c | 88
src/mesa/main/tests/hash_table/destroy_callback.c | 66 +++
src/mesa/main/tests/hash_table/insert_and_lookup.c | 57 +++
src/mesa/main/tests/hash_table/insert_many.c | 72
src/mesa/main/tests/hash_table/null_destroy.c | 37 ++
src/mesa/main/tests/hash_table/random_entry.c | 88
src/mesa/main/tests/hash_table/remove_null.c | 45 ++
src/mesa/main/tests/hash_table/replacement.c | 64 +++
src/mesa/program/hash_table.c | 431
src/mesa/sources.mak |1 +
16 files changed, 1183 insertions(+)
create mode 100644 src/mesa/main/hash_table.h
create mode 100644 src/mesa/main/tests/hash_table/.gitignore
create mode 100644 src/mesa/main/tests/hash_table/Makefile.am
create mode 100644 src/mesa/main/tests/hash_table/delete_and_lookup.c
create mode 100644 src/mesa/main/tests/hash_table/delete_management.c
create mode 100644 src/mesa/main/tests/hash_table/destroy_callback.c
create mode 100644 src/mesa/main/tests/hash_table/insert_and_lookup.c
create mode 100644 src/mesa/main/tests/hash_table/insert_many.c
create mode 100644 src/mesa/main/tests/hash_table/null_destroy.c
create mode 100644 src/mesa/main/tests/hash_table/random_entry.c
create mode 100644 src/mesa/main/tests/hash_table/remove_null.c
create mode 100644 src/mesa/main/tests/hash_table/replacement.c
create mode 100644 src/mesa/program/hash_table.c
diff --git a/configure.ac b/configure.ac
index 6b97a26..9bd2d1d 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1973,6 +1973,7 @@ AC_CONFIG_FILES([configs/current
src/mesa/drivers/x11/Makefile
src/mesa/libdricore/Makefile
src/mesa/main/tests/Makefile
+ src/mesa/main/tests/hash_table/Makefile
src/mesa/x86-64/Makefile
src/mesa/x86/Makefile])
diff --git a/src/mesa/main/hash_table.h b/src/mesa/main/hash_table.h
new file mode 100644
index 000..78e3aea
--- /dev/null
+++ b/src/mesa/main/hash_table.h
@@ -0,0 +1,105 @@
+/*
+ * Copyright © 2009,2012 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ * Authors:
+ *Eric Anholt
+ *
+ */
+
+#include
+#include
+
+#ifndef _HASH_TABLE_H
+#define _HASH_TABLE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct hash_entry {
+ uint32_t hash;
+ const void *key;
+ void *data;
+};
+
+struct hash_table {
+ void *mem_ctx;
+ struct hash_entry *table;
+ bool (*key_equals_function)(const void *a, const void *b);
+ const void *deleted_key;
+ uint32_t size;
+ uint32_t rehash;
+ uint32_t max_entries;
+ uint32_t size_index;
+ uint32_t entries;
+ uint32_t deleted_entries;
+};
+
+struct hash_table *
+_mesa_hash_table_create(void *mem_ctx,
+bool (*key_equals_function)(const void *a,
+const void *b));
+void _mesa_hash_table_destroy(struct hash_table *ht,
+ void (*delete_function)(struct hash_entry
*entry));
+void _mesa_hash_table
Re: [Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.
I look forward to seeing this improved hash table land.
Great that it includes tests. I failed to find a test that artificially
constructed collisions and verified that they were handled correctly.
Maybe I'll submit a test for that.
Comments below. Everything looked correct, so my review mostly asks for
an occasional clarifying comment.
On 10/25/2012 09:13 AM, Eric Anholt wrote:
> Mesa's chaining hash table for object names is slow, and this should be much
> faster. I namespaced the functions under _mesa_*, to avoid visibility
> troubles that we may have had before with hash_table_* functions.
> The
> hash_table.c file unfortunately lives in program/ still to avoid confusion
> with automake's dependency files that would otherwise require a make distclean
> across this change.
The end result is absurd. There is a .c/.h pair in a directory that don't match
up. It looks like this:
program/hash_table.c implements main/hash_table.h
program/hash_table.h is header for program/chaining_hash_table.c
> diff --git a/src/mesa/program/hash_table.c b/src/mesa/program/hash_table.c
> new file mode 100644
> index 000..ba49437
> --- /dev/null
> +++ b/src/mesa/program/hash_table.c
> @@ -0,0 +1,431 @@
> +/*
> + * Copyright © 2009,2012 Intel Corporation
> +
> +/**
> + * Implements an open-addressing, linear-reprobing hash table.
> + *
> + * For more information, see:
> + *
> + * http://cgit.freedesktop.org/~anholt/hash_table/tree/README
> + */
> +
> +#include
> +#include
> +
> +#include "main/hash_table.h"
> +#include "ralloc.h"
> +
> +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
> +
Static please.
> +uint32_t deleted_key_value;
> +/**
> + * Finds a hash table entry with the given key and hash of that key.
> + *
> + * Returns NULL if no entry is found. Note that the data pointer may be
> + * modified by the user.
> + */
> +struct hash_entry *
> +_mesa_hash_table_search(struct hash_table *ht, uint32_t hash,
> +const void *key)
> +{
> + uint32_t hash_address;
> +
> + hash_address = hash % ht->size;
> + do {
> + uint32_t double_hash;
> +
> + struct hash_entry *entry = ht->table + hash_address;
> +
> + if (entry_is_free(entry)) {
> + return NULL;
> + } else if (entry_is_present(ht, entry) && entry->hash == hash) {
> + if (ht->key_equals_function(key, entry->key)) {
> +return entry;
> + }
> + }
> +
> + double_hash = 1 + hash % ht->rehash;
> +
> + hash_address = (hash_address + double_hash) % ht->size;
The while condition looks mystic. A comment here would be nice
explaining that we break the loop because we've cycled around to the
first probed address. Or simply a self-documenting variable name would
suffice.
> + } while (hash_address != hash % ht->size);
> +
> + return NULL;
> +}
> +/**
> + * Inserts the key with the given hash into the table.
> + *
> + * Note that insertion may rearrange the table on a resize or rehash,
> + * so previously found hash_entries are no longer valid after this function.
> + */
> +struct hash_entry *
> +_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash,
> +const void *key, void *data)
> +{
> + uint32_t hash_address;
> +
> + if (ht->entries >= ht->max_entries) {
> + _mesa_hash_table_rehash(ht, ht->size_index + 1);
> + } else if (ht->deleted_entries + ht->entries >= ht->max_entries) {
> + _mesa_hash_table_rehash(ht, ht->size_index);
> + }
> +
> + hash_address = hash % ht->size;
> + do {
> + struct hash_entry *entry = ht->table + hash_address;
> + uint32_t double_hash;
> +
> + if (!entry_is_present(ht, entry)) {
> + if (entry_is_deleted(ht, entry))
> +ht->deleted_entries--;
> + entry->hash = hash;
> + entry->key = key;
> + entry->data = data;
> + ht->entries++;
> + return entry;
> + }
> +
> + /* Implement replacement when another insert happens
> + * with a matching key. This is a relatively common
> + * feature of hash tables, with the alternative
> + * generally being "insert the new value as well, and
> + * return it first when the key is searched for".
> + *
> + * Note that the hash table doesn't have a delete
> + * callback. If freeing of old data pointers is
> + * required to avoid memory leaks, perform a search
> + * before inserting.
> + */
> + if (entry->hash == hash &&
> + ht->key_equals_function(key, entry->key)) {
> + entry->key = key;
> + entry->data = data;
> + return entry;
> + }
> +
> +
> + double_hash = 1 + hash % ht->rehash;
> +
> + hash_address = (hash_address + double_hash) % ht->size;
Ditto as for _mesa_hash_table_search().
> + } while (hash_address != hash % ht->size);
> +
> + /* We could hit here if a required resize failed. An unchecked-malloc
> +* application could igno
Re: [Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.
On 10/25/2012 09:13 AM, Eric Anholt wrote: Mesa's chaining hash table for object names is slow, and this should be much faster. I namespaced the functions under _mesa_*, to avoid visibility troubles that we may have had before with hash_table_* functions. The hash_table.c file unfortunately lives in program/ still to avoid confusion with automake's dependency files that would otherwise require a make distclean across this change. Non-clean builds break all the time anyway (or at least have in the recent past)...I'd say just put it where you want it. ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.
On 10/25/2012 10:13 AM, Eric Anholt wrote:
Mesa's chaining hash table for object names is slow, and this should be much
faster. I namespaced the functions under _mesa_*, to avoid visibility
troubles that we may have had before with hash_table_* functions. The
hash_table.c file unfortunately lives in program/ still to avoid confusion
with automake's dependency files that would otherwise require a make distclean
across this change.
---
configure.ac |1 +
src/mesa/main/hash_table.h | 105 +
src/mesa/main/tests/Makefile.am|2 +
src/mesa/main/tests/hash_table/.gitignore | 10 +
src/mesa/main/tests/hash_table/Makefile.am | 42 ++
src/mesa/main/tests/hash_table/delete_and_lookup.c | 74
src/mesa/main/tests/hash_table/delete_management.c | 88
src/mesa/main/tests/hash_table/destroy_callback.c | 66 +++
src/mesa/main/tests/hash_table/insert_and_lookup.c | 57 +++
src/mesa/main/tests/hash_table/insert_many.c | 72
src/mesa/main/tests/hash_table/null_destroy.c | 37 ++
src/mesa/main/tests/hash_table/random_entry.c | 88
src/mesa/main/tests/hash_table/remove_null.c | 45 ++
src/mesa/main/tests/hash_table/replacement.c | 64 +++
src/mesa/program/hash_table.c | 431
src/mesa/sources.mak |1 +
[I only skimmed the test programs]
diff --git a/src/mesa/program/hash_table.c b/src/mesa/program/hash_table.c
new file mode 100644
index 000..ba49437
--- /dev/null
+++ b/src/mesa/program/hash_table.c
@@ -0,0 +1,431 @@
+/*
+ * Copyright © 2009,2012 Intel Corporation
+ * Copyright © 1988-2004 Keith Packard and Bart Massey.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ * Except as contained in this notice, the names of the authors
+ * or their institutions shall not be used in advertising or
+ * otherwise to promote the sale, use or other dealings in this
+ * Software without prior written authorization from the
+ * authors.
+ *
+ * Authors:
+ *Eric Anholt
+ *Keith Packard
+ */
+
+/**
+ * Implements an open-addressing, linear-reprobing hash table.
+ *
+ * For more information, see:
+ *
+ * http://cgit.freedesktop.org/~anholt/hash_table/tree/README
+ */
+
+#include
+#include
+
+#include "main/hash_table.h"
+#include "ralloc.h"
+
+#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
+
+uint32_t deleted_key_value;
+
+/**
+ * From Knuth -- a good choice for hash/rehash values is p, p-2 where
+ * p and p-2 are both prime. 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, rehash;
+} 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,
Re: [Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.
Brian Paul writes: > On 10/25/2012 10:13 AM, Eric Anholt wrote: >> +struct hash_entry * >> +_mesa_hash_table_random_entry(struct hash_table *ht, >> + bool (*predicate)(struct hash_entry *entry)) > > Just curious, what is this function used for? Just testing? We have some really stupid behavior some of our caches where when we get more than n thousand entries, we flush the whole cache and start again. If you have a function that lets you easily pick a random entry, you can provide more consistent performance once the app's working set is larger than the cache size. I was using this with this hash table in the i965 driver's program cache at one point, though our new program cache setup makes this harder. >> diff --git a/src/mesa/sources.mak b/src/mesa/sources.mak >> index d51adf5..13ba16a 100644 >> --- a/src/mesa/sources.mak >> +++ b/src/mesa/sources.mak >> @@ -249,6 +249,7 @@ STATETRACKER_FILES = \ >> PROGRAM_FILES = \ >> $(SRCDIR)program/arbprogparse.c \ >> $(SRCDIR)program/chaining_hash_table.c \ >> +$(SRCDIR)program/hash_table.c \ >> $(SRCDIR)program/program.c \ >> $(SRCDIR)program/program_parse_extra.c \ >> $(SRCDIR)program/prog_cache.c \ > > Update the SConscript file too? Done (and the const change). pgpNfAbwHixLn.pgp Description: PGP signature ___ mesa-dev mailing list mesa-dev@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/mesa-dev
Re: [Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.
Chad Versace writes:
> I look forward to seeing this improved hash table land.
>
> Great that it includes tests. I failed to find a test that artificially
> constructed collisions and verified that they were handled correctly.
> Maybe I'll submit a test for that.
>
> Comments below. Everything looked correct, so my review mostly asks for
> an occasional clarifying comment.
> The while condition looks mystic. A comment here would be nice
> explaining that we break the loop because we've cycled around to the
> first probed address. Or simply a self-documenting variable name would
> suffice.
Check out the new version and see if it clarified.
>> +/**
>> + * Quick FNV-1 hash implementation based on:
>> + * http://www.isthe.com/chongo/tech/comp/fnv/
>> + *
>> + * FNV-1 is not be the best hash out there -- Jenkins's lookup3 is supposed
>> to
>> + * be quite good, and it probably beats FNV. But FNV has the advantage that
>> + * it involves almost no code. For an improvement on both, see Paul
>> + * Hsieh's //www.azillionmonkeys.com/qed/hash.html
>> + */
>> +uint32_t
>> +_mesa_hash_data(const void *key, size_t size)
>
> This prototype differs from the one in hash_table.h:
> _mesa_hash_data(const void *data, size_t size);
> Should it be 'data' or 'key'?
Meh, you're hashing the data in a key. Arbitrarily picked one to be
consistent and renamed the local var to something else.
>> +/** FNV-1 string hash implementation */
>> +uint32_t
>> +_mesa_hash_string(const void *key)
>
> I expect the signature here to be _mesa_hash_string(const char *key). I
> believe
> using void* will result in a future misuse of the function that would have
> been
> caught by the type system.
>
> Why did you choose void*?
Probably I was originally typing a function that was the
_mesa_hash_data() variant. Fixed.
>> +bool
>> +_mesa_key_string_equal(const void *a, const void *b)
>> +{
>> + return strcmp(a, b) == 0;
>> +}
>
>
> As for _mesa_key_string_equal(), a comment here would be nice stating
> that _mesa_key_value_equal() function is intended to be passed to
> _mesa_hash_table_create().
>
> Also, I find the name of this function very confusing. "It's comparing
> the values of what? The pointers? The pointed-to's? How does it compare
> the pointed-to's of void pointers?" I think renaming this to
> _mesa_key_pointer_equal() makes it immediately clear what this function does:
> it compares pointers.
Yeah, for the current use case the things compared are actually uint32s
stuffed into a pointer, which resulted in the name I had before. Still,
I think it's an improvement.
pgpteQ2i1zm43.pgp
Description: PGP signature
___
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
