dymokomi/luce-canvas
Source of release 0.5.1
#==============================================================================================
#
# cache - Derived tiles kept by content key
#
# DESCRIPTION:
# Pyramid levels and composites are derived: made from other tiles, keyed by what they
# were made from, and remade on demand. The cache keeps them within a byte budget and
# drops the least recently wanted when it needs room (a clock sweep, so a lookup or an
# eviction costs the same whatever the count). What a request is still using is held:
# nothing used since `hold` is dropped until the next one, so a composite never loses a
# layer tile it fetched a moment ago. When everything is held, the cache goes over its
# budget rather than fail, and settles back at the next request. Its bytes count toward
# the GPU's budget (tiles/governor), and while the GPU is short it keeps only the
# governor's `cache_scale` of its budget.
#
# Some tiles are precious: costly to make again (a pyramid's coarse levels are made from
# everything under them) and few. Room is made from every other tile first; a precious
# tile goes only when precious tiles alone are over the budget.
#
#==============================================================================================
from luce_gpu import gpu
import memory
from keymap import KeyMap
from tiles import residency_derived, residency_cache_scale
from luce_raster.errors import invalid
struct CacheEntry:
var key: u64
var texture: gpu.Texture
var bytes: usize
## When last wanted: an entry wanted since `guard` is held.
var used: u64
## The clock's second chance.
var recent: bool
var live: bool
## Costly to make again: dropped only after every other tile.
var precious: bool
pub struct TileCache:
var entries: CacheEntry[]
var map: KeyMap
var budget: usize
var held_bytes: usize
## Of those, the precious tiles' bytes.
var precious_bytes: usize
var tick: u64
var guard: u64
var hand: usize
## Rendered versus found, for tests and tuning.
pub var misses: u64
pub var hits: u64
## A cache keeping at most `budget` bytes of tiles (`smallest` bytes the
## smallest a tile is, which sets how many entries it may need).
pub static func create(budget: usize, smallest: usize = 131072) -> TileCache!:
if budget == 0 or smallest == 0:
error(invalid, "a tile cache needs a budget")
let capacity = max_usize(64, budget // smallest + 64)
let entries = try new CacheEntry[capacity] --- in memory.heap
errdefer free(entries) in memory.heap
for index in 0..<capacity:
entries[index] = CacheEntry(key = 0, texture = gpu.Texture(), bytes = 0, used = 0, recent = false, live = false, precious = false)
var map = try KeyMap.create(capacity)
errdefer map.destroy()
return TileCache(entries = entries, map = map, budget = budget, held_bytes = 0, precious_bytes = 0, tick = 1, guard = 1, hand = 0, misses = 0, hits = 0)
## Begin a request: what it uses from now on stays until the next `hold`.
pub func hold():
self.tick += 1
self.guard = self.tick
# While the GPU is short, give back what the governor asks for.
if self.held_bytes > self.limit():
self.make_room(0)
## Whether a tile is kept for `key` (it is not marked used).
pub func has(key: u64) -> bool:
return self.map.find(key) != none
## The tile kept for `key`, borrowed; none when it is not kept.
pub func find(key: u64) -> gpu.Texture?:
let slot = self.map.find(key) else return none
let at = (usize)slot
self.entries[at].used = self.tick
self.entries[at].recent = true
self.hits += 1
return self.entries[at].texture
## Keep `texture` (this takes it over) for `key`, making room as needed.
## Not `recent`, it is the first to go once its request is done: a tile
## made only on the way to another (a pyramid's finer levels). A `precious`
## one goes only after every other tile.
pub func put(key: u64, texture: gpu.Texture, bytes: usize, recent: bool = true, precious: bool = false) -> !:
self.misses += 1
if let existing = self.map.find(key):
self.drop((usize)existing)
self.make_room(bytes)
if self.free_slot() == none:
# Every entry is held: grow rather than fail.
try self.grow()
let at = self.free_slot() else trap("a grown cache has room")
self.entries[at] = CacheEntry(key = key, texture = texture, bytes = bytes, used = self.tick, recent = recent, live = true, precious = precious)
if precious:
self.precious_bytes += bytes
try self.map.put(key, (u32)at)
self.held_bytes += bytes
residency_derived(bytes, true)
## Drop the tile kept for `key`, if any: one about to be made again from
## changed tiles, which would only take room until it was pushed out. One a
## request still holds stays, first to go.
pub func forget(key: u64):
let slot = self.map.find(key) else return
let at = (usize)slot
if self.entries[at].used >= self.guard:
self.entries[at].recent = false
return
self.drop(at)
## Drop entries (unheld, least recently wanted first) until `bytes` more
## fit: every ordinary tile before any precious one, and precious tiles only
## while they alone are over the budget. Each sweep is bounded: at most two
## turns of the clock.
func make_room(bytes: usize):
let limit = self.limit()
self.sweep(bytes, limit, false)
if self.held_bytes + bytes > limit and self.precious_bytes + bytes > limit:
self.sweep(bytes, limit, true)
func sweep(bytes: usize, limit: usize, precious: bool):
var passes: usize = 0
while self.held_bytes + bytes > limit and passes < self.entries.length * 2:
let at = self.hand
self.hand = (self.hand + 1) % self.entries.length
passes += 1
if not self.entries[at].live or self.entries[at].used >= self.guard or self.entries[at].precious != precious:
continue
if self.entries[at].recent:
self.entries[at].recent = false
continue
self.drop(at)
if precious and self.precious_bytes + bytes <= limit:
return
func free_slot() -> usize?:
for offset in 0..<self.entries.length:
let at = (self.hand + offset) % self.entries.length
if not self.entries[at].live:
return at
return none
func grow() -> !:
let capacity = self.entries.length * 2
let entries = try new CacheEntry[capacity] --- in memory.heap
errdefer free(entries) in memory.heap
var map = try KeyMap.create(capacity)
errdefer map.destroy()
for index in 0..<capacity:
entries[index] = CacheEntry(key = 0, texture = gpu.Texture(), bytes = 0, used = 0, recent = false, live = false, precious = false)
for index in 0..<self.entries.length:
entries[index] = self.entries[index]
if entries[index].live:
try map.put(entries[index].key, (u32)index)
free(self.entries) in memory.heap
self.map.destroy()
self.entries = entries
self.map = map
func drop(at: usize):
if not self.entries[at].live:
return
self.map.remove(self.entries[at].key)
self.entries[at].texture.destroy()
self.held_bytes -= self.entries[at].bytes
if self.entries[at].precious:
self.precious_bytes -= self.entries[at].bytes
residency_derived(self.entries[at].bytes, false)
self.entries[at].live = false
## The budget as the governor allows it now.
func limit() -> usize:
return max_usize(1, (usize)((f64)self.budget * residency_cache_scale()))
## What the cache keeps, in bytes.
pub func bytes() -> usize:
return self.held_bytes
## Change the budget; the cache settles to it as tiles come in.
pub func set_budget(budget: usize):
self.budget = max_usize(budget, 1)
## Forget every tile.
pub func clear():
for index in 0..<self.entries.length:
self.drop(index)
pub func destroy():
self.clear()
if self.entries.length > 0:
free(self.entries) in memory.heap
var none_left: CacheEntry[]
self.entries = none_left
self.map.destroy()
func max_usize(a: usize, b: usize) -> usize:
return a if a > b else b
test "the cache keeps within its budget, drops the least wanted, and keeps what a request holds":
var device = gpu.Device.open() catch failure:
assert(failure.code == gpu.unavailable)
return
defer device.destroy()
# Room for four 1 KiB tiles.
var cache = try TileCache.create(4096, 1024)
defer cache.destroy()
for key in 1..<(u64)5:
cache.hold()
try cache.put(key, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
assert(cache.bytes() == 4096)
# Wanting 1 again; a fifth tile then pushes out another, not 1.
cache.hold()
assert(cache.find(1) != none)
try cache.put(5, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
assert(cache.bytes() == 4096 and cache.find(1) != none and cache.find(5) != none)
# Everything held by one request: the cache grows past its budget rather than fail.
cache.hold()
for key in 1..<(u64)6:
_ = cache.find(key)
for key in 6..<(u64)12:
try cache.put(key, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
assert(cache.bytes() > 4096)
# The next request lets it settle.
cache.hold()
try cache.put(20, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
assert(cache.bytes() <= 4096 and cache.find(20) != none)
test "a tile kept as not recent goes before the tiles a request wanted":
var device = gpu.Device.open() catch failure:
assert(failure.code == gpu.unavailable)
return
defer device.destroy()
var cache = try TileCache.create(4096, 1024)
defer cache.destroy()
# Two wanted tiles and two made on the way to them.
cache.hold()
try cache.put(1, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
try cache.put(2, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024, recent = false)
try cache.put(3, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
try cache.put(4, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024, recent = false)
# Two more in the next request push out the two on the way, not the wanted ones.
cache.hold()
try cache.put(5, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
try cache.put(6, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
assert(cache.bytes() == 4096)
assert(cache.find(1) != none and cache.find(3) != none and cache.find(2) == none and cache.find(4) == none)
test "precious tiles go only after every other one, and only while they alone are too many":
var device = gpu.Device.open() catch failure:
assert(failure.code == gpu.unavailable)
return
defer device.destroy()
# Room for four 1 KiB tiles: two precious, then ordinary ones pushing in.
var cache = try TileCache.create(4096, 1024)
defer cache.destroy()
cache.hold()
try cache.put(1, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024, precious = true)
try cache.put(2, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024, precious = true)
for key in 3..<(u64)10:
cache.hold()
try cache.put(key, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024)
assert(cache.bytes() <= 4096 and cache.find(1) != none and cache.find(2) != none)
# Precious tiles alone past the budget: the least wanted of them go.
for key in 20..<(u64)26:
cache.hold()
try cache.put(key, try gpu.Texture.create(device, 16, 16, gpu.Format.rgba8_linear), 1024, precious = true)
cache.hold()
assert(cache.bytes() <= 4096)