util/sparse_array: Stash the node level in the node pointer This reworks the data structure a bit and, in my view, simplifies it. Instead of each node having a header which has the node level in it, we use the bottom 6 bits of the pointer for that. This requires us to allocate with the os_malloc/free_aligned helpers (which call into posix_memalign on Linux) but cache-line aligning our allocations is actually probably a good thing given that we're doing atomics on them. The primary advantages to doing this is that it changes the number of memory accesses per tree level from 2 to 1 when walking the tree because we no longer have to look at node->level. Reviewed-by: Lionel Landwerlin <[email protected]> Tested-by: Marge Bot <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4228> Part-of: <https://gitlab.freedesktop.org/mesa/mesa/-/merge_requests/4228>
diff --git a/src/util/sparse_array.h b/src/util/sparse_array.h index 3947a2f..f91fe21 100644 --- a/src/util/sparse_array.h +++ b/src/util/sparse_array.h
@@ -69,7 +69,7 @@ size_t elem_size; unsigned node_size_log2; - struct util_sparse_array_node *root; + uintptr_t root; }; void util_sparse_array_init(struct util_sparse_array *arr,