Author: Armin Rigo <[email protected]>
Branch:
Changeset: r1010:48150a83b44a
Date: 2014-03-14 11:17 +0100
http://bitbucket.org/pypy/stmgc/changeset/48150a83b44a/
Log: Give up with the constrain that tree_insert() only accepts keys
aligned to multiples of 8.
diff --git a/c7/stm/list.c b/c7/stm/list.c
--- a/c7/stm/list.c
+++ b/c7/stm/list.c
@@ -75,7 +75,7 @@
static wlog_t *_tree_find(char *entry, uintptr_t addr)
{
- uintptr_t key = addr;
+ uintptr_t key = TREE_HASH(addr);
while (((long)entry) & 1) {
/* points to a further level */
key >>= TREE_BITS;
@@ -122,10 +122,9 @@
static void tree_insert(struct tree_s *tree, uintptr_t addr, uintptr_t val)
{
assert(addr != 0); /* the NULL key is reserved */
- assert(!(addr & (sizeof(void *) - 1))); /* the key must be aligned */
retry:;
wlog_t *wlog;
- uintptr_t key = addr;
+ uintptr_t key = TREE_HASH(addr);
int shift = 0;
char *p = (char *)(tree->toplevel.items);
char *entry;
@@ -155,7 +154,7 @@
_tree_grab(tree, sizeof(wlog_node_t));
if (node == NULL) goto retry;
_tree_clear_node(node);
- uintptr_t key1 = wlog1->addr;
+ uintptr_t key1 = TREE_HASH(wlog1->addr);
char *p1 = (char *)(node->items);
*(wlog_t **)(p1 + ((key1 >> shift) & TREE_MASK)) = wlog1;
*(char **)p = ((char *)node) + 1;
diff --git a/c7/stm/list.h b/c7/stm/list.h
--- a/c7/stm/list.h
+++ b/c7/stm/list.h
@@ -82,17 +82,19 @@
supporting very high performance in TREE_FIND in the common case where
there are no or few elements in the tree, but scaling correctly
if the number of items becomes large (logarithmically, rather
- than almost-constant-time with hash maps, but with low constants). */
+ than almost-constant-time with hash maps, but with low constants).
+ The value 0 cannot be used as a key.
+*/
#define TREE_BITS 4
#define TREE_ARITY (1 << TREE_BITS)
-#define TREE_DEPTH_MAX ((sizeof(void*)*8 - 2 + TREE_BITS-1) / TREE_BITS)
-/* sizeof(void*) = total number of bits
- 2 = bits that we ignore anyway (2 or 3, conservatively 2)
+#define TREE_DEPTH_MAX ((sizeof(void*)*8 + TREE_BITS-1) / TREE_BITS)
+/* sizeof(void*)*8 = total number of bits
(x + TREE_BITS-1) / TREE_BITS = divide by TREE_BITS, rounding up
*/
+#define TREE_HASH(key) ((key) ^ ((key) << 4))
#define TREE_MASK ((TREE_ARITY - 1) * sizeof(void*))
typedef struct {
@@ -174,7 +176,7 @@
#define TREE_FIND(tree, addr1, result, goto_not_found) \
{ \
- uintptr_t _key = (addr1); \
+ uintptr_t _key = TREE_HASH(addr1); \
char *_p = (char *)((tree).toplevel.items); \
char *_entry = *(char **)(_p + (_key & TREE_MASK)); \
if (_entry == NULL) \
diff --git a/c7/stm/prebuilt.c b/c7/stm/prebuilt.c
--- a/c7/stm/prebuilt.c
+++ b/c7/stm/prebuilt.c
@@ -16,13 +16,11 @@
return;
/* If the object was already moved, it is stored in 'tree_prebuilt_objs'.
- For now we use this dictionary, with keys being equal to the double
- of the numeric address of the prebuilt object. We double them in
- order to support addresses that are only 4-byte-aligned in the
- static data.
+ For now we use this dictionary, with keys being equal to the numeric
+ address of the prebuilt object.
*/
wlog_t *item;
- TREE_FIND(*tree_prebuilt_objs, 2 * (uintptr_t)obj, item, goto not_found);
+ TREE_FIND(*tree_prebuilt_objs, (uintptr_t)obj, item, goto not_found);
*pstaticobj_invalid = (object_t *)item->val; /* already moved */
return;
@@ -42,7 +40,7 @@
nobj->stm_flags = GCFLAG_WRITE_BARRIER;
/* Add the object to the tree */
- tree_insert(tree_prebuilt_objs, 2 * (uintptr_t)obj, (uintptr_t)nobj);
+ tree_insert(tree_prebuilt_objs, (uintptr_t)obj, (uintptr_t)nobj);
/* Done */
*pstaticobj_invalid = nobj;
diff --git a/c7/test/test_list.py b/c7/test/test_list.py
--- a/c7/test/test_list.py
+++ b/c7/test/test_list.py
@@ -65,34 +65,34 @@
def test_tree_add():
t = lib.tree_create()
- lib.tree_insert(t, 23000, 456)
- for i in range(0, 100000, 1000):
- assert lib.tree_contains(t, i) == (i == 23000)
+ lib.tree_insert(t, 23, 456)
+ for i in range(0, 100):
+ assert lib.tree_contains(t, i) == (i == 23)
lib.tree_free(t)
def test_tree_is_cleared():
t = lib.tree_create()
assert lib.tree_is_cleared(t)
- lib.tree_insert(t, 23000, 456)
+ lib.tree_insert(t, 23, 456)
assert not lib.tree_is_cleared(t)
lib.tree_free(t)
def test_tree_delete_item():
t = lib.tree_create()
- lib.tree_insert(t, 23000, 456)
- lib.tree_insert(t, 42000, 34289)
+ lib.tree_insert(t, 23, 456)
+ lib.tree_insert(t, 42, 34289)
assert not lib.tree_is_cleared(t)
- assert lib.tree_contains(t, 23000)
- res = lib.tree_delete_item(t, 23000)
+ assert lib.tree_contains(t, 23)
+ res = lib.tree_delete_item(t, 23)
assert res
- assert not lib.tree_contains(t, 23000)
- res = lib.tree_delete_item(t, 23000)
+ assert not lib.tree_contains(t, 23)
+ res = lib.tree_delete_item(t, 23)
assert not res
- res = lib.tree_delete_item(t, 21000)
+ res = lib.tree_delete_item(t, 21)
assert not res
assert not lib.tree_is_cleared(t)
- assert lib.tree_contains(t, 42000)
- res = lib.tree_delete_item(t, 42000)
+ assert lib.tree_contains(t, 42)
+ res = lib.tree_delete_item(t, 42)
assert res
assert not lib.tree_is_cleared(t) # not cleared, but still empty
for i in range(100):
@@ -101,18 +101,18 @@
def test_tree_walk():
t = lib.tree_create()
- lib.tree_insert(t, 23000, 456)
- lib.tree_insert(t, 42000, 34289)
+ lib.tree_insert(t, 23, 456)
+ lib.tree_insert(t, 42, 34289)
a = ffi.new("uintptr_t[10]")
res = lib.test_tree_walk(t, a)
assert res == 2
- assert ((a[0] == 23000 and a[1] == 42000) or
- (a[0] == 42000 and a[1] == 23000))
+ assert ((a[0] == 23 and a[1] == 42) or
+ (a[0] == 42 and a[1] == 23))
lib.tree_free(t)
def test_tree_walk_big():
t = lib.tree_create()
- values = random.sample(xrange(0, 1000000, 8), 300)
+ values = random.sample(xrange(1, 100000), 300)
for x in values:
lib.tree_insert(t, x, x)
a = ffi.new("uintptr_t[1000]")
@@ -123,3 +123,7 @@
found.add(a[i])
assert found == set(values)
lib.tree_free(t)
+
+def test_hash_permutation():
+ hashes = [((n ^ (n << 4)) & 0xFF0) for n in range(256)]
+ assert set(hashes) == set(range(0, 4096, 16))
_______________________________________________
pypy-commit mailing list
[email protected]
https://mail.python.org/mailman/listinfo/pypy-commit
