I just tried it. Setting element 10000 of an array takes 0.35 MB more RAM than setting element 0 on perl 5.8.8 for OS X on Intel. So, there's a cost, although not a large one.

It could mark a range as empty without actually filling in each bucket.

Yes, and then you'd need a data structure to keep track of which ranges are empty. Wait, I got it! We'd use a hash to keep track which elements in the array are 'valid'! But then, you might as well use a hash to begin with.

Furthermore, it doesn't save any memory. Even if you don't initialize in the first 1000 elements if you do:

    my @array;
    $array[1000] = 1;
[download]

you still need to allocate space for 1001 pointers. Initialized or not.

I just tried it. Setting element 10000 of an array takes 0.35 MB more RAM than setting element 0 on perl 5.8.8 for OS X on Intel. So, there's a cost, although not a large one.

That's about 36 bytes/element. More that I expected. An undefined value takes 20 bytes in Perl. A pointer takes 4 bytes (32-bit platform). So, even if undefined values aren't shared, I'd expect less.

However, I cannot recreate this:

$ perl -MDevel::Size=:all -wE '$a[1] = 1; say total_size \@a'
148
$ perl -MDevel::Size=:all -wE '$a[10000] = 1; say total_size
\@a'
40136
[download]

which is a difference of about 40000 bytes, aka 10000 pointers. Replacing Devel::total_size with <c>`grep VmRSS /proc/$$/status` confirms the difference of 40000 bytes.

There are many ways to implement an array in C. You don't have to allocate pointers immediately for every bucket. It's irrelevant though, since Perl's implementation clearly does something that causes empty buckets to take up space.

40000 bytes is close enough to the 0.35 MB I saw that inaccuracies in measurement (I glanced at Apple's system monitor to check it) cover it. Looks like 5.10 has the same cost as 5.8.8.