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

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 w开发者_JS百科ould be the best way to implement this and are there any existing implementations?

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;
    }

}

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));
    }

}

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.

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.

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.

You can use the java.util.concurrent.atomic.AtomicInteger class to increment atomically. As for setting an upper bound and rolling back to 0, you'll need to do that externally...perhaps encapsulating all this within your own wrapper class.

Actually, it appears that you can use compareAndSet to check the upper bound, and then roll over to 0.

I have to create a similar circular ticker for a custom Akka Routing logic which had to be different than the default ones to avoid network overhead, since my logic is just to pick the next routee.

Note: Copied from the suggested Java 8 implementation:

import akka.routing.Routee;
import akka.routing.RoutingLogic;
import scala.collection.immutable.IndexedSeq;

import java.util.concurrent.atomic.AtomicInteger;

public class CircularRoutingLogic implements RoutingLogic {

  final AtomicInteger cycler = new AtomicInteger();

  @Override
  public Routee select(Object message, IndexedSeq<Routee> routees) {
    final int size = routees.size();
    return size == 0 ? null : routees.apply(cycler.getAndUpdate(index -> ++index < size ? index : 0));
  }
}

For highly-intensive circular counter incremented by multiple threads in parallel, I would recommend using LongAdder (since java 8, see the core idea inside Striped64.java), because it is more scalable compared to AtomicLong. It is easy to adapt it to the above solutions.

It is assumed that get operation is not so frequent in LongAdder. When calling counter.get, apply to it 'counter.get % max_number'. Yes, modulo-operation is expensive, but it is infrequent for this use-case, which should amortize the total performance cost.

Remember though, that get operation is non-blocking, nor atomic.