PEP 372 -- Adding an ordered directory to collections

[dbpokorny at gmail.com]

On Jun 18, 3:15 pm, bearophileH... at lycos.com wrote:

> In Python 2.5 a dict(int:None) needs about 36.2 bytes/element. I am
> suggesting to add 2 pointers, to create a linked list, so it probably
> becomes (on 32 bit systems) about 44.2 bytes/pair.

PyDictEntry is
typedef struct {
        Py_ssize_t me_hash;
        PyObject *me_key;
        PyObject *me_value;
} PyDictEntry;

Which should be 12 bytes on a 32-bit machine. I thought the space for
growth factor for dicts was about 12% but it is really 100%. In any
case, a pair of lists will take up less space than a dict and a list.
Or the storage could be an array of PyDictEntrys (to cache the hash
values of the keys), an approach that is in some sense halfway between
the others.

There is one advantage of this last approach - I think the amount of
hacking on dictobject.c that would have to take place is minimal. In
fact it almost seems like you could get the desired result by setting
mp->ma_lookup to a new function (and keep most of the rest of the
methods as they are). This seems too easy though, so there might be a
catch.

David