Default ordering of Hash keys

Lucian Branescu lucian.branescu at
Wed Aug 10 09:59:25 UTC 2011

fwiw, Armin Rigo had a patch to add dict mangling behaviour in
CPython, in order to help spot dict order dependencies.

lines like
    i = (size_t)hash & mask;
get indices.

Armin replaced those with
    i = (size_t) MANGLE_HASH(hash) & mask;
    #define MANGLE_HASH(h)  ((h) ^ 1291)

This isn't random, but it does make dict order a lot less predictable,
which is often enough to spot order dependencies.

On 9 August 2011 23:40, Martin D Kealey <martin at> wrote:
> On Mon, 8 Aug 2011, Luben Karavelov wrote:
>> For some types of keys (that have zero/NULL as valid value, i.e.
>> integer, ptr, cstring) parrot iterates keys in index order, not
>> ordered by creation.
>> For the rest of key types it iterates them in memory order, that is
>> the same as create order, if there were no key deleted. This is faster
>> because it has less computation and a lot less data cache fails,
>> especially with big hashes.
>> The change arround 2.9 was part of optimization of parrot hashes done
>> by me and chromatic. We were optimizing for the common case that is
>> having String hash keys.
> I suggest that pseudo-randomness would be worth retaining in order to
> prevent order dependencies from occurring in future code.
> To implement it, and yet remain efficient, it would suffice to return the
> keys in some simple function of storage order; say, reverse storage order,
> or perhaps still in storage order, but not starting at the lowest memory
> location; along the lines of
>        ( $RandomOffset .. $#HashBackingArray, 0 .. $RandomOffset-1 )
> Or even just permuting the bottom few bits of the index:
>        ( 0 .. ($#HashBackingArray .| 7) ) . map { $_ .^ 5 }
> -Martin
> _______________________________________________

More information about the parrot-dev mailing list