How are arrays implemented in Perl?

Question

The Perl array is an abstract data type. What's the internal mechanism for the Perl array? Is it implemented with dynamic array or linked list? Since the array elements have random access, I would assume a dynamic array of pointers, or references to scalars make sense. However, with shift and unshift operation at the head of array, would the array have to move all its elements with these operations? sound inefficient to me. Any thought?

Extreme

Answer 1

Have a look at this: http://www.perlmonks.org/?node_id=17890

(taken from there:)

Perl implements lists with an array and first/last element offsets. The array is allocated larger than needed with the offsets originally pointing in the middle of the array so there is room to grow in both directions (unshifts and pushes/inserts) before a re-allocation of the underlying array is necessary. The consequence of this implementation is that all of perl's primitive list operators (insertion, fetching, determining array size, push, pop, shift, unshift, etc.) perform in O(1) time.

Durance

Thanks for the link. It answers my question. – Extreme

Re "the offsets originally pointing in the middle of the array so there is room to grow in both directions", This part isn't true. The array isn't initially offset. perl -MDevel::Peek -e'my @a = "x".."z"; Dump(@a, 0); shift @a; Dump(@a, 0);' (Pay attention to ARRAY/ALLOC). – Panther

Re "The array is allocated larger than needed", Not always. The array could start with no overallocation, but it does overallocate when the array is grown. (perl -MDevel::Peek -e'my @a = 0..7; Dump(@a, 0);' shows an array that starts with no overallocation.) – Panther

Answer 2

The types are documented in the perlguts (see Perl Internals for related documentation) - and are AV for arrays and HV for hashes.

Diaphysis