[Python-Dev] More compact dictionaries with faster iteration

[Kristján Valur Jónsson]

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

________________________________________
Frá: Python-Dev [python-dev-bounces+kristjan=ccpgames.com at python.org] fyrir hönd Maciej Fijalkowski [fijall at gmail.com]
Sent: 5. janúar 2013 21:03
To: Antoine Pitrou
Cc: <python-dev at python.org>
Efni: Re: [Python-Dev] More compact dictionaries with faster iteration

On Sat, Jan 5, 2013 at 1:34 AM, Antoine Pitrou <solipsis at pitrou.net> wrote:
> On Thu, 3 Jan 2013 12:22:27 +0200
> Maciej Fijalkowski <fijall at gmail.com> wrote:
>> Hello everyone.
>>
>> Thanks raymond for writing down a pure python version ;-)
>>
>> I did an initial port to RPython for experiments. The results (on
>> large dicts only) are inconclusive - it's either a bit faster or a bit
>> slower, depending what exactly you do. There is a possibility I messed
>> something up too (there is a branch rdict-experiments in PyPy, in a
>> very sorry state though).
>
> But what about the memory consumption? This seems to be the main point
> of Raymond's proposal.
>

Er. The memory consumption can be measured on pen and paper, you don't
actually need to see right?

After a lot more experimentation I came up with something that behaves
better for large dictionaries. This was for a long time a weak point
of PyPy, because of some GC details. So I guess I'll try to implement
it fully and see how it goes. Stay tuned, I'll keep you posted.

PS. PyPy does not have lots of small dictionaries because of maps (so
you don't have a dict per instance), hence their performance is not at
all that interesting for PyPy.

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/kristjan%40ccpgames.com