Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Perl hash and rehash seeds; deterministic hash ordering

Reply
Thread Tools

Perl hash and rehash seeds; deterministic hash ordering

 
 
ozgune@gmail.com
Guest
Posts: n/a
 
      01-19-2007
Hi -

I just upgraded to Perl 5.8.6, and am evaluating the effect of random
hash ordering on my systems. Surprisingly, I seem *unaffected* by Perl
hash seeds (The following is a RHEL 3 box).

% perl -v
This is perl, v5.8.6 built for Linux-2.4c2.3-i686-64int

% perl -le '@a="a".."z";@a{@a}=();print keys %a'
HASH_SEED = 10308426221955932222
wraxdjyukhgftienvmslcpqbzo

% perl -le '@a="a".."z";@a{@a}=();print keys %a'
HASH_SEED = 2190859344420079461
wraxdjyukhgftienvmslcpqbzo

I tried this on a Fedora 3 box (5.8.6), and got the same behavior. On
OSX, the ordering is random as expected.

Looking into the source a little deeper, I see two different hash seeds
and two hash functions: PL_hash_seed (used by PERL_HASH) and
PL_rehash_seed (used by PERL_HASH_INTERNAL). PL_rehash_seed is
initialized in perl.c, but PL_hash_seed isn't.

"hv.c" seems to be calling PERL_HASH which relies on the uninitialized
seed. I added some printfs to the code, and ran perl:

% ./perl5.8.8 -le '@a="a".."z";@a{@a}=();print keys %a'
PL_hash_seed = 0
PL_rehash_seed = 17891139134198775779
IN HASH (NOT INTERNAL): PL_hash_seed = 0
IN HASH (NOT INTERNAL): PL_hash_seed = 0
..........
wraxdjyukhgftienvmslcpqbzo


Why are there two different hash seeds and hash functions? How can I
know for sure which one is going to be called?

Thanks,

Ozgun.

 
Reply With Quote
 
 
 
 
Mumia W. (NOSPAM)
Guest
Posts: n/a
 
      01-20-2007
On 01/19/2007 04:01 PM, http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:
> Hi -
>
> I just upgraded to Perl 5.8.6, and am evaluating the effect of random
> hash ordering on my systems. Surprisingly, I seem *unaffected* by Perl
> hash seeds (The following is a RHEL 3 box).
>
> % perl -v
> This is perl, v5.8.6 built for Linux-2.4c2.3-i686-64int
>
> % perl -le '@a="a".."z";@a{@a}=();print keys %a'
> HASH_SEED = 10308426221955932222
> wraxdjyukhgftienvmslcpqbzo
>
> % perl -le '@a="a".."z";@a{@a}=();print keys %a'
> HASH_SEED = 2190859344420079461
> wraxdjyukhgftienvmslcpqbzo
> [...]


FWIW, I'm getting the same behavior on Debian 3.1 i386 and Perl 5.9.4.


--
Windows Vista and your freedom in conflict:
http://www.regdeveloper.co.uk/2006/1...eula_analysis/
 
Reply With Quote
 
 
 
 
ozgune@gmail.com
Guest
Posts: n/a
 
      01-20-2007
Any ideas if there is a better group to post this?

From
http://www.xray.mpe.mpg.de/mailing-l.../msg00584.html
on DoS attacks:

>> The neat effect is that now this:


../perl -le '@a="a".."z";@a{@a}=();print keys %a'

gives a different result for each run. That _really_ should teach
people
not to expect any particular ordering of hash keys...

On our systems however:

% perl -le '@a="a".."z";@a{@a}=();print keys %a'
wraxdjyukhgftienvmslcpqbzo

% perl -le '@a="a".."z";@a{@a}=();print keys %a'
wraxdjyukhgftienvmslcpqbzo


(E-Mail Removed) wrote:
> Hi -
>
> I just upgraded to Perl 5.8.6, and am evaluating the effect of random
> hash ordering on my systems. Surprisingly, I seem *unaffected* by Perl
> hash seeds (The following is a RHEL 3 box).
>
> % perl -v
> This is perl, v5.8.6 built for Linux-2.4c2.3-i686-64int
>
> % perl -le '@a="a".."z";@a{@a}=();print keys %a'
> HASH_SEED = 10308426221955932222
> wraxdjyukhgftienvmslcpqbzo
>
> % perl -le '@a="a".."z";@a{@a}=();print keys %a'
> HASH_SEED = 2190859344420079461
> wraxdjyukhgftienvmslcpqbzo
>
> I tried this on a Fedora 3 box (5.8.6), and got the same behavior. On
> OSX, the ordering is random as expected.
>
> Looking into the source a little deeper, I see two different hash seeds
> and two hash functions: PL_hash_seed (used by PERL_HASH) and
> PL_rehash_seed (used by PERL_HASH_INTERNAL). PL_rehash_seed is
> initialized in perl.c, but PL_hash_seed isn't.
>
> "hv.c" seems to be calling PERL_HASH which relies on the uninitialized
> seed. I added some printfs to the code, and ran perl:
>
> % ./perl5.8.8 -le '@a="a".."z";@a{@a}=();print keys %a'
> PL_hash_seed = 0
> PL_rehash_seed = 17891139134198775779
> IN HASH (NOT INTERNAL): PL_hash_seed = 0
> IN HASH (NOT INTERNAL): PL_hash_seed = 0
> .........
> wraxdjyukhgftienvmslcpqbzo
>
>
> Why are there two different hash seeds and hash functions? How can I
> know for sure which one is going to be called?
>
> Thanks,
>
> Ozgun.


 
Reply With Quote
 
Bo Lindbergh
Guest
Posts: n/a
 
      01-21-2007
There's a flag in each hash that controls whether the random or the
non-random hash seed is used. Hashes start out non-random and switch to
random if and when the hsplit function thinks it's a good idea. Search for
"Pathological data" in hv.c for the details.

/Bo Lindbergh
 
Reply With Quote
 
ozgune@gmail.com
Guest
Posts: n/a
 
      01-22-2007
Thanks, that clears it; I wrongfully thought the original post on the
issue (Patch #22371) cited the final implementation behavior.

In summary, Perl gives no guarantees about the ordering of an hash's
key value pairs, and documents this behavior. Perl 5.8.8's
implementation will give a deterministic order until the hash split
can't redistribute the entries evenly. (More specifically, after a
split, if the longest chain in the hash still has a lot of entries,
Perl switches to random seeds.)

Ozgun.

Bo Lindbergh wrote:
> There's a flag in each hash that controls whether the random or the
> non-random hash seed is used. Hashes start out non-random and switch to
> random if and when the hsplit function thinks it's a good idea. Search for
> "Pathological data" in hv.c for the details.
>
> /Bo Lindbergh


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash of hash of hash of hash in c++ rp C++ 1 11-10-2011 04:45 PM
Z-Ordering (Morton ordering) question nbigaouette C Programming 2 11-06-2009 05:26 AM
OS X and Python - wxPython has forced a rehash of my approach metaperl.etc@gmail.com Python 8 09-05-2006 02:43 PM
Deterministic destruction and RAII idioms in Python plahey@alumni.caltech.edu Python 9 02-05-2006 09:14 PM
Can I rehash during execution ? Andreas Habel Ruby 5 09-01-2003 05:01 PM



Advertisments