I have taken this problem on as a little study in to lock efficiency, performance, and contention. As a result, I am posting a second answer with some additional information, and a different sort of review.
Note: The full console output from my harness is here in pastebin.com
First, my conclusion is that lock-free fib generator is a mistake. Reentrant locks are also a problem, and that the best performance comes from plain old synchronization.
So, to test this all, I created a basic interface:
package fibgen;
import java.math.BigInteger;
public interface FibGen extends AutoCloseable {
/**
* Get the next Fibonacci number in this sequence
* @return the next number
*/
public BigInteger next();
/**
* How many retries were needed in spin loops.
* @return the retry count
*/
public long retryCount();
/**
* because there may need to be some clean up in some generators.
*/
public void close();
}
Right, that's a tool to generate Fibonacci numbers in a way that is independent of the implementation.
Now, putting your original question code in to that framework, so you can see what I did using a familiar starting point, I got:
package fibgen;
import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
public class FibonacciSequence implements FibGen {
@Override
public void close() {
// nothing
}
private static class FibonacciNumber {
protected final BigInteger prev;
protected final BigInteger curr;
public FibonacciNumber(BigInteger prev, BigInteger curr) {
this.prev = prev;
this.curr = curr;
}
public FibonacciNumber next() {
return new FibonacciNumber(curr, prev.add(curr));
}
public BigInteger value() {
return curr;
}
}
private static final class FirstFibonacciNumber extends FibonacciNumber {
public FirstFibonacciNumber() {
super(null, BigInteger.valueOf(0L));
}
public FibonacciNumber next() {
return new FibonacciNumber(curr, BigInteger.valueOf(1L));
}
}
private final AtomicReference<FibonacciNumber> currentFibNumberRef;
private final AtomicLong retries = new AtomicLong();
public FibonacciSequence() {
currentFibNumberRef = new AtomicReference<>(new FirstFibonacciNumber());
}
@Override
public BigInteger next() {
while (true) {
FibonacciNumber currFibNumber = currentFibNumberRef.get();
if (currentFibNumberRef.compareAndSet(currFibNumber, currFibNumber.next()))
return currFibNumber.value();
retries.incrementAndGet();
}
}
@Override
public long retryCount() {
return retries.get();
}
}
OK, now you know how it hangs together, let's look at some of my output. After doing a lot of output, and running on my dual-core-with-hyperthreading laptop, I get the best results from 6 strategies as:
fibgen.FibGenQueue Retries 0 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=7.632us Calc=0.610us all in 104.814ms
fibgen.FibonacciSequence Retries 74188 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=5.206us Calc=1.280us all in 91.571ms
fibgen.FibGenLock Retries 0 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=6.338us Calc=0.551us all in 91.333ms
fibgen.FibGenRolfl Retries 4451265 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=4.677us Calc=0.618us all in 72.015ms
fibgen.FibGenSync Retries 0 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=4.695us Calc=0.611us all in 67.888ms
Let me explain the above results, using your generator:
fibgen.FibonacciSequence Retries 74188 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=5.206us Calc=1.280us all in 91.571ms
Your generator needed to spin-loop almost 75,000 times in order to generate 50,000 values in the sequence. A quality-checking XOR function has some value 212738101 (this is a good thing, I will explain later), and the average latency on the 'next()' call was 5.2 microseconds, the time to calculate the XOR function was an average of 1.3 microseconds, and the whole sequence was completed, in many threads, in 91.5 milliseconds.
Put another way, you ran 4 threads at 100% for 91.5 milliseconds, and you generated 125,000 fibonacci numbers (but only used 50,000).
Note, when I ran your code, I did it 10 times (after warmups), with the following results:
fibgen.FibonacciSequence Retries 70284 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=7.813us Calc=0.677us all in 132.730ms
fibgen.FibonacciSequence Retries 88643 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=6.030us Calc=0.695us all in 107.690ms
fibgen.FibonacciSequence Retries 81224 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=7.501us Calc=0.879us all in 121.851ms
fibgen.FibonacciSequence Retries 90017 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=7.992us Calc=0.749us all in 113.700ms
fibgen.FibonacciSequence Retries 89161 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=7.785us Calc=0.964us all in 117.558ms
fibgen.FibonacciSequence Retries 87775 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=5.022us Calc=0.912us all in 93.947ms
fibgen.FibonacciSequence Retries 80012 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=6.034us Calc=0.650us all in 105.458ms
fibgen.FibonacciSequence Retries 71632 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=4.862us Calc=0.640us all in 110.539ms
fibgen.FibonacciSequence Retries 74188 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=5.206us Calc=1.280us all in 91.571ms
fibgen.FibonacciSequence Retries 105237 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=6.891us Calc=0.905us all in 103.621ms
Note that the fastest run (91.5ms) has the slowest 'Calc' time. I am not sure why this happened. I believe the variances I see in your code are in part caused by the increased thrashing your algorithm puts on the garbage collector. The other algorithms result in more stable performance.
Compare your fastest time to the alternatives. I suggested one in the answer code I supplied before. In my test framework, it looks like:
package fibgen;
import java.math.BigInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
public class FibGenRolfl implements FibGen {
@Override
public void close() {
// Nothing here..
}
protected final AtomicReference<BigInteger> nextRef = new AtomicReference<>(BigInteger.ONE);
protected final AtomicReference<BigInteger> currRef = new AtomicReference<>(BigInteger.ZERO);
protected final AtomicLong retries = new AtomicLong();
@Override
public BigInteger next() {
BigInteger current = null;
long tries = -1L;
do {
// spin loop while someone else is updating the reference.
// updating is indicated by a null value in the reference.
tries++;
current = currRef.getAndSet(null);
} while (current == null);
BigInteger next = nextRef.get();
nextRef.set(next.add(current));
currRef.set(next);
if (tries > 0L) {
retries.addAndGet(tries);
}
return current;
}
@Override
public long retryCount() {
return retries.get();
}
}
Now, I claimed this is an improvement over your code, and, is it? It produces the result:
fibgen.FibGenRolfl Retries 4451265 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=4.677us Calc=0.618us all in 72.015ms
It ran about 25% faster overall than your code. The individual average latency on each next() call is slightly faster at 4.7us (instead of 5.2). The big difference, is that your code calculations are significantly slower, so my code 'spins' a lot faster.... While your code retried 75,000 times, my code retried 4.5million times. The difference is that your code computes and throws-away a fib number, whereas my code uses it as a spin-lock and only computes the fib number when it is free to do so.... hopefully that reduces memory churn... maybe. I create no garbage in my spins, your code makes two objects each wasted cycle.
So, I run all threads at 100%, but I get results slightly faster, on average, and my overall run time is reduced. I believe the imprved latency is because the BigInteger.add operation is relativey slow, and in your code, the 'latency' of each call is in increments of that time. For example, if an add takes 4us, then your code will return in either 4us, 8us, 12us, 16us, etc. My code, on the other hand, can 'delay' for partial amounts of time, and then return after a single 4us calculation.
But, if the partial delay is beneficial, would a blocking system be better than a spin system? Note that your algorithm kept 4 threads busy for 91.5ms, and mine kept threads busy for 72ms. Combined that's 370ms of CPU time vs. 290ms CPU time
I tried using a Reentrant lock instead, with the code:
package fibgen;
import java.math.BigInteger;
import java.util.concurrent.locks.ReentrantLock;
public class FibGenLock implements FibGen {
@Override
public void close() {
// Nothing here..
}
private BigInteger nextRef = BigInteger.ONE;
private BigInteger currRef = BigInteger.ZERO;
private final ReentrantLock lock = new ReentrantLock();
@Override
public BigInteger next() {
lock.lock();
try {
BigInteger current = currRef;
currRef = nextRef;
nextRef = current.add(currRef);
return current;
} finally {
lock.unlock();
}
}
@Override
public long retryCount() {
return 0;
}
}
That code is has about the same latency and overall elapsed time as your code, but, in terms of used CPU time, it blocks all threads except one, so it is 4-times more efficient than your code.
Now, the fastest result was using plain-jane synchronization. I believe it is fastest because there's only one memory-barrier activity (just one synchronization - whereas the Reentrant lock has two - a lock, and an unlock).
Here's the code:
package fibgen;
import java.math.BigInteger;
public class FibGenSync implements FibGen {
@Override
public void close() {
// Nothing here..
}
private BigInteger nextRef = BigInteger.ONE;
private BigInteger currRef = BigInteger.ZERO;
private final Object lock = new Object();
@Override
public BigInteger next() {
synchronized(lock) {
BigInteger current = currRef;
currRef = nextRef;
nextRef = current.add(currRef);
return current;
}
}
@Override
public long retryCount() {
return 0;
}
}
Note that this runs in 67ms, and has the same latency as the tight spin-lock mechanism. The major difference is in the fact that it wastes no CPU cycles. It's much more efficient.
That's the best algorithm.
As an aside, I through it would be interesting to try a queue, where one thread feeds Fib numbers in to the queue, and the other threads read it out. It was significantly slower than the alternatives, more complicated, and just generally ugly... here's the code for your reference:
package fibgen;
import java.math.BigInteger;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicLong;
public class FibGenQueue implements FibGen, Runnable {
private final ArrayBlockingQueue<BigInteger> queue = new ArrayBlockingQueue<>(64);
private AtomicBoolean active = new AtomicBoolean(true);
private AtomicLong retries = new AtomicLong();
public FibGenQueue() {
Thread t = new Thread(this, "FibGen");
t.setDaemon(true);
t.start();
}
@Override
public BigInteger next() {
try {
do {
BigInteger fib = queue.poll(1, TimeUnit.SECONDS);
if (fib != null) {
return fib;
}
retries.incrementAndGet();
} while (active.get());
} catch (InterruptedException ie) {
Thread.currentThread().interrupt();
}
throw new IllegalStateException("Attempt to read from an invalid queue");
}
@Override
public long retryCount() {
return retries.get();
}
@Override
public void run() {
BigInteger current = BigInteger.ZERO;
BigInteger next = BigInteger.ONE;
try {
while(true) {
if (queue.offer(current, 1, TimeUnit.SECONDS)) {
BigInteger tmp = next.add(current);
current = next;
next = tmp;
} else {
if (!active.get()) {
return;
}
}
}
} catch (InterruptedException ie) {
Thread.currentThread().interrupt();
} finally {
queue.clear();
active.set(false);
}
}
@Override
public void close() {
active.set(false);
}
}
Now, how was this all tested? Using the following framework, and some Java-8 magic:
package fibgen;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class FibTester {
private static final class BigIntCollector {
private long nextTime = 0L;
private long calcTime = 0L;
private long runTime = -1L;
private int count = 0;
private int hasXOR = 0;
public void accumulate(int index, FibGen gen) {
long start = System.nanoTime();
BigInteger big = gen.next();
long next = System.nanoTime();
hasXOR ^= big.hashCode();
long done = System.nanoTime();
nextTime += next - start;
calcTime += done - next;
count++;
}
public BigIntCollector merge (BigIntCollector toMerge) {
nextTime += toMerge.nextTime;
calcTime += toMerge.calcTime;
count += toMerge.count;
hasXOR ^= toMerge.hasXOR;
return this;
}
@Override
public String toString() {
double factor = (1000.0 * count);
return String.format("Statistics: %d BigIntegers with hashXOR %d - Next=%.3fus Calc=%.3fus all in %.3fms", count, hasXOR,
nextTime / factor, calcTime / factor, runTime / 1000000.0);
}
public void runTime(long time) {
runTime = time;
}
}
public static final String benchmark(Supplier<FibGen> supplier, int volume) {
long start = System.nanoTime();
try (FibGen gen = supplier.get()) {
BigIntCollector coll = IntStream.range(0, volume).parallel()
.collect(BigIntCollector::new, (c, i) -> c.accumulate(i, gen), (a,b) -> a.merge(b));
coll.runTime(System.nanoTime() - start);
return String.format("%25s Retries %8d %s", gen.getClass().getName(), gen.retryCount(), coll.toString());
}
}
public static void main(String[] args) {
List<Supplier<FibGen>> suppliers = new ArrayList<>();
suppliers.add(FibonacciSequence::new);
suppliers.add(FibGenRolfl::new);
suppliers.add(FibGenQueue::new);
suppliers.add(FibGenSync::new);
suppliers.add(FibGenLock::new);
dump(suppliers, 100);
for (Supplier<FibGen> supplier : suppliers) {
System.out.println(benchmark(supplier, 1000));
}
for (int i = 0; i < 100; i++) {
for (Supplier<FibGen> supplier : suppliers) {
benchmark(supplier, 1000);
}
}
for (Supplier<FibGen> supplier : suppliers) {
System.out.println();
for (int i = 0; i < 10; i++) {
System.out.println(benchmark(supplier, 50000));
}
}
}
private static void dump(List<Supplier<FibGen>> suppliers, int count) {
FibGen[] gens = suppliers.stream().map(s -> s.get()).collect(Collectors.toList()).toArray(new FibGen[suppliers.size()]);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= count; i++) {
sb.setLength(0);
sb.append(String.format("%5d ", i));
for (FibGen fg : gens) {
sb.append(String.format("%20s ", fg.next()));
}
System.out.println(sb.toString());
}
}
}
