[issue28183] Clean up and speed up dict iteration

[Raymond Hettinger]

Raymond Hettinger added the comment:

Here is a rough (very rough and not compileable) sketch of the direction that resizing should take:

static void
insert_indices_clean(PyDictObject *mp, Py_hash_t hash)
{
    size_t i, perturb;
    PyDictKeysObject *k = mp->ma_keys;
    size_t mask = (size_t)DK_SIZE(k)-1;

    i = hash & mask;
    for (perturb = hash; dk_get_index(k, i) != DKIX_EMPTY;
         perturb >>= PERTURB_SHIFT) {
	i = mask & ((i << 2) + i + perturb + 1);
    }
    dk_set_index(k, i, k->dk_nentries);
}

static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
    Py_ssize_t i, newsize;
    PyDictKeyEntry *ep0;

    /* Find the smallest table size > minused. */
    for (newsize = PyDict_MINSIZE;
         newsize <= minused && newsize > 0;
         newsize <<= 1)
        ;
    if (newsize <= 0) {
        PyErr_NoMemory();
        return -1;
    }

    realloc(dk->dk_indicies, es * newsize);
    memset(&dk->dk_indices.as_1[0], 0xff, es * size);
    dk->dk_size = size;

    for (i = 0; i < mp->dk_nentries; i++) {
        PyDictKeyEntry *ep = &ep0[i];
        if (ep->me_value != NULL) {
            insert_indices_clean(mp, ep->me_hash);
        }
    }
    return 0;
}

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue28183>
_______________________________________