第五章 (5): キャッシュの実装

あるスレッドAが高価な計算処理Xを計算中の場合に、別のスレッドBがXの計算結果を得たい場合があるとする。この場合、BはAの計算が終わるのを待ち、Xを返すとメモリを節約することが出来る。ところがコレは通常のConcurrentMapを使ったキャッシュでは実現出来ない。ConcurrentMapで見ることが出来るのは、「計算結果があるか、無いか」だけである。「計算結果があるか、無いか」に加えて、「計算中か否か」を見れないといけない。タスクが継続中か完了したかを判断するにはFutureTaskを使う。

public static interface Computable<A, V> {
	V compute(A arg) throws InterruptedException;
}

// FutureTaskをキャッシュすることにより, 同じ高価な計算を2度行わないようにする
public static class Memoizer<A, V> implements Computable<A, V> {

	private final ConcurrentMap<A, Future<V>> cache = new ConcurrentHashMap<A, Future<V>>();
	private final Computable<A, V> delegate;

	public Memoizer(Computable<A, V> computable) {
		this.delegate = computable;
	}

	public V compute(final A arg) throws InterruptedException {
		while (true) {
			Future<V> future = cache.get(arg);
			if (future == null) {
				Callable<V> eval = new Callable<V>() {
					public V call() throws Exception {
						return delegate.compute(arg);
					}
				};
				FutureTask<V> ft = new FutureTask<V>(eval);
				// アトミックにputする
				future = cache.putIfAbsent(arg, ft);
				if (future == null) {
					future = ft;
					ft.run();
				}
			}
			try {
				// 結果を取得する: 計算完了まで待機する
				return future.get();
			} catch (CancellationException e) {
				cache.remove(arg, future);
			} catch (ExecutionException e) {
				// TODO
			}
		}
	};