From e4da94bee94bdd7e0dbb2e5021ab4cc5f89f8256 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 30 Mar 2015 19:54:23 +0200 Subject: erts: Refactor encode_size_struct_int to handle the "start of list" case in one place and not seven. Note that this commit reverts (47d6fd3ccf35) back to using WSTACK and pushing raw pointers. We disable GC while yielding, so this should not be a problem. --- erts/emulator/beam/dist.c | 4 +- erts/emulator/beam/dist.h | 2 +- erts/emulator/beam/external.c | 187 ++++++++++++++++-------------------------- 3 files changed, 73 insertions(+), 120 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/dist.c b/erts/emulator/beam/dist.c index bfecac1612..32f3cda4f5 100644 --- a/erts/emulator/beam/dist.c +++ b/erts/emulator/beam/dist.c @@ -712,7 +712,7 @@ void erts_dsend_context_dtor(Binary* ctx_bin) ErtsSendContext* ctx = ERTS_MAGIC_BIN_DATA(ctx_bin); switch (ctx->dss.phase) { case ERTS_DSIG_SEND_PHASE_MSG_SIZE: - DESTROY_SAVED_ESTACK(&ctx->dss.u.sc.estack); + DESTROY_SAVED_WSTACK(&ctx->dss.u.sc.wstack); break; case ERTS_DSIG_SEND_PHASE_MSG_ENCODE: DESTROY_SAVED_WSTACK(&ctx->dss.u.ec.wstack); @@ -1800,7 +1800,7 @@ erts_dsig_send(ErtsDSigData *dsdp, struct erts_dsig_send_context* ctx) erts_encode_dist_ext_size(ctx->ctl, ctx->flags, ctx->acmp, &ctx->data_size); if (is_value(ctx->msg)) { - ctx->u.sc.estack.start = NULL; + ctx->u.sc.wstack.wstart = NULL; ctx->u.sc.flags = ctx->flags; ctx->u.sc.level = 0; ctx->phase = ERTS_DSIG_SEND_PHASE_MSG_SIZE; diff --git a/erts/emulator/beam/dist.h b/erts/emulator/beam/dist.h index 2a2ba0c83f..cd2cc0ef4a 100644 --- a/erts/emulator/beam/dist.h +++ b/erts/emulator/beam/dist.h @@ -282,7 +282,7 @@ typedef struct TTBSizeContext_ { int level; Uint result; Eterm obj; - ErtsEStack estack; + ErtsWStack wstack; } TTBSizeContext; typedef struct TTBEncodeContext_ { diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c index 2117dbec62..fe48298155 100644 --- a/erts/emulator/beam/external.c +++ b/erts/emulator/beam/external.c @@ -1779,7 +1779,7 @@ static void ttb_context_destructor(Binary *context_bin) context->alive = 0; switch (context->state) { case TTBSize: - DESTROY_SAVED_ESTACK(&context->s.sc.estack); + DESTROY_SAVED_WSTACK(&context->s.sc.wstack); break; case TTBEncode: DESTROY_SAVED_WSTACK(&context->s.ec.wstack); @@ -1847,7 +1847,7 @@ static Eterm erts_term_to_binary_int(Process* p, Eterm Term, int level, Uint fla /* Setup enough to get started */ context->state = TTBSize; context->alive = 1; - context->s.sc.estack.start = NULL; + context->s.sc.wstack.wstart = NULL; context->s.sc.flags = flags; context->s.sc.level = level; } else { @@ -3962,51 +3962,35 @@ static int encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, unsigned dflags, Sint *reds, Uint *res) { - DECLARE_ESTACK(s); + DECLARE_WSTACK(s); Uint m, i, arity; Uint result = 0; Sint r = 0; if (ctx) { - ESTACK_CHANGE_ALLOCATOR(s, ERTS_ALC_T_SAVED_ESTACK); + WSTACK_CHANGE_ALLOCATOR(s, ERTS_ALC_T_SAVED_ESTACK); r = *reds; - if (ctx->estack.start) { /* restore saved stack */ - ESTACK_RESTORE(s, &ctx->estack); + if (ctx->wstack.wstart) { /* restore saved stack */ + WSTACK_RESTORE(s, &ctx->wstack); result = ctx->result; obj = ctx->obj; } } - goto L_jump_start; +#define LIST_TAIL_OP ((0 << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER) +#define TERM_ARRAY_OP(N) (((N) << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER) +#define TERM_ARRAY_OP_DEC(OP) ((OP) - (1 << _TAG_PRIMARY_SIZE)) + + + for (;;) { + ASSERT(!is_header(obj)); - outer_loop: - while (!ESTACK_ISEMPTY(s)) { - obj = ESTACK_POP(s); - handle_popped_obj: - if (is_list(obj)) { - Eterm* cons = list_val(obj); - Eterm tl; - - tl = CDR(cons); - obj = CAR(cons); - ESTACK_PUSH(s, tl); - } else if (is_nil(obj)) { - result++; - goto outer_loop; - } else { - /* - * Other term (in the tail of a non-proper list or - * in a fun's environment). - */ - } - - L_jump_start: if (ctx && --r == 0) { *reds = r; ctx->obj = obj; ctx->result = result; - ESTACK_SAVE(s, &ctx->estack); + WSTACK_SAVE(s, &ctx->wstack); return -1; } switch (tag_val_def(obj)) { @@ -4089,69 +4073,43 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, result += m + 2 + 1; } else { result += 5; - goto handle_popped_obj; + WSTACK_PUSH2(s, (UWord)CDR(list_val(obj)), (UWord)LIST_TAIL_OP); + obj = CAR(list_val(obj)); + continue; /* big loop */ } break; case TUPLE_DEF: { Eterm* ptr = tuple_val(obj); - Uint i; arity = arityval(*ptr); if (arity <= 0xff) { result += 1 + 1; } else { result += 1 + 4; } - for (i = 1; i <= arity; ++i) { - if (is_list(ptr[i])) { - if ((m = is_string(ptr[i])) && (m < MAX_STRING_LEN)) { - result += m + 2 + 1; - continue; - } else { - result += 5; - } - } - ESTACK_PUSH(s,ptr[i]); + if (arity > 1) { + WSTACK_PUSH2(s, (UWord) (ptr + 2), + (UWord) TERM_ARRAY_OP(arity-1)); } - goto outer_loop; + else if (arity == 0) { + break; + } + obj = ptr[1]; + continue; /* big loop */ } - break; case MAP_DEF: if (is_flatmap(obj)) { flatmap_t *mp = (flatmap_t*)flatmap_val(obj); Uint size = flatmap_get_size(mp); - Uint i; - Eterm *ptr; result += 1 + 4; /* tag + 4 bytes size */ - /* push values first */ - ptr = flatmap_get_values(mp); - for (i = size; i; i--, ptr++) { - if (is_list(*ptr)) { - if ((m = is_string(*ptr)) && (m < MAX_STRING_LEN)) { - result += m + 2 + 1; - continue; - } else { - result += 5; - } - } - ESTACK_PUSH(s,*ptr); + if (size) { + WSTACK_PUSH4(s, (UWord) flatmap_get_values(mp), + (UWord) TERM_ARRAY_OP(size), + (UWord) flatmap_get_keys(mp), + (UWord) TERM_ARRAY_OP(size)); } - - ptr = flatmap_get_keys(mp); - for (i = size; i; i--, ptr++) { - if (is_list(*ptr)) { - if ((m = is_string(*ptr)) && (m < MAX_STRING_LEN)) { - result += m + 2 + 1; - continue; - } else { - result += 5; - } - } - ESTACK_PUSH(s,*ptr); - } - goto outer_loop; } else { Eterm *ptr; Eterm hdr; @@ -4178,35 +4136,13 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, } ptr++; - ESTACK_RESERVE(s, node_sz*2); + WSTACK_RESERVE(s, node_sz*2); while(node_sz--) { if (is_list(*ptr)) { - Eterm* leaf = list_val(*ptr); - if (is_not_list(CAR(leaf))) { - ESTACK_FAST_PUSH(s, CAR(leaf)); - } - else { - if ((m = is_string(CAR(leaf))) && (m < MAX_STRING_LEN)) { - result += m + 2 + 1; - } else { - result += 5; - ESTACK_FAST_PUSH(s, CAR(leaf)); - } - } - if (is_not_list(CDR(leaf))) { - ESTACK_FAST_PUSH(s, CDR(leaf)); - } - else { - if ((m = is_string(CDR(leaf))) && (m < MAX_STRING_LEN)) { - result += m + 2 + 1; - } else { - result += 5; - ESTACK_FAST_PUSH(s, CDR(leaf)); - } - } - } - else { - ESTACK_FAST_PUSH(s, *ptr); + WSTACK_FAST_PUSH(s, CAR(list_val(*ptr))); + WSTACK_FAST_PUSH(s, CDR(list_val(*ptr))); + } else { + WSTACK_FAST_PUSH(s, *ptr); } ptr++; } @@ -4262,25 +4198,13 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, result += 2 * (1 + 4); /* Index + Uniq */ result += 1 + (funp->num_free < 0x100 ? 1 : 4); } - for (i = 1; i < funp->num_free; i++) { - obj = funp->env[i]; - - if (is_not_list(obj)) { - /* Push any non-list terms on the stack */ - ESTACK_PUSH(s, obj); - } else { - /* Lists must be handled specially. */ - if ((m = is_string(obj)) && (m < MAX_STRING_LEN)) { - result += m + 2 + 1; - } else { - result += 5; - ESTACK_PUSH(s, obj); - } - } + if (funp->num_free > 1) { + WSTACK_PUSH2(s, (UWord) (funp->env + 1), + (UWord) TERM_ARRAY_OP(funp->num_free-1)); } if (funp->num_free != 0) { obj = funp->env[0]; - goto L_jump_start; + continue; /* big loop */ } break; } @@ -4303,11 +4227,40 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, erl_exit(1,"Internal data structure error (in encode_size_struct2)%x\n", obj); } + + if (WSTACK_ISEMPTY(s)) { + break; + } + obj = (Eterm) WSTACK_POP(s); + + if (is_header(obj)) { + switch (obj) { + case LIST_TAIL_OP: + obj = (Eterm) WSTACK_POP(s); + if (is_list(obj)) { + Eterm* cons = list_val(obj); + + WSTACK_PUSH2(s, (UWord)CDR(cons), (UWord)LIST_TAIL_OP); + obj = CAR(cons); + } + break; + + case TERM_ARRAY_OP(1): + obj = *(Eterm*)WSTACK_POP(s); + break; + default: { /* TERM_ARRAY_OP(N) when N > 1 */ + Eterm* ptr = (Eterm*) WSTACK_POP(s); + WSTACK_PUSH2(s, (UWord) (ptr+1), + (UWord) TERM_ARRAY_OP_DEC(obj)); + obj = *ptr; + } + } + } } - DESTROY_ESTACK(s); + WSTACK_DESTROY(s); if (ctx) { - ASSERT(ctx->estack.start == NULL); + ASSERT(ctx->wstack.wstart == NULL); *reds = r; } *res = result; -- cgit v1.2.3 From 450e5b610ac2de4817606c2966d9fb5a9850887a Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 30 Mar 2015 21:45:42 +0200 Subject: erts: Optimize == and /= for unequal big maps Bail out as soon as we find a diff between maps if we are not interested in term order. --- erts/emulator/beam/erl_bif_lists.c | 2 +- erts/emulator/beam/erl_db_tree.c | 8 ++++---- erts/emulator/beam/erl_utils.h | 28 +++++++++++++++------------- erts/emulator/beam/utils.c | 9 +++++---- 4 files changed, 25 insertions(+), 22 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_bif_lists.c b/erts/emulator/beam/erl_bif_lists.c index 820ed2385d..e006d57124 100644 --- a/erts/emulator/beam/erl_bif_lists.c +++ b/erts/emulator/beam/erl_bif_lists.c @@ -390,7 +390,7 @@ keyfind(int Bif, Process* p, Eterm Key, Eterm Pos, Eterm List) Eterm *tuple_ptr = tuple_val(term); if (pos <= arityval(*tuple_ptr)) { Eterm element = tuple_ptr[pos]; - if (CMP(Key, element) == 0) { + if (CMP_EQ(Key, element)) { return term; } } diff --git a/erts/emulator/beam/erl_db_tree.c b/erts/emulator/beam/erl_db_tree.c index 577da35b75..d90af46659 100644 --- a/erts/emulator/beam/erl_db_tree.c +++ b/erts/emulator/beam/erl_db_tree.c @@ -1116,7 +1116,7 @@ static int db_select_tree(Process *p, DbTable *tbl, sc.all_objects = mpi.all_objects; if (!mpi.got_partial && mpi.some_limitation && - CMP(mpi.least,mpi.most) == 0) { + CMP_EQ(mpi.least,mpi.most)) { doit_select(tb,mpi.save_term,&sc,0 /* direction doesn't matter */); RET_TO_BIF(sc.accum,DB_ERROR_NONE); } @@ -1324,7 +1324,7 @@ static int db_select_count_tree(Process *p, DbTable *tbl, sc.all_objects = mpi.all_objects; if (!mpi.got_partial && mpi.some_limitation && - CMP(mpi.least,mpi.most) == 0) { + CMP_EQ(mpi.least,mpi.most)) { doit_select_count(tb,mpi.save_term,&sc,0 /* dummy */); RET_TO_BIF(erts_make_integer(sc.got,p),DB_ERROR_NONE); } @@ -1429,7 +1429,7 @@ static int db_select_chunk_tree(Process *p, DbTable *tbl, sc.all_objects = mpi.all_objects; if (!mpi.got_partial && mpi.some_limitation && - CMP(mpi.least,mpi.most) == 0) { + CMP_EQ(mpi.least,mpi.most)) { doit_select(tb,mpi.save_term,&sc, 0 /* direction doesn't matter */); if (sc.accum != NIL) { hp=HAlloc(p, 3); @@ -1673,7 +1673,7 @@ static int db_select_delete_tree(Process *p, DbTable *tbl, sc.mp = mpi.mp; if (!mpi.got_partial && mpi.some_limitation && - CMP(mpi.least,mpi.most) == 0) { + CMP_EQ(mpi.least,mpi.most)) { doit_select_delete(tb,mpi.save_term,&sc, 0 /* direction doesn't matter */); RET_TO_BIF(erts_make_integer(sc.accum,p),DB_ERROR_NONE); diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h index 7cb8972e29..6a28105cb9 100644 --- a/erts/emulator/beam/erl_utils.h +++ b/erts/emulator/beam/erl_utils.h @@ -167,24 +167,26 @@ int eq(Eterm, Eterm); #define EQ(x,y) (((x) == (y)) || (is_not_both_immed((x),(y)) && eq((x),(y)))) #if HALFWORD_HEAP -Sint erts_cmp_rel_opt(Eterm, Eterm*, Eterm, Eterm*, int); -#define cmp_rel(A,A_BASE,B,B_BASE) erts_cmp_rel_opt(A,A_BASE,B,B_BASE,0) -#define cmp_rel_term(A,A_BASE,B,B_BASE) erts_cmp_rel_opt(A,A_BASE,B,B_BASE,1) -#define CMP(A,B) erts_cmp_rel_opt(A,NULL,B,NULL,0) -#define CMP_TERM(A,B) erts_cmp_rel_opt(A,NULL,B,NULL,1) +Sint erts_cmp_rel_opt(Eterm, Eterm*, Eterm, Eterm*, int, int); +#define cmp_rel(A,A_BASE,B,B_BASE) erts_cmp_rel_opt(A,A_BASE,B,B_BASE,0,0) +#define cmp_rel_term(A,A_BASE,B,B_BASE) erts_cmp_rel_opt(A,A_BASE,B,B_BASE,1,0) +#define CMP(A,B) erts_cmp_rel_opt(A,NULL,B,NULL,0,0) +#define CMP_TERM(A,B) erts_cmp_rel_opt(A,NULL,B,NULL,1,0) +#define CMP_EQ_ONLY(A,B) erts_cmp_rel_opt(A,NULL,B,NULL,0,1) #else -Sint cmp(Eterm, Eterm); -Sint erts_cmp(Eterm, Eterm, int); -#define cmp_rel(A,A_BASE,B,B_BASE) erts_cmp(A,B,0) -#define cmp_rel_term(A,A_BASE,B,B_BASE) erts_cmp(A,B,1) -#define CMP(A,B) erts_cmp(A,B,0) -#define CMP_TERM(A,B) erts_cmp(A,B,1) +Sint erts_cmp(Eterm, Eterm, int, int); +Sint cmp(Eterm a, Eterm b); +#define cmp_rel(A,A_BASE,B,B_BASE) erts_cmp(A,B,0,0) +#define cmp_rel_term(A,A_BASE,B,B_BASE) erts_cmp(A,B,1,0) +#define CMP(A,B) erts_cmp(A,B,0,0) +#define CMP_TERM(A,B) erts_cmp(A,B,1,0) +#define CMP_EQ_ONLY(A,B) erts_cmp(A,B,0,1) #endif #define cmp_lt(a,b) (CMP((a),(b)) < 0) #define cmp_le(a,b) (CMP((a),(b)) <= 0) -#define cmp_eq(a,b) (CMP((a),(b)) == 0) -#define cmp_ne(a,b) (CMP((a),(b)) != 0) +#define cmp_eq(a,b) (CMP_EQ_ONLY((a),(b)) == 0) +#define cmp_ne(a,b) (CMP_EQ_ONLY((a),(b)) != 0) #define cmp_ge(a,b) (CMP((a),(b)) >= 0) #define cmp_gt(a,b) (CMP((a),(b)) > 0) diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 8fc8962e4f..889c217b0b 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -2911,7 +2911,7 @@ static int cmp_atoms(Eterm a, Eterm b) */ Sint cmp(Eterm a, Eterm b) { - return erts_cmp(a, b, 0); + return erts_cmp(a, b, 0, 0); } #endif @@ -2920,9 +2920,10 @@ Sint cmp(Eterm a, Eterm b) * exact = 0 -> arith-based compare */ #if HALFWORD_HEAP -Sint erts_cmp_rel_opt(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base, int exact) +Sint erts_cmp_rel_opt(Eterm a, Eterm* a_base, Eterm b, Eterm* b_base, + int exact, int eq_only) #else -Sint erts_cmp(Eterm a, Eterm b, int exact) +Sint erts_cmp(Eterm a, Eterm b, int exact, int eq_only) #endif { #define PSTACK_TYPE struct erts_cmp_hashmap_state @@ -3742,7 +3743,7 @@ pop_next: return 0; not_equal: - if (!PSTACK_IS_EMPTY(hmap_stack)) { + if (!PSTACK_IS_EMPTY(hmap_stack) && !eq_only) { WSTACK_ROLLBACK(stack, PSTACK_TOP(hmap_stack)->wstack_rollback); goto pop_next; } -- cgit v1.2.3 From 8f7246a7c02a50561c171f3d91170a2af96eddbf Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 31 Mar 2015 12:13:57 +0200 Subject: erts: Optimize insert and delete for big maps Do fast path without bit count for full internal nodes. --- erts/emulator/beam/erl_map.c | 71 +++++++++++++++++++++++++------------------- 1 file changed, 40 insertions(+), 31 deletions(-) (limited to 'erts') 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); -- cgit v1.2.3