Talk:Circular buffer

The C implementation is wrong

Try putting 1..N, followed by getting 1..N times, then try putting, where the buffer is empty shows it is full. — Preceding unsigned comment added by 4ureyz (talk • contribs) 18:18, 25 November 2023 (UTC)

yes it is wrong - the simplest way is to track head,len instead of head and tail; if using head and tail then you must use unsigned int and never wrap them (modulo on access instead of storing modulo version) Laurent Demailly (talk) 17:09, 27 June 2024 (UTC)

IsFull function is incorrect

The template queue's IsFull function is incorrect. Notice it is identical to IsEmpty(), only advancing the tail before doing a check. Consider: Q::Resize(2); Q::Enqueue(T); Q::Enqueue(T); The second enqueue will throw as IsFull reports true (tail=1, +1 & mask = head == true) — Preceding unsigned comment added by 98.232.107.82 (talk) 23:09, 12 June 2011 (UTC)

history

When was the ring buffer invented or first publicly discussed or first mentioned in an academic paper or first used in an actual operating system? 209.252.104.131 (talk) 10:47, 16 March 2008 (UTC) ring buffer has been invented by Alblas Hans (pe1ayx) publicly made in 1993-1995 in linux kernel source tree in /drivers/char/scc.c under the name buffer pool concept and ring buffer chain. copyricht by none gnu use —Preceding unsigned comment added by 83.101.55.202 (talk) 15:35, 3 October 2010 (UTC)

Ringbuffers did exist before Linux. The keyboard buffer of a IBM PC is a ringbuffer as well with either 14 or 16 bytes in size (don't remember the actual size) and when it's full the speaker beeps to indicate this.--91.34.84.81 (talk) 22:24, 3 December 2014 (UTC)

I have code written in 1983 that uses them and calls them "rings", and I suspect that they are *much* older than that, but I don't have time to investigate. Vincent J. Lipsio (talk) 23:02, 3 December 2014 (UTC)

Here's a 1973 paper that discusses ring buffers. Without reference or claim of originality, which suggests they were common knowledge back then. QVVERTYVS (hm?) 15:35, 4 December 2014 (UTC)

Here's a video of a late 1950s patented German mechanical telephone equipment that functions very similarly to a circular buffer. The device stores telephone pulse signals in a circular ring and features a producer and consumer operating independently of one another. This suggests the idea and the use case of circular buffers was around even then. 115.134.249.202 (talk) 12:58, 20 November 2021 (UTC)

no mention of additional overheads

one still has to always check before a read or a write if the read pointer and a write pointer overlap.

this is never needed incase of a simple write ->read->write buffer a simple write->read->write kind of buffer works sequentially and simply does not let one write to the buffer is someone has not read what is already written because it assumes buffer_size=max message size and simply keeps check of whether the buffer is read or not.

incoherence between 2 paragraphs

In Circular buffer mechanics paragraph, it says that the start pointer points to the start of valid data and the end pointer points to the end of valid data. So, in my understanding, and according to the figures:

• 1 element buffer: start = end
• Full buffer: start = (end+1)%size
• Free buffer: not defined since we have no "valid data", but we can suppose that start = end too.

In the following paragraph Difficulties, a full buffer is represented with start = end. This is the same for the free buffer. We can suppose that the rule is different in this paragraph: the start pointer points to the start of valid data and the end pointer points to the next element after the end of valid data (if any). If there is no valid data, start = end.

Did I miss something ? —Preceding unsigned comment added by 84.14.106.33 (talk) 14:45, August 27, 2007 (UTC)

You didn't miss anything, the Circular buffer mechanics paragraph is incorrect, the first pointer will point to the first element to be read, and the second pointer will point to the first element to be written. I'm going to try to remember this when I have some time to correct the diagrams and fix it. 70.230.2.66 (talk) 23:24, 10 March 2008 (UTC)

I agree with 70.230.2.66. The classic implementation has a "read pointer" and a "write pointer".

The "write pointer" points to the location where the next element will be written, which is (in general) just past the newest element (most recently written element) in the buffer.

The "write pointer" always points to an empty slot in the buffer, except in the special case where the buffer is completely full. The point of the "Always Keep One Byte Open" variant is to eliminate this special case.

• 1 element in buffer: (read pointer + 1)%size == write pointer

When we have 1 element in the buffer, and then we read that element (incrementing the read pointer just as we always do), then we inevitably get:

• Free buffer: read pointer == write pointer

--68.0.124.33 (talk) 18:59, 14 January 2009 (UTC)

Buffer border

In Circular buffer mechanics it talks about a "buffer border". What is the buffer border and when can it be "read over"? 137.44.2.188 (talk) 09:51, 9 April 2008 (UTC)

 I rewrote the sentence about a "buffer border" to hopefully make it more clear. Maybe the 'clarify' notice can be removed?  Shervinemami (talk) 18:50, 1 July 2010 (UTC)

round robin archive

The RRDtool currently mentions a "a round-robin archive (RRA).", and the brief description reminds me of a circular buffer. Is "round-robin archive" an exact synonym for "circular buffer", or some specific variant of a circular buffer? Or is it something significantly different? --68.0.124.33 (talk) 00:49, 15 January 2009 (UTC)

Used Buffer space

When checking to see how much space is used in the buffer, needing to be read (The space between the write and read pointers) could you not just use another variable, incrementing it as you write something, and decrementing it as you read something? For example, once it is initialized, the buffer is empty therefore your variable would = 0. But once you write, say 3 bytes, with out reading something, the variable would than = 3. And again after reading 2 bytes, that same variable would equal 1, effectively indicating that there is one byte remaining to be read in the buffer. This eliminates the need for any crazy algorithms for when your write pointer has wrapped around before you read pointer has. —Preceding unsigned comment added by 205.250.74.174 (talk) 23:15, 17 June 2009 (UTC)

C# Example

I find the C# example distinctly uninformative and overly verbose. While perhaps it shows good design, it doesn't illustrate the subject matter any better than the other two C examples. I'm removing it for now. SiegeLord (talk) 18:33, 13 September 2010 (UTC)

Full/Empty Buffer Distinction

Another solution not mentioned in the article is to have an additional boolean variable. When an element is inserted, it is set to true, and when an element is removed, it is set to false. If the indices are equal and the variable is true, the buffer is full. If the indices are equal and the varaible is false, the buffer is empty. Platypus1130 (talk) 21:58, 30 January 2011 (UTC)

Full implementation?

Please don't replace the C code with some pseudo code which doesnt really help anybody... — Preceding unsigned comment added by 130.149.245.245 (talk) 16:17, 19 December 2012 (UTC)

Is it really useful to have two full implementations of a ring buffer? Wouldn't it be better to just have some pseudo code? This is an encyclopedia, not a pastebin, is it not? —Preceding unsigned comment added by 142.244.143.199 (talk) 17:22, 12 April 2011 (UTC)

Agreed, it's currently quite unencyclopaedic. See below a simpler C implementation which I think works as an easy-to-understand example without being too C-specific. I suggest replacing the whole "Difficulties section" using this as a starting point. Thoughts? HoboBen (talk) 20:05, 20 April 2011 (UTC) Edit: spoke too soon, there's a bug in my RetrieveFromQueue function where start==end when it's full. Needs to be fixed first. HoboBen (talk) 21:05, 21 April 2011 (UTC)

Fixed. HoboBen (talk) 16:06, 22 April 2011 (UTC)

While it might not be written in its founding statement, many people turn to wikipedia as a place to quickly learn about a topic. I wanted to quickly learn about circular buffers - specifically, how to use them - and I found the description, as well as the implementations, to be extremely useful. I don't think it would be "better" to remove some information that some might find useful. It is at the bottom of the article - you only scroll to that section if you want to read it. However, I STILL think there is a problem with the implementation, though. I'm not sure why the IsFull and IsEmpty variables are included in the read/write functions, and they seem to be updated at the wrong time (before the increment).Hithisishal (talk) 07:31, 10 January 2012 (UTC)

#define BUFFER_SIZE 256

item *buffer[BUFFER_SIZE];
int start = 0;
int end = 0
int active = 0;

void PushToQueue(item *p)
{
    buffer[end] = p;
    end = (end + 1) % BUFFER_SIZE;

    if (active < BUFFER_SIZE)
    {
        active++;
    } else {
        /* Move start to next-oldest */
        start = (start + 1) % BUFFER_SIZE;
    }
}

item *RetrieveFromQueue(void)
{
    item *p;

    if (!active) { return NULL; }

    p = buffer[start];
    start = (start + 1) % BUFFER_SIZE;

    active--;
    return p;
}

Can we please get consensus on replacing the current C examples with this alternative? Agree, disagree, or suggest modifications below. HoboBen (talk) 12:58, 27 July 2011 (UTC)

Is there a way we could put the code into some kind of infobox structure that by default would be closed, but could be opened by the user if they wanted? I don't know what WikiMarkup has for this kind of thing, but I know I've seen it on a couple of articles before. Then perhaps put some short psudocode in the boy, with a full/more complete C implementation in the closed box. I don't know whether you could do a psudocode in 10 lines, I'm thinking along these lines:

Initialization:

 p1=0; p2=0; numItems=0; isFull=false; isEmpty=true;
 Function put(x):
   array[p1] = x; p1++; numItems++;  // insert item and advance write pointer
 Function get():
   return array[p2]; p2++; numItems--;  // remove item and advance read pointer
 With either function:
   if (p1= arrayLength) then p1 = 0;  // reset write pointer to beginning if we've reached the end ("ring" around)
   if (p2= arrayLength) then p2 = 0;  // same for read pointer
   if (p1<0) then p1 = arrayLength;  // reset write pointer to end of buffer if we've reached the beginning
   if (p2<0) then p2 = arrayLength;  // same for read pointer
   if (numItems >= arrayLength) then isFull = true; isEmpty = false;  // check if we've filled all spaces
   if (numItems <= 0) then isEmpty = true; isFull = false;  // check if we've read from all spaces
 Function isFull(): return isFull  // return whether the buffer is full or empty
 Function isEmpty(): return isEmpty

I just wrote that off the top of my head. It's not really "proper psudocode" - and I'm not even sure it will work correctly - I'm pretty sure that the isFull and isEmpty logic isn't right. But something like that. — Preceding unsigned comment added by Jimw338 (talk • contribs) 19:40, 9 August 2012 (UTC)

Java Implementation

A while back, I added the following external link:

CircularArrayList for Java - a Java implementation of a circular buffer

This is a link to a page on my own website. I know that under some circumstances this is allowed if there is consensus that the link is a useful addition to the article. But alas, I have a bit of a history for linking to my site, and after I became a bit pushy in a discussion elsewhere, the links were (understandably) removed. To save you some time, I should mention that I have been made very aware of the WP guidelines that are frowning upon me. I stand on nothing except IAR and a sure conviction that the article is better off with the link than without it. Some points to note:

• The article does not, as it stands, have a link to a Java implementation.
• CircularArrayList plugs something of a hole in the Java Collections Framework. Some readers may come to the article specifically looking for this (as I did, originally).
• Its minimalism makes it 10 times shorter than the shortest currently externally linked implementation (in any language).

(until they disappeared during the course of the discussion) --Tennenrishin (talk) 22:55, 13 August 2011 (UTC)

• It is probably the only production-ready implementation supporting Java generic element types that is available on the web.

I have learned my lesson about pushing when there is potential for COI, but I believe there is rather an alignment of interest (even though the only interest I derive from my website is satisfaction). Would you consider the case for restoring the link, based purely on the merits of its inclusion? (Those essays listed in IAR make for some really good reading :) --Tennenrishin (talk) 15:55, 13 July 2011 (UTC)

I don't see how a link to yet another implementation would add to an encyclopedic understanding of this type of data structure. - MrOllie (talk) 20:59, 13 July 2011 (UTC)

Thank you for explaining why you removed the link, MrOllie. If you were a reader that is familiar only/mainly with Java, would you then? --Tennenrishin (talk) 21:53, 22 July 2011 (UTC)

Does anyone have a position to offer on this matter? I would like to restore the link if it is in the interest of the article. --Tennenrishin (talk) 21:10, 12 August 2011 (UTC)

I'll make myself more clear: Please do not restore the link, it is not helpful nor is it consistent with WP:EL. - MrOllie (talk) 21:11, 12 August 2011 (UTC)

MrOllie, why do you say the link is not helpful? --Tennenrishin (talk) 16:01, 13 August 2011 (UTC)

We already have three implementations in the article. We don't need to duplicate that ad nauseam for additional platforms and programming languages in the external links. It's not educational. - MrOllie (talk) 16:27, 13 August 2011 (UTC)

1. Indeed, the article has about 450 lines of low-level code for C readers. What is wrong with adding one line to the article for Java readers?

2. If you don't care about languages, you would find this brief high-level implementation much more educational than any number of low-level implementations, because Java affords more abstraction than C. (I am trying to trust that you have actually looked at the link.)

3. Even if one imagines it is not "educational", it is still helpful. See 2nd and 4th bullets in the original post. An encyclopedia is a reference work.

4. Regarding "duplicating ad nauseam for additional languages": C and Java are by far the two most popular languages.

5. Regarding "duplicating ad nauseam for additional platforms": Actually, Java would be the one language where you don't have to worry about that. --Tennenrishin (talk) 07:14, 18 August 2011 (UTC)

MrOllie, if you still think the link is not helpful, please help me understand. --Tennenrishin (talk) 10:58, 29 August 2011 (UTC)

It would appear that you have changed your view, MrOllie. If this is true, thank you for being unbiased.--Tennenrishin (talk) 14:24, 5 September 2011 (UTC)

I have not changed my view, so I removed the link you added based on the lack of consensus demonstrated on this talk page and because of the guidelines in WP:EL. Please do not continue to add links to your own website. Thanks. - MrOllie (talk) 14:33, 5 September 2011 (UTC)

MrOllie, why is the link not helpful, in your view?--Tennenrishin (talk) 07:33, 6 September 2011 (UTC)

We already have implementations in the article which it duplicates. WP:ELNO point one says that we only include sites that will provide unique content that cannot otherwise be included. I find your arguments that it is different because one is Java and one is C++ to be unconvincing. - MrOllie (talk) 14:45, 6 September 2011 (UTC)

If you really believe the implementations are similar, please take a moment to compare them. It will also help you to understand my arguments. --Tennenrishin (talk) 21:23, 6 September 2011 (UTC)

I have reviewed your site and fully understand your arguments. Nonetheless, I disagree with them. - MrOllie (talk) 12:53, 7 September 2011 (UTC)

Do you refuse to explain why you disagree? --Tennenrishin (talk) 13:11, 7 September 2011 (UTC)

(If they are a little overwhelming I can summarize the most important ones for you.) --Tennenrishin (talk) 13:39, 7 September 2011 (UTC)

Fine, from your numbered list above: 1), It's a problem because it does not comply with the external links guidelines. 2) This argument compares apples and oranges: an implementation in the article vs an external link to your site. 3) This argument does not appear to be grounded in Wikipedia policy. 'Helpful' is not a criteria for link inclusion. 4) This argument does not appear to be grounded in Wikipedia policy. 5) This argument does not appear to be grounded in Wikipedia policy. - MrOllie (talk) 13:55, 7 September 2011 (UTC)

Please explain why you disagree that the link is helpful. I have now asked 5 times.

Also, since you have mistaken that numbered list of responses, let me help you identify the arguments throughout the discussion:

• A. Many readers are familiar with Java, but not with C. That segment of readers would find the link very helpful if not indispensable.
• B. The linked implementation is at a completely different level of abstraction compared to the article's implementation. In other words, it does away with many implementation details (pointers, #defines, typedefs, pointers to pointers! etc.) that only serve to obscure the concept being explained by the article. For this reason, even readers that are familiar with both languages would find the Java implementation adds considerable educational value.
• C. A ready-to-go Java implementation is, obviously, ideal information for readers looking to implement a circular buffer in Java. (And this happens often, for a reason explained in my original post.)

I believe any one of the above arguments is enough to prove that the link is helpful. I am a reasonable man:) I will not try to save face if I see your POV is valid. But with the views you claim to be holding, I'm finding it hard to believe you even know Java. (No offence - just an appeal for reasonableness.) --Tennenrishin (talk) 16:07, 7 September 2011 (UTC)

Please try to stick to the external links guidelines. None of what you are arguing seems to have much relation to them. Perhaps your fundamental disconnect is that you think the purpose of Wikipedia is to provide helpful links to readers. It is not. In fact Wikipedia is specifically not supposed to serve as a directory of external links. Perhaps you should add your link to a site which is supposed to be a directory, such as dmoz.org. Please don't mistake my refusal to engage with you on whether Java is better than C++ with ignorance of Java, I can assure you that I am familiar with both languages. - MrOllie (talk) 16:20, 7 September 2011 (UTC)

Guidelines are guidelines. The overruling question is whether the link improves WP or not. For most of this discussion, my quest has been to understand why you say the link is not helpful, in the face of three arguments (each of which seem undeniably compelling to me). This is the 6th time I ask.

If, on the other hand, you have now realized that the link is helpful, but you want to remove it despite its helpfulness, just because it violates guidelines, then please say so, because that is a different argument entirely. --Tennenrishin (talk)

The link is not helpful in the context of this Wikipedia article. It is not surprising that you find your own arguments compelling, or that you think it is a good site, it is your site and presumably you would not have put it up if you didn't think it was good. This is a large part of why we have the guideline on conflict of interest, which discourages siteowners from linking their sites. - MrOllie (talk) 03:55, 8 September 2011 (UTC)

So, in spite of arguments A, B and C above, the link is not helpful, because of who added it? Am I interpreting your response correctly? --Tennenrishin (talk) 11:46, 8 September 2011 (UTC)

No, that is incorrect. I have repeated my reasoning a couple of times above. I am really not interested in repeating myself again. - MrOllie (talk) 12:13, 8 September 2011 (UTC)

There is no need to repeat yourself. Just explain why you say the link is not helpful, or point me to where you have explained this already. Let me break the question down for you:

• Why is argument A invalid?
• Why is argument B invalid?
• Why is argument C invalid?

Alternatively, if you no longer wish to dispute that the link is helpful, but insist on its removal despite its helpfulness (for reasons such as WP:COI or WP:EL), then please say so. --Tennenrishin (talk) 13:26, 8 September 2011 (UTC)

I have brought this up at the noticeboard for external links to gain more input. - MrOllie (talk) 14:58, 8 September 2011 (UTC)

The link is not appropriate, per WP:EL and WP:COI. "Helpfulness" isn't much of an argument. OhNoitsJamie ^Talk 15:01, 8 September 2011 (UTC)

"Helpful" in the sense that the link constitutes a significant improvement to the article. I believe that this claim is supported by arguments A, B and C above, independently. The case I make stands or falls by them, but so far, they have not been addressed or acknowledged. --Tennenrishin (talk) 15:54, 8 September 2011 (UTC)

(Following up from the noticeboard request...) I agree with MrOllie and Ohnoitsjamie - it's code in a different language with little explanation. It's heavily redundant with the content of this article, so it should not be added to the list.

Please see arguments A, B and C. --Tennenrishin (talk) 07:44, 9 September 2011 (UTC)

Similarly, I'd remove the first link, http://c2.com/cgi/wiki?CircularBuffer , from the list as well. --Ronz (talk) 15:18, 8 September 2011 (UTC)

Regarding your request for "someone with Java experience" to come over; I've been writing Java since 1997, and I've already given you my opinion. I suggest stepping away from the deceased equine. OhNoitsJamie ^Talk 16:59, 8 September 2011 (UTC)

Your stated opinion appears to suggest that you agree the link is helpful, but that its helpfulness should be ignored. Is this true? --Tennenrishin (talk) 07:44, 9 September 2011 (UTC)

As to the arguments: taken to their logical conclusions, they would justify links to examples in every possible language - not even remotely appropriate. The other aspect of the arguments is that the article does not make the issue clear enough - but that's actually an argument for improving the article, not for going against WP:EL. --- Barek (talk • contribs) - 17:13, 8 September 2011 (UTC)

Thank you. You are the very first one to allude to the arguments I have raised.

• "they would justify links to examples in every possible language": All the arguments (A, B and C) are conditional on the wide popularity of Java. Java is the most, or the second most popular language, I'm not sure which.
• "but that's actually an argument for improving the article": My claim is that the link improves the article. That does not preclude the possibility that there is a different way to improve the article more. --Tennenrishin (talk) 19:40, 8 September 2011 (UTC)

You seem to have missed my point. The purpose of Wikipedia is to provide content, not an internet directory. The link does not improve the article, it expands a link directory. If the article is unclear, that's a reason to improve the article content, not to expand the link directory. --- Barek (talk • contribs) - 21:18, 8 September 2011 (UTC)

WP is not a link directory. Nonetheless, WP articles have helpful external links.

Implementations have inimitable ability to define the concept unambiguously, but easily "overload" the reader with lots of lines of code. That is why there have been complaints on this page about the amount of code in the article. The link discretely puts that extra helpfulness (see A, B, C, D below) within the reader's reach, but out of the reader's face. --Tennenrishin (talk) 09:06, 9 September 2011 (UTC)

Allow me to repeat the arguments, and summarize my position for the benefit of any newcomers. (B2 and D were added now)

• A. Many readers are familiar with Java, but not with C. That segment of readers would find the link very helpful if not indispensable.
• B1. The linked implementation is at a completely different level of abstraction compared to the article's implementation. In other words, it does away with many implementation details (pointers, code-structure, #defines, typedefs, pointers to pointers! etc.) that obscure the concept in question.
• B2. The linked implementation is a self-contained module implementing a very widely recognized interface from JCF. A pre-understood interface gives many readers a substantial head-start in assimilating it mentally (or in a project), because the circular buffer is decoupled from its context at no cost in generality.
• B. For reasons B1 and B2, even readers that are familiar with both languages would find the Java implementation adds considerable educational value.
• C. A ready-to-go Java implementation is, obviously, ideal reference information for readers looking to implement a circular buffer in Java. (And this happens often, for reasons explained in bullets 2 and 4 of my original post.)
• D. The main distinguishing feature (even though it is not a defining feature) of a circular buffer over a linked list, is its potential support for random access. Readers interested in this particular feature will find that the link implements it neatly, under the same widely recognized interface. (Working this optional functionality into the C implementation would incur some cost in clarity and article length.)

Now, my claim is that each of A, B, C and D point to a significant improvement in the WP article. --Tennenrishin (talk) 19:40, 8 September 2011 (UTC)

A, B, C and D have not been disputed anywhere in this entire discussion so far. Does anyone disagree? --Tennenrishin (talk) 11:22, 9 September 2011 (UTC)

I suggest everyone cease participating in this tiresome discussion. Wikipedia is not a court of law. There are three editors who are telling you the same thing; the link is not appropriate. There is no burden of proof that must be established to exclude a link. Policy backed by simple consensus is sufficient. OhNoitsJamie ^Talk 15:12, 9 September 2011 (UTC)

I am sorry that the discussion has been tiresome. Actually, in my original post, I said I wouldn't push, but one thing led to another... and I kept thinking a breakthrough is around the corner. I should have stopped a long time ago.

I have been quite stubborn, and I owe you all an explanation. But words are tiresome...

Helpless helpful external link

--Tennenrishin (talk) 22:41, 9 September 2011 (UTC)

That's pretty damned funny! Sorry if I was a bit gruff about the whole bit. It's just that I've had many, many, many similar discussions. Thanks for having a good sense of humor about it! OhNoitsJamie ^Talk 22:45, 9 September 2011 (UTC)

It's okay :) I just wish I hadn't waited so long before making my words into a picture. Tennenrishin (talk) 10:31, 2 January 2012 (UTC)

(Practicing for a career in horse necromancy here..) [half-serious] Maybe we should just have a page called "Implementations of Ring Buffers in Different Programming Languages"? Or perhaps a list for any data structure in general.. — Preceding unsigned comment added by Jimw338 (talk • contribs) 19:47, 9 August 2012 (UTC)

Why has Tennenrishin been ignored on all of his central arguments? Batting them aside like that is no way to address what may very well be valid arguments. Certainly at least some of them seem valid, and their claims have substantial consequence. --37.183.93.159 (talk) 13:13, 14 August 2012 (UTC)

@Jimw338: That might be very useful. Let's find out by doing the experiment at http://en.wikibooks.org/wiki/Algorithm_Implementation . --DavidCary (talk) 05:35, 30 October 2012 (UTC)

Removal of Implementations

I'm a little surprised to see my Bip Buffer article removed from here (not that I added it, but I was quite honored that it was linked). It was removed during removal of specific implementations... except it's not an actual implementation per se - it's a variant algorithm which provides nearly the efficiency of a regular circular buffer, but with reduced overhead for reading data in chunks; it ensures that all chunks read are contiguous.Fleetingshadow (talk) 22:15, 7 September 2011 (UTC)

MrOllie, this is collateral damage from our discussion above. Is there anything I can say to make you restore these links? --Tennenrishin (talk) 08:46, 8 September 2011 (UTC)

Regardless of the quality of such articles and ideas, Wikipedia needs to be consistent with its No Original Research policy. There are plenty of great venues for advancing new code paradigms/data structures/algorithms, etc. This just isn't the place for it. 02:48, 10 September 2011 (UTC)

I added a brief mention of the Bip Buffer, with a reference link, not realizing that this had already been discussed. I hope this doesn't trigger any unpleasantness. --DavidCary (talk) 05:35, 30 October 2012 (UTC)

I just came here to review the C implementation and, for the first time in a decade, I had to look at older revisions of the page to get value from a Wikipedia article. You guys should really put that back. It's the most useful part of this page and conveys ideas cleanly. -ml — Preceding unsigned comment added by 70.36.56.149 (talk) 00:50, 6 February 2015 (UTC)

Uses

I think the "Uses"-part is too black-and-white as it is...

"If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed."

Wrong, just use a pointer to the start of the buffer. The circularity just helps in reclaiming the dead space in front of such a buffer.

"Circular buffering makes a good implementation strategy for a queue that has fixed maximum size.

Wrong if the queue almost never uses the maximum size.

"For arbitrarily expanding queues, a Linked list approach may be preferred instead."

Yes, but Linked lists have a huge space (and sometimes cache miss) overhead, and a performance penalty because of the indirections, while a Circular buffer can be almost as fast as an Array. So the "may" is strong in this one.

Bottom line, the claims are more or less correct, but they do not reflect the fine distinctions necessary to choose a data structure in the real world. Also, there are applications in some scheduling algorithms, and the multimedia example can be generalized to the synchronization of many more single-producer-single-consumer-cases. Sorry I'm only criticizing, and not editing, but my English is not good enough for that... --89.204.152.53 (talk) 04:36, 8 August 2013 (UTC)

Circular buffer‎ contradiction in definitions

Please explain why you undid my revision which I commented thus: "there is a contradiction because the "end" pointer is defined in two different ways, once as an end pointer and once as a next pointer." Methinks this contradiction is obvious and, if I had the time, I'd make the examples consistent. Vincent J. Lipsio (talk) 22:25, 11 November 2013 (UTC)

From the article:

definition	quote	illustration
end pointer	"end of valid data"
next pointer	"in the case the buffer is entirely full, both pointers point to the same element"

I've noted this with an inline contradiction template. Since I am not familiar with the subject I'd rather let someone with better knowledge of the subject choose which definition is more appropriate, however, the contradiction does exist. IsaacAA (talk) 12:52, 12 November 2013 (UTC)

The above diagram contradicts this text:

• one to the buffer end in memory (or alternately: the size of the buffer)
  

Thus, the "end" is being used to designate both the next in and the last byte in the buffer. Vincent J. Lipsio (talk) 18:05, 12 November 2013 (UTC)

If you are versed in the subject it would be a lot simpler if you just fix the article instead of saying "there's a contradiction but it's not important". IsaacAA (talk) 18:14, 12 November 2013 (UTC)

I just proved *your* point; point well taken.

Yes, I am well versed, having written circular buffer code for more than 30 years (actually, at this point in time, I just re-use things I wrote in the 1980s); however, fixing the article would take more time than I have as the terminology is mixed all over the place. Vincent J. Lipsio (talk) 18:18, 12 November 2013 (UTC)

Removal of Optimized POSIX implementation

I'm surprised to see the Optimized POSIX implementation example being removed from the article on April 14, 2014. This example is extremely useful, well written, and provides a great benefit to readers. Please consider restoring it. --Victorspm (talk) 17:53, 21 April 2014 (UTC)

Wikipedia is an encyclopedia, not a code repository. That piece of code was a clear piece of original research. WP isn't a good place to share code: it has the wrong license and it doesn't have sufficient quality control. QVVERTYVS (hm?) 16:04, 4 December 2014 (UTC)

For anyone else that might stumble upon this, I implemented a slightly improved version (see set_up_mirroring()) based on the original version from the article. Hardcoding /dev/shm and hoping the file ends up in an in-memory filesystem can be avoided by using the POSIX shared memory shm_open() and shm_unlink() functions. -- Ulfalizer (talk) 23:12, 30 January 2015 (UTC)

So, taking into account that the discussed piece of code is available only in the history of this page, I have uploaded a bit modified copy of this excellent and valuable piece of code here rng buf on GitHub. --Vitaly.v.ch (talk) 20:18, 1 February 2020 (UTC)

• Version of 13 July 2014 02:25 still contains the Optimized POSIX implementation
• Version of 29 January 2015 14:35 still contains the last removed snippets. Oliver H (talk) 08:43, 10 March 2016 (UTC)

needs additional citations?

From the desciption of a 1950s telephone exchange I quote: "The mechanical storage element of the pulse repeater is a lamellar disc with 72 resilient lamellae which is rotatably arranged in a raceway. The storage magnet turns the disc one step further with each incoming pulse. The marker magnet presses the lamellas on one side of the ring when the magnet is attracted and on the other side of the ring when the magnet has fallen off. These markings are retained for one full turn of the flap disc and thus mark the end of a previously stored series of pulses. Up to the start of withdrawal, 64 pulses can be saved. The scanning arm is on the other side (scanning side). This arm moves with the lamellar disc when it is stored. When releasing, the scanning arm slides over the lamellar support ring against the rotary movement of the lamellar disk and thereby scans each lamellar step until it is stopped at the end of the series of marked lamellas." See https://www.youtube.com/watch?v=_xI9tXi-UNs for the german original text.

From the US patent 3979733 I quote: "Responsive to clock signal CK1 and the coincidence of the comparator and input enable signals on lead 302, the contents of the read address register are incremented by adder 350. Thereby the contents of the read address register are advanced to correspond to the direct address of the next of the consecutive memory cells in the FIFO queue, i.e., the cell from which a packet may next be read ... Thereafter, responsive to clock signal CK3 and the coincidence of the comparator and input enable signals, the contents of the write address register are incremented by adder 350. Thereby the contents of the write address register are advanced to correspond to the direct address of the next available memory cell in the FIFO queue, i.e., the next cell into which a packet may be written." Is it necessary to put this quote into the Wikimedia article? I am sure that a 1976 patent is not the first document about circular buffer. The original inventor of circular buffer is not known to me, I think the name got lost in history. Can we now put down the "needs additional citations" sign? AndreAdrian (talk) 11:31, 15 December 2021 (UTC)

Optimization

The article cites an example in which consecutive virtual memory pages are mapped to the same buffer for apparent performance improvement as "automatic" wrap around is managed by hardware. However it is not necessarily true that virtual memory homonyms are performantly accessed. In fact, mapping in this fashion may significantly slow stores to the buffer on modern CPUs (and other hardware). At a minimum, a citation showing how this improves performance is needed. — Preceding unsigned comment added by Jcm (talk • contribs) 16:25, 23 January 2022 (UTC)

I believe that the performance problems exist for virtual memory homonyms, as you say, but the technique here is actually virtual memory synonyms or aliasing. See https://www.cse.unsw.edu.au/~cs9242/02/lectures/03-cache/node8.html. I think it is reasonable to assume that offloading this to hardware will be faster, but I can try cooking up a little benchmark. 74.109.39.81 (talk) 03:14, 26 May 2024 (UTC)

It might also be worth noting that GNURadio uses this technique for its circular buffers. It's in gr::vmcircbuf and its subclasses. See: [1] Ammrat13 (talk) 05:31, 16 June 2024 (UTC)

I was searching for this and came across this implementation: https://lo.calho.st/posts/black-magic-buffer/, where there is a benchmark showing some performance benefit (on a i5-6400, for some specific workload). So it seems that this optimisation can be good at least on some relatively modern hardware. 83.253.76.88 (talk) 16:49, 28 October 2024 (UTC)