Recursion and caching

[Maaartin G]

I've already posted a similar question to SO [1], however it was quite confused and didn't carry over the idea (and got hardly any views since I fixed it), so I hesitantly decided to post here. Deeply recursive functions may easily lead to StackOverflowError, so it's often advisable to rewrite them iteratively. Normally, it's easy, but caching may complicate it a lot.

I'm pretty sure there could be a cache allowing to write a method recursively and converting it to iteration. I believe it could be a rather simple addition to existing Guava Cache (see the files linked in [1] for the idea). As there were hardly any views of my question since I reformulated it, I'm asking here:

- Do you agree it's (quite easily) doable?

- Do you think it's broadly usable?

- Do you think it's suitable for inclusion in Guava?

[1]: http://stackoverflow.com/questions/11153173/how-to-convert-recursion-into-iteration-with-loadingcache

[Louis Wasserman]

I'm...not sure.  In particular, I don't believe Cache was built with that sort of recursion in mind, and I suspect -- but I'm not sure -- that things might get hairy once concurrency gets into the picture.

If it were something we were going to support with Cache, do we need special support in the API?  I suppose there might be some chicken-and-egg issues if the CacheLoader needs a reference to the Cache, which needs a reference to the CacheLoader...

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

--
guava-...@googlegroups.com
Project site: http://guava-libraries.googlecode.com
This group: http://groups.google.com/group/guava-discuss
 
This list is for general discussion.
To report an issue: http://code.google.com/p/guava-libraries/issues/entry
To get help: http://stackoverflow.com/questions/ask (use the tag "guava")

[Maaartin G]

On Friday, August 24, 2012 6:39:09 PM UTC+2, Louis Wasserman wrote:

I'm...not sure.  In particular, I don't believe Cache was built with that sort of recursion in mind, and I suspect -- but I'm not sure -- that things might get hairy once concurrency gets into the picture.

I don't know.... it might get a bit complicated, but if solved properly it takes the burden from the user. It could allow a lot of useful things, e.g. adding an Executor to speed things up.

 

If it were something we were going to support with Cache, do we need special support in the API?

I'm thinking about an interface extending the existing one, but currently I'm only guessing how it could look like. A single method like `CacheLoader.load` surely can't suffice. A nice idea has been posted as an answer to my question on SO.

 

I suppose there might be some chicken-and-egg issues if the CacheLoader needs a reference to the Cache, which needs a reference to the CacheLoader...

Actually, (if you wanted a trivially recursive solution) you can write

private final LoadingCache<Integer, Integer> cache = CacheBuilder.newBuilder().build(

new CacheLoader<Integer, Integer>() {

@Override

public Integer load(Integer key) throws Exception {

if (key<=1) return 1;

return cache.get(key-1) + cache.get(key-2);

}

});

and it works since in the loader a reference to the enclosing class gets captured, rather then a reference to the not-yet-initialized member `cache`. So this should be no problem.

[Louis Wasserman]

Putting it another way: "A single method like `CacheLoader.load` surely can't suffice."  What would you prefer?  I'm just not seeing what other methods would possibly be of use in this scenario.

Louis Wasserman
wasserm...@gmail.com
http://profiles.google.com/wasserman.louis

[Maaartin G]

On Saturday, August 25, 2012 12:09:11 AM UTC+2, Louis Wasserman wrote:

> Putting it another way: "A single method like `CacheLoader.load` surely can't suffice."  What would you prefer?

The problem with `load` is that it must not call `cache.get` if we want to prevent stack overflow.

> I'm just not seeing what other methods would possibly be of use in this scenario.

You need something to break the recursion. I see two possibilities, both of them quite simple.

1. GET-OR-REQUEST

This was one of my first ideas:

public Integer load(Integer key) throws Exception {

if (key<=1) return 1;

Integer x1 = cache.getOrRequest(key-1, key);

Integer x2 = cache.getOrRequest(key-2, key);

return x1==null || x2==null ? null : x1+x2;

}

where `getOrRequest(x, master)` is similar to `getIfPresent(x)`. In case it returns `null`, it records that the value for `x` was requested when computing the value for `master`. If `load` returns null, the cache processes the requests iteratively, and finally calls `load(key)` again.

There would be something like `public final class ComputingCache extends AbstractLoadingCache` with this single additional method and the `CacheLoader` would be allowed to return `null` if used for the `ComputingCache`.

2. TWO-PHASE-LOADER

A more structured approach was given in

http://stackoverflow.com/a/12108459/581205

Basically, the `TwoPhaseLoader` has two methods, one for determining its dependencies, the other for computing the value when they're satisfied. Concerning the cache, nothing but a new private implementation is needed. His idea is nice, but it has some weaknesses, e.g. it's can't handle complicated recursion like

http://mathworld.wolfram.com/AckermannFunction.html

REMARKS

That all can be done on top of Guava, no changes are required. If it were part of Guava, then there could be some support in `CacheBuilder`, possibly also allowing to throw in some `ExecutorService`, that's all.

[Torbjorn Gannholm]

This discussion reminds me of a LazyExecutorService I wrote once. Each Callable is "submitted" to the executor service, but isn't evaluated until you call get() on the returned Future. Obviously calculation/evaluation is done once-only.