Simplified algorithm for calculating remaining space in a circular buffer?

Question

I was wonder if there is a simpler (single) way to calculate the remaining space in a circular buffer than this?

int remaining = (end > start)
                ? end-start
                : bufferSize - start + end;

Answer 1

If you're worried about poorly-predicted conditionals slowing down your CPU's pipeline, you could use this:

int remaining = (end - start) + (-((int) (end <= start)) & bufferSize);

But that's likely to be premature optimisation (unless you have really identified this as a hotspot). Stick with your current technique, which is much more readable.

Answer 2

Hmmm....

int remaining = (end - start + bufferSize) % bufferSize;

13 tokens, do I win?

Answer 3

According to the C++ Standard, section 5.6, paragraph 4:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.

A footnote suggests that rounding the quotient towards zero is preferred, which would leave the remainder negative.

Therefore, the (end - start) % bufferSize approaches do not work reliably. C++ does not have modular arithmetic (except in the sense offered by unsigned integral types).

The approach recommended by j_random_hacker is different, and looks good, but I don't know that it's any actual improvement in simplicity or speed. The conversion of a boolean to an int is ingenious, but requires mental parsing, and that fiddling could be more expensive than the use of ?:, depending on compiler and machine.

I think you've got the simplest and best version right there, and I wouldn't change it.

Answer 4

If your circular buffer size is a power of two, you can do even better by having start and end represent positions in a virtual stream instead of indices into the circular buffer's storage. Assuming that start and end are unsigned, the above becomes:

int remaining= bufferSize - (end - start);

Actually getting elements out of the buffer is a little more complicated, but the overhead is usually small enough with a power of 2 sized circular buffer (just masking with bufferSize - 1) to make all the other logic of your circular buffer much simpler and cleaner. Plus, you get to use all the elements since you no longer worry about end==start!

Answer 5

Lose the conditional:

int remaining = (end + bufferSize - start - 1) % bufferSize + 1

Edit: The -1 and +1 are for the case when end == start. In that case, this method will assume the buffer is empty. Depending on the specific implementation of your buffer, you may need to adjust these to avoid an off-by-1 situation.

Answer 6

Older thread I know but thought this might be helpful.

Not sure how fast this implements in C++ but in rtl we do this if size is n^2

remaining = (end[n] ^ start[n])
            ? start[n-1:0] - end[n-1:0]
            : end[n-1:0] - start[n-1:0];

or

remaining = if (end[n] ^ start[n]) {
              start[n-1:0] - end[n-1:0]
            } else { 
              end[n-1:0] - start[n-1:0] 
            };