Message276921
The dictresize() method unnecessarily copies the keys, values, and hashes as well as making insertions in the index table. Only the latter step is necessary or desirable.
Here in the pure Python code for resizing taking from the original proof-of-concept code at https://code.activestate.com/recipes/578375
def _resize(self, n):
'''Reindex the existing hash/key/value entries.
Entries do not get moved, they only get new indices.
No calls are made to hash() or __eq__().
'''
n = 2 ** n.bit_length() # round-up to power-of-two
self.indices = self._make_index(n)
for index, hashvalue in enumerate(self.hashlist):
for i in Dict._gen_probes(hashvalue, n-1):
if self.indices[i] == FREE:
break
self.indices[i] = index
self.filled = self.used
And here is a rough sketch of what it would look like in the C code (very rough, not yet compileable):
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;
}
/* Resize and zero-out the indices array */
realloc(dk->dk_indices, es * newsize);
memset(&dk->dk_indices.as_1[0], 0xff, es * size);
dk->dk_size = size;
/* Loop over hashes, skipping NULLs, inserting new indices */
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;
} |
|
Date |
User |
Action |
Args |
2016-09-18 22:13:49 | rhettinger | set | recipients:
+ rhettinger, methane, serhiy.storchaka |
2016-09-18 22:13:49 | rhettinger | set | messageid: <1474236829.43.0.744002065698.issue28199@psf.upfronthosting.co.za> |
2016-09-18 22:13:49 | rhettinger | link | issue28199 messages |
2016-09-18 22:13:49 | rhettinger | create | |
|