Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-canvas

Source of release 0.5.1

0.5.1 / src / cache.lucb

#==============================================================================================
#
#   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)