aboutsummaryrefslogtreecommitdiff
path: root/src/dotty/tools/dotc
diff options
context:
space:
mode:
Diffstat (limited to 'src/dotty/tools/dotc')
-rw-r--r--src/dotty/tools/dotc/core/SymDenotations.scala8
-rw-r--r--src/dotty/tools/dotc/util/LRUCache.scala176
-rw-r--r--src/dotty/tools/dotc/util/SixteenNibbles.scala27
-rw-r--r--src/dotty/tools/dotc/util/lrutest.sc40
4 files changed, 152 insertions, 99 deletions
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
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-21 20:20:56 +0000