[Python-Dev] More compact dictionaries with faster iteration (original) (raw)

Maciej Fijalkowski fijall at gmail.com
Mon Jan 7 11:55:39 CET 2013

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

More information about the Python-Dev mailing list