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_init.c | 4 ++-- erts/emulator/beam/erl_process_dict.c | 21 +++++++++++++++++++-- erts/emulator/beam/erl_process_dict.h | 1 + 3 files changed, 22 insertions(+), 4 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/erl_init.c b/erts/emulator/beam/erl_init.c index d9c3b0dcf4..0a34d91a01 100644 --- a/erts/emulator/beam/erl_init.c +++ b/erts/emulator/beam/erl_init.c @@ -197,7 +197,7 @@ Uint32 verbose; /* See erl_debug.h for information about verbose */ int erts_atom_table_size = ATOM_LIMIT; /* Maximum number of atoms */ -int erts_pd_initial_size = 10; +int erts_pd_initial_size = 8; /* must be power of 2 */ int erts_modified_timing_level; @@ -1479,7 +1479,7 @@ erl_start(int argc, char **argv) VERBOSE(DEBUG_SYSTEM, ("using minimum heap size %d\n", H_MIN_SIZE)); } else if (has_prefix("pds", sub_param)) { arg = get_arg(sub_param+3, argv[i+1], &i); - if ((erts_pd_initial_size = atoi(arg)) <= 0) { + if (!erts_pd_set_initial_size(atoi(arg))) { erts_fprintf(stderr, "bad initial process dictionary size %s\n", arg); erts_usage(); } 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; } diff --git a/erts/emulator/beam/erl_process_dict.h b/erts/emulator/beam/erl_process_dict.h index 9aa21b7c38..ab50d45c63 100644 --- a/erts/emulator/beam/erl_process_dict.h +++ b/erts/emulator/beam/erl_process_dict.h @@ -31,6 +31,7 @@ typedef struct proc_dict { Eterm data[1]; /* The beginning of an array of erlang terms */ } ProcDict; +int erts_pd_set_initial_size(int size); Uint erts_dicts_mem_size(struct process *p); void erts_erase_dicts(struct process *p); void erts_dictionary_dump(int to, void *to_arg, ProcDict *pd); -- 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') 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 bb5f71a7573158056dd9c80228c95833f970ec0b Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 9 Dec 2015 19:28:15 +0100 Subject: erts: Add proc dict macros ERTS_PD_START/SIZE --- erts/emulator/beam/beam_bif_load.c | 4 ++-- erts/emulator/beam/erl_debug.c | 6 +++--- erts/emulator/beam/erl_gc.c | 10 +++++----- erts/emulator/beam/erl_process_dict.h | 3 +++ 4 files changed, 13 insertions(+), 10 deletions(-) (limited to 'erts') diff --git a/erts/emulator/beam/beam_bif_load.c b/erts/emulator/beam/beam_bif_load.c index 0e192b1ebd..c804a09f87 100644 --- a/erts/emulator/beam/beam_bif_load.c +++ b/erts/emulator/beam/beam_bif_load.c @@ -851,8 +851,8 @@ check_process_code(Process* rp, Module* modp, int allow_gc, int *redsp) } if (rp->dictionary != NULL) { - Eterm* start = rp->dictionary->data; - Eterm* end = start + rp->dictionary->used; + Eterm* start = ERTS_PD_START(rp->dictionary); + Eterm* end = start + ERTS_PD_SIZE(rp->dictionary); if (any_heap_ref_ptrs(start, end, mod_start, mod_size)) { goto need_gc; diff --git a/erts/emulator/beam/erl_debug.c b/erts/emulator/beam/erl_debug.c index 2dcfb79f00..a2af3adf70 100644 --- a/erts/emulator/beam/erl_debug.c +++ b/erts/emulator/beam/erl_debug.c @@ -416,7 +416,7 @@ void verify_process(Process *p) erts_check_heap(p); if (p->dictionary) - VERIFY_AREA("dictionary",p->dictionary->data, p->dictionary->used); + VERIFY_AREA("dictionary", ERTS_PD_START(p->dictionary), ERTS_PD_SIZE(p->dictionary)); VERIFY_ETERM("seq trace token",p->seq_trace_token); VERIFY_ETERM("group leader",p->group_leader); VERIFY_ETERM("fvalue",p->fvalue); @@ -542,8 +542,8 @@ static void print_process_memory(Process *p) } if (p->dictionary != NULL) { - int n = p->dictionary->used; - Eterm *ptr = p->dictionary->data; + int n = ERTS_PD_SIZE(p->dictionary); + Eterm *ptr = ERTS_PD_START(p->dictionary); erts_printf(" Dictionary: "); while (n--) erts_printf("0x%0*lx ",PTR_SIZE,(unsigned long)ptr++); erts_printf("\n"); diff --git a/erts/emulator/beam/erl_gc.c b/erts/emulator/beam/erl_gc.c index d2604f1595..b743b7e8f6 100644 --- a/erts/emulator/beam/erl_gc.c +++ b/erts/emulator/beam/erl_gc.c @@ -1953,7 +1953,7 @@ collect_heap_frags(Process* p, Eterm* n_hstart, Eterm* n_htop, #ifdef HARDDEBUG disallow_heap_frag_ref(p, n_htop, p->stop, STACK_START(p) - p->stop); if (p->dictionary != NULL) { - disallow_heap_frag_ref(p, n_htop, p->dictionary->data, p->dictionary->used); + disallow_heap_frag_ref(p, n_htop, ERTS_PD_START(p->dictionary), ERTS_PD_SIZE(p->dictionary)); } disallow_heap_frag_ref_in_heap(p); #endif @@ -1993,8 +1993,8 @@ setup_rootset(Process *p, Eterm *objv, int nobj, Rootset *rootset) ++n; if (p->dictionary != NULL) { - roots[n].v = p->dictionary->data; - roots[n].sz = p->dictionary->used; + roots[n].v = ERTS_PD_START(p->dictionary); + roots[n].sz = ERTS_PD_SIZE(p->dictionary); ++n; } if (nobj > 0) { @@ -2589,8 +2589,8 @@ offset_one_rootset(Process *p, Sint offs, char* area, Uint area_size, Eterm* objv, int nobj) { if (p->dictionary) { - offset_heap(p->dictionary->data, - p->dictionary->used, + offset_heap(ERTS_PD_START(p->dictionary), + ERTS_PD_SIZE(p->dictionary), offs, area, area_size); } diff --git a/erts/emulator/beam/erl_process_dict.h b/erts/emulator/beam/erl_process_dict.h index ab50d45c63..3ad070d914 100644 --- a/erts/emulator/beam/erl_process_dict.h +++ b/erts/emulator/beam/erl_process_dict.h @@ -31,6 +31,9 @@ typedef struct proc_dict { Eterm data[1]; /* The beginning of an array of erlang terms */ } ProcDict; +#define ERTS_PD_START(PD) ((PD)->data) +#define ERTS_PD_SIZE(PD) ((PD)->used) + int erts_pd_set_initial_size(int size); Uint erts_dicts_mem_size(struct process *p); void erts_erase_dicts(struct process *p); -- 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 +++++++++----------- erts/emulator/beam/erl_process_dict.h | 3 +-- 2 files changed, 10 insertions(+), 13 deletions(-) (limited to 'erts') 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; diff --git a/erts/emulator/beam/erl_process_dict.h b/erts/emulator/beam/erl_process_dict.h index 3ad070d914..eb26a1ffcc 100644 --- a/erts/emulator/beam/erl_process_dict.h +++ b/erts/emulator/beam/erl_process_dict.h @@ -24,7 +24,6 @@ typedef struct proc_dict { unsigned int size; - unsigned int used; unsigned int homeSize; unsigned int splitPosition; Uint numElements; @@ -32,7 +31,7 @@ typedef struct proc_dict { } ProcDict; #define ERTS_PD_START(PD) ((PD)->data) -#define ERTS_PD_SIZE(PD) ((PD)->used) +#define ERTS_PD_SIZE(PD) ((PD)->homeSize + (PD)->splitPosition) int erts_pd_set_initial_size(int size); Uint erts_dicts_mem_size(struct process *p); -- 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 +++++++++++++++----------- erts/emulator/beam/erl_process_dict.h | 1 + 2 files changed, 16 insertions(+), 11 deletions(-) (limited to 'erts') 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; } diff --git a/erts/emulator/beam/erl_process_dict.h b/erts/emulator/beam/erl_process_dict.h index eb26a1ffcc..fd59c969cf 100644 --- a/erts/emulator/beam/erl_process_dict.h +++ b/erts/emulator/beam/erl_process_dict.h @@ -23,6 +23,7 @@ #include "sys.h" typedef struct proc_dict { + unsigned int sizeMask; unsigned int size; unsigned int homeSize; unsigned int splitPosition; -- 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 ++++++++++++++++++++--------------- erts/emulator/beam/erl_process_dict.h | 4 +-- 2 files changed, 31 insertions(+), 23 deletions(-) (limited to 'erts') 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 */ diff --git a/erts/emulator/beam/erl_process_dict.h b/erts/emulator/beam/erl_process_dict.h index fd59c969cf..f0d57da1e6 100644 --- a/erts/emulator/beam/erl_process_dict.h +++ b/erts/emulator/beam/erl_process_dict.h @@ -25,14 +25,14 @@ typedef struct proc_dict { unsigned int sizeMask; unsigned int size; - unsigned int homeSize; + unsigned int usedSlots; unsigned int splitPosition; Uint numElements; Eterm data[1]; /* The beginning of an array of erlang terms */ } ProcDict; #define ERTS_PD_START(PD) ((PD)->data) -#define ERTS_PD_SIZE(PD) ((PD)->homeSize + (PD)->splitPosition) +#define ERTS_PD_SIZE(PD) ((PD)->usedSlots) int erts_pd_set_initial_size(int size); Uint erts_dicts_mem_size(struct process *p); -- 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 +++++++++++++------------- erts/emulator/beam/erl_process_dict.h | 2 +- 2 files changed, 14 insertions(+), 14 deletions(-) (limited to 'erts') 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]; diff --git a/erts/emulator/beam/erl_process_dict.h b/erts/emulator/beam/erl_process_dict.h index f0d57da1e6..dac214c8a1 100644 --- a/erts/emulator/beam/erl_process_dict.h +++ b/erts/emulator/beam/erl_process_dict.h @@ -24,8 +24,8 @@ typedef struct proc_dict { unsigned int sizeMask; - unsigned int size; unsigned int usedSlots; + unsigned int arraySize; unsigned int splitPosition; Uint numElements; Eterm data[1]; /* The beginning of an array of erlang terms */ -- cgit v1.2.3 From 46a1a3b8c8819a117d7f48a864d8e0f5e08ac548 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 14 Dec 2015 20:02:54 +0100 Subject: erts: Add 'fill_heap' to erts_debug:state_internal_state to make it easy to provoke GC inside/after a BIF or instruction. --- erts/emulator/beam/erl_bif_info.c | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'erts') diff --git a/erts/emulator/beam/erl_bif_info.c b/erts/emulator/beam/erl_bif_info.c index b44382cde8..caa1cb7608 100644 --- a/erts/emulator/beam/erl_bif_info.c +++ b/erts/emulator/beam/erl_bif_info.c @@ -4085,6 +4085,17 @@ BIF_RETTYPE erts_debug_set_internal_state_2(BIF_ALIST_2) BIF_RET(am_ok); } } + else if (ERTS_IS_ATOM_STR("fill_heap", BIF_ARG_1)) { + UWord left = HeapWordsLeft(BIF_P); + if (left > 1) { + Eterm* hp = HAlloc(BIF_P, left); + *hp = make_pos_bignum_header(left - 1); + } + if (BIF_ARG_2 == am_true) { + FLAGS(BIF_P) |= F_NEED_FULLSWEEP; + } + BIF_RET(am_ok); + } } BIF_ERROR(BIF_P, BADARG); -- cgit v1.2.3