How to convert recursion into iteration with LoadingCache?

Question

I completely rewrote this question as the original one was unsolvable. In order to keep it simple I'm using Fibonacci numbers a toy example.

The trivial recursive cached computation ends with a very long stacktrace, just as expected. That's why I'd like to have an abstract class like IterativeLoadingCache, which I could extend like here by something like

@Override
protected Integer computeNonRecursivelly(Integer key) {
    final Integer x1 = getOrEnqueue(key-1);
    final Integer x2 = getOrEnqueue(key-2);
    if (x1==null) return null;
    if (x2==null) return null;
    return x1+x2;
}

and which would take care about all the caching and computation without using recursion.

I'm really not looking for an efficient computation of Fibonacci numbers. I need something allowing to use caching together with recursive functions, where the recursion depth can get arbitrary high.

I've got already a sort of solution, but it's quite inefficient and very ugly, so I hope to get some good advice. I'm also curious if somebody else needs it or maybe already implemented it.

Answer 1

Since you've rewritten your question, here's a new answer.

First, it looks to me like your implementation of computeNonRecursivelly is still recursive, since getOrEnqueue calls it.

I don't think you can use a Cache directly, because you need to have 2 steps in your computation: one that states the dependencies for the wanted value, and one that does the computation once the dependencies are met. It will only work if you never have cyclic dependencies, though (it's the same requirement as in the recursion).

That way, you can queue the dependencies which are not already in the cache (and their dependencies, etc.) then compute them in the correct order. Something along the lines of :

public abstract class TwoStepCacheLoader<K, V> extends CacheLoader<K, V> {
    public abstract Set<K> getDependencies(K key);
}

public class TwoStepCache<K, V> extends ForwardingLoadingCache<K, V> {
    private final TwoStepCacheLoader<K, V> loader;
    private LoadingCache<K, V> cache;

    public TwoStepCache(TwoStepCacheLoader<K, V> loader) {
        this.loader = loader;
        cache = CacheBuilder.newBuilder().build(loader);
    }

    @Override
    public V get(K key) 
            throws ExecutionException {
        V value = cache.getIfPresent(key);
        if (value != null) {
            return value;
        }

        Deque<K> toCompute = getDependenciesToCompute(key);
        return computeDependencies(toCompute);
    }

    private Deque<K> getDependenciesToCompute(K key) {
        Set<K> seen = Sets.newHashSet(key);
        Deque<K> dependencies = new ArrayDeque<K>(seen), toCompute = new ArrayDeque<K>(seen);
        do {
            for (K dependency : loader.getDependencies(dependencies.remove())) {
                if (seen.add(dependency) && // Deduplication in the dependencies
                    cache.getIfPresent(dependency) == null) {
                    // We need to compute it.
                    toCompute.push(dependency);
                    // We also need its dependencies.
                    dependencies.add(dependency);
                }
            }
        } while (!dependencies.isEmpty());
        return toCompute;
    }

    private V computeDependencies(Deque<K> toCompute)
            throws ExecutionException {
        V value;
        do {
            value = cache.get(toCompute.pop());
        } while (!toCompute.isEmpty());
        // The last computed value is for our key.
        return value;
    }

    @Override
    public V getUnchecked(K key) {
        try {
            return get(key);
        } catch (ExecutionException e) {
            throw new UncheckedExecutionException(e.getCause());
        }
    }

    @Override
    protected LoadingCache<K, V> delegate() {
        return cache;
    }
}

Now you can implement a TwoStepCacheLoader that calls the cache safely:

public class Fibonacci {
    private LoadingCache<Integer, Integer> cache = new TwoStepCache<Integer, Integer>(new FibonacciCacheLoader());


    public int fibonacci(int n) {
        return cache.getUnchecked(n);
    }


    private class FibonacciCacheLoader extends TwoStepCacheLoader<Integer, Integer> {
        @Override
        public Set<Integer> getDependencies(Integer key) {
            if (key <= 1) {
                return ImmutableSet.of();
            }
            return ImmutableSet.of(key - 2, key - 1);
        }


        @Override
        public Integer load(Integer key)
                throws Exception {
            if (key <= 1) {
                return 1;
            }
            return cache.get(key - 2) + cache.get(key - 1);
        }
    }
}

I've run a unit test on it, it seems to run correctly.