12
\$\begingroup\$

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<FibonacciNumber> 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};
        FibonacciNumber currFibNumber = new FirstFibonacciNumber();

        for (int num : some) {
            assert num == currFibNumber.value().intValue();
            currFibNumber = currFibNumber.next();
        }
    }
}
\$\endgroup\$
5
\$\begingroup\$

BigInteger operations are slow. Each iteration through the process you are creating a new BigInteger, as well as a new FibonacciNumber instance.

These instances are likely more expensive to process (and garbage collect) than the time saved through lock-free management. Still, using a three-state operation you can solve this problem without the FibonacciNumber class:

protected final AtomicReference<BigInteger> nextRef = new AtomicReference<>(BigInteger.ONE);
protected final AtomicReference<BigInteger> currRef = new AtomicReference<>(BigInteger.ONE);

public BigInteger next() {
    BigInteger current = null;
    do {
        // spin loop while someone else is updating the reference.
        // updating is indicated by a null value in the reference.
        current = currRef.getAndSet(null);
    } while (current == null);
    BigInteger next = nextRef.get();
    nextRef.set(next.add(current));
    currRef.set(next);
    return current;
}

Note that the above code puts a waiting process in to a spin lock (100% CPU) instead of locking. This is the same as your code.

My preference would be to use a more traditional Lock (or even synchronization) and block threads that are waiting.

\$\endgroup\$
  • \$\begingroup\$ Are you sure these 2 statements "nextRef.set(next.add(current)); currRef.set(next);" can't be reordered during compile/run time? If so than currRef can be set before nextRef... \$\endgroup\$ – Serge Veras Dec 27 '14 at 16:42
  • \$\begingroup\$ @SergeVeras - quite sure. \$\endgroup\$ – rolfl Dec 27 '14 at 17:43
7
\$\begingroup\$

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

    }

}
\$\endgroup\$
3
\$\begingroup\$

I modified the sequence class' next method to work when called from other threads such as below in order to test it with multiple threads:

1   public BigInteger next() {
2           FibonacciNumber currFibNumber = currentFibNumberRef.get();
3           if (currentFibNumberRef.compareAndSet(currFibNumber,
4                   currFibNumber.next()))
5               return currFibNumber.value();
6           return currentFibNumberRef.get().value();
7   }

This will return the current value of the Fibonacci number if it is not updated.

Here is the test that I wrote for it:

@Test
public void testSequenceThreaded() throws InterruptedException,
        ExecutionException {
    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 };

    final int threads = 4;

    FibonacciSequence currFibNumber = new FibonacciSequence();

    ExecutorCompletionService<BigInteger> executor = new ExecutorCompletionService<BigInteger>(
            Executors.newFixedThreadPool(threads));

    for (int i = 0; i < some.length; i++) {
        executor.submit(new CallableNumber(currFibNumber));
    }

    for (int num : some) {
        Future<BigInteger> val = executor.take();
        int value = val.get().intValue();
        assertTrue("Expected " + num + " but got " + value,
                num == value);
    }
}

// Callable sequence that will return the next value of the fibonacci
// sequence.
private static class CallableNumber implements Callable<BigInteger> {

    private final FibonacciSequence sequence;

    public CallableNumber(FibonacciSequence sequence) {
        this.sequence = sequence;
    }

    @Override
    public BigInteger call() throws Exception {
        return sequence.next();
    }
}

There are various other ways to test the solution however this is the one that I chose.

With 4 threads I cannot get your solution to pass the test. Essentially, this is testing that the next method of the sequence returns the correct next value in the sequence. The solution allows for a race condition between lines (in my version) 2 and 3 of the next method. Additionally, if you update the value of the reference you are returning the old value not the new one.

\$\endgroup\$
  • \$\begingroup\$ Your code could end up with many threads getting the same value if they all (except 1) happen at the same time.... your code allows multiple threads to call 'next' with the same value, and has no correction if that happens. \$\endgroup\$ – rolfl Dec 26 '14 at 22:15
  • \$\begingroup\$ I agree. My code is just testing his code with a modification due to the implementation provided by the OP not allowing for concurrent execution. The while (true) doesn't allow for concurrent calls to next of the FibonacciSequence class. \$\endgroup\$ – nattyddubbs Dec 26 '14 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.