From 9ca2c14787f42c5fe98c9c00364b508844059438 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 21 Feb 2018 17:23:49 +0100 Subject: erts: Refactor erlang:put/2 --- erts/emulator/beam/erl_process_dict.c | 49 ++++++++++++++++++++--------------- 1 file changed, 28 insertions(+), 21 deletions(-) diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 3c80f0e0f6..1ec81f50a3 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -577,11 +577,12 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) { unsigned int hval; Eterm *hp; + Eterm *tp; Eterm tpl; Eterm old; Eterm tmp; int needed; - int i = 0; + int key_at = 0; #ifdef DEBUG Eterm *hp_limit; #endif @@ -603,21 +604,26 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) */ needed = 3; /* {Key,Value} tuple */ if (is_boxed(old)) { - /* - * We don't want to compare keys twice, so we'll always - * reserve the space for two CONS cells. - */ - needed += 2+2; + ASSERT(is_tuple(old)); + tp = tuple_val(old); + if (EQ(tp[1], id)) { + key_at = 1; + } + else { + needed += 2+2; + } } else if (is_list(old)) { - i = 0; - for (tmp = old; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); tmp = TCDR(tmp)) { - ++i; - } - if (is_nil(tmp)) { - i = -1; - needed += 2; - } else { - needed += 2*(i+1); + int i = 1; + + needed += 2; + for (tmp = old; tmp != NIL; tmp = TCDR(tmp)) { + tp = tuple_val(TCAR(tmp)); + if (EQ(tp[1], id)) { + key_at = i; + needed += 2*(key_at-1); + break; + } + ++i; } } if (HeapWordsLeft(p) < needed) { @@ -648,7 +654,8 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) ++(p->dictionary->numElements); } else if (is_boxed(old)) { ASSERT(is_tuple(old)); - if (EQ(tuple_val(old)[1],id)) { + if (key_at) { + ASSERT(EQ(tuple_val(old)[1],id)); ARRAY_PUT(p->dictionary, hval, tpl); return tuple_val(old)[2]; } else { @@ -661,7 +668,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) ASSERT(hp <= hp_limit); } } else if (is_list(old)) { - if (i == -1) { + if (!key_at) { /* * New key. Simply prepend the tuple to the beginning of the list. */ @@ -672,7 +679,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) ++(p->dictionary->numElements); } else { /* - * i = Number of CDRs to skip to reach the changed element in the list. + * key_at = Key position in the list. * * Replace old value in list. To avoid pointers from the old generation * to the new, we must rebuild the list from the beginning up to and @@ -681,17 +688,17 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) Eterm nlist; int j; - hp = HeapOnlyAlloc(p, (i+1)*2); + hp = HeapOnlyAlloc(p, key_at*2); /* Find the list element to change. */ - for (j = 0, nlist = old; j < i; j++, nlist = TCDR(nlist)) { + for (j = 1, nlist = old; j < key_at; j++, nlist = TCDR(nlist)) { ; } ASSERT(EQ(tuple_val(TCAR(nlist))[1], id)); nlist = TCDR(nlist); /* Unchanged part of list. */ /* Rebuild list before the updated element. */ - for (tmp = old; i-- > 0; tmp = TCDR(tmp)) { + for (tmp = old; --key_at > 0; tmp = TCDR(tmp)) { nlist = CONS(hp, TCAR(tmp), nlist); hp += 2; } -- cgit v1.2.3 From 4d547dfb2a012ba1cf8fb9dd3cdc4d9df933a37f Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 21 Feb 2018 22:05:10 +0100 Subject: erts: Optimize erlang:put/2 for immed values Do destructive write of immed value if key exists. This is an optimization at the expense of get/0 which must now copy all (mutable) key-value tuples. --- erts/emulator/beam/erl_process_dict.c | 41 +++++++++++++++++++++++++++++------ lib/kernel/test/pdict_SUITE.erl | 32 +++++++++++++++++++++++++++ 2 files changed, 66 insertions(+), 7 deletions(-) diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 1ec81f50a3..87b440093b 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -92,7 +92,7 @@ static void pd_hash_erase_all(Process *p); static Eterm pd_hash_get_with_hval(Process *p, Eterm bucket, Eterm id); static Eterm pd_hash_get_keys(Process *p, Eterm value); static Eterm pd_hash_get_all_keys(Process *p, ProcDict *pd); -static Eterm pd_hash_get_all(Process *p, ProcDict *pd); +static Eterm pd_hash_get_all(Process *p, ProcDict *pd, int keep_dict); static Eterm pd_hash_put(Process *p, Eterm id, Eterm value); static void shrink(Process *p, Eterm* ret); @@ -281,7 +281,7 @@ BIF_RETTYPE get_0(BIF_ALIST_0) { Eterm ret; PD_CHECK(BIF_P->dictionary); - ret = pd_hash_get_all(BIF_P, BIF_P->dictionary); + ret = pd_hash_get_all(BIF_P, BIF_P->dictionary, 1); PD_CHECK(BIF_P->dictionary); BIF_RET(ret); } @@ -329,7 +329,7 @@ BIF_RETTYPE erase_0(BIF_ALIST_0) { Eterm ret; PD_CHECK(BIF_P->dictionary); - ret = pd_hash_get_all(BIF_P, BIF_P->dictionary); + ret = pd_hash_get_all(BIF_P, BIF_P->dictionary, 0); pd_hash_erase_all(BIF_P); PD_CHECK(BIF_P->dictionary); BIF_RET(ret); @@ -541,29 +541,46 @@ static Eterm pd_hash_get_keys(Process *p, Eterm value) static Eterm -pd_hash_get_all(Process *p, ProcDict *pd) +pd_hash_get_all(Process *p, ProcDict *pd, int keep_dict) { Eterm* hp; + Eterm* tp; Eterm res = NIL; Eterm tmp, tmp2; unsigned int i; unsigned int num; + Uint need; if (pd == NULL) { return res; } num = HASH_RANGE(pd); - hp = HAlloc(p, pd->numElements * 2); - + + /* + * If this is not erase/0, then must copy all key-value tuples + * as they may be mutated by put/2. + */ + need = pd->numElements * (keep_dict ? 2+3 : 2); + hp = HAlloc(p, need); + for (i = 0; i < num; ++i) { tmp = ARRAY_GET(pd, i); if (is_boxed(tmp)) { - ASSERT(is_tuple(tmp)); + if (keep_dict) { + tp = tuple_val(tmp); + tmp = TUPLE2(hp, tp[1], tp[2]); + hp += 3; + } res = CONS(hp, tmp, res); hp += 2; } else if (is_list(tmp)) { while (tmp != NIL) { tmp2 = TCAR(tmp); + if (keep_dict) { + tp = tuple_val(tmp2); + tmp2 = TUPLE2(hp, tp[1], tp[2]); + hp += 3; + } res = CONS(hp, tmp2, res); hp += 2; tmp = TCDR(tmp); @@ -607,6 +624,11 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) ASSERT(is_tuple(old)); tp = tuple_val(old); if (EQ(tp[1], id)) { + if (is_immed(value)) { + Eterm old_val = tp[2]; + tp[2] = value; + return old_val; + } key_at = 1; } else { @@ -619,6 +641,11 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) for (tmp = old; tmp != NIL; tmp = TCDR(tmp)) { tp = tuple_val(TCAR(tmp)); if (EQ(tp[1], id)) { + if (is_immed(value)) { + Eterm old_val = tp[2]; + tp[2] = value; + return old_val; + } key_at = i; needed += 2*(key_at-1); break; diff --git a/lib/kernel/test/pdict_SUITE.erl b/lib/kernel/test/pdict_SUITE.erl index d105952df9..a891451c82 100644 --- a/lib/kernel/test/pdict_SUITE.erl +++ b/lib/kernel/test/pdict_SUITE.erl @@ -33,6 +33,7 @@ init_per_group/2,end_per_group/2, mixed/1, literals/1, + destructive/1, simple/1, complicated/1, heavy/1, simple_all_keys/1, info/1]). -export([init_per_testcase/2, end_per_testcase/2]). -export([other_process/2]). @@ -52,6 +53,7 @@ suite() -> all() -> [simple, complicated, heavy, simple_all_keys, info, literals, + destructive, mixed]. groups() -> @@ -367,6 +369,36 @@ match_keys(All) -> ok. +%% Test destructive put optimization of immed values +%% does not affect get/0 or process_info. +destructive(_Config) -> + Keys = lists:seq(1,100), + [put(Key, 17) || Key <- Keys], + Get1 = get(), + {dictionary,PI1} = process_info(self(), dictionary), + + [begin + {Key, 17} = lists:keyfind(Key, 1, Get1), + {Key, 17} = lists:keyfind(Key, 1, PI1) + end + || Key <- Keys], + + [17 = put(Key, 42) || Key <- Keys], % Mutate + + Get2 = get(), + {dictionary,PI2} = process_info(self(), dictionary), + + [begin + {Key, 17} = lists:keyfind(Key, 1, Get1), + {Key, 17} = lists:keyfind(Key, 1, PI1), + {Key, 42} = lists:keyfind(Key, 1, Get2), + {Key, 42} = lists:keyfind(Key, 1, PI2) + + end + || Key <- Keys], + + ok. + %% Do random mixed put/erase to test grow/shrink %% Written for a temporary bug in gc during shrink mixed(_Config) -> -- cgit v1.2.3 From 847c465d9fae3630c011d928743f262288072057 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 5 Mar 2018 17:54:01 +0100 Subject: erts: Optimize erlang:put/2 for hash collision lists Instead of rebuilding all cons cells before key, just unlink key cell from list with a destructive heap write op. This is safe as these lists never leak out and any new-to-old-heap-refs are preserved. --- erts/emulator/beam/erl_process_dict.c | 102 ++++++++++++---------------------- 1 file changed, 37 insertions(+), 65 deletions(-) diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 87b440093b..aee88841ae 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -79,6 +79,8 @@ /* Array access macro */ #define ARRAY_GET(PDict, Index) (ASSERT((Index) < (PDict)->arraySize), \ (PDict)->data[Index]) +#define ARRAY_GET_PTR(PDict, Index) (ASSERT((Index) < (PDict)->arraySize), \ + &(PDict)->data[Index]) #define ARRAY_PUT(PDict, Index, Val) (ASSERT((Index) < (PDict)->arraySize), \ (PDict)->data[Index] = (Val)) @@ -595,11 +597,13 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) unsigned int hval; Eterm *hp; Eterm *tp; + Eterm *bucket; Eterm tpl; Eterm old; + Eterm old_val = am_undefined; Eterm tmp; int needed; - int key_at = 0; + int new_key = 1; #ifdef DEBUG Eterm *hp_limit; #endif @@ -613,7 +617,8 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) p->dictionary->numElements = 0; } hval = pd_hash_value(p->dictionary, id); - old = ARRAY_GET(p->dictionary, hval); + bucket = ARRAY_GET_PTR(p->dictionary, hval); + old = *bucket; /* * Calculate the number of heap words needed and garbage @@ -624,44 +629,46 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) ASSERT(is_tuple(old)); tp = tuple_val(old); if (EQ(tp[1], id)) { + old_val = tp[2]; if (is_immed(value)) { - Eterm old_val = tp[2]; - tp[2] = value; + tp[2] = value; /* DESTRUCTIVE HEAP ASSIGNMENT */ return old_val; } - key_at = 1; + new_key = 0; } else { needed += 2+2; } } else if (is_list(old)) { - int i = 1; + Eterm* prev_cdr = bucket; needed += 2; - for (tmp = old; tmp != NIL; tmp = TCDR(tmp)) { + for (tmp = old; tmp != NIL; prev_cdr = &TCDR(tmp), tmp = *prev_cdr) { tp = tuple_val(TCAR(tmp)); if (EQ(tp[1], id)) { + old_val = tp[2]; if (is_immed(value)) { - Eterm old_val = tp[2]; - tp[2] = value; + tp[2] = value; /* DESTRUCTIVE HEAP ASSIGNMENT */ return old_val; } - key_at = i; - needed += 2*(key_at-1); + new_key = 0; + /* Unlink old {Key,Value} from list */ + *prev_cdr = TCDR(tmp); /* maybe DESTRUCTIVE HEAP ASSIGNMENT */ break; } - ++i; } } if (HeapWordsLeft(p) < needed) { Eterm root[3]; root[0] = id; root[1] = value; - root[2] = old; + root[2] = old_val; erts_garbage_collect(p, needed, root, 3); id = root[0]; value = root[1]; - old = root[2]; + old_val = root[2]; + ASSERT(bucket == ARRAY_GET_PTR(p->dictionary, hval)); + old = *bucket; } #ifdef DEBUG hp_limit = p->htop + needed; @@ -677,67 +684,29 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) * Update the dictionary. */ if (is_nil(old)) { - ARRAY_PUT(p->dictionary, hval, tpl); - ++(p->dictionary->numElements); + *bucket = tpl; } else if (is_boxed(old)) { ASSERT(is_tuple(old)); - if (key_at) { + if (!new_key) { ASSERT(EQ(tuple_val(old)[1],id)); - ARRAY_PUT(p->dictionary, hval, tpl); - return tuple_val(old)[2]; + *bucket = tpl; + return old_val; } else { hp = HeapOnlyAlloc(p, 4); tmp = CONS(hp, old, NIL); hp += 2; - ++(p->dictionary->numElements); - ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, tmp)); + *bucket = CONS(hp, tpl, tmp); hp += 2; ASSERT(hp <= hp_limit); } } else if (is_list(old)) { - if (!key_at) { - /* - * New key. Simply prepend the tuple to the beginning of the list. - */ - hp = HeapOnlyAlloc(p, 2); - ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, old)); - hp += 2; - ASSERT(hp <= hp_limit); - ++(p->dictionary->numElements); - } else { - /* - * key_at = Key position in the list. - * - * Replace old value in list. To avoid pointers from the old generation - * to the new, we must rebuild the list from the beginning up to and - * including the changed element. - */ - Eterm nlist; - int j; - - hp = HeapOnlyAlloc(p, key_at*2); - - /* Find the list element to change. */ - for (j = 1, nlist = old; j < key_at; j++, nlist = TCDR(nlist)) { - ; - } - ASSERT(EQ(tuple_val(TCAR(nlist))[1], id)); - nlist = TCDR(nlist); /* Unchanged part of list. */ - - /* Rebuild list before the updated element. */ - for (tmp = old; --key_at > 0; tmp = TCDR(tmp)) { - nlist = CONS(hp, TCAR(tmp), nlist); - hp += 2; - } - ASSERT(EQ(tuple_val(TCAR(tmp))[1], id)); - - /* Put the updated element first in the new list. */ - nlist = CONS(hp, tpl, nlist); - hp += 2; - ASSERT(hp <= hp_limit); - ARRAY_PUT(p->dictionary, hval, nlist); - return tuple_val(TCAR(tmp))[2]; - } + /* + * Simply prepend the tuple to the beginning of the list. + */ + hp = HeapOnlyAlloc(p, 2); + *bucket = CONS(hp, tpl, *bucket); + hp += 2; + ASSERT(hp <= hp_limit); } else { #ifdef DEBUG erts_fprintf(stderr, @@ -748,10 +717,13 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) erts_exit(ERTS_ERROR_EXIT, "Damaged process dictionary found during put/2."); } + + p->dictionary->numElements += new_key; + if (HASH_RANGE(p->dictionary) <= p->dictionary->numElements) { grow(p); } - return am_undefined; + return old_val; } /* -- cgit v1.2.3