31–40 of 175 posts
Earlier quoted context omitted.
It's not just an optimization, it's necessary for correct operation. With a non-power of two buffer the integer wraparound causes a discontinuity.
No, it's an optimization.
Why do people use the version that's inferior and more complicated? Because it's easier to understand at first glance, has no performance penalty, and for most busy programmers that often wins.
This question needs little context to be relevant, so long as the topic is "computer programming".
Certainly not limited to writing ring buffers. It could be an apropos comment in almost any discussion.
Of course in many cases, the part about "no performance penalty" does not apply. Performance is a routine trade off for some other perceived gain.
Earlier quoted context omitted.
It's not just an optimization, it's necessary for correct operation. With a non-power of two buffer the integer wraparound causes a discontinuity.
No, it's an optimization.
Imagine we had four bit integers and a three cell array. Stepping from 7 (= 1 mod 3) to 8 (= 2 mod 3) winds up stepping instead to 0 (= 0 mod 3) because overflow, which would reuse cells inappropriately.
Earlier quoted context omitted.
The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.
I don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.
"The finished "Ian Knot" is identical to either the Standard Shoelace Knot or the Two Loop Shoelace Knot. Because it was tied much more quickly and symmetrically, the laces suffer less wear and tear and thus last longer."
Earlier quoted context omitted.
The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.
I don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.
Earlier quoted context omitted.
No, it's an optimization.
No, it's not. A non-power-of-two will lead to incorrect behavior, implementing the data structure the way the author describes, for precisely the reason given by your parent comment. There are other implementations that don't suffer from this (described in the comments there), but it's not simply a matter of replacing bitwise-and with a more generic computation of the modulus. Imagine we had four bit integers and a t…
Earlier quoted context omitted.
Depending on the machine, a modulo can cost _alot_ . Last time I checked, the operation cost was 26k cycles on my PIC. Using a 2^n + mask made my queue perform 10 times faster (if not more).
Don't use a modulo then. Use subtraction.
Usually when I'm writing a ring buffer, it's for tasks where the loss of an item is acceptable (even desirable - a destructive ring buffer for debugging messages is a fantastic tool). As such, I simply push the read indicator when I get to the r=1, w=1 case. Using the mask method is slick (I'd cache that mask with the array to reduce runtime calculations), but it's definitely going to add cognitive overhead and get m…
In general, this makes sense; certainly data you're putting into a ring buffer is data you're willing to lose. Doesn't it break the order invariant of the buffer, though? I can't see a way to do this without the risk of getting reads of newer data prior to older data. That's probably fine in many cases, but something like non-timestamped-debugging strikes me as a case where I'd want to know that the data arrived in t…
No, if you increment the read pointer prior to the write pointer, the read pointer will still point at the oldest valid value in the buffer.
So, in pseudo code:
if (w+1 >= r) {
r = w + 2
}
w++
b[w-1] = value
This is of course not a new invention. The earliest instance I could find with a bit of searching was from 2004, with Andrew Morton mentioning in it a code review so casually that it seems to have been a well established trick. But the vast majority of implementations I looked at do not do this. I was doing this in 1992 so it's at least 12 years older than the 2004 implementation. I suspect it was being done long bef…
Depending on the machine, a modulo can cost _alot_ . Last time I checked, the operation cost was 26k cycles on my PIC. Using a 2^n + mask made my queue perform 10 times faster (if not more).