[Python-Dev] More compact dictionaries with faster iteration

[Maciej Fijalkowski]

On Wed, Dec 31, 2014 at 3:12 PM, Serhiy Storchaka <storchaka at gmail.com> wrote:
> On 10.12.12 03:44, Raymond Hettinger wrote:
>>
>> The current memory layout for dictionaries is
>> unnecessarily inefficient.  It has a sparse table of
>> 24-byte entries containing the hash value, key pointer,
>> and value pointer.
>>
>> Instead, the 24-byte entries should be stored in a
>> dense table referenced by a sparse table of indices.
>
>
> FYI PHP 7 will use this technique [1]. In conjunction with other
> optimizations this will decrease memory consumption of PHP hashtables up to
> 4 times.

"up to 4 times" is a bit of a stretch, given that most of their
savings come from:

* saving on the keeping of ordering
* other optimizations in zval

None of it applies to python

PHP does not implement differing sizes of ints in key dict, which
makes memory saving php-only (if we did the same thing as PHP, we
would save more or less nothing, depending on how greedy you are with
the list overallocation)

We implemented the same strategy in PyPy as of last year, testing it
to become a default "dict" and "OrderedDict" for PyPy in the next
release.

Cheers,
fijal

PS. I wonder who came up with the idea first, PHP or rhettinger and
who implemented it first (I'm pretty sure it was used in hippy before
it was used in Zend PHP)