aboutsummaryrefslogtreecommitdiffstats
path: root/erts
diff options
context:
space:
mode:
authorSverker Eriksson <[email protected]>2015-03-24 15:03:46 +0100
committerSverker Eriksson <[email protected]>2015-03-24 20:04:16 +0100
commit8d31ecea8b68ef6e16d7d77c0160e36f078b98de (patch)
tree7ca724bc0db8221a64a28bfb5fc83b37e0181d42 /erts
parentdb54eaa94562b49c81b677948a8e9139ebdb010e (diff)
downloadotp-8d31ecea8b68ef6e16d7d77c0160e36f078b98de.tar.gz
otp-8d31ecea8b68ef6e16d7d77c0160e36f078b98de.tar.bz2
otp-8d31ecea8b68ef6e16d7d77c0160e36f078b98de.zip
erts: Optimize hashmap_get
Diffstat (limited to 'erts')
-rw-r--r--erts/emulator/beam/erl_map.c96
1 files changed, 36 insertions, 60 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index ef806c2cfa..3852366876 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -1837,75 +1837,51 @@ erts_hashmap_get_rel(Uint32 hx, Eterm key, Eterm node, Eterm *map_base)
erts_hashmap_get(Uint32 hx, Eterm key, Eterm node)
#endif
{
- Eterm *ptr, hdr;
- Uint ix,slot, lvl = 0;
+ Eterm *ptr, hdr, *res;
+ Uint ix, lvl = 0;
Uint32 hval,bp;
DeclareTmpHeapNoproc(th,2);
UseTmpHeapNoproc(2);
+ ASSERT(is_boxed(node));
+ ptr = boxed_val(node);
+ hdr = *ptr;
+ ASSERT(is_header(hdr));
+ ASSERT(is_hashmap_header_head(hdr));
+ ptr++;
+
for (;;) {
- switch(primary_tag(node)) {
- case TAG_PRIMARY_LIST: /* LEAF NODE [K|V] */
- ptr = list_val(node);
- UnUseTmpHeapNoproc(2);
-
- if (eq_rel(CAR(ptr), map_base, key, NULL)) {
- return &(CDR(ptr));
- }
- return NULL;
- case TAG_PRIMARY_BOXED:
- ptr = boxed_val(node);
- hdr = *ptr;
- ASSERT(is_header(hdr));
-
- switch(hdr & _HEADER_MAP_SUBTAG_MASK) {
- case HAMT_SUBTAG_HEAD_ARRAY:
- ix = hashmap_index(hx);
- hx = hashmap_shift_hash(th,hx,lvl,key);
- node = ptr[ix+2];
- break;
- case HAMT_SUBTAG_NODE_BITMAP:
- hval = MAP_HEADER_VAL(hdr);
- ix = hashmap_index(hx);
- bp = 1 << ix;
- slot = hashmap_bitcount(hval & (bp - 1));
-
- /* occupied */
- if (bp & hval) {
- hx = hashmap_shift_hash(th,hx,lvl,key);
- node = ptr[slot+1];
- break;
- }
- /* not occupied */
- UnUseTmpHeapNoproc(2);
- return NULL;
- case HAMT_SUBTAG_HEAD_BITMAP:
- hval = MAP_HEADER_VAL(hdr);
- ix = hashmap_index(hx);
- bp = 1 << ix;
- slot = hashmap_bitcount(hval & (bp - 1));
-
- /* occupied */
- if (bp & hval) {
- hx = hashmap_shift_hash(th,hx,lvl,key);
- node = ptr[slot+2];
- break;
- }
- /* not occupied */
- UnUseTmpHeapNoproc(2);
- return NULL;
- default:
- erl_exit(1, "bad header tag %ld\r\n", hdr & _HEADER_MAP_SUBTAG_MASK);
- break;
- }
- break;
- default:
- erl_exit(1, "bad primary tag %p\r\n", node);
+ hval = MAP_HEADER_VAL(hdr);
+ ix = hashmap_index(hx);
+ if (hval != 0xffff) {
+ bp = 1 << ix;
+ if (!(bp & hval)) {
+ /* not occupied */
+ res = NULL;
break;
+ }
+ ix = hashmap_bitcount(hval & (bp - 1));
+ }
+ node = ptr[ix+1];
+
+ if (is_list(node)) { /* LEAF NODE [K|V] */
+ ptr = list_val(node);
+
+ res = eq_rel(CAR(ptr), map_base, key, NULL) ? &(CDR(ptr)) : NULL;
+ break;
}
+
+ hx = hashmap_shift_hash(th,hx,lvl,key);
+
+ ASSERT(is_boxed(node));
+ ptr = boxed_val(node);
+ hdr = *ptr;
+ ASSERT(is_header(hdr));
+ ASSERT(!is_hashmap_header_head(hdr));
}
+
UnUseTmpHeapNoproc(2);
- return NULL;
+ return res;
}
Eterm erts_hashmap_insert(Process *p, Uint32 hx, Eterm key, Eterm value,