Circular increment: Which is "better"?

Question

When you have a circular buffer represented as an array, and you need the index to wraparound (i.e., when you reach the highest possible index and increment it), is it "better" to:

return (++i == buffer.length) ? 0: i;

Or

return ++i % buffer.length;

Has using the modulo operator any drawbacks? Is it less readable than the first solution?

EDIT:

Of course it should be ++i instead of i++, changed that.

EDIT 2:

One interting note: I found the first line of code in ArrayBlockingQueue's implementation by Doug Lea.

Answer 1

This is very subjective and depends on what your colleagues are used to see. I would personally prefer the first option, as it expresses explicitly what the code does, i.e. if the buffer length is reached, reset to 0. You don't have to perform any mathematical thinking or even know what the modulo does (of course you should! :)

Answer 2

I prefer the modulo operator for the simple reason it is shorter. And any program should be able to dream in modulo since it is almost as common as a plus operator.

Answer 3

Wouldn't the i++ % buffer.length version have the drawback that it keeps incrementing i, which could lead to it hitting some sort of max_int/max_long/max_whatever limit?

Also, I would split this into

i = (i++ == buffer.length) ? 0 : i;
return i;

since otherwise you'd most likely have a bug.

Answer 4

I think the second solution has the clear advantage that it works, whereas the first does not. The first solution will always return zero when i becomes bigger than buffer.length because i is never reset.

The modulo operator has no drawbacks.

Answer 5

Don't ask me to choose between two options which both contain postincrement (*) mixed with expression evaluation. I'll say "none".

(*) Update: It was later fixed to preincrement.

Answer 6

Update: OP has admitted in a comment that it should have been pre-increment instead. Most of the other answers missed this. There lies proof that the increment in this scenario leads to horrible readability: there's a bug, and most people couldn't see it.

The most readable version is the following:

return (i == buffer.length-1) ? 0 : i+1;

Using ++ adds unnecessary side effect to the check (not to mention that I strongly feel that you should've used pre-increment instead)

What's the problem with the original code? Let's have a look, shall we?

return (i++ == N) ? 0 : i; // OP's original, slightly rewritten

So we know that:

• i is post-incremented, so when i == N-1 before the return statement, this will return N instead of wrapping to 0 immediately
  • Is this intended? Most of the time, the intent is to use N as an exclusive upper bound
• The variable name i suggests a local variable by naming convention, but is it really?
  • Need to double check if it's a field, due to side-effect

In comparison:

return (i == N-1) ? 0 : i+1; // proposed alternative

Here we know that:

• i is not modified, doesn't matter if it's local variable or field
• When i == N-1, the returned value is 0, which is more typical scenario

---

The % approach

Alternatively, you can also use the % version as follows:

return (i+1) % N;

What's the problem with %? Well, the problem is that even though most people think it's the modulo operator, it's NOT! It's the remainder operator (JLS 15.17.3). A lot of people often get this confused. Here's a classic example:

boolean isOdd(int n) {
   return (n % 2) == 1; // does this work???
}

That code is broken!!! It returns false for all negative values! The problem is that -1 % 2 == -1, although mathematically -1 = 1 (mod 2).

% can be tricky, and that's why I recommend the ternary operator version instead. The most important part, though, is to remove the side-effect of the increment.

See also

• Wikipedia: modulo operation

Answer 7

Surely it would be more readable to use an if:

i++;
if (i >= buffer.length) 
{
  i = 0;
}
return i;

Depends a bit if buffer.length ever changes.

Answer 8

I prefer the condition approach even if we use unsigned type, modulo operation has drawbacks. Using modulo has a bad side effect when the number tested rolls back to zero

Example:

255 % 7 == 3

So if you use byte (unsigned char) for example, when the number roll after 255 (i.e. zero), it will not result to 4. Should result to 4 (when 256 % 7), so it rotates correctly. So just use testing(if and ternary operator) constructs for correctness

---

If for achieving performance, and if the number is multiple of 2 (i.e. 2, 4, 8, 16, 32, 64, ...), use & operator.

So if the buffer length is 16, use:

n & 15

If buffer length is 64, use 63:

n & 63

Those rotate correctly even if the number goes back to zero. By the way, if the number is multiple of 2, even the modulo/remainder approach would also fit the bill, i.e. it will rotate correctly. But I can hazard a guess that & operation is faster than % operation.

Answer 9

Personally, I prefer the modulo approach. When I see modulo, I immediately think of range limiting and looping but when I see the ternary operator, I always want to think more carefully about it simply because there are more terms to look at. Readability is subjective though, as you already pointed out in your tagging, and I suspect that most people will disagree with my opinion.

However, performance is not subjective. Modulo implies a divison operation which is often slower than a comparison against zero. Obviously, this is more difficult to determine in Java since we're not compiling to native code until the jitter kicks in.

My advice would be write which ever you feel is most appropriate (so long as it works!) and get a colleague (assuming you have one) to asses it. If they disagree, ask another colleague - then go with the majority vote. #codingbydemocracy

Answer 10

The first one will give you an ArrayIndexOutOfBoundsException because i is never actually reset to 0.

The second one will (probably) give you an overflow error (or related undesirable effect) when i == Integer.MAX_VALUE (which might not actually happen in your case, but isn't good practice, IMHO).

So I'd say the second one is "more correct", but I would use something like:

i = (i+1) % buffer.length;
return i;

Which I think has neither of the two problems.

I went ahead and tested everyone's code, and was sad to find that only one of the previous posts (at the time of this post's writing) works. (Which one? Try them all to find out! You might be surprised!)

public class asdf {

    static int i=0;
    static int[] buffer = {0,1,2};

    public static final void main(String args[]){
        for(int j=0; j<5; j++){
            System.out.println(buffer[getIndex()]);
        }
    }

    public static int getIndex(){
//      return (++i == buffer.length) ? 0: i;
//      return ++i % buffer.length;

//      i = (i++ == buffer.length) ? 0 : i;
//      return i;

//      i++;
//      if (i >= buffer.length) 
//      {
//        i = 0;
//      }
//      return i;

//      return (i+1 == buffer.length) ? 0 : i+1;

        i = (i+1) % buffer.length;
        return i;
    }

}

Expected output is: 1 2 0 1 2

Apologies in advance if there's a coding error on my part and I accidentally insult someone! x.x

PS: +1 for the previous comment about not using post-increment with equality checks (I can't actually upmod posts yet =/ )