Possible to safely increment BigInteger in a thread safe way, perhaps with AtomicReference, w/o locking?
Asked Answered
D

2

14

A lot of our code is legacy but we are moving to a "Big Data" back-end and I'm trying to evangelize the newer API calls, encourage the use of the latest Spring libraries etc. One of our problems is application layer ID generation. For reasons I don't understand, a higher authority wants sequential BigInteger's. I would have made them random with re-generate and re-try on failed insertions but I done got vetoed.

Grumbling aside, I'm in a position where I need to increment and get a BigInteger across threads and do it in a safe and performant manner. I've never used AtomicReference before but it looks pretty close to perfect for this application. Right now we have a synchronized code block which hurts our performance pretty badly.

Is this the right way to go? Syntax examples?

I should mention that the way this module works, it hits the database using a Stored Procedure to grab a range of values to use. Tens of thousands at a time so that it only happens maybe once in 20 minutes. This keeps the various servers from stepping on each-other but it also adds the wrinkle of having to set the BigInteger to an arbitrarily subsequent value. Of course, that needs to be thread safe also.

P.S. I still think my random generation idea is better than handling all this threading stuff. A BigInteger is a ridiculously large number and the odds of ever generating the same one twice have to be close to nil.

Delphine answered 22/12, 2012 at 20:53 Comment(5)
Doesn't seem like AtomicReference does it for you without locking. But unless you need integers larger than longs, I would be surprised if BigInteger wasn't slowing you down. Try to convince them to go with AtomicLong.Sandrocottus
I'll look into that. Regardless, I'm still professionally curious about the answer. ;-) Especially because they might veto me again. Politics.Delphine
AtomicReference (like the other Atomic.. classes) do not use locking.Dowel
Regarding the non-locking for AtomicReference, the impression I got from the documentation was that it was somewhat (at least a little) system dependent.... so while it wasn't guaranteed, it was what one might expect. For example, on my ancient 32 bit Flintstonian Stone-Box-With-A-Bird-In-It desktop dev box, one might expect the processor wouldn't be advanced enough to support it... but on the actual server after deployment this would seem significantly more likely.Delphine
From 'Java Concurrency in Practice' : "in the worst case if a CAS-like instruction is not available the JVM uses a spin lock."Dowel
D
14

It is possible using AtomicReference here's a quick draft :

public final class AtomicBigInteger {

    private final AtomicReference<BigInteger> valueHolder = new AtomicReference<>();

    public AtomicBigInteger(BigInteger bigInteger) {
        valueHolder.set(bigInteger);
    }

    public BigInteger incrementAndGet() {
        for (; ; ) {
            BigInteger current = valueHolder.get();
            BigInteger next = current.add(BigInteger.ONE);
            if (valueHolder.compareAndSet(current, next)) {
                return next;
            }
        }
    }
}

It is basically a copy of the AtomicLong code for incrementAndGet()

Dowel answered 22/12, 2012 at 21:9 Comment(8)
Didn't notice this answer while I was writing mine :)Housewarming
Happens to me all the time :)Dowel
Yes, I was just looking at that code, here: docjar.com/html/api/java/util/concurrent/atomic/…Delphine
It occurs to me now that I might need an AtomicLong in an AtomicReference... The problem is that I also have to set the value in a threadsafe manner due to the occasional SP calls to get a new range of values for use.Delphine
Nope. A review of the API shows that it has all the requisite get/set routines that AtomicReference does.Delphine
So why didn't anyone claim that BigInteger was thread safe by right of immutablity? ;-) This would not necessarily be true according to some of the things I've read but it should be a widely held belief.Delphine
BigInteger is thread safe because it is immutable. However, a class that has a reference to a BigInteger, and which allows that reference to change is not immutable. The problem is not BigInteger, it's the client.Dowel
Actually it was a JVM bug, since resolved. There was a big row over it at the time but it was quite a while ago.Delphine
S
10

This becomes more manageable and easier to understand using the accumulateAndGet or getAndAccumulate introduced in Java 8. These allow you to atomically update the value by supplying an accumulator function that sets the value to the result of the function, and also either returns the previous or calculated result depending on what you need. Here is an example of what that class might look like, followed by a simple example I wrote up that uses it:

import java.math.BigInteger;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicReference;

public final class AtomicBigInteger {

  private final AtomicReference<BigInteger> bigInteger;

  public AtomicBigInteger(final BigInteger bigInteger) {
    this.bigInteger = new AtomicReference<>(Objects.requireNonNull(bigInteger));
  }

  // Method references left out for demonstration purposes
  public BigInteger incrementAndGet() {
    return bigInteger.accumulateAndGet(BigInteger.ONE, (previous, x) -> previous.add(x));
  }

  public BigInteger getAndIncrement() {
    return bigInteger.getAndAccumulate(BigInteger.ONE, (previous, x) -> previous.add(x));
  }

  public BigInteger get() {
    return bigInteger.get();
  }
}

An example using it:

import java.math.BigInteger;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ABIExample {

  private static final int AVAILABLE_PROCS = Runtime.getRuntime().availableProcessors();
  private static final int INCREMENT_AMOUNT = 2_500_000;
  private static final int TASK_AMOUNT = AVAILABLE_PROCS * 2;
  private static final BigInteger EXPECTED_VALUE = BigInteger.valueOf(INCREMENT_AMOUNT)
                                                             .multiply(BigInteger
                                                                           .valueOf(TASK_AMOUNT));

  public static void main(String[] args)
      throws InterruptedException, ExecutionException {
    System.out.println("Available processors: " + AVAILABLE_PROCS);


    final ExecutorService executorService = Executors
        .newFixedThreadPool(Runtime.getRuntime().availableProcessors());

    final AtomicBigInteger atomicBigInteger = new AtomicBigInteger(BigInteger.ZERO);

    final List<Callable<Void>> incrementTasks =  IntStream.rangeClosed(1, TASK_AMOUNT)
             .mapToObj(i -> incrementTask(i, atomicBigInteger))
             .collect(Collectors.toList());
    final List<Future<Void>> futures = executorService.invokeAll(incrementTasks);
    for (Future<Void> future : futures) {
      future.get();
    }
    executorService.shutdown();
    executorService.awaitTermination(30, TimeUnit.SECONDS);
    System.out.println("Final value: " + atomicBigInteger.get());
    final boolean areEqual = EXPECTED_VALUE.equals(atomicBigInteger.get());
    System.out.println("Does final value equal expected? - " + areEqual);
  }

  private static Callable<Void> incrementTask(
      final int taskNumber,
      final AtomicBigInteger atomicBigInteger
  ) {
    return () -> {
      for (int increment = 0; increment < INCREMENT_AMOUNT; increment++) {
        atomicBigInteger.incrementAndGet();
      }
      System.out.println("Task #" + taskNumber + " Completed");
      return null;
    };

  }
}

And an output from running the example on my machine:

Available processors: 8
Task #3 Completed
Task #8 Completed
Task #7 Completed
Task #6 Completed
Task #5 Completed
Task #2 Completed
Task #4 Completed
Task #1 Completed
Task #9 Completed
Task #10 Completed
Task #11 Completed
Task #13 Completed
Task #16 Completed
Task #12 Completed
Task #14 Completed
Task #15 Completed
Final value: 80000000
Does final value equal expected? - true
Saturation answered 9/4, 2016 at 16:54 Comment(5)
I understand the previous answer but not this one. I've not had much opportunity to use "->" as yet, so that may or may not be why. Where are "previous" and "x" coming from?Delphine
@Delphine Java 8 introduced lambda expressions. There is a tutorial from Oracle here that is more comprehensive than I can explain. I recommend going through that. Basically, the *accumulate* methods on AtomicReference allow you to pass in a BinaryOperator that invokes the method in an atomic way. BinaryOperator is a @FunctionalInterface. The previous and x are the parameters to the method being invoked. In the case above, both parameters are being passed into the method.Saturation
@mkobit: I think your increment methods could be written more clearly with getAndUpdate/updateAndGet: bigInteger.getAndUpdate(BigInteger.ONE::add)Tsai
@Tsai Probably! I tried to "mirror" the accepted answer, to show a contrast between the two and attempt to demonstrate the different between the *andGet and the *andAccumulate type methods. I do agree with you that the API for this class could be improved either by the way you suggested, or possible with other methods.Saturation
Even with accumulateAndGet the code becomes simpler with bigInteger.accumulateAndGet(BigInteger.ONE, BigInteger::add)Kentledge

© 2022 - 2024 — McMap. All rights reserved.