From 30bfa5b1be62652fc07292d36ed1261edbcdb362 Mon Sep 17 00:00:00 2001 From: Martin Odersky Date: Sun, 3 Mar 2013 14:53:04 +0100 Subject: New LRU Cache implementation --- src/dotty/tools/dotc/core/SymDenotations.scala | 8 +- src/dotty/tools/dotc/util/LRUCache.scala | 176 ++++++++++++------------- src/dotty/tools/dotc/util/SixteenNibbles.scala | 27 ++++ src/dotty/tools/dotc/util/lrutest.sc | 40 ++++++ 4 files changed, 152 insertions(+), 99 deletions(-) create mode 100644 src/dotty/tools/dotc/util/SixteenNibbles.scala create mode 100644 src/dotty/tools/dotc/util/lrutest.sc (limited to 'src') diff --git a/src/dotty/tools/dotc/core/SymDenotations.scala b/src/dotty/tools/dotc/core/SymDenotations.scala index 0f519493a..975c4d6f1 100644 --- a/src/dotty/tools/dotc/core/SymDenotations.scala +++ b/src/dotty/tools/dotc/core/SymDenotations.scala @@ -577,7 +577,7 @@ object SymDenotations { extends SymDenotation(symbol, _owner, name, initFlags, initInfo, initPrivateWithin) { import NameFilter._ - import util.LRU8Cache + import util.LRUCache // ----- denotation fields and accessors ------------------------------ @@ -707,10 +707,10 @@ object SymDenotations { _definedFingerPrint } - private[this] var _memberCache: LRU8Cache[Name, PreDenotation] = null + private[this] var _memberCache: LRUCache[Name, PreDenotation] = null - private def memberCache: LRU8Cache[Name, PreDenotation] = { - if (_memberCache == null) _memberCache = new LRU8Cache + private def memberCache: LRUCache[Name, PreDenotation] = { + if (_memberCache == null) _memberCache = new LRUCache _memberCache } diff --git a/src/dotty/tools/dotc/util/LRUCache.scala b/src/dotty/tools/dotc/util/LRUCache.scala index b9d96a061..35dc97527 100644 --- a/src/dotty/tools/dotc/util/LRUCache.scala +++ b/src/dotty/tools/dotc/util/LRUCache.scala @@ -2,110 +2,96 @@ package dotty.tools.dotc.util import reflect.ClassTag -class LRU8Cache[Key >: Null, Value >: Null] { - - import LRU8Cache._ - - private var key0, key1, key2, key3, key4, key5, key6, key7: Key = null - private var val0, val1, val2, val3, val4, val5, val6, val7: Value = null - private var hits = 0 - private var entered = 0 - - private def incr(n: Int): Unit = { - val shift = n * width - hits = (hits ^ (mask << shift)) | (next((hits >>> shift) & mask) << shift) - } - - private def decr(n: Int): Unit = { - val shift = n * width - hits = (hits ^ (mask << shift)) | (prev((hits >>> shift) & mask) << shift) - } - - private def init(n: Int): Unit = { - val shift = n * width - hits = (hits ^ (mask << shift)) | (1 << shift) - } - - private def clear(n: Int): Unit = { - val shift = n * width - hits = (hits ^ (mask << shift)) - } - - private def evict(): Int = { - var min = hits & mask - var minIdx = 0 - hits = hits >>> width - if ((hits & mask) < min) { min = hits & mask; minIdx = 1 } - hits = hits >>> width - if ((hits & mask) < min) { min = hits & mask; minIdx = 2 } - hits = hits >>> width - if ((hits & mask) < min) { min = hits & mask; minIdx = 3 } - hits = hits >>> width - if ((hits & mask) < min) { min = hits & mask; minIdx = 4 } - hits = hits >>> width - if ((hits & mask) < min) { min = hits & mask; minIdx = 5 } - hits = hits >>> width - if ((hits & mask) < min) { min = hits & mask; minIdx = 6 } - hits = hits >>> width - if ((hits & mask) < min) { min = hits & mask; minIdx = 7 } - minIdx - } - - /** Return value associated with key, or `null` if key not present. - * Key must be different from `null`. +/** A least-recently-used cache for Key -> Value computations + * It currently keeps the last 8 associations, but this can be + * changed to anywhere between 2 and 16 by changing `LRUCache.Retained`. + * + * Implementation: We keep a ring of eight places, linked + * with the `next` data structure. The ring models a priority queue. + * `last` points to the last element of the queue, and + * `next(last)` to the first one. Lookups compare keys + * sequentially from first to last. Elements with successful lookup + * get promoted to be first in the queue. Elements are evicted + * at the `last` position. + */ +class LRUCache[Key >: Null : ClassTag, Value >: Null: ClassTag] { + import LRUCache._ + val keys = new Array[Key](Retained) + val values = new Array[Value](Retained) + var next = new SixteenNibbles(initialRing.bits) + var last = Retained - 1 // value is arbitrary + var lastButOne: Int = last - 1 + + def first = next(last) + + /** Lookup key, returning value or `null` for not found. + * As a side effect, sets `lastButOne` to the element before `last` + * if key was not found. */ def lookup(key: Key): Value = { - if (key == key0) { incr(0); return val0 } - if (key == key1) { incr(1); return val1 } - if (key == key2) { incr(2); return val2 } - if (key == key3) { incr(3); return val3 } - if (key == key4) { incr(4); return val4 } - if (key == key5) { incr(5); return val5 } - if (key == key6) { incr(6); return val6 } - if (key == key7) { incr(7); return val7 } - null + def lookupNext(prev: Int, current: Int, nx: SixteenNibbles): Value = { + val follow = nx(current) + if (keys(current) == key) { + if (current == last) last = prev + else { + next = next.updated(prev, follow) + next = next.updated(current, first) + next = next.updated(last, current) + } + values(current) + } else if (current == last) { + lastButOne = prev + null + } else + lookupNext(current, follow, nx) + } + lookupNext(last, first, next) } - /** Enter key/value association in cache */ + /** Enter key/value in cache at position `last`. + * As a side effect, sets `last` to `lastButOne`. + * If `lastButOne` was set by a preceding unsuccessful `lookup` + * for the same key, this means that the new element is now the + * first in the queue. If there was no preceding lookup, the element + * is inserted at a random position in the queue. + */ def enter(key: Key, value: Value): Unit = { - val idx = if ((entered & 7) == entered) entered else evict() - idx match { - case 0 => key0 = key; val0 = value - case 1 => key1 = key; val1 = value - case 2 => key2 = key; val2 = value - case 3 => key3 = key; val3 = value - case 4 => key4 = key; val4 = value - case 5 => key5 = key; val5 = value - case 6 => key6 = key; val6 = value - case 7 => key7 = key; val7 = value - } - init(idx) - entered += 1 - if (entered % 8 == 0) { - var i = 0 - while (i < 8) { decr(i); i += 1 } - } + keys(last) = key + values(last) = value + last = lastButOne } - /** Remove entry for `key` from cache if it was present */ - def invalidate(key: Key): Unit = { - if (key == key0) { clear(0); key0 = null } - if (key == key1) { clear(1); key1 = null } - if (key == key2) { clear(2); key2 = null } - if (key == key3) { clear(3); key3 = null } - if (key == key4) { clear(4); key4 = null } - if (key == key5) { clear(5); key5 = null } - if (key == key6) { clear(6); key6 = null } - if (key == key7) { clear(7); key7 = null } - } + /** Invalidate key. The invalidated element becomes + * the last in the queue. + */ + def invalidate(key: Key): Unit = + if (lookup(key) != null) { + keys(first) = null + last = first + } + + def indices: Iterator[Int] = Iterator.iterate(first)(next.apply) + def keysIterator: Iterator[Key] = + indices take Retained map keys filter (_ != null) + override def toString = { + val assocs = keysIterator + .toList // double reverse so that lookups do not perturb order + .reverse + .map(key => s"$key -> ${lookup(key)}") + .reverse + s"LRUCache(${assocs.mkString(", ")})" + } } -object LRU8Cache { - private final val width = 32 / 8 // width of a counter in bits - private final val mask = (1 << width) - 1 +object LRUCache { + + /** The number of retained elements in the cache; must be at most 16. */ + val Retained = 8 - private val next: Array[Int] = (1 to mask).toArray :+ mask - private val prev: Array[Int] = 0 +: (0 until mask).toArray -} \ No newline at end of file + /** The initial ring: 0 -> 1 -> ... -> 7 -> 0 */ + val initialRing = + (new SixteenNibbles(0L) /: (0 until Retained))((nibbles, idx) => + nibbles.updated(idx, (idx + 1) % Retained)) +} diff --git a/src/dotty/tools/dotc/util/SixteenNibbles.scala b/src/dotty/tools/dotc/util/SixteenNibbles.scala new file mode 100644 index 000000000..58d4a1182 --- /dev/null +++ b/src/dotty/tools/dotc/util/SixteenNibbles.scala @@ -0,0 +1,27 @@ +package dotty.tools.dotc.util + +/** An efficient implementation of sequences of 16 indexed elements with + * values 0..15 in a single Long. + * + */ +class SixteenNibbles(val bits: Long) extends AnyVal { + import SixteenNibbles._ + + def apply(idx: Int): Int = + (bits >>> (idx * Width)).toInt & Mask + + def updated(idx: Int, value: Int): SixteenNibbles = + new SixteenNibbles( + (bits & ~(Mask << (idx * Width))) | + ((value & Mask).toLong << (idx * Width))) + + def elements: IndexedSeq[Int] = (0 until 16) map apply + + override def toString = + s"SixteenNibbles(${elements.mkString(", ")})" +} + +object SixteenNibbles { + final val Width = 4 + final val Mask = (1 << Width) - 1 +} \ No newline at end of file diff --git a/src/dotty/tools/dotc/util/lrutest.sc b/src/dotty/tools/dotc/util/lrutest.sc new file mode 100644 index 000000000..6e6328b24 --- /dev/null +++ b/src/dotty/tools/dotc/util/lrutest.sc @@ -0,0 +1,40 @@ +package dotty.tools.dotc.util + +object lrutest { + println("Welcome to the Scala worksheet") //> Welcome to the Scala worksheet + val bits = new SixteenNibbles(0L) //> bits : dotty.tools.dotc.util.SixteenNibbles = SixteenNibbles(0, 0, 0, 0, 0, + //| 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) + bits.updated(1, 3) //> res0: dotty.tools.dotc.util.SixteenNibbles = SixteenNibbles(0, 3, 0, 0, 0, 0 + //| , 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) + LRUCache.initialRing //> res1: dotty.tools.dotc.util.SixteenNibbles = SixteenNibbles(1, 2, 3, 4, 5, 6 + //| , 7, 0, 0, 0, 0, 0, 0, 0, 0, 0) + val cache = new LRUCache[String, String] //> cache : dotty.tools.dotc.util.LRUCache[String,String] = LRUCache() + cache lookup "hi" //> res2: String = null + cache enter ("hi", "x") + cache.indices.take(10).toList //> res3: List[Int] = List(7, 0, 1, 2, 3, 4, 5, 6, 7, 0) + cache.last //> res4: Int = 6 + cache lookup "hi" //> res5: String = x + cache.indices.take(10).toList //> res6: List[Int] = List(7, 0, 1, 2, 3, 4, 5, 6, 7, 0) + + for (i <- 1 to 10) { + if (cache.lookup(i.toString) == null) + cache.enter(i.toString, i.toString) + } + + cache.indices.take(10).toList //> res7: List[Int] = List(5, 6, 7, 0, 1, 2, 3, 4, 5, 6) + cache //> res8: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(10 -> 10, 9 - + //| > 9, 8 -> 8, 7 -> 7, 6 -> 6, 5 -> 5, 4 -> 4, 3 -> 3) + cache //> res9: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(10 -> 10, 9 - + //| > 9, 8 -> 8, 7 -> 7, 6 -> 6, 5 -> 5, 4 -> 4, 3 -> 3) + cache.lookup("7") //> res10: String = 7 + cache.indices.take(10).toList //> res11: List[Int] = List(0, 5, 6, 7, 1, 2, 3, 4, 0, 5) + cache.keysIterator.toList //> res12: List[String] = List(7, 10, 9, 8, 6, 5, 4, 3) + cache.lookup("10") //> res13: String = 10 + cache.lookup("5") //> res14: String = 5 + cache //> res15: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(5 -> 5, 10 - + //| > 10, 7 -> 7, 9 -> 9, 8 -> 8, 6 -> 6, 4 -> 4, 3 -> 3) + cache.lookup("11") //> res16: String = null + cache.enter("11", "!!") + cache //> res17: dotty.tools.dotc.util.LRUCache[String,String] = LRUCache(11 -> !!, 5 + //| -> 5, 10 -> 10, 7 -> 7, 9 -> 9, 8 -> 8, 6 -> 6, 4 -> 4) +} \ No newline at end of file -- cgit v1.2.3