There are many ways to implement an array in C.

Really? And for decades, I assumed there was just one way: just line up the elements of the array in consecutive memory locations.

And that's how Perl implements arrays as well. A sequence of pointers to SVs in consecutive memory locations. Each pointer taking 4 (32-bit platform) or 8 (64-bit platform) bytes.

You don't have to allocate pointers immediately for every bucket.

Not quite sure what you mean by 'allocate pointers'. But even if you don't initialize the array elements (which in the Perl cause would mean, not fill the slot with a pointer to an SV - but note that since Perl doesn't keep track of which pointers are valid and which aren't, it has to), you still have to allocate memory for it. To get to $a[10000] fast, Perl will use the pointer found 40000 (80000 on 64-bit platforms) from the start of the array.