[Python-Dev] More compact dictionaries with faster iteration

[Mark Shannon]

On 07/01/13 10:55, Maciej Fijalkowski wrote:
> 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

In 3.3 dicts no longer have a small table.
>
> 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.

They are called shared keys in CPython 3.3 :)

>
> Cheers,
> fijal
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> http://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/mark%40hotpy.org
>