[Israel.pm] preallocation of hash buckets or arrays

Yossi.Itzkovich at ecitele.com Yossi.Itzkovich at ecitele.com
Sat Mar 12 21:59:06 PST 2005






Shlomo,

That for your help.  The answer to question #2 is in the answer to #1:
"(This is similar to pre-extending an array by assigning a larger number to
$#array.)"

Thanks
Yossi





                                                                                                                                    
                      Yona Shlomo                                                                                                   
                      <yona at cs.technio         To:      Perl in Israel <perl at perl.org.il>                                           
                      n.ac.il>                 cc:                                                                                  
                      Sent by:                 Subject: Re: [Israel.pm] preallocation of hash buckets or arrays                     
                      perl-bounces at per                                                                                              
                      l.org.il                                                                                                      
                                                                                                                                    
                                                                                                                                    
                      03/13/2005 07:54                                                                                              
                      Please respond                                                                                                
                      to Perl in                                                                                                    
                      Israel                                                                                                        
                                                                                                                                    
                                                                                                                                    



On Sun, 13 Mar 2005 Yossi.Itzkovich at ecitele.com wrote:

> In YAPC::Israel::2003book I saw that Shlomo gave an example of
> preallocation of hash buckets:
>
> keys my %cache =@in;
>
> my questions:
> 1) I always thought that keys() returns a copy of the hash' keys.
According
> to the code above, itlooks like you can set the lnternal keys list. As it
> true ?

>From `perldoc -f keys`:

             As an lvalue "keys" allows you to increase the number of hash
             buckets allocated for the given hash.  This can gain you a
mea-
             sure of efficiency if you know the hash is going to get big.
             (This is similar to pre-extending an array by assigning a
             larger number to $#array.)  If you say

                keys %hash = 200;

             then %hash will have at least 200 buckets allocated for
it--256
             of them, in fact, since it rounds up to the next power of two.
             These buckets will be retained even if you do "%hash = ()",
use
             "undef %hash" if you want to free the storage while %hash is
             still in scope.  You can't shrink the number of buckets allo-
             cated for the hash using "keys" in this way (but you needn't
             worry about doing this by accident, as trying has no effect).

> 2) Does this trick work with normal arrays too ? What is the syntax
> (assuming I don't have such @in list as in the code above) ?

I can't recall anything but actually assignning to the list.

> 3) Is there any disadvantage of using this trick, assuming I know the
> minimal size of the hash/array ?

As it rounds the number of buckets to the next power of two,
if you need only 2^N+1 buckets, you will end up with 2^(N+1)
buckets allocated. This becomes worse and worse as N grows.
I don't remember what's the growth pattern for hashes
otherwise (i.e. not during initialization). Most probably,
other mongers can fill in the blanks.


--
Shlomo Yona
yona at cs.haifa.ac.il
http://yeda.cs.technion.ac.il/~yona/

_______________________________________________
Perl mailing list
Perl at perl.org.il
http://perl.org.il/mailman/listinfo/perl






More information about the Perl mailing list