Android で LruCache

Android アプリ開発でキャッシュを実装した際に、メモリ（キャッシュサイズ）管理が必要になり、LruCacheの導入を検討した際の調査内容です。

LruCache とは

最近最も使われていないデータを最初に捨てるアルゴリズム LRU（Least Recently Used）のキャッシュ。
LruCache 内部では Map　を持っており、Map　と同様に Key-Value で値を保持できる。

使い方

基本的な使い方としては、インスタンス生成時に、キャッシュサイズの上限を指定し、使用するだけ。
デフォルトのキャッシュサイズは、要素数を表します。
また、キャッシュサイズは resize メソッドで変更可能です。

    @Test
    fun testPut() {
        val map1To3 = mapOf(1 to "one", 2 to "two", 3 to "three")
        // キャッシュサイズ3の LruCache を生成
        // デフォルトのキャッシュサイズは、要素数を表す
        val cache = LruCache<Int, String>(map1To3.size)
        // キャッシュサイズの上限まで要素を追加
        map1To3.forEach { (key, value) ->
            cache.put(key, value)
        }
        Assert.assertEquals(map1To3, cache.snapshot())

        // キャッシュサイズの上限を超えて要素を追加すると、最も使用されていない要素が削除される
        cache.put(4, "four")
        val map2To4 = mapOf(2 to "two", 3 to "three", 4 to "four")
        Assert.assertEquals(map2To4, cache.snapshot())
    }

キャッシュサイズ

sizeOf　メソッドをオーバーライドすることで、キャッシュで扱うサイズを変更することができる。
下記の例では、キャッシュサイズを要素数から要素の文字列に変更しています。

    @Test
    fun testSizeOf() {
        // キャッシュサイズ6の LruCache を生成
        val cache = object: LruCache<Int, String>(6) {
            // sizeOf をオーバーライドして LruCache で扱うサイズを文字数にする
            override fun sizeOf(key: Int?, value: String?): Int {
                return value?.length ?: 0
            }
        }

        // キャッシュサイズの上限を超えるまでは put 可能
        cache.put(1, "one")
        Assert.assertEquals(3, cache.size())
        cache.put(2, "two")
        Assert.assertEquals(6, cache.size())

        // キャッシュサイズの上限を超えると、追加するサイズに応じて、要素が削除される
        cache.put(3, "three")
        Assert.assertEquals(5, cache.size())
        Assert.assertEquals("three", cache[3])
    }

Key に紐づく要素が無かった場合の処理

create メソッドをオーバーライドすることで、存在しない key で get した場合の初期値を設定することができます。
下記の例では、"Default" という文字列をの要素を返しています。

    @Test
    fun testCreate() {
        // create メソッドを override しない場合に、存在しない key で get すると null が返る
        val cache = LruCache<Int, String>(6)
        Assert.assertNull(cache.get(1))

        // create メソッドを override することで、存在しない key で get した場合の初期値を設定できる
        val cacheOverrideCreate = object: LruCache<Int, String>(6) {
            // 初期値を設定
            override fun create(key: Int?): String {
                return "Default"
            }
        }
        Assert.assertEquals("Default", cacheOverrideCreate.get(1))
    }

削除時の処理

entryRemoved メソッドを override することで、要素が削除される場合に処理を行うことが出来ます。
entryRemoved は remove、put で要素が削除される場合や、キャッシュサイズの上限を超えて削除される場合に呼ばれます。
パラメータとして、key、value 意外に、「キャッシュサイズの上限を超えたことによる削除」かが判断できる evicted（Boolean） がわたされます。

    @Test
    fun testEntryRemoved() {
        var isEvicted = false
        var k: Int? = null
        var old: String? = null
        var new: String? = null

        // entryRemoved メソッドを override することで、要素が削除される場合に処理が行える
        val cache = object: LruCache<Int, String>(1) {
            override fun entryRemoved(
                evicted: Boolean,
                key: Int?,
                oldValue: String?,
                newValue: String?
            ) {
                isEvicted = evicted
                k = key
                old = oldValue
                new = newValue
            }
        }

        // 削除される要素がない場合は、entryRemoved は呼ばれない
        cache.put(1, "one")
        Assert.assertFalse(isEvicted)
        Assert.assertNull(k)
        Assert.assertNull(old)
        Assert.assertNull(new)

        // put で要素が削除される場合は、entryRemoved が呼ばれる（evicted は false）
        cache.put(1, "1")
        Assert.assertFalse(isEvicted)
        Assert.assertEquals(1, k)
        Assert.assertEquals("one", old)
        Assert.assertEquals("1", new)

        // remove で要素が削除される場合も、entryRemoved が呼ばれる（evicted は false、newValue は null）
        cache.remove(1)
        Assert.assertFalse(isEvicted)
        Assert.assertEquals(1, k)
        Assert.assertEquals("1", old)
        Assert.assertNull(new)

        // キャッシュサイズの上限により要素が削除される場合も、entryRemoved が呼ばれる
        // （evicted は true、newValue は null）
        cache.put(1, "1")
        cache.put(2, "2")
        Assert.assertTrue(isEvicted)
        Assert.assertEquals(1, k)
        Assert.assertEquals("1", old)
        Assert.assertNull(new)
    }

注意点

sizeOf をオーバーライドしてサイズを要素数意外にした場合は、cache 保存後にサイズを更新しないようにしなければなりません。
下記の例では、サイズをリストサイズにしていますが、リストサイズを put した後に更新すると resize のタイミングで IllegalStateException が発生します。

    @Test(expected = IllegalStateException::class)
    fun testException() {
        // sizeOf を override してサイズを List のサイズにする
        val cache = object: LruCache<Int, MutableList<String>>(2) {
            override fun sizeOf(key: Int?, value: MutableList<String>?): Int {
                return value?.size ?: 0
            }
        }
        cache.put(1, mutableListOf("one"))
        val value = cache.get(1)
        // キャッシュ外でサイズが変わるような処理を行う。
        value.add("1")
        value.add("いち")
        cache.put(2, mutableListOf("two"))
        // 下記の処理で、IllegalStateException が発生
        cache.resize(1)
    }

原意は LruCache 内部で保持しているキャッシュサイズに不整合が起きるためです。

java.lang.IllegalStateException: com.ykato.sample.kotlin.LruCacheTest$testException$cache$1.sizeOf() is reporting inconsistent results!
	at android.util.LruCache.trimToSize(LruCache.java:203)
	at android.util.LruCache.resize(LruCache.java:104)

キャッシュサイズが変わるような変更を行うときは、下記のように put しなおします。

    @Test
    fun testTrimToSize() {
        // sizeOf を override してサイズを List のサイズにする
        val cache = object: LruCache<Int, MutableList<String>>(2) {
            override fun sizeOf(key: Int?, value: MutableList<String>?): Int {
                return value?.size ?: 0
            }
        }
        cache.put(1, mutableListOf("one"))
        val value = cache.get(1)
        // キャッシュ外でサイズが変わるような処理を行う。
        cache.put(1, mutableListOf("one", "1", "いち"))
        cache.put(2, mutableListOf("two"))
        // Exception は発生しない
        cache.resize(1)
    }