[Python-Dev] More compact dictionaries with faster iteration

[PJ Eby]

On Wed, Dec 12, 2012 at 3:37 PM, Dag Sverre Seljebotn
<d.s.seljebotn at astro.uio.no> wrote:
> On 12/12/2012 01:15 AM, Nick Coghlan wrote:
>>
>> On Wed, Dec 12, 2012 at 5:37 AM, Dino Viehland <dinov at microsoft.com
>> <mailto:dinov at microsoft.com>> wrote:
>>
>>     OTOH changing certain dictionaries in IronPython (such as keyword
>>     args) to be
>>     ordered would certainly be possible.  Personally I just wouldn't
>>     want to see it
>>     be the default as that seems like unnecessary overhead when the
>>     specialized
>>     class exists.
>>
>>
>> Which reminds me, I was going to note that one of the main gains with
>> ordered keyword arguments, is their use in the construction of
>> string-keyed objects where you want to be able to control the order of
>> iteration (e.g. for serialisation or display purposes). Currently you
>> have to go the path of something like namedtuple where you define the
>> order of iteration in one operation, and set the values in another.
>
>
> So here's a brand new argument against ordered dicts: The existence of
> perfect hashing schemes. They fundamentally conflict with ordered dicts.

If I understand your explanation, then they don't conflict with the
type of ordering described in this thread.  Raymond's optimization
separates the "hash table" part from the "contents" part of a
dictionary, and there is no requirement that these two parts be in the
same size or the same order.

Indeed, Raymond's split design lets you re-parameterize the hashing
all you want, without perturbing the iteration order at all.  You
would in fact be able to take a dictionary at any moment, and say,
"optimize the 'hash table' part to a non-colliding state based on the
current contents", without touching the 'contents' part at all.

(One could do this at class creation time on a class dictionary, and
just after importing on a module dictionary, for example.)