[Melbourne-pm] Timer::HiRes and alarms?

Sam Watkins sam at nipl.net
Thu Nov 11 18:06:57 PST 2010

On Fri, Nov 12, 2010 at 11:05:57AM +1100, Jacinta Richardson wrote:
> When you create an array in Perl, Perl creates a hunk of memory for it and
> puts the array in the middle.  If you unshift or push things onto the array
> they bring the start or end of the array closer to the boundaries of the
> memory Perl put aside for you.  If you get "too close" to either end, then
> Perl allocates twice as much space for you (as it did the first time) and
> copies your array into the middle of that.

That's interesting, I didn't know it worked like that.  I use a similar method
to grow vectors in C, but only at the 'push' end.  To 'unshift' I use it as a
circular buffer, using the empty space from both ends.  This makes indexing a
little more complex, but it's a bit more efficient with the space /
reallocations.  Once done growing it, I can 'squeeze' the vector / deque to
free up any wasted space.

The circular buffer code is useful in other cases, e.g. to implement a queue.
With the perl method as you described it, perl would have to reallocate the
array (or memmove its elements) while using it as queue, even if the total size
of the queue was not increasing.

I was thinking a bit about how to create a data structure that would be very
efficient for insertions / deletions at any point, and also for random access.
Maybe a hybrid tree of arrays (or tree of deques), where the user could balance
insert performance against compactness and random-access speed, and call a
'squeeze' or 'flatten' function to squash it into a simple array / deque.  This
could be useful.  It sounds a bit complex, but I guess could be implemented
fairly simply.


More information about the Melbourne-pm mailing list