HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Lock-free thread-safe Fibonacci number generator

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
codereviewfibonacci-sequencejavastackoverflowlock-free
numberfibonaccifreegeneratorthreadsafelock

Problem

Here is my implementation of a lock-free thread-safe Fibonacci number generator. Is it correct? The idea is to use an immutable holder for previous and current numbers (since it's hard to change two values atomically at the same time) and AtomicReference which points to the current Fibonacci number.

Lock-free

public class FibonacciSequence {

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

    public FibonacciSequence() {
        currentFibNumberRef = new AtomicReference<>(new FirstFibonacciNumber());
    }

    public BigInteger next() {
        while (true) {
            FibonacciNumber currFibNumber = currentFibNumberRef.get();
            if (currentFibNumberRef.compareAndSet(currFibNumber, currFibNumber.next()))
                return currFibNumber.value();
        }
    }


Testing

```
public static void main(String[] args) {
testFibonacciNumberCorrectness();
// todo add thread-safe test
}

private static void testFibonacciNumberCorrectness() {
int[] some = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,
233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946,
17711, 28657, 46368, 75025, 121393, 196418, 317811};
Fib

Solution

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 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 Stat

Code Snippets

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

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


}
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
fibgen.FibonacciSequence Retries    74188 Statistics: 50000 BigIntegers with hashXOR 212738101 - Next=5.206us Calc=1.280us all in 91.571ms
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

Context

StackExchange Code Review Q#74934, answer score: 7

Revisions (0)

No revisions yet.