Re: Circular buffer

A circular buffer is one way in languages like C to implement typically a FIFO (First In First Out) queue.
Typically a fixed size hunk of memory is allocated and two pointers "chase" each other, the input and the output pointers. The C version involves pointer arithmetic and is a little complicated in the details, but is extremely performant. The Perl version is also very fast - not as fast as C, but much easier to write!

In Perl, a Perl array can be used to implement a FIFO buffer. A Perl array is different from arrays in C or other programming language's ideas of arrays in that it can change size. 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. The size of the Perl array (and the indicies) will adjust themselves without you having to "move" anything. For the idea, this code is untested, but I figure should work...

my @fifo;
my $MAX_FIFO = 53; #max size is optional

sub add_entry
{
   die "Cicular buffer overflow\n" if (@fifo >= $MAX_FIFO);
   my $entry = shift;  #well, $_[0] is ok for syntax too
                       #but I think this is more clear
                       #these simple assignment statements are 
                       #  not "expensive"
   push @fifo, $entry; 
}

sub get_entry
{
   return (shift @fifo);
}
[download]

The Perl array also can implement essentially the equivalent of a 'C' doubly linked list. In Perl, this is an array of pointer to hash (an Array of Hash). In C this might be an array of struct and you couldn't change it without a lot of hassle or a linked list where you have to adjust many forward and backward pointers. But in Perl you can use splice() to insert or delete something from the middle of the array (or linked list 'C' analog)! WOW!

get_entry() above could be modified to "die" if the @fifo is empty. There are lots of other possibilities. I advise the OP to study the Perl functions: push, pop, shift, unshift and splice.

Comment on Re: Circular buffer Download Code

Replies are listed 'Best First'.
Re^2: Circular buffer by ikegami (Patriarch) on Mar 21, 2011 at 03:11 UTC
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).	[reply] [d/l]
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]