scmno****@osdn*****
scmno****@osdn*****
Thu Jun 7 05:27:26 JST 2018
changeset 5a8261f71055 in quipu/quipu details: http://hg.osdn.jp/view/quipu/quipu?cmd=changeset;node=5a8261f71055 user: Agustina Arzille <avarz****@riseu*****> date: Wed Jun 06 17:27:16 2018 -0300 description: Improve table implementation diffstat: table.cpp | 145 ++++++++++++++++++++++++++----------------------------------- table.h | 1 - 2 files changed, 61 insertions(+), 85 deletions(-) diffs (truncated from 329 to 300 lines): diff -r 41f759fb7070 -r 5a8261f71055 table.cpp --- a/table.cpp Mon Jun 04 16:34:44 2018 -0300 +++ b/table.cpp Wed Jun 06 17:27:16 2018 -0300 @@ -28,7 +28,7 @@ } static inline object& -tabvec_pad (array *vecp) +tabvec_pidx (array *vecp) { return (vecp->data[3]); } @@ -48,9 +48,6 @@ "table entries must be correctly aligned for double atomic CAS"); #endif -static const uint32_t SECONDARY_KEYS[] = { 3, 5, 7, 11, 13, 17, 19, 23 }; -static const int N_SECONDARY_KEYS = QP_NELEM (SECONDARY_KEYS); - static inline bool table_equal (interpreter *interp, const table *tp, object k1, object k2) @@ -75,37 +72,34 @@ return ((uint32_t)as_int (interp->retval)); } -static uint32_t -table_size (uint32_t isz) +static const uint32_t SECONDARY_KEYS[] = { 2, 3, 5, 7 }; +static const int N_SECONDARY_KEYS = QP_NELEM (SECONDARY_KEYS); + +static const uint32_t PRIMES[] = { - if (isz <= SECONDARY_KEYS[N_SECONDARY_KEYS - 1]) - return (SECONDARY_KEYS[N_SECONDARY_KEYS - 1]); - else - for (isz |= 1 ; ; isz += 2) - { /* Return a size that is prime to all secondary - * keys (relatively speaking, at least). */ - for (int i = 0; i < N_SECONDARY_KEYS; ++i) - if (isz % SECONDARY_KEYS[i] == 0) - goto next; - - return (isz); - next: ; - } -} + 0xb, 0x25, 0x71, 0x15b, 0x419, 0xc4d, 0x24f5, 0x6ee3, 0x14cb3, 0x3e61d, + 0xbb259, 0x23170f, 0x694531, 0x13bcf95, 0x3b36ec3, 0xb1a4c4b, 0x214ee4e3, + 0x63ecaead +}; static int -compute_hsize (uint32_t size, float mv_size, - float mv_ratio, int *vsizep) +compute_hsize (uint32_t min_size, float mv_ratio, int *idxp) { - uint32_t tmp = (uint32_t)(mv_size * size + 0.5f); - uint32_t nsize = max (30u, tmp); - - if (nsize < size) - nsize = size + 1; // Hopefully this doesn't happen. - - *vsizep = (int)table_size (max (nsize + 2, - (uint32_t)(0.5f + mv_ratio * nsize))); - return ((int)nsize); + int i1 = 0, i2 = QP_NELEM (PRIMES), cnt = i2 - i1; + while (cnt > 0) + { + int step = cnt >> 1; + if (PRIMES[step] < min_size) + { + i1 = step; + cnt -= step + 1; + } + else + cnt = step; + } + + *idxp = i1; + return ((int)(PRIMES[i1] * mv_ratio)); } // Special values used by the table implementation. @@ -117,9 +111,9 @@ "FREE_HASH and DELETED_KEY must not be equal"); static array* -make_tabvec (interpreter *interp, uint32_t size) +make_tabvec (interpreter *interp, int prime_idx) { - uint32_t tsize = tabvec_idx (size); + uint32_t size = PRIMES[prime_idx], tsize = tabvec_idx (size); #ifdef QP_HAS_ATOMIC_CASX array *ret = as_array (alloc_array (interp, tsize + 1, FREE_HASH)); @@ -132,10 +126,10 @@ array *ret = as_array (alloc_array (interp, tsize, FREE_HASH)); #endif - tabvec_tab(ret) = intobj (0); // Will be set later. + tabvec_tab(ret) = intobj (0); tabvec_size(ret) = intobj (size); - tabvec_cnt(ret) = intobj (0); - tabvec_pad(ret) = intobj (0); // Not used for now. + tabvec_cnt(ret) = intobj (0); + tabvec_pidx(ret) = intobj (prime_idx); return (ret); } @@ -145,16 +139,16 @@ object tst, object hashfn) { evh_guard eg (interp); - int tsize, gt = compute_hsize (size ? size - 1 : 1, 1.0f, 0.85f, &tsize); + float mv_ratio = 0.85f; + int pidx, gt = compute_hsize (0, mv_ratio, &pidx); table *ret = (table *)alloch (sizeof (*ret), typecode::TABLE); - array *vec = make_tabvec (interp, tsize); + array *vec = make_tabvec (interp, pidx); lwlock_init (&ret->lock); - ret->mv_size = 1.5f; ret->cmpfct = tst == NIL ? UNBOUND : tst; ret->hashfct = hashfn == NIL ? UNBOUND : hashfn; ret->grow_limit = gt; - ret->mv_ratio = 0.85f; + ret->mv_ratio = mv_ratio; ret->vector = interp->alval; interp->alval = tabvec_tab (vec) = ret->as_obj (); gcregister (interp, ret); @@ -235,7 +229,7 @@ array *vecp, object key) { /* Same as above, only this function is called when migrating, which means - * it'll never return failure, and it can also reuse deleted entries. */ + * it cannot return failure. */ uint32_t hashcode = table_hash (interp, tp, key); int entries = as_int (tabvec_size (vecp)); int idx = (int)(hashcode % entries); @@ -263,12 +257,9 @@ table_migrate_lk (interpreter *interp, table *tp) { array *oldvp = as_array (tp->vector); - int i, cnt = as_int (tabvec_size (oldvp)); - int vsize, gt = compute_hsize (cnt * 2, - tp->mv_size, tp->mv_ratio, &vsize); - array *newvp = make_tabvec (interp, vsize); + array *newvp = make_tabvec (interp, as_int (tabvec_pidx (oldvp)) + 1); - for (i = tabvec_idx (0); i < oldvp->len; i += 2) + for (int i = tabvec_idx (0); i < oldvp->len; i += 2) { int new_idx; @@ -280,7 +271,9 @@ newvp->data[new_idx + 1] = oldvp->data[i + 1]; } - tp->grow_limit = gt - as_int (tabvec_cnt (oldvp)); + tp->grow_limit = (atomic_t)(tp->mv_ratio * + as_int (tabvec_size (newvp)) - as_int (tabvec_cnt (oldvp))); + tabvec_cnt(newvp) = tabvec_cnt (oldvp); tabvec_tab(newvp) = tp->as_obj (); tp->vector = newvp->as_obj (); @@ -320,27 +313,23 @@ if (tp->grow_limit <= 0) { array *oldvp = as_array (tp->vector); - int cnt = as_int (tabvec_size (oldvp)); - int vsize, gt = compute_hsize (cnt * 2, - tp->mv_size, tp->mv_ratio, &vsize); - array *newvp = make_tabvec (interp, vsize); + array *newvp = make_tabvec (interp, as_int (tabvec_pidx (oldvp)) + 1); int nelem = 0; - valref tmp (interp, intobj (0)); g.set_vec (oldvp); for (int i = tabvec_idx (0); i < oldvp->len; i += 2) { object key = oldvp->data[i]; - *tmp = atomic_or ((atomic_t *)&oldvp->data[i + 1], EXTRA_BIT); + object val = atomic_or ((atomic_t *)&oldvp->data[i + 1], EXTRA_BIT); /* No other thread can be migrating the table at this point, * so it's safe to do a simplified test here. */ - if (valid_key_p (key) && *tmp != DELETED_VAL && *tmp != FREE_HASH) + if (valid_key_p (key) && val != DELETED_VAL && val != FREE_HASH) { int new_idx = growtab_probe (interp, tp, newvp, key); newvp->data[new_idx + 0] = key; - newvp->data[new_idx + 1] = *tmp; + newvp->data[new_idx + 1] = val; ++nelem; } } @@ -350,7 +339,9 @@ // Set up the new table. tabvec_cnt(newvp) = intobj (nelem); tabvec_tab(newvp) = tp->as_obj (); - tp->grow_limit = gt - nelem; + tp->grow_limit = (atomic_t)(tp->mv_ratio * + as_int (tabvec_size (newvp))) - nelem; + atomic_mfence_rel (); /* At this point, another thread may decrement the growth limit from * the wrong table vector. That's fine, it just means we'll have to * migrate sooner than necessary. */ @@ -368,15 +359,12 @@ array *vecp = as_array (interp->aux); int idx = table_probe (interp, tp, key, false); - if (qp_unlikely (vecp != as_array (tp->vector))) - continue; - else if (idx < 0) + if (idx < 0) return (dfl); - else + else if (qp_likely (vecp == as_array (tp->vector))) { - interp->aux = vecp->data[idx + 1] & ~EXTRA_BIT; - return (interp->aux == DELETED_VAL || - interp->aux == FREE_HASH ? dfl : interp->aux); + object ret = vecp->data[idx + 1] & ~EXTRA_BIT; + return (ret == DELETED_VAL || ret == FREE_HASH ? dfl : ret); } } } @@ -480,7 +468,7 @@ if (empty) { - if (tp->grow_limit <= 0) + if (--tp->grow_limit <= 0) { table_migrate_lk (interp, tp); idx = table_probe (interp, tp, key, true); @@ -488,7 +476,6 @@ } vecp->data[idx] = key; - --tp->grow_limit; tabvec_cnt(vecp) += intobj (1); } @@ -521,8 +508,6 @@ atomic_add (&tp->grow_limit, -1); #ifdef QP_ATOMIC_HAS_CASX - /* Make sure the key and value pairs are passed in - * the right order, depending on endianness. */ if (atomic_casx (&vecp->data[idx], FREE_HASH, FREE_HASH, # if QP_LITTLE_ENDIAN key, val @@ -544,10 +529,9 @@ } else { - interp->aux = vecp->data[idx + 1]; - if (interp->aux != DELETED_VAL && interp->aux != FREE_HASH && - (interp->aux & EXTRA_BIT) == 0 && - setv_cond (vecp, idx, interp->aux, val)) + object tmp = vecp->data[idx + 1]; + if (tmp != DELETED_VAL && tmp != FREE_HASH && + (tmp & EXTRA_BIT) == 0 && setv_cond (vecp, idx, tmp, val)) return (empty); continue; @@ -572,12 +556,10 @@ static void table_clr_lk (interpreter *interp, table *tp) { - int vsize, gt = compute_hsize (1, - tp->mv_size, tp->mv_ratio, &vsize); - array *vecp = make_tabvec (interp, vsize); + array *vecp = make_tabvec (interp, 0); tabvec_tab(vecp) = tp->as_obj (); - tp->grow_limit = gt; + tp->grow_limit = (atomic_t)(tp->mv_ratio * tabvec_size (vecp)); tp->vector = vecp->as_obj (); } @@ -585,8 +567,7 @@ table_clr_mt (interpreter *interp, table *tp) { array *vecp = as_array (tp->vector); - int vsize, gt = compute_hsize (1, tp->mv_size, tp->mv_ratio, &vsize); - array *np = make_tabvec (interp, vsize); + array *np = make_tabvec (interp, 0); lwlock_guard g (&tp->lock); // Prevent any further insertions. @@ -607,7 +588,8 @@ #endif tabvec_tab(np) = tp->as_obj (); - tp->grow_limit = gt; + tp->grow_limit = (atomic_t)(tp->mv_ratio * tabvec_size (vecp));
Fork