aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-03-31 12:13:57 +0200
committerSverker Eriksson <[email protected]>2015-03-31 12:13:57 +0200
commit8f7246a7c02a50561c171f3d91170a2af96eddbf (patch)
tree04e28fcb966cf0fe5c250af832a8400cdf1e5bca
parent450e5b610ac2de4817606c2966d9fb5a9850887a (diff)
downloadotp-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.c71
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);