[Israel.pm] preallocation of hash buckets or arrays

[Yona Shlomo]

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/