From 9c6f45b901ee701553afe34c0b33b7d931d73fd9 Mon Sep 17 00:00:00 2001 From: Rickard Green Date: Wed, 11 Nov 2015 11:39:32 +0100 Subject: Bump reductions on GC --- erts/emulator/beam/erl_process_dict.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 8606371bdf..f82cad745a 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -583,7 +583,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) root[0] = id; root[1] = value; root[2] = old; - BUMP_REDS(p, erts_garbage_collect(p, needed, root, 3)); + erts_garbage_collect(p, needed, root, 3); id = root[0]; value = root[1]; old = root[2]; @@ -715,7 +715,7 @@ static void shrink(Process *p, Eterm* ret) needed = 2*erts_list_length(hi); } if (HeapWordsLeft(p) < needed) { - BUMP_REDS(p, erts_garbage_collect(p, needed, ret, 1)); + erts_garbage_collect(p, needed, ret, 1); hi = pd->data[(pd->splitPosition + pd->homeSize)]; lo = pd->data[pd->splitPosition]; } @@ -811,7 +811,7 @@ static void grow(Process *p) } } if (HeapWordsLeft(p) < needed) { - BUMP_REDS(p, erts_garbage_collect(p, needed, 0, 0)); + erts_garbage_collect(p, needed, 0, 0); } #ifdef DEBUG hp_limit = p->htop + needed; -- cgit v1.2.3 From f67a7375e19734c3f7d6947b0dcf608d0fe1c8fa Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 1 Dec 2015 18:02:54 +0100 Subject: erts: Use internal hash for process dictionaries --- erts/emulator/beam/erl_process_dict.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 8606371bdf..81469e8716 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -53,11 +53,11 @@ /* Hash utility macros */ #define HASH_RANGE(PDict) ((PDict)->homeSize + (PDict)->splitPosition) -#define MAKE_HASH(Term) \ -((is_small(Term)) ? unsigned_val(Term) : \ - ((is_atom(Term)) ? \ - (atom_tab(atom_val(term))->slot.bucket.hvalue) : \ - make_hash2(Term))) +#define MAKE_HASH(Term) \ + ((is_small(Term)) ? unsigned_val(Term) : \ + ((is_atom(Term)) ? \ + (atom_tab(atom_val(Term))->slot.bucket.hvalue) : \ + make_internal_hash(Term))) #define PD_SZ2BYTES(Sz) (sizeof(ProcDict) + ((Sz) - 1)*sizeof(Eterm)) -- cgit v1.2.3 From c97f3332aeddf039ee2207196229b9ff07047c72 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Wed, 2 Dec 2015 13:17:28 +0100 Subject: erts: Add i_get_hash instruction Calculate hashvalue in load-time for constant process dictionary gets. --- erts/emulator/beam/erl_process_dict.c | 56 +++++++++++++++++++++++------------ 1 file changed, 37 insertions(+), 19 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 81469e8716..e497267b63 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -61,6 +61,9 @@ #define PD_SZ2BYTES(Sz) (sizeof(ProcDict) + ((Sz) - 1)*sizeof(Eterm)) +#define pd_hash_value(Pdict, Key) \ + pd_hash_value_to_ix(Pdict, MAKE_HASH((Key))) + /* Memory allocation macros */ #define PD_ALLOC(Sz) \ erts_alloc(ERTS_ALC_T_PROC_DICT, (Sz)) @@ -82,6 +85,7 @@ */ static void pd_hash_erase(Process *p, Eterm id, Eterm *ret); 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); @@ -93,7 +97,7 @@ static void grow(Process *p); static void array_shrink(ProcDict **ppd, unsigned int need); static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term); -static unsigned int pd_hash_value(ProcDict *pdict, Eterm term); +static unsigned int pd_hash_value_to_ix(ProcDict *pdict, Uint32 hx); static unsigned int next_array_size(unsigned int need); /* @@ -390,40 +394,55 @@ static void pd_hash_erase_all(Process *p) } } +Eterm erts_pd_hash_get_with_hx(Process *p, Uint32 hx, Eterm id) +{ + unsigned int hval; + ProcDict *pd = p->dictionary; + + if (pd == NULL) + return am_undefined; + hval = pd_hash_value_to_ix(pd, hx); + return pd_hash_get_with_hval(p, ARRAY_GET(pd, hval), id); +} + Eterm erts_pd_hash_get(Process *p, Eterm id) { unsigned int hval; - Eterm tmp; ProcDict *pd = p->dictionary; if (pd == NULL) return am_undefined; hval = pd_hash_value(pd, id); - tmp = ARRAY_GET(pd, hval); - if (is_boxed(tmp)) { /* Tuple */ - ASSERT(is_tuple(tmp)); - if (EQ(tuple_val(tmp)[1], id)) { - return tuple_val(tmp)[2]; + return pd_hash_get_with_hval(p, ARRAY_GET(pd, hval), id); +} + +Eterm pd_hash_get_with_hval(Process *p, Eterm bucket, Eterm id) +{ + if (is_boxed(bucket)) { /* Tuple */ + ASSERT(is_tuple(bucket)); + if (EQ(tuple_val(bucket)[1], id)) { + return tuple_val(bucket)[2]; } - } else if (is_list(tmp)) { - for (; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); tmp = TCDR(tmp)) { + } else if (is_list(bucket)) { + for (; bucket != NIL && !EQ(tuple_val(TCAR(bucket))[1], id); bucket = TCDR(bucket)) { ; } - if (tmp != NIL) { - return tuple_val(TCAR(tmp))[2]; + if (bucket != NIL) { + return tuple_val(TCAR(bucket))[2]; } - } else if (is_not_nil(tmp)) { + } else if (is_not_nil(bucket)) { #ifdef DEBUG erts_fprintf(stderr, "Process dictionary for process %T is broken, trying to " "display term found in line %d:\n" - "%T\n", p->common.id, __LINE__, tmp); + "%T\n", p->common.id, __LINE__, bucket); #endif erl_exit(1, "Damaged process dictionary found during get/1."); } return am_undefined; } + #define PD_GET_TKEY(Dst,Src) \ do { \ ASSERT(is_tuple((Src))); \ @@ -932,17 +951,16 @@ static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term) ** Basic utilities */ -static unsigned int pd_hash_value(ProcDict *pdict, Eterm term) +static unsigned int pd_hash_value_to_ix(ProcDict *pdict, Uint32 hx) { - Uint hash, high; - - hash = MAKE_HASH(term); - high = hash % (pdict->homeSize*2); + Uint high; + high = hx % (pdict->homeSize*2); if (high >= HASH_RANGE(pdict)) - return hash % pdict->homeSize; + return hx % pdict->homeSize; return high; } + static unsigned int next_array_size(unsigned int need) { static unsigned int tab[] = -- cgit v1.2.3 From 343f461a2810ce3440b1d7c55cda996038071d87 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 8 Dec 2015 18:45:32 +0100 Subject: erts: Optimize hashing in process dictionary by limiting table sizes to powers of 2. This will change the default size from 10 to 8. --- erts/emulator/beam/erl_process_dict.c | 21 +++++++++++++++++++-- 1 file changed, 19 insertions(+), 2 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index e497267b63..c56a722542 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -80,6 +80,8 @@ #define ARRAY_GET(PDict, Index) (((PDict)->size > (Index)) ? \ (PDict)->data[Index] : NIL) +#define IS_POW2(X) ((X) && !((X) & ((X)-1))) + /* * Forward decalarations */ @@ -138,6 +140,16 @@ static void pd_check(ProcDict *pd); ** External interface */ +int +erts_pd_set_initial_size(int size) +{ + if (size <= 0) + return 0; + + erts_pd_initial_size = 1 << erts_fit_in_bits_uint(size-1); + return 1; +} + /* * Called from break handler */ @@ -399,6 +411,7 @@ Eterm erts_pd_hash_get_with_hx(Process *p, Uint32 hx, Eterm id) unsigned int hval; ProcDict *pd = p->dictionary; + ASSERT(hx == MAKE_HASH(id)); if (pd == NULL) return am_undefined; hval = pd_hash_value_to_ix(pd, hx); @@ -570,6 +583,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) /* Create it */ array_put(&(p->dictionary), INITIAL_SIZE - 1, NIL); p->dictionary->homeSize = INITIAL_SIZE; + ASSERT(IS_POW2(p->dictionary->homeSize)); } hval = pd_hash_value(p->dictionary, id); old = ARRAY_GET(p->dictionary, hval); @@ -954,9 +968,12 @@ static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term) static unsigned int pd_hash_value_to_ix(ProcDict *pdict, Uint32 hx) { Uint high; - high = hx % (pdict->homeSize*2); + + ASSERT(IS_POW2(pdict->homeSize)); + + high = hx & (pdict->homeSize*2 - 1); if (high >= HASH_RANGE(pdict)) - return hx % pdict->homeSize; + return hx & (pdict->homeSize - 1); return high; } -- cgit v1.2.3 From eb2e118ee2be5c008fc4417a443c351807adf123 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 8 Dec 2015 20:28:38 +0100 Subject: erts: Optimize away function "array_put" in proc dict Replace heave array_put() with a dumb array index assignment ARRAY_PUT and instead introduce ensure_array_size() to be called when we know the array might need to grow. This change also ensures the entire HASH_RANGE is always allocated. No need for ARRAY_GET to check index any more. --- erts/emulator/beam/erl_process_dict.c | 104 ++++++++++++++++------------------ 1 file changed, 48 insertions(+), 56 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index c56a722542..0934183b6a 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -77,8 +77,10 @@ #define TCDR(Term) CDR(list_val(Term)) /* Array access macro */ -#define ARRAY_GET(PDict, Index) (((PDict)->size > (Index)) ? \ - (PDict)->data[Index] : NIL) +#define ARRAY_GET(PDict, Index) (ASSERT((Index) < (PDict)->size), \ + (PDict)->data[Index]) +#define ARRAY_PUT(PDict, Index, Val) (ASSERT((Index) < (PDict)->size), \ + (PDict)->data[Index] = (Val)) #define IS_POW2(X) ((X) && !((X) & ((X)-1))) @@ -97,7 +99,7 @@ static void shrink(Process *p, Eterm* ret); static void grow(Process *p); static void array_shrink(ProcDict **ppd, unsigned int need); -static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term); +static void ensure_array_size(ProcDict**, unsigned int size); static unsigned int pd_hash_value_to_ix(ProcDict *pdict, Uint32 hx); static unsigned int next_array_size(unsigned int need); @@ -361,7 +363,7 @@ static void pd_hash_erase(Process *p, Eterm id, Eterm *ret) if (is_boxed(old)) { /* Tuple */ ASSERT(is_tuple(old)); if (EQ(tuple_val(old)[1], id)) { - array_put(&(p->dictionary), hval, NIL); + ARRAY_PUT(p->dictionary, hval, NIL); --(p->dictionary->numElements); *ret = tuple_val(old)[2]; } @@ -381,7 +383,7 @@ static void pd_hash_erase(Process *p, Eterm id, Eterm *ret) old = ARRAY_GET(p->dictionary, hval); ASSERT(is_list(old)); if (is_nil(TCDR(old))) { - array_put(&p->dictionary, hval, TCAR(old)); + ARRAY_PUT(p->dictionary, hval, TCAR(old)); } } else if (is_not_nil(old)) { #ifdef DEBUG @@ -581,9 +583,8 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) if (p->dictionary == NULL) { /* Create it */ - array_put(&(p->dictionary), INITIAL_SIZE - 1, NIL); + ensure_array_size(&p->dictionary, INITIAL_SIZE); p->dictionary->homeSize = INITIAL_SIZE; - ASSERT(IS_POW2(p->dictionary->homeSize)); } hval = pd_hash_value(p->dictionary, id); old = ARRAY_GET(p->dictionary, hval); @@ -635,19 +636,19 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) * Update the dictionary. */ if (is_nil(old)) { - array_put(&(p->dictionary), hval, tpl); + ARRAY_PUT(p->dictionary, hval, tpl); ++(p->dictionary->numElements); } else if (is_boxed(old)) { ASSERT(is_tuple(old)); if (EQ(tuple_val(old)[1],id)) { - array_put(&(p->dictionary), hval, tpl); + ARRAY_PUT(p->dictionary, hval, tpl); return tuple_val(old)[2]; } else { hp = HeapOnlyAlloc(p, 4); tmp = CONS(hp, old, NIL); hp += 2; ++(p->dictionary->numElements); - array_put(&(p->dictionary), hval, CONS(hp, tpl, tmp)); + ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, tmp)); hp += 2; ASSERT(hp <= hp_limit); } @@ -657,7 +658,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) * 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)); + ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, old)); hp += 2; ASSERT(hp <= hp_limit); ++(p->dictionary->numElements); @@ -692,7 +693,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) nlist = CONS(hp, tpl, nlist); hp += 2; ASSERT(hp <= hp_limit); - array_put(&(p->dictionary), hval, nlist); + ARRAY_PUT(p->dictionary, hval, nlist); return tuple_val(TCAR(tmp))[2]; } } else { @@ -741,7 +742,7 @@ static void shrink(Process *p, Eterm* ret) lo = ARRAY_GET(pd, pd->splitPosition); if (hi != NIL) { if (lo == NIL) { - array_put(&(p->dictionary), pd->splitPosition, hi); + ARRAY_PUT(p->dictionary, pd->splitPosition, hi); } else { int needed = 4; if (is_list(hi) && is_list(lo)) { @@ -760,13 +761,13 @@ static void shrink(Process *p, Eterm* ret) hp = HeapOnlyAlloc(p, 4); tmp = CONS(hp, hi, NIL); hp += 2; - array_put(&(p->dictionary), pd->splitPosition, + ARRAY_PUT(p->dictionary, pd->splitPosition, CONS(hp,lo,tmp)); hp += 2; ASSERT(hp <= hp_limit); } else { /* hi is a list */ hp = HeapOnlyAlloc(p, 2); - array_put(&(p->dictionary), pd->splitPosition, + ARRAY_PUT(p->dictionary, pd->splitPosition, CONS(hp, lo, hi)); hp += 2; ASSERT(hp <= hp_limit); @@ -774,7 +775,7 @@ static void shrink(Process *p, Eterm* ret) } else { /* lo is a list */ if (is_tuple(hi)) { hp = HeapOnlyAlloc(p, 2); - array_put(&(p->dictionary), pd->splitPosition, + ARRAY_PUT(p->dictionary, pd->splitPosition, CONS(hp, hi, lo)); hp += 2; ASSERT(hp <= hp_limit); @@ -786,12 +787,12 @@ static void shrink(Process *p, Eterm* ret) hp += 2; } ASSERT(hp <= hp_limit); - array_put(&(p->dictionary), pd->splitPosition, lo); + ARRAY_PUT(p->dictionary, pd->splitPosition, lo); } } } } - array_put(&(p->dictionary), (pd->splitPosition + pd->homeSize), NIL); + ARRAY_PUT(p->dictionary, (pd->splitPosition + pd->homeSize), NIL); } if (HASH_RANGE(p->dictionary) <= (p->dictionary->size / 4)) { array_shrink(&(p->dictionary), (HASH_RANGE(p->dictionary) * 3) / 2); @@ -808,7 +809,7 @@ static void grow(Process *p) unsigned int pos; unsigned int homeSize; int needed = 0; - ProcDict *pd; + ProcDict *pd = p->dictionary; #ifdef DEBUG Eterm *hp_limit; #endif @@ -817,16 +818,18 @@ static void grow(Process *p) if (steps == 0) steps = 1; /* Dont grow over MAX_HASH */ - if ((MAX_HASH - steps) <= HASH_RANGE(p->dictionary)) { + if ((MAX_HASH - steps) <= HASH_RANGE(pd)) { return; } + ensure_array_size(&p->dictionary, HASH_RANGE(pd) + steps); + pd = p->dictionary; + /* * Calculate total number of heap words needed, and garbage collect * if necessary. */ - pd = p->dictionary; pos = pd->splitPosition; homeSize = pd->homeSize; for (i = 0; i < steps; ++i) { @@ -855,7 +858,6 @@ static void grow(Process *p) */ for (i = 0; i < steps; ++i) { - ProcDict *pd = p->dictionary; if (pd->splitPosition == pd->homeSize) { pd->homeSize *= 2; pd->splitPosition = 0; @@ -865,9 +867,8 @@ static void grow(Process *p) l = ARRAY_GET(pd, pos); if (is_tuple(l)) { if (pd_hash_value(pd, tuple_val(l)[1]) != pos) { - array_put(&(p->dictionary), pos + - p->dictionary->homeSize, l); - array_put(&(p->dictionary), pos, NIL); + ARRAY_PUT(pd, pos + pd->homeSize, l); + ARRAY_PUT(pd, pos, NIL); } } else { l2 = NIL; @@ -889,10 +890,8 @@ static void grow(Process *p) if (l2 != NIL && TCDR(l2) == NIL) l2 = TCAR(l2); ASSERT(hp <= hp_limit); - /* After array_put pd is no longer valid */ - array_put(&(p->dictionary), pos, l1); - array_put(&(p->dictionary), pos + - p->dictionary->homeSize, l2); + ARRAY_PUT(pd, pos, l1); + ARRAY_PUT(pd, pos + pd->homeSize, l2); } } @@ -912,7 +911,7 @@ static void array_shrink(ProcDict **ppd, unsigned int need) HDEBUGF(("array_shrink: size = %d, used = %d, need = %d", (*ppd)->size, (*ppd)->used, need)); - if (siz > (*ppd)->size) + if (siz >= (*ppd)->size) return; /* Only shrink */ *ppd = PD_REALLOC(((void *) *ppd), @@ -925,40 +924,33 @@ static void array_shrink(ProcDict **ppd, unsigned int need) } -static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term) +static void ensure_array_size(ProcDict **ppdict, unsigned int size) { + ProcDict *pd = *ppdict; unsigned int i; - Eterm ret; - if (*ppdict == NULL) { - Uint siz = next_array_size(ndx+1); - ProcDict *p; - p = PD_ALLOC(PD_SZ2BYTES(siz)); + if (pd == NULL) { + Uint siz = next_array_size(size); + + pd = PD_ALLOC(PD_SZ2BYTES(siz)); for (i = 0; i < siz; ++i) - p->data[i] = NIL; - p->size = siz; - p->homeSize = p->splitPosition = p->numElements = p->used = 0; - *ppdict = p; - } else if (ndx >= (*ppdict)->size) { - Uint osize = (*ppdict)->size; - Uint nsize = next_array_size(ndx+1); - *ppdict = PD_REALLOC(((void *) *ppdict), + pd->data[i] = NIL; + pd->size = siz; + pd->homeSize = pd->splitPosition = pd->numElements = pd->used = 0; + *ppdict = pd; + } else if (size > pd->size) { + Uint osize = pd->size; + Uint nsize = next_array_size(size); + pd = PD_REALLOC(((void *) pd), PD_SZ2BYTES(osize), PD_SZ2BYTES(nsize)); for (i = osize; i < nsize; ++i) - (*ppdict)->data[i] = NIL; - (*ppdict)->size = nsize; + pd->data[i] = NIL; + pd->size = nsize; + *ppdict = pd; } - ret = (*ppdict)->data[ndx]; - (*ppdict)->data[ndx] = term; - if ((ndx + 1) > (*ppdict)->used) - (*ppdict)->used = ndx + 1; -#ifdef HARDDEBUG - HDEBUGF(("array_put: (*ppdict)->size = %d, (*ppdict)->used = %d, ndx = %d", - (*ppdict)->size, (*ppdict)->used, ndx)); - erts_fprintf(stderr, "%T", term); -#endif /* HARDDEBUG */ - return ret; + if (size > pd->used) + pd->used = size; } /* -- cgit v1.2.3 From 4179ca9f10cdc78e882ce4496cf0a1261a0129af Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 9 Dec 2015 19:34:45 +0100 Subject: erts: Remove ProcDict.used (homeSize + splitPosition) will do just fine --- erts/emulator/beam/erl_process_dict.c | 20 +++++++++----------- 1 file changed, 9 insertions(+), 11 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 0934183b6a..34c1f0c993 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -164,9 +164,9 @@ erts_dictionary_dump(int to, void *to_arg, ProcDict *pd) /*PD_CHECK(pd);*/ if (pd == NULL) return; - erts_print(to, to_arg, "(size = %d, used = %d, homeSize = %d, " + erts_print(to, to_arg, "(size = %d, homeSize = %d, " "splitPosition = %d, numElements = %d)\n", - pd->size, pd->used, pd->homeSize, + pd->size, pd->homeSize, pd->splitPosition, (unsigned int) pd->numElements); for (i = 0; i < HASH_RANGE(pd); ++i) { erts_print(to, to_arg, "%d: %T\n", i, ARRAY_GET(pd, i)); @@ -908,8 +908,8 @@ static void array_shrink(ProcDict **ppd, unsigned int need) { unsigned int siz = next_array_size(need); - HDEBUGF(("array_shrink: size = %d, used = %d, need = %d", - (*ppd)->size, (*ppd)->used, need)); + HDEBUGF(("array_shrink: size = %d, need = %d", + (*ppd)->size, need)); if (siz >= (*ppd)->size) return; /* Only shrink */ @@ -919,8 +919,6 @@ static void array_shrink(ProcDict **ppd, unsigned int need) PD_SZ2BYTES(siz)); (*ppd)->size = siz; - if ((*ppd)->size < (*ppd)->used) - (*ppd)->used = (*ppd)->size; } @@ -936,7 +934,7 @@ static void ensure_array_size(ProcDict **ppdict, unsigned int size) for (i = 0; i < siz; ++i) pd->data[i] = NIL; pd->size = siz; - pd->homeSize = pd->splitPosition = pd->numElements = pd->used = 0; + pd->homeSize = pd->splitPosition = pd->numElements = 0; *ppdict = pd; } else if (size > pd->size) { Uint osize = pd->size; @@ -949,8 +947,6 @@ static void ensure_array_size(ProcDict **ppdict, unsigned int size) pd->size = nsize; *ppdict = pd; } - if (size > pd->used) - pd->used = size; } /* @@ -1029,12 +1025,14 @@ static unsigned int next_array_size(unsigned int need) static void pd_check(ProcDict *pd) { unsigned int i; + unsigned int used; Uint num; if (pd == NULL) return; - ASSERT(pd->size >= pd->used); + used = HASH_RANGE(pd); + ASSERT(pd->size >= used); ASSERT(HASH_RANGE(pd) <= MAX_HASH); - for (i = 0, num = 0; i < pd->used; ++i) { + for (i = 0, num = 0; i < used; ++i) { Eterm t = pd->data[i]; if (is_nil(t)) { continue; -- cgit v1.2.3 From 4804ea2aa50af490ab3998466269efa540abd90d Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 10 Dec 2015 15:25:22 +0100 Subject: erts: Add sizeMask for faster proc dict indexing --- erts/emulator/beam/erl_process_dict.c | 26 +++++++++++++++----------- 1 file changed, 15 insertions(+), 11 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 34c1f0c993..97a2828b4e 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -585,6 +585,9 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) /* Create it */ ensure_array_size(&p->dictionary, INITIAL_SIZE); p->dictionary->homeSize = INITIAL_SIZE; + p->dictionary->sizeMask = p->dictionary->homeSize*2 - 1; + p->dictionary->splitPosition = 0; + p->dictionary->numElements = 0; } hval = pd_hash_value(p->dictionary, id); old = ARRAY_GET(p->dictionary, hval); @@ -718,6 +721,7 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) static void shrink(Process *p, Eterm* ret) { + ProcDict *pd = p->dictionary; unsigned int range = HASH_RANGE(p->dictionary); unsigned int steps = (range*3) / 10; Eterm hi, lo, tmp; @@ -732,8 +736,8 @@ static void shrink(Process *p, Eterm* ret) } for (i = 0; i < steps; ++i) { - ProcDict *pd = p->dictionary; if (pd->splitPosition == 0) { + pd->sizeMask = pd->homeSize - 1; pd->homeSize /= 2; pd->splitPosition = pd->homeSize; } @@ -742,7 +746,7 @@ static void shrink(Process *p, Eterm* ret) lo = ARRAY_GET(pd, pd->splitPosition); if (hi != NIL) { if (lo == NIL) { - ARRAY_PUT(p->dictionary, pd->splitPosition, hi); + ARRAY_PUT(pd, pd->splitPosition, hi); } else { int needed = 4; if (is_list(hi) && is_list(lo)) { @@ -761,13 +765,13 @@ static void shrink(Process *p, Eterm* ret) hp = HeapOnlyAlloc(p, 4); tmp = CONS(hp, hi, NIL); hp += 2; - ARRAY_PUT(p->dictionary, pd->splitPosition, + ARRAY_PUT(pd, pd->splitPosition, CONS(hp,lo,tmp)); hp += 2; ASSERT(hp <= hp_limit); } else { /* hi is a list */ hp = HeapOnlyAlloc(p, 2); - ARRAY_PUT(p->dictionary, pd->splitPosition, + ARRAY_PUT(pd, pd->splitPosition, CONS(hp, lo, hi)); hp += 2; ASSERT(hp <= hp_limit); @@ -775,7 +779,7 @@ static void shrink(Process *p, Eterm* ret) } else { /* lo is a list */ if (is_tuple(hi)) { hp = HeapOnlyAlloc(p, 2); - ARRAY_PUT(p->dictionary, pd->splitPosition, + ARRAY_PUT(pd, pd->splitPosition, CONS(hp, hi, lo)); hp += 2; ASSERT(hp <= hp_limit); @@ -787,12 +791,12 @@ static void shrink(Process *p, Eterm* ret) hp += 2; } ASSERT(hp <= hp_limit); - ARRAY_PUT(p->dictionary, pd->splitPosition, lo); + ARRAY_PUT(pd, pd->splitPosition, lo); } } } } - ARRAY_PUT(p->dictionary, (pd->splitPosition + pd->homeSize), NIL); + ARRAY_PUT(pd, (pd->splitPosition + pd->homeSize), NIL); } if (HASH_RANGE(p->dictionary) <= (p->dictionary->size / 4)) { array_shrink(&(p->dictionary), (HASH_RANGE(p->dictionary) * 3) / 2); @@ -860,7 +864,8 @@ static void grow(Process *p) for (i = 0; i < steps; ++i) { if (pd->splitPosition == pd->homeSize) { pd->homeSize *= 2; - pd->splitPosition = 0; + pd->sizeMask = pd->homeSize*2 - 1; + pd->splitPosition = 0; } pos = pd->splitPosition; ++pd->splitPosition; /* For the hashes */ @@ -934,7 +939,6 @@ static void ensure_array_size(ProcDict **ppdict, unsigned int size) for (i = 0; i < siz; ++i) pd->data[i] = NIL; pd->size = siz; - pd->homeSize = pd->splitPosition = pd->numElements = 0; *ppdict = pd; } else if (size > pd->size) { Uint osize = pd->size; @@ -959,9 +963,9 @@ static unsigned int pd_hash_value_to_ix(ProcDict *pdict, Uint32 hx) ASSERT(IS_POW2(pdict->homeSize)); - high = hx & (pdict->homeSize*2 - 1); + high = hx & pdict->sizeMask; if (high >= HASH_RANGE(pdict)) - return hx & (pdict->homeSize - 1); + return hx & (pdict->sizeMask >> 1); return high; } -- cgit v1.2.3 From 5801defc866e34c6effd49b9dec995b5dac164f3 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 10 Dec 2015 16:21:59 +0100 Subject: erts: Refactor proc dict with 'usedSlots' which is same as old homeSize + splitPosition. --- erts/emulator/beam/erl_process_dict.c | 50 ++++++++++++++++++++--------------- 1 file changed, 29 insertions(+), 21 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 97a2828b4e..b3d7627f08 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -51,7 +51,7 @@ #define INITIAL_SIZE (erts_pd_initial_size) /* Hash utility macros */ -#define HASH_RANGE(PDict) ((PDict)->homeSize + (PDict)->splitPosition) +#define HASH_RANGE(PDict) ((PDict)->usedSlots) #define MAKE_HASH(Term) \ ((is_small(Term)) ? unsigned_val(Term) : \ @@ -164,9 +164,9 @@ erts_dictionary_dump(int to, void *to_arg, ProcDict *pd) /*PD_CHECK(pd);*/ if (pd == NULL) return; - erts_print(to, to_arg, "(size = %d, homeSize = %d, " + erts_print(to, to_arg, "(size = %d, usedSlots = %d, " "splitPosition = %d, numElements = %d)\n", - pd->size, pd->homeSize, + pd->arraySize, pd->usedSlots, pd->splitPosition, (unsigned int) pd->numElements); for (i = 0; i < HASH_RANGE(pd); ++i) { erts_print(to, to_arg, "%d: %T\n", i, ARRAY_GET(pd, i)); @@ -584,8 +584,8 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value) if (p->dictionary == NULL) { /* Create it */ ensure_array_size(&p->dictionary, INITIAL_SIZE); - p->dictionary->homeSize = INITIAL_SIZE; - p->dictionary->sizeMask = p->dictionary->homeSize*2 - 1; + p->dictionary->usedSlots = INITIAL_SIZE; + p->dictionary->sizeMask = INITIAL_SIZE*2 - 1; p->dictionary->splitPosition = 0; p->dictionary->numElements = 0; } @@ -737,12 +737,13 @@ static void shrink(Process *p, Eterm* ret) for (i = 0; i < steps; ++i) { if (pd->splitPosition == 0) { - pd->sizeMask = pd->homeSize - 1; - pd->homeSize /= 2; - pd->splitPosition = pd->homeSize; + ASSERT(IS_POW2(pd->usedSlots)); + pd->sizeMask = pd->usedSlots - 1; + pd->splitPosition = pd->usedSlots / 2; } --(pd->splitPosition); - hi = ARRAY_GET(pd, (pd->splitPosition + pd->homeSize)); + /* Must wait to decrement 'usedSlots' for GC rootset below */ + hi = ARRAY_GET(pd, pd->usedSlots - 1); lo = ARRAY_GET(pd, pd->splitPosition); if (hi != NIL) { if (lo == NIL) { @@ -754,7 +755,7 @@ static void shrink(Process *p, Eterm* ret) } if (HeapWordsLeft(p) < needed) { BUMP_REDS(p, erts_garbage_collect(p, needed, ret, 1)); - hi = pd->data[(pd->splitPosition + pd->homeSize)]; + hi = pd->data[pd->usedSlots - 1]; lo = pd->data[pd->splitPosition]; } #ifdef DEBUG @@ -796,7 +797,8 @@ static void shrink(Process *p, Eterm* ret) } } } - ARRAY_PUT(pd, (pd->splitPosition + pd->homeSize), NIL); + --pd->usedSlots; + ARRAY_PUT(pd, pd->usedSlots, NIL); } if (HASH_RANGE(p->dictionary) <= (p->dictionary->size / 4)) { array_shrink(&(p->dictionary), (HASH_RANGE(p->dictionary) * 3) / 2); @@ -806,7 +808,7 @@ static void shrink(Process *p, Eterm* ret) static void grow(Process *p) { unsigned int i,j; - unsigned int steps = p->dictionary->homeSize / 5; + unsigned int steps = (p->dictionary->usedSlots / 4) & 0xf; Eterm l1,l2; Eterm l; Eterm *hp; @@ -835,7 +837,7 @@ static void grow(Process *p) */ pos = pd->splitPosition; - homeSize = pd->homeSize; + homeSize = pd->usedSlots - pd->splitPosition; for (i = 0; i < steps; ++i) { if (pos == homeSize) { homeSize *= 2; @@ -860,19 +862,21 @@ static void grow(Process *p) /* * Now grow. */ - + homeSize = pd->usedSlots - pd->splitPosition; for (i = 0; i < steps; ++i) { - if (pd->splitPosition == pd->homeSize) { - pd->homeSize *= 2; - pd->sizeMask = pd->homeSize*2 - 1; + if (pd->splitPosition == homeSize) { + homeSize *= 2; + pd->sizeMask = homeSize*2 - 1; pd->splitPosition = 0; } pos = pd->splitPosition; ++pd->splitPosition; /* For the hashes */ + ++pd->usedSlots; + ASSERT(pos + homeSize == pd->usedSlots - 1); l = ARRAY_GET(pd, pos); if (is_tuple(l)) { if (pd_hash_value(pd, tuple_val(l)[1]) != pos) { - ARRAY_PUT(pd, pos + pd->homeSize, l); + ARRAY_PUT(pd, pos + homeSize, l); ARRAY_PUT(pd, pos, NIL); } } else { @@ -896,7 +900,7 @@ static void grow(Process *p) l2 = TCAR(l2); ASSERT(hp <= hp_limit); ARRAY_PUT(pd, pos, l1); - ARRAY_PUT(pd, pos + pd->homeSize, l2); + ARRAY_PUT(pd, pos + homeSize, l2); } } @@ -961,7 +965,9 @@ static unsigned int pd_hash_value_to_ix(ProcDict *pdict, Uint32 hx) { Uint high; - ASSERT(IS_POW2(pdict->homeSize)); + ASSERT(IS_POW2(pdict->sizeMask+1)); + ASSERT(HASH_RANGE(pdict) >= (pdict->sizeMask >> 1)); + ASSERT(HASH_RANGE(pdict) <= (pdict->sizeMask + 1)); high = hx & pdict->sizeMask; if (high >= HASH_RANGE(pdict)) @@ -1043,12 +1049,14 @@ static void pd_check(ProcDict *pd) } else if (is_tuple(t)) { ++num; ASSERT(arityval(*tuple_val(t)) == 2); + ASSERT(pd_hash_value(pd, tuple_val(t)[1]) == i); continue; } else if (is_list(t)) { while (t != NIL) { ++num; ASSERT(is_tuple(TCAR(t))); ASSERT(arityval(*(tuple_val(TCAR(t)))) == 2); + ASSERT(pd_hash_value(pd, tuple_val(TCAR(t))[1]) == i); t = TCDR(t); } continue; @@ -1059,7 +1067,7 @@ static void pd_check(ProcDict *pd) } } ASSERT(num == pd->numElements); - ASSERT(pd->splitPosition <= pd->homeSize); + ASSERT(pd->usedSlots >= pd->splitPosition*2); } #endif /* DEBUG */ -- cgit v1.2.3 From 0f32d250876e7bb226fb96e07fb31734ba7d16f2 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 10 Dec 2015 17:47:37 +0100 Subject: erts: Rename proc dict size to arraySize for naming style consistency. --- erts/emulator/beam/erl_process_dict.c | 26 +++++++++++++------------- 1 file changed, 13 insertions(+), 13 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index b3d7627f08..e384f4c3f6 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -77,9 +77,9 @@ #define TCDR(Term) CDR(list_val(Term)) /* Array access macro */ -#define ARRAY_GET(PDict, Index) (ASSERT((Index) < (PDict)->size), \ +#define ARRAY_GET(PDict, Index) (ASSERT((Index) < (PDict)->arraySize), \ (PDict)->data[Index]) -#define ARRAY_PUT(PDict, Index, Val) (ASSERT((Index) < (PDict)->size), \ +#define ARRAY_PUT(PDict, Index, Val) (ASSERT((Index) < (PDict)->arraySize), \ (PDict)->data[Index] = (Val)) #define IS_POW2(X) ((X) && !((X) & ((X)-1))) @@ -221,7 +221,7 @@ erts_dicts_mem_size(Process *p) { Uint size = 0; if (p->dictionary) - size += PD_SZ2BYTES(p->dictionary->size); + size += PD_SZ2BYTES(p->dictionary->arraySize); return size; } @@ -800,7 +800,7 @@ static void shrink(Process *p, Eterm* ret) --pd->usedSlots; ARRAY_PUT(pd, pd->usedSlots, NIL); } - if (HASH_RANGE(p->dictionary) <= (p->dictionary->size / 4)) { + if (HASH_RANGE(p->dictionary) <= (p->dictionary->arraySize / 4)) { array_shrink(&(p->dictionary), (HASH_RANGE(p->dictionary) * 3) / 2); } } @@ -918,16 +918,16 @@ static void array_shrink(ProcDict **ppd, unsigned int need) unsigned int siz = next_array_size(need); HDEBUGF(("array_shrink: size = %d, need = %d", - (*ppd)->size, need)); + (*ppd)->arraySize, need)); - if (siz >= (*ppd)->size) + if (siz >= (*ppd)->arraySize) return; /* Only shrink */ *ppd = PD_REALLOC(((void *) *ppd), - PD_SZ2BYTES((*ppd)->size), + PD_SZ2BYTES((*ppd)->arraySize), PD_SZ2BYTES(siz)); - (*ppd)->size = siz; + (*ppd)->arraySize = siz; } @@ -942,17 +942,17 @@ static void ensure_array_size(ProcDict **ppdict, unsigned int size) pd = PD_ALLOC(PD_SZ2BYTES(siz)); for (i = 0; i < siz; ++i) pd->data[i] = NIL; - pd->size = siz; + pd->arraySize = siz; *ppdict = pd; - } else if (size > pd->size) { - Uint osize = pd->size; + } else if (size > pd->arraySize) { + Uint osize = pd->arraySize; Uint nsize = next_array_size(size); pd = PD_REALLOC(((void *) pd), PD_SZ2BYTES(osize), PD_SZ2BYTES(nsize)); for (i = osize; i < nsize; ++i) pd->data[i] = NIL; - pd->size = nsize; + pd->arraySize = nsize; *ppdict = pd; } } @@ -1040,7 +1040,7 @@ static void pd_check(ProcDict *pd) if (pd == NULL) return; used = HASH_RANGE(pd); - ASSERT(pd->size >= used); + ASSERT(pd->arraySize >= used); ASSERT(HASH_RANGE(pd) <= MAX_HASH); for (i = 0, num = 0; i < used; ++i) { Eterm t = pd->data[i]; -- cgit v1.2.3 From 14680fcc3fb9d0357fe33a94525d08896afed1c5 Mon Sep 17 00:00:00 2001 From: Richard Carlsson Date: Thu, 3 Dec 2015 14:33:53 +0100 Subject: erts: Use Sint instead of int for list lengths This avoids potential integer arithmetic overflow for very large lists. --- erts/emulator/beam/erl_process_dict.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'erts/emulator/beam/erl_process_dict.c') diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 84cd81aecf..36d16f7f42 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -749,7 +749,7 @@ static void shrink(Process *p, Eterm* ret) if (lo == NIL) { ARRAY_PUT(pd, pd->splitPosition, hi); } else { - int needed = 4; + Sint needed = 4; if (is_list(hi) && is_list(lo)) { needed = 2*erts_list_length(hi); } @@ -814,7 +814,7 @@ static void grow(Process *p) Eterm *hp; unsigned int pos; unsigned int homeSize; - int needed = 0; + Sint needed = 0; ProcDict *pd = p->dictionary; #ifdef DEBUG Eterm *hp_limit; -- cgit v1.2.3