[Python-Dev] More compact dictionaries with faster iteration

[Maciej Fijalkowski]

On Sun, Jan 6, 2013 at 11:40 PM, Kristján Valur Jónsson
<kristjan at ccpgames.com> wrote:
> The memory part is also why I am interested in this approach.
> Another thing has been bothering me.  This is the fact that with the default implementation, the smll table is only ever populated up to a certain percentage, I cant recall, perhaps 50%.  Since the small table is small by definition, I think it ought to be worth investigating if we cannot allow it to fill to 100% before growing, even if it costs some collisions.  A linear lookup in a handful of slots can't be that much of a bother, it is only with larger number of entries that the O(1) property starts to matter.
> K

If you're very interested in the memory footprint you should do what
PyPy does. It gives you no speed benefits without the JIT, but it
makes all the instances behave like they are having slots. The trick
is to keep a dictionary name -> index into a list on a class (you go
through hierarchy of such dicts as you add or remove attributes) and a
list of attributes on the instance.

We call it maps, V8 calls it hidden classes, it's well documented on
the pypy blog.

Cheers,
fijal