A very related post by ryg: https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-qu...
I've been writing ring buffers wrong all these years
11–20 of 175 posts
Re: I've been writing ring buffers wrong all these years
#12This 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…
It's odd that you were using ring buffers in 1992 for low level code but don't understand the value of avoiding a modulus instruction. Masking is far more efficient and often a ring buffer will be used in code where performance is absolutely critical.
Re: I've been writing ring buffers wrong all these years
#13This 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).
Re: I've been writing ring buffers wrong all these years
#14This 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…
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.
Re: I've been writing ring buffers wrong all these years
#15This 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…
It's odd that you were using ring buffers in 1992 for low level code but don't understand the value of avoiding a modulus instruction. Masking is far more efficient and often a ring buffer will be used in code where performance is absolutely critical.
You wouldn't use the modulus operation. You aren't adding some arbitrary number that's going to make you increase either index by more than the buffer length so you know that at worse you are going to need to subtract the length of the buffer.
IIRC the way we made this really fast was the write the buffer backwards. That way you can detect wrapping around the buffer because DEC will underflow and set the sign flag. Then you can JS to whatever code needs to ADD back the buffer length to handle the wrap around.
But 2^n has another problem (back in that era): buffer size. You are stuck with 1K, 2K, 4K, etc. buffers. When memory is tight you likely need something very specific, so you end up with the solution we had.
But, hey, if memory is free use 2^n bytes for your buffer.
Re: I've been writing ring buffers wrong all these years
#16> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.
I wasn't given the attribution when I heard about this, it's nice to see the face behind it. Not sure I can even tie my shoes the old way anymore, I've never done it once since learning Ian's knot. Every once in a while someone observant will see me doing it and say, "whoa, WHAT?" I do get a kick out of telling people I re-learned how to tie my shoes on the internet.
Re: I've been writing ring buffers wrong all these years
#17This 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…
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.
Re: I've been writing ring buffers wrong all these years
#18Hmm..., interesting.
I've always been doing it the "wrong" way, mostly on embedded systems. My classic application is a ring buffer for the received characters over a serial port. What's nice is that this sort of data structure doesn't need a mutex or such to protect access. Only the ISR changes the head, and only the main routine changes the tail.
Re: I've been writing ring buffers wrong all these years
#19> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.
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.
Re: I've been writing ring buffers wrong all these years
#20> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.
I wasn't given the attribution when I heard about this, it's nice to see the face behind it. Not sure I can even tie my shoes the old way anymore, I've never done it once since learning Ian's knot. Every once in a while someone observant will see me doing it and say, "whoa, WHAT?" I do get a kick out of telling people I re-learned how to tie my shoes on the internet.
It seems to be almost the same as the traditional method to me, since the crossing of the laces seems to cost about 50% of the time. It gets a lot better when you leave the crossing in. Edit: Apparently, there also is a routine to get the crossing in a nice, fast way, it just wasn't included in the pictures :)
More importantly, I can't seem to get a Ian's knot very tight. Does this get better over time?