From 3a34a18c2f318a4a9ea475ee80fe05bd64f05070 Mon Sep 17 00:00:00 2001 From: Rickard Green Date: Tue, 24 Jan 2017 17:31:01 +0100 Subject: Use magic refs for maps merge trap context --- erts/emulator/beam/erl_map.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 979a0040b0..990be8efb2 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1197,7 +1197,7 @@ static void hashmap_merge_ctx_destructor(Binary* ctx_bin) } BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1) { - Binary* ctx_bin = ((ProcBin *) binary_val(BIF_ARG_1))->val; + Binary* ctx_bin = erts_magic_ref2bin(BIF_ARG_1); ASSERT(ERTS_MAGIC_BIN_DESTRUCTOR(ctx_bin) == hashmap_merge_ctx_destructor); @@ -1453,9 +1453,9 @@ trap: /* Yield */ hashmap_merge_ctx_destructor); ctx = ERTS_MAGIC_BIN_DATA(ctx_b); sys_memcpy(ctx, &local_ctx, sizeof(HashmapMergeContext)); - hp = HAlloc(p, PROC_BIN_SIZE); + hp = HAlloc(p, ERTS_MAGIC_REF_THING_SIZE); ASSERT(ctx->trap_bin == THE_NON_VALUE); - ctx->trap_bin = erts_mk_magic_binary_term(&hp, &MSO(p), ctx_b); + ctx->trap_bin = erts_mk_magic_ref(&hp, &MSO(p), ctx_b); erts_set_gc_state(p, 0); } -- cgit v1.2.1 From 118de47d703e303aea7f4575849a37c11416ba14 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 14 Feb 2017 18:26:31 +0100 Subject: erts: Add deallocation veto for magic destructors A magic destructor can return 0 and thereby take control and prolong the lifetime of a magic binary. --- erts/emulator/beam/erl_map.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 990be8efb2..9062e44b10 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1188,12 +1188,13 @@ typedef struct HashmapMergeContext_ { #endif } HashmapMergeContext; -static void hashmap_merge_ctx_destructor(Binary* ctx_bin) +static int hashmap_merge_ctx_destructor(Binary* ctx_bin) { HashmapMergeContext* ctx = (HashmapMergeContext*) ERTS_MAGIC_BIN_DATA(ctx_bin); ASSERT(ERTS_MAGIC_BIN_DESTRUCTOR(ctx_bin) == hashmap_merge_ctx_destructor); PSTACK_DESTROY_SAVED(&ctx->pstack); + return 1; } BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1) { -- cgit v1.2.1 From d8c0f76c800051629cd9cf7279bf075435708a1c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Wed, 22 Feb 2017 16:52:29 +0100 Subject: erts: Introduce erts_internal:maps_to_list/2 --- erts/emulator/beam/erl_map.c | 66 +++++++++++++++++++++++++++++++++++++++----- 1 file changed, 59 insertions(+), 7 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 9062e44b10..a80f5d6a16 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -91,7 +91,7 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_ static Export hashmap_merge_trap_export; static BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1); static Uint hashmap_subtree_size(Eterm node); -static Eterm hashmap_to_list(Process *p, Eterm map); +static Eterm hashmap_to_list(Process *p, Eterm map, Sint n); static Eterm hashmap_keys(Process *p, Eterm map); static Eterm hashmap_values(Process *p, Eterm map); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node, Eterm *value); @@ -161,13 +161,58 @@ BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) { BIF_RET(res); } else if (is_hashmap(BIF_ARG_1)) { - return hashmap_to_list(BIF_P, BIF_ARG_1); + return hashmap_to_list(BIF_P, BIF_ARG_1, -1); } BIF_P->fvalue = BIF_ARG_1; BIF_ERROR(BIF_P, BADMAP); } +/* erts_internal:maps_to_list/2 + * + * This function should be removed once iterators are in place. + * Never document it. + * Never encourage its usage. + * + * A negative value in ARG 2 means the entire map. + */ + +BIF_RETTYPE erts_internal_maps_to_list_2(BIF_ALIST_2) { + Sint m; + if (term_to_Sint(BIF_ARG_2, &m)) { + if (is_flatmap(BIF_ARG_1)) { + Uint n; + Eterm* hp; + Eterm *ks,*vs, res, tup; + flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1); + + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); + n = flatmap_get_size(mp); + + if (m >= 0) { + n = m < n ? m : n; + } + + hp = HAlloc(BIF_P, (2 + 3) * n); + res = NIL; + + while(n--) { + tup = TUPLE2(hp, ks[n], vs[n]); hp += 3; + res = CONS(hp, tup, res); hp += 2; + } + + BIF_RET(res); + } else if (is_hashmap(BIF_ARG_1)) { + return hashmap_to_list(BIF_P, BIF_ARG_1, m); + } + BIF_P->fvalue = BIF_ARG_1; + BIF_ERROR(BIF_P, BADMAP); + } + BIF_ERROR(BIF_P, BADARG); +} + + /* maps:find/2 * return value if key *matches* a key in the map */ @@ -1917,15 +1962,22 @@ BIF_RETTYPE maps_values_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADMAP); } -static Eterm hashmap_to_list(Process *p, Eterm node) { +static Eterm hashmap_to_list(Process *p, Eterm node, Sint m) { DECLARE_WSTACK(stack); Eterm *hp, *kv; - Eterm res = NIL; + Eterm tup, res = NIL; + Uint n = hashmap_size(node); - hp = HAlloc(p, hashmap_size(node) * (2 + 3)); + if (m >= 0) { + n = m < n ? m : n; + } + + hp = HAlloc(p, n * (2 + 3)); hashmap_iterator_init(&stack, node, 0); - while ((kv=hashmap_iterator_next(&stack)) != NULL) { - Eterm tup = TUPLE2(hp, CAR(kv), CDR(kv)); + while (n--) { + kv = hashmap_iterator_next(&stack); + ASSERT(kv != NULL); + tup = TUPLE2(hp, CAR(kv), CDR(kv)); hp += 3; res = CONS(hp, tup, res); hp += 2; -- cgit v1.2.1 From 83e20c62057ebc1d8064bf57b01be560cd244e1d Mon Sep 17 00:00:00 2001 From: Raimo Niskanen Date: Thu, 4 May 2017 15:42:21 +0200 Subject: Update copyright year --- erts/emulator/beam/erl_map.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index a80f5d6a16..f0c54e05f7 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2014-2016. All Rights Reserved. + * Copyright Ericsson AB 2014-2017. All Rights Reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. -- cgit v1.2.1 From 513a322941d208d9dcdc4c39db2966ae4c707fe7 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Tue, 19 Sep 2017 14:37:59 +0200 Subject: erts: Implement map iterator using a stack This version does not work great as the subtrees created are not proper hash maps. Also it is not all that performant as the extra allocations to keep the stack there is expensive. --- erts/emulator/beam/erl_map.c | 72 ++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 70 insertions(+), 2 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index f0c54e05f7..37fcedbc6d 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -90,7 +90,6 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_ struct HashmapMergeContext_*); static Export hashmap_merge_trap_export; static BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1); -static Uint hashmap_subtree_size(Eterm node); static Eterm hashmap_to_list(Process *p, Eterm map, Sint n); static Eterm hashmap_keys(Process *p, Eterm map); static Eterm hashmap_values(Process *p, Eterm map); @@ -1519,7 +1518,7 @@ trap: /* Yield */ return trap_ret; } -static Uint hashmap_subtree_size(Eterm node) { +Uint hashmap_subtree_size(Eterm node) { DECLARE_WSTACK(stack); Uint size = 0; @@ -3060,6 +3059,75 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) return res; } +static Uint32 +index_to_hash(Sint idx, Uint32 hval) +{ + Uint32 new_hval = 1; + while (1) { + if (hval & 0x1) { + idx--; + if (!idx) break; + } + new_hval = new_hval << 1; + hval = hval >> 1; + } + return new_hval; +} + +BIF_RETTYPE erts_internal_map_get_index_2(BIF_ALIST_2) { + Sint idx; + Uint32 hval, sz; + Eterm *ptr, hdr; + + if (!is_hashmap(BIF_ARG_2) || is_not_small(BIF_ARG_1)) + BIF_ERROR(BIF_P, BADARG); + + idx = signed_val(BIF_ARG_1); + + if (idx < 1 || idx > 17) + BIF_ERROR(BIF_P, BADARG); + + ASSERT(is_boxed(BIF_ARG_2)); + + ptr = boxed_val(BIF_ARG_2); +again: + hdr = *ptr; + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; + sz = 16; + hval = 0xffff; + break; + case HAMT_SUBTAG_HEAD_BITMAP: + ptr++; + if (ptr[0] == -1) { + ptr = boxed_val(ptr[1]); + goto again; + } + case HAMT_SUBTAG_NODE_BITMAP: + hval = MAP_HEADER_VAL(hdr); + sz = hashmap_bitcount(hval); + ASSERT(sz < 17); + break; + default: + erts_exit(ERTS_ABORT_EXIT, "bad header"); + } + + if (idx <= sz) { + if (is_list(ptr[idx])) + return ptr[idx]; + else { + Eterm *hp = HAlloc(BIF_P, HAMT_HEAD_BITMAP_SZ(1)); + hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(index_to_hash(idx, hval)); + hp[1] = -1; + hp[2] = ptr[idx]; + return make_hashmap(hp); + } + } else { + return am_none; + } +} /* implementation of builtin emulations */ -- cgit v1.2.1 From 0149a73d15df1f80cb46752ec3829f48c38dd230 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 21 Sep 2017 09:20:30 +0200 Subject: erts: Implement maps path iterator --- erts/emulator/beam/erl_map.c | 288 ++++++++++++++++++++++++++++++++++--------- 1 file changed, 231 insertions(+), 57 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 37fcedbc6d..a5fda7b86d 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -90,6 +90,7 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_ struct HashmapMergeContext_*); static Export hashmap_merge_trap_export; static BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1); +static Uint hashmap_subtree_size(Eterm node); static Eterm hashmap_to_list(Process *p, Eterm map, Sint n); static Eterm hashmap_keys(Process *p, Eterm map); static Eterm hashmap_values(Process *p, Eterm map); @@ -1518,7 +1519,7 @@ trap: /* Yield */ return trap_ret; } -Uint hashmap_subtree_size(Eterm node) { +static Uint hashmap_subtree_size(Eterm node) { DECLARE_WSTACK(stack); Uint size = 0; @@ -3059,74 +3060,247 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) return res; } -static Uint32 -index_to_hash(Sint idx, Uint32 hval) -{ - Uint32 new_hval = 1; - while (1) { - if (hval & 0x1) { - idx--; - if (!idx) break; - } - new_hval = new_hval << 1; - hval = hval >> 1; - } - return new_hval; -} -BIF_RETTYPE erts_internal_map_get_index_2(BIF_ALIST_2) { - Sint idx; - Uint32 hval, sz; - Eterm *ptr, hdr; +/* + * The iterator work in about the same way for both + * flat- and hash-maps. It consists of a Path, Map + * term where Path describes where to find the + * term to get. + * + * In flatmap Path is just the index of the element + * in the flatmap array. + * + * In hashmap the Path is a bit pattern that describes + * which slot we should traverse in each hashmap node. + * Since each hashmap node can only be up to 16 elements + * large we use 4 bits per level in the path. + * + * So a Path with value 0x110 will first get the 0:th + * slot in the head node, and then the 1:st slot in the + * resulting node and then finally the 1:st slot in the + * node beneath. If that slot is not a leaf, then the path + * continues down the 0:th slot until it finds a leaf and + * returns that leaf. + * + * Once the leaf has been found, the Path to the next leaf + * is built using a stack that was created while traversing + * the tree down. + * + * The index can become a bignum, which complicates the code + * a bit. However it should be very rare that this happens + * even on a 32bit system as you would need a tree of depth + * 7 or more. + */ - if (!is_hashmap(BIF_ARG_2) || is_not_small(BIF_ARG_1)) - BIF_ERROR(BIF_P, BADARG); +#define PATH_ELEM_SIZE 4 +#define PATH_ELEM_MASK 0xf +#define PATH_ELEM(PATH) ((PATH) & PATH_ELEM_MASK) +#define PATH_ELEMS_PER_DIGIT (sizeof(ErtsDigit) * 8 / PATH_ELEM_SIZE) - idx = signed_val(BIF_ARG_1); +BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { - if (idx < 1 || idx > 17) + Eterm *hp = NULL, *lst, + iter, path, map, k, v; + + path = BIF_ARG_1; + map = BIF_ARG_2; + + if (!is_map(map)) BIF_ERROR(BIF_P, BADARG); - ASSERT(is_boxed(BIF_ARG_2)); + if (path == am_none) + BIF_RET(am_none); - ptr = boxed_val(BIF_ARG_2); -again: - hdr = *ptr; + if (is_flatmap(map)) { + flatmap_t *mp = (flatmap_t *)flatmap_val(map); + Uint idx, sz = flatmap_get_size(mp); - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - sz = 16; - hval = 0xffff; - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - if (ptr[0] == -1) { - ptr = boxed_val(ptr[1]); - goto again; + if (is_not_small(path)) + BIF_ERROR(BIF_P, BADARG); + + idx = unsigned_val(path); + + if (sz == 0) { + if (idx == 0) + BIF_RET(am_none); + else + BIF_ERROR(BIF_P, BADARG); } - case HAMT_SUBTAG_NODE_BITMAP: - hval = MAP_HEADER_VAL(hdr); - sz = hashmap_bitcount(hval); - ASSERT(sz < 17); - break; - default: - erts_exit(ERTS_ABORT_EXIT, "bad header"); - } - - if (idx <= sz) { - if (is_list(ptr[idx])) - return ptr[idx]; - else { - Eterm *hp = HAlloc(BIF_P, HAMT_HEAD_BITMAP_SZ(1)); - hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(index_to_hash(idx, hval)); - hp[1] = -1; - hp[2] = ptr[idx]; - return make_hashmap(hp); + + k = flatmap_get_keys(mp)[idx]; + v = flatmap_get_values(mp)[idx]; + + if (idx + 1 < sz) { + path = make_small(idx + 1); + } else if (idx < sz) { + path = am_none; + } else { + BIF_ERROR(BIF_P, BADARG); } } else { - return am_none; + Uint curr_path; + Uint path_length = 0; + Uint *path_rest = NULL; + int i; + Eterm node = map; + DECLARE_WSTACK(stack); + + ASSERT(is_hashmap(node)); + + if (is_small(path)) { + curr_path = unsigned_val(path); + } else if (is_big(path)) { + Eterm *big = big_val(path); + if (bignum_header_is_neg(*big)) + BIF_ERROR(BIF_P, BADARG); + path_length = BIG_ARITY(big) - 1; + curr_path = BIG_DIGIT(big, 0); + path_rest = BIG_V(big) + 1; + } else { + BIF_ERROR(BIF_P, BADARG); + } + + /* First we look for the K and V to return using the + path given. While doing so, we push each map node + and the index onto the stack so use later when + building the next index. */ + for (i = 1; ; i++) { + Eterm *ptr = hashmap_val(node), + hdr = *ptr; + Uint sz; + + ptr++; + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; + sz = 16; + break; + case HAMT_SUBTAG_HEAD_BITMAP: + ptr++; + case HAMT_SUBTAG_NODE_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); + break; + default: + erts_exit(ERTS_ABORT_EXIT, "bad header"); + } + + if (PATH_ELEM(curr_path) >= sz) + BIF_ERROR(BIF_P, BADARG); + + WSTACK_PUSH2(stack, node, PATH_ELEM(curr_path)); + + /* We have found a leaf, return it and calculate the path to next */ + if (is_list(ptr[PATH_ELEM(curr_path)])) { + lst = list_val(ptr[PATH_ELEM(curr_path)]); + k = CAR(lst); + v = CDR(lst); + break; + } + + node = ptr[PATH_ELEM(curr_path)]; + + curr_path >>= PATH_ELEM_SIZE; + + if (i == PATH_ELEMS_PER_DIGIT) { + /* Switch to next bignum word if available, + otherwise just follow 0 path */ + i = 0; + if (path_length) { + curr_path = *path_rest; + path_length--; + path_rest++; + } else { + curr_path = 0; + } + } + } + + /* We pop the stack until we come to the next leaf to return */ + while (1) { + Uint idx = (Uint)WSTACK_POP(stack); + Eterm node = (Eterm)WSTACK_POP(stack); + Eterm *ptr = hashmap_val(node), + hdr = *ptr; + Uint sz; + + ptr++; + + switch(hdr & _HEADER_MAP_SUBTAG_MASK) { + case HAMT_SUBTAG_HEAD_ARRAY: + ptr++; + sz = 16; + break; + case HAMT_SUBTAG_HEAD_BITMAP: + ptr++; + case HAMT_SUBTAG_NODE_BITMAP: + sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); + break; + default: + erts_exit(ERTS_ABORT_EXIT, "bad header"); + } + + if (idx + 1 < sz) { + curr_path = idx + 1; + break; + } + + /* We have reached the end of the iteration */ + if (WSTACK_ISEMPTY(stack)) { + path = am_none; + break; + } + + } + + if (path != am_none) { + Uint depth = WSTACK_COUNT(stack) / 2 + 1; + /* +1 because we already have the first element in curr_path */ + Eterm *path_digits = NULL; + + /* If the path cannot fit in a small, we allocate a bignum */ + if (depth >= PATH_ELEMS_PER_DIGIT) { + /* We need multiple ErtsDigit's to represent the path */ + int big_size = BIG_NEED_FOR_BITS(depth * PATH_ELEM_SIZE); + hp = HAlloc(BIF_P, big_size); + hp[0] = make_pos_bignum_header(big_size - BIG_NEED_SIZE(0)); + path_digits = hp + big_size - 1; + } + + /* Pop the stack to create the complete path to the next leaf */ + while(!WSTACK_ISEMPTY(stack)) { + Uint idx = (Uint)WSTACK_POP(stack); + (void)WSTACK_POP(stack); + + depth--; + if (depth % PATH_ELEMS_PER_DIGIT == 0) { + path_digits[0] = curr_path; + path_digits--; + curr_path = 0; + } + + curr_path <<= PATH_ELEM_SIZE; + curr_path |= idx; + } + + if (path_digits) { + path_digits[0] = curr_path; + path = make_big(hp); + } else { + /* The Uint could be too large for a small */ + path = erts_make_integer(curr_path, BIF_P); + } + } + + DESTROY_WSTACK(stack); } + + hp = HAlloc(BIF_P, 4 + 3 /* 3-tuple + 2-tuple */); + iter = TUPLE2(hp, path, map); + hp += 3; + BIF_RET(TUPLE3(hp, k, v, iter)); } /* implementation of builtin emulations */ -- cgit v1.2.1 From a1c796e7f6b86b4b506492ae6354382c565278d1 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 12 Oct 2017 16:00:50 +0200 Subject: erts: Implement batching maps:iterator This iterator implementation fetches multiple elements to iterate over in one call to erts_internal:maps_next instead of one at a time. This means that the memory usage will go up for the iterator as we are buffering elements, but the usage is still bounded. In this implementation the max memory usage is 1000 words. Using this approach makes the iterator as fast as using maps:to_list, so maps:iterator/2 has been removed. --- erts/emulator/beam/erl_map.c | 375 +++++++++++++++++++++++++------------------ 1 file changed, 216 insertions(+), 159 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index a5fda7b86d..135053dd18 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -139,35 +139,6 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADMAP); } -/* maps:to_list/1 */ - -BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) { - if (is_flatmap(BIF_ARG_1)) { - Uint n; - Eterm* hp; - Eterm *ks,*vs, res, tup; - flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1); - - ks = flatmap_get_keys(mp); - vs = flatmap_get_values(mp); - n = flatmap_get_size(mp); - hp = HAlloc(BIF_P, (2 + 3) * n); - res = NIL; - - while(n--) { - tup = TUPLE2(hp, ks[n], vs[n]); hp += 3; - res = CONS(hp, tup, res); hp += 2; - } - - BIF_RET(res); - } else if (is_hashmap(BIF_ARG_1)) { - return hashmap_to_list(BIF_P, BIF_ARG_1, -1); - } - - BIF_P->fvalue = BIF_ARG_1; - BIF_ERROR(BIF_P, BADMAP); -} - /* erts_internal:maps_to_list/2 * * This function should be removed once iterators are in place. @@ -1986,21 +1957,31 @@ static Eterm hashmap_to_list(Process *p, Eterm node, Sint m) { return res; } -void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) { - Eterm hdr = *hashmap_val(node); +static ERTS_INLINE +Uint hashmap_node_size(Eterm hdr, Eterm **nodep) +{ Uint sz; switch(hdr & _HEADER_MAP_SUBTAG_MASK) { case HAMT_SUBTAG_HEAD_ARRAY: sz = 16; + if (nodep) ++*nodep; break; case HAMT_SUBTAG_HEAD_BITMAP: + if (nodep) ++*nodep; case HAMT_SUBTAG_NODE_BITMAP: sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); + ASSERT(sz < 17); break; default: erts_exit(ERTS_ABORT_EXIT, "bad header"); } + return sz; +} + +void hashmap_iterator_init(ErtsWStack* s, Eterm node, int reverse) { + Eterm hdr = *hashmap_val(node); + Uint sz = hashmap_node_size(hdr, NULL); WSTACK_PUSH3((*s), (UWord)THE_NON_VALUE, /* end marker */ (UWord)(!reverse ? 0 : sz+1), @@ -2024,20 +2005,7 @@ Eterm* hashmap_iterator_next(ErtsWStack* s) { ptr = boxed_val(node); hdr = *ptr; ASSERT(is_header(hdr)); - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - sz = 16; - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - case HAMT_SUBTAG_NODE_BITMAP: - sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); - ASSERT(sz < 17); - break; - default: - erts_exit(ERTS_ABORT_EXIT, "bad header"); - } + sz = hashmap_node_size(hdr, &ptr); idx++; @@ -2074,20 +2042,7 @@ Eterm* hashmap_iterator_prev(ErtsWStack* s) { ptr = boxed_val(node); hdr = *ptr; ASSERT(is_header(hdr)); - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - sz = 16; - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - case HAMT_SUBTAG_NODE_BITMAP: - sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); - ASSERT(sz < 17); - break; - default: - erts_exit(ERTS_ERROR_EXIT, "bad header"); - } + sz = hashmap_node_size(hdr, &ptr); if (idx > sz) idx = sz; @@ -3061,15 +3016,7 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) } -/* - * The iterator work in about the same way for both - * flat- and hash-maps. It consists of a Path, Map - * term where Path describes where to find the - * term to get. - * - * In flatmap Path is just the index of the element - * in the flatmap array. - * +/** * In hashmap the Path is a bit pattern that describes * which slot we should traverse in each hashmap node. * Since each hashmap node can only be up to 16 elements @@ -3079,17 +3026,35 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) * slot in the head node, and then the 1:st slot in the * resulting node and then finally the 1:st slot in the * node beneath. If that slot is not a leaf, then the path - * continues down the 0:th slot until it finds a leaf and - * returns that leaf. + * continues down the 0:th slot until it finds a leaf. * - * Once the leaf has been found, the Path to the next leaf - * is built using a stack that was created while traversing - * the tree down. + * Once the leaf has been found, the return value is created + * by traversing the tree using the the stack that was built + * when searching for the first leaf to return. * * The index can become a bignum, which complicates the code * a bit. However it should be very rare that this happens * even on a 32bit system as you would need a tree of depth * 7 or more. + * + * If the number of elements remaining in the map is greater + * than how many we want to return, we build a new Path, using + * the stack, that points to the next leaf. + * + * The third argument to this function controls how the data + * is returned. + * + * iterator: The key-value associations are to be used by + * maps:iterator. The return has this format: + * {K1,V1,{K2,V2,none | [Path | Map]}} + * this makes the maps:next function very simple + * and performant. + * + * list(): The key-value associations are to be used by + * maps:to_list. The return has this format: + * [Path, Map | [{K1,V1},{K2,V2} | BIF_ARG_3]] + * or if no more associations remain + * [{K1,V1},{K2,V2} | BIF_ARG_3] */ #define PATH_ELEM_SIZE 4 @@ -3097,10 +3062,24 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) #define PATH_ELEM(PATH) ((PATH) & PATH_ELEM_MASK) #define PATH_ELEMS_PER_DIGIT (sizeof(ErtsDigit) * 8 / PATH_ELEM_SIZE) -BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { +/* How many elements we return in one call depends on the number of reductions + that the process has left to run. In debug we return fewer elements to test + the Path implementation better. */ +#if defined(DEBUG) +#define FCALLS_ELEMS(BIF_P) ((BIF_P->fcalls / 4) & 0xF) +#else +#define FCALLS_ELEMS(BIF_P) (BIF_P->fcalls / 4) +#endif + +#define NUM_ELEMS_TO_RETURN(BIF_P, map) \ + ((MAX(FCALLS_ELEMS(BIF_P), 1) < hashmap_size(map)) ? \ + MAX(FCALLS_ELEMS(BIF_P), 1) : hashmap_size(map)) - Eterm *hp = NULL, *lst, - iter, path, map, k, v; + +BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { + + Eterm path, map; + enum { iterator, list } type; path = BIF_ARG_1; map = BIF_ARG_2; @@ -3108,41 +3087,65 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { if (!is_map(map)) BIF_ERROR(BIF_P, BADARG); - if (path == am_none) - BIF_RET(am_none); + if (BIF_ARG_3 == am_iterator) { + type = iterator; + } else if (is_nil(BIF_ARG_3) || is_list(BIF_ARG_3)) { + type = list; + } else { + BIF_ERROR(BIF_P, BADARG); + } if (is_flatmap(map)) { - flatmap_t *mp = (flatmap_t *)flatmap_val(map); - Uint idx, sz = flatmap_get_size(mp); - - if (is_not_small(path)) - BIF_ERROR(BIF_P, BADARG); + Uint n; + Eterm *ks,*vs, res, *hp; + flatmap_t *mp = (flatmap_t*)flatmap_val(map); - idx = unsigned_val(path); + ks = flatmap_get_keys(mp); + vs = flatmap_get_values(mp); + n = flatmap_get_size(mp); - if (sz == 0) { - if (idx == 0) - BIF_RET(am_none); - else - BIF_ERROR(BIF_P, BADARG); - } + if (!is_small(BIF_ARG_1) || n < unsigned_val(BIF_ARG_1)) + BIF_ERROR(BIF_P, BADARG); - k = flatmap_get_keys(mp)[idx]; - v = flatmap_get_values(mp)[idx]; + if (type == iterator) { + hp = HAlloc(BIF_P, 4 * n); + res = am_none; - if (idx + 1 < sz) { - path = make_small(idx + 1); - } else if (idx < sz) { - path = am_none; + while(n--) { + res = TUPLE3(hp, ks[n], vs[n], res); hp += 4; + } } else { - BIF_ERROR(BIF_P, BADARG); + hp = HAlloc(BIF_P, (2 + 3) * n); + res = BIF_ARG_3; + + while(n--) { + Eterm tup = TUPLE2(hp, ks[n], vs[n]); hp += 3; + res = CONS(hp, tup, res); hp += 2; + } } + + BIF_RET(res); } else { Uint curr_path; Uint path_length = 0; Uint *path_rest = NULL; - int i; - Eterm node = map; + int i, elems = NUM_ELEMS_TO_RETURN(BIF_P, map); + Eterm node = map, res, *path_ptr = NULL, *hp; + + /* A stack WSTACK is used when traversing the hashmap. + * It contains: node, idx, sz, ptr + * + * `node` is not really needed, but it is very nice to + * have when debugging. + * + * `idx` always points to the next un-explored entry in + * a node. If there are no more un-explored entries, + * `idx` is equal to `sz`. + * + * `sz` is the number of elements in the node. + * + * `ptr` is a pointer to where the elements of the node begins. + */ DECLARE_WSTACK(stack); ASSERT(is_hashmap(node)); @@ -3152,7 +3155,7 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { } else if (is_big(path)) { Eterm *big = big_val(path); if (bignum_header_is_neg(*big)) - BIF_ERROR(BIF_P, BADARG); + goto badarg; path_length = BIG_ARITY(big) - 1; curr_path = BIG_DIGIT(big, 0); path_rest = BIG_V(big) + 1; @@ -3160,42 +3163,45 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADARG); } - /* First we look for the K and V to return using the + if (type == iterator) { + /* iterator uses the format {K, V, {K, V, {K, V, [Path | Map]}}}, + * so each element is 4 words large */ + hp = HAlloc(BIF_P, 4 * NUM_ELEMS_TO_RETURN(BIF_P, map)); + res = am_none; + } else { + /* list used the format [Path, Map, {K,V}, {K,V} | BIF_ARG_3], + * so each element is 2+3 words large */ + hp = HAlloc(BIF_P, (2 + 3) * NUM_ELEMS_TO_RETURN(BIF_P, map)); + res = BIF_ARG_3; + } + + /* First we look for the leaf to start at using the path given. While doing so, we push each map node - and the index onto the stack so use later when - building the next index. */ + and the index onto the stack to use later. */ for (i = 1; ; i++) { Eterm *ptr = hashmap_val(node), - hdr = *ptr; + hdr = *ptr++; Uint sz; - ptr++; - - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - sz = 16; - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - case HAMT_SUBTAG_NODE_BITMAP: - sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); - ASSERT(sz < 17); - break; - default: - erts_exit(ERTS_ABORT_EXIT, "bad header"); - } + sz = hashmap_node_size(hdr, &ptr); if (PATH_ELEM(curr_path) >= sz) - BIF_ERROR(BIF_P, BADARG); + goto badarg; - WSTACK_PUSH2(stack, node, PATH_ELEM(curr_path)); + WSTACK_PUSH4(stack, node, PATH_ELEM(curr_path)+1, sz, (UWord)ptr); - /* We have found a leaf, return it and calculate the path to next */ + /* We have found a leaf, return it and the next X elements */ if (is_list(ptr[PATH_ELEM(curr_path)])) { - lst = list_val(ptr[PATH_ELEM(curr_path)]); - k = CAR(lst); - v = CDR(lst); + Eterm *lst = list_val(ptr[PATH_ELEM(curr_path)]); + if (type == iterator) { + res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4; + /* Note where we should patch the Iterator is needed */ + path_ptr = hp-1; + } else { + Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; + res = CONS(hp, tup, res); hp += 2; + } + elems--; break; } @@ -3217,48 +3223,70 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { } } - /* We pop the stack until we come to the next leaf to return */ - while (1) { + /* We traverse the hashmap and return at most `elems` elements */ + while(1) { + Eterm *ptr = (Eterm*)WSTACK_POP(stack); + Uint sz = (Uint)WSTACK_POP(stack); Uint idx = (Uint)WSTACK_POP(stack); Eterm node = (Eterm)WSTACK_POP(stack); - Eterm *ptr = hashmap_val(node), - hdr = *ptr; - Uint sz; - ptr++; - - switch(hdr & _HEADER_MAP_SUBTAG_MASK) { - case HAMT_SUBTAG_HEAD_ARRAY: - ptr++; - sz = 16; - break; - case HAMT_SUBTAG_HEAD_BITMAP: - ptr++; - case HAMT_SUBTAG_NODE_BITMAP: - sz = hashmap_bitcount(MAP_HEADER_VAL(hdr)); - ASSERT(sz < 17); - break; - default: - erts_exit(ERTS_ABORT_EXIT, "bad header"); - } + while (idx < sz && elems != 0 && is_list(ptr[idx])) { + Eterm *lst = list_val(ptr[idx]); + if (type == iterator) { + res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4; + } else { + Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; + res = CONS(hp, tup, res); hp += 2; + } + elems--; + idx++; + } - if (idx + 1 < sz) { - curr_path = idx + 1; + if (elems == 0) { + if (idx < sz) { + /* There are more elements in this node to explore */ + WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr); + } else { + /* pop stack to find the next value */ + while (!WSTACK_ISEMPTY(stack)) { + Eterm *ptr = (Eterm*)WSTACK_POP(stack); + Uint sz = (Uint)WSTACK_POP(stack); + Uint idx = (Uint)WSTACK_POP(stack); + Eterm node = (Eterm)WSTACK_POP(stack); + if (idx < sz) { + WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr); + break; + } + } + } break; + } else { + if (idx < sz) { + Eterm hdr; + /* Push next idx in current node */ + WSTACK_PUSH4(stack, node, idx+1, sz, (UWord)ptr); + + /* Push first idx in child node */ + node = ptr[idx]; + ptr = hashmap_val(ptr[idx]); + hdr = *ptr++; + sz = hashmap_node_size(hdr, &ptr); + WSTACK_PUSH4(stack, node, 0, sz, (UWord)ptr); + } } - /* We have reached the end of the iteration */ + /* There are no more element in the hashmap */ if (WSTACK_ISEMPTY(stack)) { - path = am_none; break; } } - if (path != am_none) { - Uint depth = WSTACK_COUNT(stack) / 2 + 1; + if (!WSTACK_ISEMPTY(stack)) { + Uint depth = WSTACK_COUNT(stack) / 4 + 1; /* +1 because we already have the first element in curr_path */ Eterm *path_digits = NULL; + Uint curr_path = 0; /* If the path cannot fit in a small, we allocate a bignum */ if (depth >= PATH_ELEMS_PER_DIGIT) { @@ -3269,13 +3297,21 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { path_digits = hp + big_size - 1; } + /* Pop the stack to create the complete path to the next leaf */ while(!WSTACK_ISEMPTY(stack)) { - Uint idx = (Uint)WSTACK_POP(stack); + Uint idx; + + (void)WSTACK_POP(stack); + (void)WSTACK_POP(stack); + idx = (Uint)WSTACK_POP(stack)-1; + /* idx - 1 because idx in the stack is pointing to + the next element to fetch. */ (void)WSTACK_POP(stack); depth--; if (depth % PATH_ELEMS_PER_DIGIT == 0) { + /* Switch to next bignum element */ path_digits[0] = curr_path; path_digits--; curr_path = 0; @@ -3292,15 +3328,36 @@ BIF_RETTYPE erts_internal_map_next_2(BIF_ALIST_2) { /* The Uint could be too large for a small */ path = erts_make_integer(curr_path, BIF_P); } + + if (type == iterator) { + hp = HAlloc(BIF_P, 2); + *path_ptr = CONS(hp, path, map); hp += 2; + } else { + hp = HAlloc(BIF_P, 4); + res = CONS(hp, map, res); hp += 2; + res = CONS(hp, path, res); hp += 2; + } + } else { + if (type == iterator) { + HRelease(BIF_P, hp + 4 * elems, hp); + } else { + HRelease(BIF_P, hp + (2+3) * elems, hp); + } } + BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems); + DESTROY_WSTACK(stack); + BIF_RET(res); + badarg: + if (type == iterator) { + HRelease(BIF_P, hp + 4 * elems, hp); + } else { + HRelease(BIF_P, hp + (2+3) * elems, hp); + } + BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems); DESTROY_WSTACK(stack); + BIF_ERROR(BIF_P, BADARG); } - - hp = HAlloc(BIF_P, 4 + 3 /* 3-tuple + 2-tuple */); - iter = TUPLE2(hp, path, map); - hp += 3; - BIF_RET(TUPLE3(hp, k, v, iter)); } /* implementation of builtin emulations */ -- cgit v1.2.1 From 488049bd59352670ba4df17df7cc8a288b273b63 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Thu, 12 Oct 2017 16:01:43 +0200 Subject: erts: Remove erts_internal:maps_to_list/2 This function is no longer needed as maps:iterator has now been implemented. --- erts/emulator/beam/erl_map.c | 70 -------------------------------------------- 1 file changed, 70 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 135053dd18..cbbd62f1a2 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -91,7 +91,6 @@ static BIF_RETTYPE hashmap_merge(Process *p, Eterm nodeA, Eterm nodeB, int swap_ static Export hashmap_merge_trap_export; static BIF_RETTYPE maps_merge_trap_1(BIF_ALIST_1); static Uint hashmap_subtree_size(Eterm node); -static Eterm hashmap_to_list(Process *p, Eterm map, Sint n); static Eterm hashmap_keys(Process *p, Eterm map); static Eterm hashmap_values(Process *p, Eterm map); static Eterm hashmap_delete(Process *p, Uint32 hx, Eterm key, Eterm node, Eterm *value); @@ -139,51 +138,6 @@ BIF_RETTYPE map_size_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADMAP); } -/* erts_internal:maps_to_list/2 - * - * This function should be removed once iterators are in place. - * Never document it. - * Never encourage its usage. - * - * A negative value in ARG 2 means the entire map. - */ - -BIF_RETTYPE erts_internal_maps_to_list_2(BIF_ALIST_2) { - Sint m; - if (term_to_Sint(BIF_ARG_2, &m)) { - if (is_flatmap(BIF_ARG_1)) { - Uint n; - Eterm* hp; - Eterm *ks,*vs, res, tup; - flatmap_t *mp = (flatmap_t*)flatmap_val(BIF_ARG_1); - - ks = flatmap_get_keys(mp); - vs = flatmap_get_values(mp); - n = flatmap_get_size(mp); - - if (m >= 0) { - n = m < n ? m : n; - } - - hp = HAlloc(BIF_P, (2 + 3) * n); - res = NIL; - - while(n--) { - tup = TUPLE2(hp, ks[n], vs[n]); hp += 3; - res = CONS(hp, tup, res); hp += 2; - } - - BIF_RET(res); - } else if (is_hashmap(BIF_ARG_1)) { - return hashmap_to_list(BIF_P, BIF_ARG_1, m); - } - BIF_P->fvalue = BIF_ARG_1; - BIF_ERROR(BIF_P, BADMAP); - } - BIF_ERROR(BIF_P, BADARG); -} - - /* maps:find/2 * return value if key *matches* a key in the map */ @@ -1933,30 +1887,6 @@ BIF_RETTYPE maps_values_1(BIF_ALIST_1) { BIF_ERROR(BIF_P, BADMAP); } -static Eterm hashmap_to_list(Process *p, Eterm node, Sint m) { - DECLARE_WSTACK(stack); - Eterm *hp, *kv; - Eterm tup, res = NIL; - Uint n = hashmap_size(node); - - if (m >= 0) { - n = m < n ? m : n; - } - - hp = HAlloc(p, n * (2 + 3)); - hashmap_iterator_init(&stack, node, 0); - while (n--) { - kv = hashmap_iterator_next(&stack); - ASSERT(kv != NULL); - tup = TUPLE2(hp, CAR(kv), CDR(kv)); - hp += 3; - res = CONS(hp, tup, res); - hp += 2; - } - DESTROY_WSTACK(stack); - return res; -} - static ERTS_INLINE Uint hashmap_node_size(Eterm hdr, Eterm **nodep) { -- cgit v1.2.1 From 10912210641fe7d784c4ba6398c24504200ed339 Mon Sep 17 00:00:00 2001 From: Lukas Larsson Date: Wed, 18 Oct 2017 15:34:10 +0200 Subject: erts: Limit size of first iterator for hashmaps --- erts/emulator/beam/erl_map.c | 53 +++++++++++++++++++++++++++----------------- 1 file changed, 33 insertions(+), 20 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index cbbd62f1a2..8047a9567f 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -2992,20 +2992,6 @@ static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]) #define PATH_ELEM(PATH) ((PATH) & PATH_ELEM_MASK) #define PATH_ELEMS_PER_DIGIT (sizeof(ErtsDigit) * 8 / PATH_ELEM_SIZE) -/* How many elements we return in one call depends on the number of reductions - that the process has left to run. In debug we return fewer elements to test - the Path implementation better. */ -#if defined(DEBUG) -#define FCALLS_ELEMS(BIF_P) ((BIF_P->fcalls / 4) & 0xF) -#else -#define FCALLS_ELEMS(BIF_P) (BIF_P->fcalls / 4) -#endif - -#define NUM_ELEMS_TO_RETURN(BIF_P, map) \ - ((MAX(FCALLS_ELEMS(BIF_P), 1) < hashmap_size(map)) ? \ - MAX(FCALLS_ELEMS(BIF_P), 1) : hashmap_size(map)) - - BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { Eterm path, map; @@ -3059,7 +3045,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { Uint curr_path; Uint path_length = 0; Uint *path_rest = NULL; - int i, elems = NUM_ELEMS_TO_RETURN(BIF_P, map); + int i, elems, orig_elems; Eterm node = map, res, *path_ptr = NULL, *hp; /* A stack WSTACK is used when traversing the hashmap. @@ -3080,12 +3066,37 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { ASSERT(is_hashmap(node)); +/* How many elements we return in one call depends on the number of reductions + * that the process has left to run. In debug we return fewer elements to test + * the Path implementation better. + * + * Also, when the path is 0 (i.e. for the first call) we limit the number of + * elements to MAP_SMALL_MAP_LIMIT in order to not use a huge amount of heap + * when only the first X associations in the hashmap was needed. + */ +#if defined(DEBUG) +#define FCALLS_ELEMS(BIF_P) ((BIF_P->fcalls / 4) & 0xF) +#else +#define FCALLS_ELEMS(BIF_P) (BIF_P->fcalls / 4) +#endif + + if (MAX(FCALLS_ELEMS(BIF_P), 1) < hashmap_size(map)) + elems = MAX(FCALLS_ELEMS(BIF_P), 1); + else + elems = hashmap_size(map); + +#undef FCALLS_ELEMS + if (is_small(path)) { curr_path = unsigned_val(path); + + if (curr_path == 0 && elems > MAP_SMALL_MAP_LIMIT) { + elems = MAP_SMALL_MAP_LIMIT; + } } else if (is_big(path)) { Eterm *big = big_val(path); if (bignum_header_is_neg(*big)) - goto badarg; + BIF_ERROR(BIF_P, BADARG); path_length = BIG_ARITY(big) - 1; curr_path = BIG_DIGIT(big, 0); path_rest = BIG_V(big) + 1; @@ -3096,15 +3107,17 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { if (type == iterator) { /* iterator uses the format {K, V, {K, V, {K, V, [Path | Map]}}}, * so each element is 4 words large */ - hp = HAlloc(BIF_P, 4 * NUM_ELEMS_TO_RETURN(BIF_P, map)); + hp = HAlloc(BIF_P, 4 * elems); res = am_none; } else { /* list used the format [Path, Map, {K,V}, {K,V} | BIF_ARG_3], * so each element is 2+3 words large */ - hp = HAlloc(BIF_P, (2 + 3) * NUM_ELEMS_TO_RETURN(BIF_P, map)); + hp = HAlloc(BIF_P, (2 + 3) * elems); res = BIF_ARG_3; } + orig_elems = elems; + /* First we look for the leaf to start at using the path given. While doing so, we push each map node and the index onto the stack to use later. */ @@ -3274,7 +3287,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { HRelease(BIF_P, hp + (2+3) * elems, hp); } } - BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems); + BIF_P->fcalls -= 4 * (orig_elems - elems); DESTROY_WSTACK(stack); BIF_RET(res); @@ -3284,7 +3297,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } else { HRelease(BIF_P, hp + (2+3) * elems, hp); } - BIF_P->fcalls -= 4 * (NUM_ELEMS_TO_RETURN(BIF_P, map) - elems); + BIF_P->fcalls -= 4 * (orig_elems - elems); DESTROY_WSTACK(stack); BIF_ERROR(BIF_P, BADARG); } -- cgit v1.2.1 From 187564ffccee4a3b5727bdab3df2458f3b5ced72 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Tue, 20 Mar 2018 13:28:26 +0100 Subject: Add enif_make_map_from_arrays --- erts/emulator/beam/erl_map.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 8047a9567f..4ec6960997 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -490,7 +490,9 @@ Eterm erts_map_from_ks_and_vs(ErtsHeapFactory *factory, Eterm *ks0, Eterm *vs0, sys_memcpy(ks, ks0, n * sizeof(Eterm)); sys_memcpy(vs, vs0, n * sizeof(Eterm)); - erts_validate_and_sort_flatmap(mp); + if (!erts_validate_and_sort_flatmap(mp)) { + return THE_NON_VALUE; + } return make_flatmap(mp); } else { -- cgit v1.2.1 From ad72c0d37ffb214cac874f51ac29fe2cdb47a2a4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Muska=C5=82a?= Date: Sat, 3 Feb 2018 15:41:11 +0100 Subject: Introduce map_get guard-safe function Rationale Today all compound data types except for maps can be deconstructed in guards. For tuples we have `element/2` and for lists `hd/1` and `tl/1`. Maps are completely opaque to guards. This means matching on maps can't be abstracted into macros, which is often done with repetitive guards. It also means that maps have to be always selected whole from ETS tables, even when only one field would be enough, which creates a potential efficiency issue. This PR introduces an `erlang:map_get/2` guard-safe function that allows extracting a map field in guard. An alternative to this function would be to introduce the syntax for extracting a value from a map that was planned in the original EEP: `Map#{Key}`. Even outside of guards, since this function is a guard-BIF it is more efficient than using `maps:get/2` (since it does not need to set up the stack), and more convenient from pattern matching on the map (compare: `#{key := Value} = Map, Value` to `map_get(key, Map)`). Performance considerations A common concern against adding this function is the notion that "guards have to be fast" and ideally execute in constant time. While there are some counterexamples (`length/1`), what is more important is the fact that adding those functions does not change in any way the time complexity of pattern matching - it's already possible to match on map fields today directly in patterns - adding this ability to guards will niether slow down or speed up the execution, it will only make certain programs more convenient to write. This first version is very naive and does not perform any optimizations. --- erts/emulator/beam/erl_map.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 4ec6960997..f577b017c3 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -44,6 +44,7 @@ * DONE: * - erlang:is_map/1 * - erlang:map_size/1 + * - erlang:map_get/2 * * - maps:find/2 * - maps:from_list/1 @@ -202,7 +203,7 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADMAP); } -/* maps:get/2 +/* maps:get/2 and erlang:map_get/2 * return value if key *matches* a key in the map * exception badkey if none matches */ @@ -223,6 +224,10 @@ BIF_RETTYPE maps_get_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADMAP); } +BIF_RETTYPE map_get_2(BIF_ALIST_2) { + BIF_RET(maps_get_2(BIF_CALL_ARGS)); +} + /* maps:from_list/1 * List may be unsorted [{K,V}] */ -- cgit v1.2.1 From 5d0874a8f9fd617308d9024783db1e4e24268184 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Muska=C5=82a?= Date: Fri, 27 Apr 2018 12:40:07 +0200 Subject: Introduce is_map_key/2 guard BIF This complements the `map_get/2` guard BIF introduced in #1784. Rationale. `map_get/2` allows accessing map fields in guards, but it might be problematic in more complex guard expressions, for example: foo(X) when map_get(a, X) =:= 1 or is_list(X) -> ... The `is_list/1` part of the guard could never succeed since the `map_get/2` guard would fail the whole guard expression. In this situation, this could be solved by using `;` instead of `or` to separate the guards, but it is not possible in every case. To solve this situation, this PR proposes a `is_map_key/2` guard that allows to check if a map has key inside a guard before trying to access that key. When combined with `is_map/1` this allows to construct a purely boolean guard expression testing a value of a key in a map. Implementation. Given the use case motivating the introduction of this function, the PR contains compiler optimisations that produce optimial code for the following guard expression: foo(X) when is_map(X) and is_map_key(a, X) and map_get(a, X) =:= 1 -> ok; foo(_) -> error. Given all three tests share the failure label, the `is_map_key/2` and `is_map/2` tests are optimised away. As with `map_get/2` the `is_map_key/2` BIF is allowed in match specs. --- erts/emulator/beam/erl_map.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index f577b017c3..3d565b1bb8 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -43,6 +43,7 @@ * * DONE: * - erlang:is_map/1 + * - erlang:is_map_key/2 * - erlang:map_size/1 * - erlang:map_get/2 * @@ -919,7 +920,7 @@ static int hxnodecmp(hxnode_t *a, hxnode_t *b) { return -1; } -/* maps:is_key/2 */ +/* maps:is_key/2 and erlang:is_map_key/2 */ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { if (is_map(BIF_ARG_2)) { @@ -929,6 +930,10 @@ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADMAP); } +BIF_RETTYPE is_map_key_2(BIF_ALIST_2) { + BIF_RET(maps_is_key_2(BIF_CALL_ARGS)); +} + /* maps:keys/1 */ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { -- cgit v1.2.1 From eedfe1a5e3a85ff5ec7ab49d491250f3b501f3ba Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 8 May 2018 17:20:07 +0200 Subject: erts: Try fix contant maps:next order Symptom: maps:iterator+next returns different orders for the exact same map. Problem: Number of cached key-values within iterator term depends on number of input reductions to erts_internal_map_next_3. Solution: Build cached key-values in destructive non-reverse order to not affect iteration order. --- erts/emulator/beam/erl_map.c | 32 +++++++++++++++++++++----------- 1 file changed, 21 insertions(+), 11 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 3d565b1bb8..05e8fc11a2 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -3058,7 +3058,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { Uint path_length = 0; Uint *path_rest = NULL; int i, elems, orig_elems; - Eterm node = map, res, *path_ptr = NULL, *hp; + Eterm node = map, res, *patch_ptr = NULL, *hp; /* A stack WSTACK is used when traversing the hashmap. * It contains: node, idx, sz, ptr @@ -3117,13 +3117,21 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } if (type == iterator) { - /* iterator uses the format {K, V, {K, V, {K, V, [Path | Map]}}}, - * so each element is 4 words large */ + /* + * Iterator uses the format {K1, V1, {K2, V2, {K3, V3, [Path | Map]}}}, + * so each element is 4 words large. + * To make iteration order independent of input reductions + * the KV-pairs are here built in DESTRUCTIVE non-reverse order. + */ hp = HAlloc(BIF_P, 4 * elems); - res = am_none; } else { - /* list used the format [Path, Map, {K,V}, {K,V} | BIF_ARG_3], - * so each element is 2+3 words large */ + /* + * List used the format [Path, Map, {K3,V3}, {K2,V2}, {K1,V1} | BIF_ARG_3], + * so each element is 2+3 words large. + * To make list order independent of input reductions + * the KV-pairs are here built in FUNCTIONAL reverse order + * as this is how the list as a whole is constructed. + */ hp = HAlloc(BIF_P, (2 + 3) * elems); res = BIF_ARG_3; } @@ -3149,9 +3157,9 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { if (is_list(ptr[PATH_ELEM(curr_path)])) { Eterm *lst = list_val(ptr[PATH_ELEM(curr_path)]); if (type == iterator) { - res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4; - /* Note where we should patch the Iterator is needed */ - path_ptr = hp-1; + res = TUPLE3(hp, CAR(lst), CDR(lst), make_tuple(hp+4)); + hp += 4; + patch_ptr = hp-1; } else { Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; res = CONS(hp, tup, res); hp += 2; @@ -3188,7 +3196,8 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { while (idx < sz && elems != 0 && is_list(ptr[idx])) { Eterm *lst = list_val(ptr[idx]); if (type == iterator) { - res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4; + (void) TUPLE3(hp, CAR(lst), CDR(lst), make_tuple(hp+4)); hp += 4; + patch_ptr = hp-1; } else { Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; res = CONS(hp, tup, res); hp += 2; @@ -3286,7 +3295,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { if (type == iterator) { hp = HAlloc(BIF_P, 2); - *path_ptr = CONS(hp, path, map); hp += 2; + *patch_ptr = CONS(hp, path, map); hp += 2; } else { hp = HAlloc(BIF_P, 4); res = CONS(hp, map, res); hp += 2; @@ -3294,6 +3303,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } } else { if (type == iterator) { + *patch_ptr = am_none; HRelease(BIF_P, hp + 4 * elems, hp); } else { HRelease(BIF_P, hp + (2+3) * elems, hp); -- cgit v1.2.1 From 23db9db1dbe6ef3549a2b219dab7b849bb56c307 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 16 May 2018 17:16:49 +0200 Subject: erts: Silence gcc warnings MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ‘res’ may be used uninitialized in this function --- erts/emulator/beam/erl_map.c | 18 ++++++++++++------ 1 file changed, 12 insertions(+), 6 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 05e8fc11a2..48154b5d0f 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -3133,7 +3133,6 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { * as this is how the list as a whole is constructed. */ hp = HAlloc(BIF_P, (2 + 3) * elems); - res = BIF_ARG_3; } orig_elems = elems; @@ -3157,12 +3156,15 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { if (is_list(ptr[PATH_ELEM(curr_path)])) { Eterm *lst = list_val(ptr[PATH_ELEM(curr_path)]); if (type == iterator) { - res = TUPLE3(hp, CAR(lst), CDR(lst), make_tuple(hp+4)); + res = make_tuple(hp); + hp[0] = make_arityval(3); + hp[1] = CAR(lst); + hp[2] = CDR(lst); + patch_ptr = &hp[3]; hp += 4; - patch_ptr = hp-1; } else { Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; - res = CONS(hp, tup, res); hp += 2; + res = CONS(hp, tup, BIF_ARG_3); hp += 2; } elems--; break; @@ -3196,8 +3198,12 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { while (idx < sz && elems != 0 && is_list(ptr[idx])) { Eterm *lst = list_val(ptr[idx]); if (type == iterator) { - (void) TUPLE3(hp, CAR(lst), CDR(lst), make_tuple(hp+4)); hp += 4; - patch_ptr = hp-1; + *patch_ptr = make_tuple(hp); + hp[0] = make_arityval(3); + hp[1] = CAR(lst); + hp[2] = CDR(lst); + patch_ptr = &hp[3]; + hp += 4; } else { Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; res = CONS(hp, tup, res); hp += 2; -- cgit v1.2.1 From 5ca92e2eac1e84fd22f60e7abc3aa2b0ff1cb42b Mon Sep 17 00:00:00 2001 From: Henrik Nord Date: Mon, 18 Jun 2018 14:51:18 +0200 Subject: Update copyright year --- erts/emulator/beam/erl_map.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 48154b5d0f..cba17d3e6a 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -1,7 +1,7 @@ /* * %CopyrightBegin% * - * Copyright Ericsson AB 2014-2017. All Rights Reserved. + * Copyright Ericsson AB 2014-2018. All Rights Reserved. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. -- cgit v1.2.1