///|
/// A runnable tour of `moonlarder`, covering LRU eviction, TTL expiry,
/// memoization, weighted capacity, the LFU, ARC, and WindowTinyLfu
/// eviction policies, the TinyLFU-style admission filter, removal
/// listeners, and JSON snapshotting. Every step uses an explicit
/// `now_ms` rather than a real clock, on purpose: `Larder` never reads
/// time on its own, so this program's behavior is exactly reproducible
/// on every target `moon run cmd/main` can build for.
fn main {
println(
"moonlarder -- a generic in-memory cache with LRU/LFU/ARC/WindowTinyLfu eviction, TTL, and JSON snapshots",
)
demo_lru()
demo_bulk()
demo_ttl()
demo_memoize()
demo_weighted()
demo_lfu()
demo_arc()
demo_admission_filter()
demo_window_tiny_lfu()
demo_removal_listener()
demo_json()
}
///|
fn demo_lru() -> Unit {
println("\n== LRU eviction ==")
let cache : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=3,
)
cache.set("a", 1, now_ms=0L)
cache.set("b", 2, now_ms=0L)
cache.set("c", 3, now_ms=0L)
println("inserted \"a\", \"b\", \"c\" into a capacity-3 cache: \{cache}")
ignore(cache.get("a", now_ms=0L))
println("touched \"a\", making it the most-recently-used")
cache.set("d", 4, now_ms=0L)
println("inserted \"d\": \{cache}")
let b = @moonbitlang/core/debug.to_string(cache.get("b", now_ms=0L))
println(
"\"b\" was the least-recently-used, so it's the one that got evicted: get(\"b\") = \{b}",
)
let survivors = @moonbitlang/core/debug.to_string(cache.to_array(now_ms=0L))
println("\"a\", \"c\", \"d\" all survive: \{survivors}")
}
///|
fn demo_bulk() -> Unit {
println("\n== Batch lookups and inserts ==")
let cache : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=10,
)
cache.set_many([("a", 1), ("b", 2), ("c", 3)], now_ms=0L)
println("set_many([(\"a\",1), (\"b\",2), (\"c\",3)]): \{cache}")
let found = cache.get_many(["c", "missing", "a"], now_ms=0L)
let found_text = @moonbitlang/core/debug.to_string(found)
println(
"get_many([\"c\", \"missing\", \"a\"]) -> only the hits, in order: \{found_text}",
)
}
///|
fn demo_ttl() -> Unit {
println("\n== TTL expiry ==")
let cache : @moonlarder.Larder[String, String] = @moonlarder.Larder::new(
capacity=10,
default_ttl_ms=5_000L,
)
cache.set("session:alice", "logged in", now_ms=0L)
println("set \"session:alice\" at t=0 with the cache's 5s default TTL")
let before_deadline = @moonbitlang/core/debug.to_string(
cache.get("session:alice", now_ms=4_999L),
)
println("at t=4999ms: get(\"session:alice\") = \{before_deadline}")
let at_deadline = @moonbitlang/core/debug.to_string(
cache.get("session:alice", now_ms=5_000L),
)
println("at t=5000ms: get(\"session:alice\") = \{at_deadline}")
}
///|
fn demo_memoize() -> Unit {
println("\n== Memoization ==")
let cache : @moonlarder.Larder[Int, Int] = @moonlarder.Larder::new(
capacity=10,
)
let mut calls = 0
fn expensive_square(n : Int) -> Int {
calls += 1
n * n
}
let first = cache.get_or_insert_with(7, now_ms=0L, fn() {
expensive_square(7)
})
let second = cache.get_or_insert_with(7, now_ms=1L, fn() {
expensive_square(7)
})
println(
"get_or_insert_with(7) called twice -> \{first}, \{second}, but the loader ran \{calls} time(s)",
)
}
///|
fn demo_weighted() -> Unit {
println("\n== Weighted capacity ==")
let cache : @moonlarder.Larder[String, String] = @moonlarder.Larder::new(
capacity=15,
weigher=fn(_key, value : String) { value.length() },
)
cache.set("short", "hi", now_ms=0L)
cache.set("long", "0123456789", now_ms=0L)
let weight = cache.weight()
let capacity = cache.capacity()
println(
"after \"short\" (weight 2) and \"long\" (weight 10): weight = \{weight} / capacity \{capacity} - both fit",
)
cache.set("more", "abcabc", now_ms=0L)
println(
"inserting \"more\" (weight 6) pushes total weight to 18, over capacity 15:",
)
println(" \{cache}")
let survivors = @moonbitlang/core/debug.to_string(cache.to_array(now_ms=0L))
println(" survivors: \{survivors}")
}
///|
fn demo_lfu() -> Unit {
println("\n== LFU vs LRU ==")
let cache : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=2,
policy=Lfu,
)
cache.set("popular", 1, now_ms=0L)
cache.set("one-hit-wonder", 2, now_ms=0L)
ignore(cache.get("popular", now_ms=0L))
ignore(cache.get("popular", now_ms=0L))
println("\"popular\" used 3 times total; \"one-hit-wonder\" used once")
cache.set("newcomer", 3, now_ms=0L)
println("inserting \"newcomer\" (capacity 2, so something evicts): \{cache}")
let one_hit_wonder = @moonbitlang/core/debug.to_string(
cache.get("one-hit-wonder", now_ms=0L),
)
println(
"\"one-hit-wonder\" was the least-frequently-used, so it's gone even though it's more recent than \"popular\": get(\"one-hit-wonder\") = \{one_hit_wonder}",
)
let popular = @moonbitlang/core/debug.to_string(
cache.get("popular", now_ms=0L),
)
println(
"\"popular\" survives on frequency alone: get(\"popular\") = \{popular}",
)
}
///|
fn demo_arc() -> Unit {
println("\n== ARC: adapting to a scan that plain LRU falls for ==")
// A small, frequently-reused working set ("hot:1".."hot:3"), interrupted
// partway through by a single long sequential scan ("scan:0".."scan:9")
// that's never touched again - the classic case plain LRU handles badly,
// since the scan evicts the whole working set on its way through.
let lru : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=5,
)
let arc : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=5,
policy=Arc,
)
fn workload(cache : @moonlarder.Larder[String, Int]) -> Unit {
for key in ["hot:1", "hot:2", "hot:3"] {
cache.set(key, 1, now_ms=0L)
}
ignore(cache.get("hot:1", now_ms=0L))
ignore(cache.get("hot:2", now_ms=0L))
for i = 0; i < 10; i = i + 1 {
cache.set("scan:\{i}", i, now_ms=0L)
}
}
workload(lru)
workload(arc)
let lru_survivors = ["hot:1", "hot:2", "hot:3"].filter(fn(key) {
lru.contains(key, now_ms=0L)
})
let arc_survivors = ["hot:1", "hot:2", "hot:3"].filter(fn(key) {
arc.contains(key, now_ms=0L)
})
println(
"after a one-time scan of 10 keys through a capacity-5 cache, on top of a hot set used just before it:",
)
let lru_text = @moonbitlang/core/debug.to_string(lru_survivors)
let arc_text = @moonbitlang/core/debug.to_string(arc_survivors)
println(" Lru keeps of the hot set: \{lru_text}")
println(" Arc keeps of the hot set: \{arc_text}")
}
///|
fn demo_admission_filter() -> Unit {
println(
"\n== Admission filter: a second, different defense against the same scan ==",
)
// Same shape of workload as the ARC demo above - a hot working set
// touched twice each, then a one-time scan - but this time the
// defense is a TinyLFU-style admission check layered on top of
// plain Lru, rather than an adaptive eviction policy: a newcomer
// that would evict a more historically popular entry is turned away
// outright instead of being let in.
let plain : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=5,
)
let filtered : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=5,
admission_filter=true,
)
fn workload(cache : @moonlarder.Larder[String, Int]) -> Unit {
for key in ["hot:1", "hot:2", "hot:3"] {
cache.set(key, 1, now_ms=0L)
}
ignore(cache.get("hot:1", now_ms=0L))
ignore(cache.get("hot:1", now_ms=0L))
ignore(cache.get("hot:2", now_ms=0L))
ignore(cache.get("hot:2", now_ms=0L))
for i = 0; i < 10; i = i + 1 {
cache.set("scan:\{i}", i, now_ms=0L)
}
}
workload(plain)
workload(filtered)
let plain_survivors = ["hot:1", "hot:2", "hot:3"].filter(fn(key) {
plain.contains(key, now_ms=0L)
})
let filtered_survivors = ["hot:1", "hot:2", "hot:3"].filter(fn(key) {
filtered.contains(key, now_ms=0L)
})
println(
"same scan as above, through a capacity-5 cache, on top of a hot set requested twice each just before it:",
)
let plain_text = @moonbitlang/core/debug.to_string(plain_survivors)
let filtered_text = @moonbitlang/core/debug.to_string(filtered_survivors)
let rejections = filtered.admission_rejections()
println(" plain Lru keeps of the hot set: \{plain_text}")
println(" Lru + admission_filter keeps of the hot set: \{filtered_text}")
println(
" admission_filter turned away \{rejections} of the 10 scan keys outright",
)
}
///|
fn demo_window_tiny_lfu() -> Unit {
println(
"\n== WindowTinyLfu: giving a rising key a chance admission_filter can't ==",
)
// A cache already full of entries with real request history, then a
// brand-new key that's about to become popular - requested
// repeatedly right after it first shows up, the same "just-fetched
// page that's about to go viral" pattern a cache-aside call site
// produces naturally. admission_filter judges it on its very first,
// frequency-0 appearance; WindowTinyLfu gives it a window slot first.
let filtered : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=3,
admission_filter=true,
)
let windowed : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=3,
policy=WindowTinyLfu,
)
fn establish_hot_set(cache : @moonlarder.Larder[String, Int]) -> Unit {
cache.set("a", 1, now_ms=0L)
cache.set("b", 2, now_ms=0L)
ignore(cache.get("a", now_ms=0L))
ignore(cache.get("a", now_ms=0L))
ignore(cache.get("b", now_ms=0L))
ignore(cache.get("b", now_ms=0L))
cache.set("c", 3, now_ms=0L) // cache now full, capacity 3
}
fn ramp_up(cache : @moonlarder.Larder[String, Int]) -> (Int, Int) {
let mut hits = 0
let mut misses = 0
for _i = 0; _i < 5; _i = _i + 1 {
match cache.get("rising", now_ms=0L) {
Some(_) => hits += 1
None => {
misses += 1
cache.set("rising", 100, now_ms=0L)
}
}
}
(hits, misses)
}
establish_hot_set(filtered)
establish_hot_set(windowed)
let (filtered_hits, filtered_misses) = ramp_up(filtered)
let (windowed_hits, windowed_misses) = ramp_up(windowed)
println(
"requesting the same not-yet-cached key 5 times in a row, right after it first appears, against a full capacity-3 cache:",
)
println(
" Lru + admission_filter: \{filtered_hits} hit(s), \{filtered_misses} miss(es) before it's finally admitted",
)
println(
" WindowTinyLfu: \{windowed_hits} hit(s), \{windowed_misses} miss(es) - served from the window almost immediately",
)
}
///|
fn demo_removal_listener() -> Unit {
println("\n== Removal listener ==")
// Simulates a resource tied to each cached value - a connection
// handle, say - that needs to be released whenever its entry
// leaves, no matter why.
let closed = []
let cache : @moonlarder.Larder[String, String] = @moonlarder.Larder::new(
capacity=2,
on_remove=fn(key, _value, cause) {
let cause_text = @moonbitlang/core/debug.to_string(cause)
println(" on_remove: \"\{key}\" (\{cause_text})")
closed.push(key)
},
)
cache.set("conn-a", "handle-a", now_ms=0L)
cache.set("conn-b", "handle-b", now_ms=0L)
println("inserted conn-a, conn-b (capacity 2, no evictions yet)")
cache.set("conn-a", "handle-a-2", now_ms=0L) // fires Replaced
println("re-set conn-a with a new handle -- old one needs closing:")
cache.set("conn-c", "handle-c", now_ms=0L) // evicts conn-b: fires Evicted
println("inserted conn-c, over capacity -- least-recently-used gets evicted:")
let closed_text = @moonbitlang/core/debug.to_string(closed)
println("closed so far, in order: \{closed_text}")
}
///|
fn demo_json() -> Unit {
println("\n== JSON snapshot ==")
let cache : @moonlarder.Larder[String, Int] = @moonlarder.Larder::new(
capacity=5,
)
cache.set("a", 1, now_ms=0L)
cache.set("b", 2, now_ms=0L)
let text = ToJson::to_json(cache).stringify(indent=2)
println("serialized:")
println(text)
try {
let restored : @moonlarder.Larder[String, Int] = @json.from_json(
@json.parse(text),
)
let a = @moonbitlang/core/debug.to_string(restored.get("a", now_ms=0L))
println("reloaded from that text: \{restored}, get(\"a\") = \{a}")
} catch {
error =>
println(
"failed to reload the snapshot (this would be a real bug): \{error}",
)
}
}