How to implement a concurrent circular ticker (counter) in Java?

Question

I want to implement a circular counter in Java. The counter on each request should increment (atomically) and on reaching an upper limit should roll over to 0.

What would be the best way to implement this and are there any existing implementations?

Solution 1

If you're that worried about contention using either CAS or synchronized then you could consider something more sophisticated like the proposed JSR 166e LongAdder (source, javadoc).

That's a straightforward counter with low contention on multithreaded access. You could wrap that to expose (current value mod max value). That is, don't store the wrapped value at all.

Solution 2

It is easy to implement such a counter atop AtomicInteger:

public class CyclicCounter {

    private final int maxVal;
    private final AtomicInteger ai = new AtomicInteger(0);

    public CyclicCounter(int maxVal) {
        this.maxVal = maxVal;
    }

    public int cyclicallyIncrementAndGet() {
        int curVal, newVal;
        do {
          curVal = this.ai.get();
          newVal = (curVal + 1) % this.maxVal;
        } while (!this.ai.compareAndSet(curVal, newVal));
        return newVal;
    }

}

Solution 3

With Java 8

public class CyclicCounter {

    private final int maxVal;
    private final AtomicInteger counter = new AtomicInteger(0);

    public CyclicCounter(int maxVal) {
      this.maxVal = maxVal;
    }

    public long incrementAndGet() {
        return counter.accumulateAndGet(1, (index, inc) -> (++index >= maxVal ? 0 : index));
    }

}

Solution 4

If you use the modulus operator, you could just increment and return the modulus. Unfortunately the modulus operator is expensive, so I encourage other solutions where performance is important.

public class Count {
    private final AtomicLong counter = new AtomicLong();
    private static final long MAX_VALUE = 500;
    public long getCount() {
        return counter.get() % MAX_VALUE;
    }
    public long incrementAndGet(){
        return counter.incrementAndGet() % MAX_VALUE;

    }
}

You would have to solve the Long.MAX_VALUE case as well.

Solution 5

I personally think the AtomicInteger solution is a little ugly as it introduces a race-condition which means your update attempt could "fail" and have to be repeated (by iterating within the while loop) making the update time less deterministic than performing the entire operation within a critical section.

Writing your own counter is so trivial I'd recommend that approach. It's nicer from an OO-perspective too as it only exposes the operations you're allowed to perform.

public class Counter {
  private final int max;
  private int count;

  public Counter(int max) {
    if (max < 1) { throw new IllegalArgumentException(); }

    this.max = max;
  }

  public synchronized int getCount() {
    return count;
  }

  public synchronized int increment() {
    count = (count + 1) % max;
    return count;
  }
}

EDIT

The other problem I perceive with the while loop solution is that given a large number of threads attempting to update the counter you could end up with a situation where you have several live threads spinning and attempting to update the counter. Given that only 1 thread would succeed, all other threads would fail causing them to iterate and waste CPU cycles.

View more solutions

Comments

[GreenMatt]

You'll should also implement toString() if you think you'll ever want to print a Counter.

[sheki]

Performance wise the Atomic Integer seems to be faster. See gist.github.com/1245597

[CPerkins]

Adamski, all the while loop does is to provide the benefits we normally get from synchronization. Your solution will have the same non-deterministic update time (from the standpoint of the caller).

[Adamski]

@sheki: The test code you've referenced only times a single thread accessing the counter. The real slowdown with the while loop approach is due to thread contention whereby several live threads end up competing and hence spinning in the while loop wasting CPU cycles.

[Adamski]

@CPerkins: With my solution if multiple threads attempt to call increment() simultaneously I would hope that they would gain access in the order they blocked on the method call. I don't think this is guaranteed by the language spec but I would hope a sensible VM implementation would use some kind of queue data structure. However, as per my previous comment my main issue with the while loop solution is that you could end up with many live thread spinning and competing to update the counter, wasting CPU cycles.

[CPerkins]

@Adamski, I see your point. I did think that the spec guaranteed sequential access (never really thought about it, just assumed that would be true), so that's an interesting thing to learn. Your new edit about spinning is intriguing. Seems like the relative speed would end up being a function of the number of threads wanting to simultaneously update it. If I had access to a true multiprocessor machine, I'd very much like to test this. Maybe I'll poke around a bit.

[Adamski]

@CPerkins: Actually after speaking to my colleagues they seem to prefer the while-loop approach with the justification that compareAndSet doesn't cause any blocking (as it typically relies on a machine level "test and set" instruction). The point was made that if thread contention does occur then there are bigger problems at hand, namely that the counter is not keeping up with the threads using it (which makes my point about spinning largely redundant).

[CPerkins]

@Adamski Fair enough. Thanks again for the note about synchronization not guaranteeing order.

[Erdinç Taşkın]

Not too important but, counter never being equal to max value. We would change as count = (count + 1) % (max + 1);

[igor.zh]

Does LongAdder have get method? Do you mean sum()? sum(), yes, is non-atomic, so wouldn't it pose a problem with rolling over upper limit to 0? Anyway, it's interesting to see actual implementation...

[Renato Back]

I wonder if this would really be atomic if thread looses priority between this.ai.get() and } while (!this.ai.compareAndSet(curVal, newal));

[Guido Medina]

We are talking Java 8 here, hence you have to take into account how AtomicInteger changed from Java 7 to 8, basically get and add or add and get are done at the assembly level -XADD- which is explained here: ashkrit.blogspot.com/2014/02/… LongAdder is the wrong tool for this, because you need each sum every time you increment.

[TJR]

What do you do when counter exceeds long?

[expert]

How would you implement atomic rollover to zero with LongAdder ?

[igor.zh]

@GuidoMedina, How accurate is this blog you referred to? In Java 8 sun.misc.Unsafe accumulation methods still call compareAndSwapInt/Long methods. Maybe these CAS methods do not actually invoke CAS processor instruction, but these are native methods, so how can we be sure of all platforms; after all XADD is platform-specific instruction, is it not?

[Guido Medina]

Is not platform specific, is JVM specific, prior to JDK 8 it was done in two steps where starting from JDK 8 and forward it is done in a single CPU atomic op, Google "JDK 8 vs 7 XADD" and you will find something like this: ashkrit.blogspot.com/2014/02/…