diff options
| author | Sverker Eriksson <[email protected]> | 2015-03-31 12:13:57 +0200 |
|---|---|---|
| committer | Sverker Eriksson <[email protected]> | 2015-03-31 12:13:57 +0200 |
| commit | 8f7246a7c02a50561c171f3d91170a2af96eddbf (patch) | |
| tree | 04e28fcb966cf0fe5c250af832a8400cdf1e5bca | |
| parent | 450e5b610ac2de4817606c2966d9fb5a9850887a (diff) | |
| download | otp-8f7246a7c02a50561c171f3d91170a2af96eddbf.tar.gz otp-8f7246a7c02a50561c171f3d91170a2af96eddbf.tar.bz2 otp-8f7246a7c02a50561c171f3d91170a2af96eddbf.zip | |
erts: Optimize insert and delete for big maps
Do fast path without bit count for full internal nodes.
| -rw-r--r-- | erts/emulator/beam/erl_map.c | 71 |
1 files changed, 40 insertions, 31 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index ab40f47919..5a70407e42 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1937,26 +1937,31 @@ int erts_hashmap_insert_down(Uint32 hx, Eterm key, Eterm node, Uint *sz, case HAMT_SUBTAG_NODE_BITMAP: hval = MAP_HEADER_VAL(hdr); ix = hashmap_index(hx); - bp = 1 << ix; - slot = hashmap_bitcount(hval & (bp - 1)); - n = hashmap_bitcount(hval); + bp = 1 << ix; + if (hval == 0xffff) { + slot = ix; + n = 16; + } else { + slot = hashmap_bitcount(hval & (bp - 1)); + n = hashmap_bitcount(hval); + } + + ESTACK_PUSH4(*sp, n, bp, slot, node); + + if (!(bp & hval)) { /* not occupied */ + if (is_update) { + return 0; + } + size += HAMT_NODE_BITMAP_SZ(n+1); + goto unroll; + } + + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+1]; + ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); + size += HAMT_NODE_BITMAP_SZ(n); + break; - ESTACK_PUSH4(*sp, n, bp, slot, node); - - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+1]; - ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); - size += HAMT_NODE_BITMAP_SZ(n); - break; - } - /* not occupied */ - if (is_update) { - return 0; - } - size += HAMT_NODE_BITMAP_SZ(n+1); - goto unroll; case HAMT_SUBTAG_HEAD_BITMAP: hval = MAP_HEADER_VAL(hdr); ix = hashmap_index(hx); @@ -2183,21 +2188,25 @@ static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm map) { hval = MAP_HEADER_VAL(hdr); ix = hashmap_index(hx); bp = 1 << ix; - slot = hashmap_bitcount(hval & (bp - 1)); - n = hashmap_bitcount(hval); + if (hval == 0xffff) { + slot = ix; + n = 16; + } else if (bp & hval) { + slot = hashmap_bitcount(hval & (bp - 1)); + n = hashmap_bitcount(hval); + } else { + /* not occupied */ + goto not_found; + } ESTACK_PUSH4(stack, n, bp, slot, node); - /* occupied */ - if (bp & hval) { - hx = hashmap_shift_hash(th,hx,lvl,key); - node = ptr[slot+1]; - ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); - size += HAMT_NODE_BITMAP_SZ(n); - break; - } - /* not occupied */ - goto not_found; + hx = hashmap_shift_hash(th,hx,lvl,key); + node = ptr[slot+1]; + ASSERT(HAMT_NODE_BITMAP_SZ(n) <= 17); + size += HAMT_NODE_BITMAP_SZ(n); + break; + case HAMT_SUBTAG_HEAD_BITMAP: hval = MAP_HEADER_VAL(hdr); ix = hashmap_index(hx); |