[Israel.pm] preallocation of hash buckets or arrays

Yona Shlomo yona at cs.technion.ac.il
Sat Mar 12 21:54:56 PST 2005

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

More information about the Perl mailing list