Re^2: Circular buffer

The Perl version is also very fast - not as fast as C, but much easier to write!

No, it's practically exactly the same, op for op.

So to implement a FIFO queue in Perl, just push new entries onto the bottom of the Perl array and shift out "oldest" entries from the top.

A circular buffer is a queue (FIFO), but a queue is not necessarily a circular buffer. You didn't provide any indication as to whether the code you posted is a suitable solution for the OP or not.

It turns out the code you (and I) posted does exhibit the same characteristics as a circular buffer. See my reply.

The Perl array also can implement essentially the equivalent of a 'C' doubly linked list. [...] But in Perl you can use splice()

If you can use splice, you don't have a linked list. Linked lists take O(1) to remove a previously found element. splice takes O(N).

Comment on Re^2: Circular buffer Download Code

Replies are listed 'Best First'.
Re^3: Circular buffer by Marshall (Canon) on Mar 21, 2011 at 05:56 UTC
The more I learn about Perl, the more impressed I become with the performance. Perl codes at about a 3x-5x and sometimes 10x efficiency in terms of source lines vs 'C'. From what I can see, great Perl code runs like 1/3 the speed of average 'C' code which given the coding efficiency is just fine - actually Great! I have become a fan of Perl. I am curious as to the implementation of splice() in Perl. Does a splice() really result in a copy of an entire array, like a typical 'C' realloc()? If a Perl array has say 1,000 elements and I do an "insert" after element 2, how does the low level Perl deal with this? Does it really do 1,000+ operations? How does Perl handle the push or unshift operations?	[reply]
Re^4: Circular buffer by ikegami (Patriarch) on Mar 21, 2011 at 15:52 UTC
Perl uses a flat array (`SV*[]`) for arrays. It over-allocates, and it keeps track of where the visible array starts and end. In your example, if there's at least one extra spare element at the end of the underlying array, it will move the pointers at indexes 3..999 to indexes 4..1000. I expect this to be a really fast memcpy. The new element is then assigned. If there isn't any free room, Perl allocates a new array roughly twice its old size and copies everything over. `push` works the same way, but keep in mind there will usually be extra spare elements to push into. `unshift` is the same as well. Perl leaves spare elements at the start of the array. The catch is that it starts with no spare elements and any reallocation of the array that isn't caused by unshift will remove the spare elements.	[reply] [d/l] [select]