5

I was surprised that Java's AtomicInteger and AtomicLong classes don't have methods for modular increments (so that the value wraps around to zero after hitting a limit).

I figure I've got to be missing something obvious. What's the best way to do this?

For example, I want to share a simple int between threads, and I want each thread to be able to increment it, say, mod 10.

I can create a class which uses synchronization/locks, but is there a better, easier way?

4 Answers4

16

Just mod 10 the value when you read from it?

public class AtomicWrappingCounter {
  private final AtomicLong counter = new AtomicLong();
  private final int max;

  public AtomicWrappingCounter(int max) {
    this.max = max;
  }

  public int get() {
    return (int) (counter.get() % max);
  }

  public int incrementAndGet() {
    return (int) (counter.incrementAndGet() % max);
  }
}

Obviously if you might increment this counter more than Long.MAX_VALUE times, you couldn't use this approach, but 9 quintillion is a lot of times to be incrementing (around 292 years at a rate of 1 per nanosecond!).

ColinD
  • 108,630
  • 30
  • 201
  • 202
  • Don't these methods need to be synchronized, ColinD? What if one thread is inside incrementAndGet(), and the increment has completed, but not the modulo, and a different thread calls get() and it returns the incremented but not modulo'ed value? –  Oct 19 '16 at 21:55
  • 1
    @Mark: No. The modulo is local to each thread. The `AtomicLong` will ensure that once `incrementAndGet()` has been called on it, the other thread calling `get()` will see the new value. Both threads then modulo the value on their own, and each sees the expected final result. – ColinD Oct 24 '16 at 01:53
13

In Java 8 you can use getAndUpdate (and updateAndGet) in AtomicInteger.

For example if we want to have a counter that wraps to zero each time it hits 10.

AtomicInteger counter = new AtomicInteger(0);

// to get & update
counter.getAndUpdate(value -> (value + 1) % 10)
cakraww
  • 2,493
  • 28
  • 30
9

I would think the simplest way is to build a wrapping counter yourself which stores it's values in an AtomicInteger, something like

public class AtomicWrappingCounter {
    private AtomicInteger value;
    private final int max;

    public AtomicWrappingCounter(int start, int max) {
        this.value = new AtomicInteger(start);
        this.max = max;
    }

    public int get() {
        return value.get();
    }

    /* Simple modification of AtomicInteger.incrementAndGet() */
    public int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = (current + 1) % max;
            if (value.compareAndSet(current, next))
                return next;
        }
    }
}

Why doesn't AtomicInteger provide something like this itself? Who knows, but I think the intention of the concurrency framework authors were to provide some building blocks you could use to better create your own higher-level functions.

JT.
  • 633
  • 1
  • 8
  • 9
matt b
  • 138,234
  • 66
  • 282
  • 345
  • They only really need to implement `get` and `compareAndSet` in the framework. All the other methods can be built on those. – finnw Jan 26 '11 at 22:54
  • 1
    Clever - but I suspect that under heave contention this would actually perform worse than synchronization. – Michael Borgwardt Jan 26 '11 at 23:09
  • @Michael can you elaborate why? Would it be any different than AtomicInteger's own behavior? – matt b Jan 26 '11 at 23:35
  • @matt: The more threads execute your code simultaneously, the higher the likelyhood that `compareAndSet()` will fail and you'll have to retry. If contention is very high, all threads will spend most of their time running through the loop repeatedly. This is different from `compareAndSet()` itself, which is (on hardware that supports it) implemented by actually atomic CPU instructions. – Michael Borgwardt Jan 26 '11 at 23:39
  • 1
    @Michael: The thing is, `incrementAndGet()` is implemented just like his method here except without the mod. – ColinD Jan 26 '11 at 23:40
  • @ColinD: ...and it performs worse than synchronization under heavy contention: http://stackoverflow.com/questions/3556283/in-java-what-is-the-performance-of-atomicinteger-compareandset-versus-synchroni/3556314#3556314 – Michael Borgwardt Jan 26 '11 at 23:46
  • Well michael is correct. Under heavy contention lock free implementations with a non infinite consesnus will perform worse then a locking alternative. And to answer matt b, the same type of issue applies to all non compare and set operartions for example getAndAdd. – John Vint Jan 26 '11 at 23:55
  • To further the proof. You can look at a LinkedBlockingQueue and ConcurrentLinkedQueue and see that under normal contention CLQ is far superior then LBQ but under heavy contention LBQ is better – John Vint Jan 26 '11 at 23:57
  • 2
    Right, so in such a situation you wouldn't want to use Atomic classes anyway, a situation which basically negates the core of this question. Good info to know though. – matt b Jan 26 '11 at 23:58
  • I don't want to think through what would happen if `start` was outside of `[0, max)` or if `max` was non-positive. `value` should be `final`. / Also `compareAndSet` should be called on `value` and it's very odd to have a cas-loop with a return like that instead of being `do-while`. – Tom Hawtin - tackline Mar 17 '11 at 14:21
  • @Tom Hawtin I'm not sure I understand what you mean - as mentioned above, the `incrementAndGet()` in my sample is the exact same as the implementation in the Sun JDK of AtomicInteger with a slight modification. The cas-loop with a return is direct from Sun code. As for validating parameters passed to the constructor, this is just a code sample and proper validation / asserting invariants is an exercise best left to the reader. – matt b Mar 17 '11 at 14:39
  • In the above code, max will never be reached. We should mod with max + 1 instead. – Akshay Gehi Nov 12 '16 at 07:00
4

What's difficult about adding a synchronized modifier or block to your addModular() method?

The reason why the Atomic classes don't have this functionality is that they're based on specific atomic hardware instructions offered by current CPUs, and modular arithmetic cannot be implemented by those without resorting to locking or other more complex and potentially inefficient algorithms like the one suggested by matt.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720