dymokomi/luce-geocore
Source of release 0.7.8
0.7.8 / src / core / shared.lucb
## Shared, immutable-after-publish arrays. A Block is one heap allocation: a
## header with an atomic user count and a change id, then the elements. A
## Column[T] is a typed handle to one. Meshes, snapshots and worker results
## share columns by count instead of copying them, and every derived cache
## (GPU buffers included) is keyed by the ids of the columns it read: equal
## ids mean equal bytes, on any thread, so invalidation needs no tags.
import memory
import sync
## The last id handed out; ids start at 1 and are never reused.
var last_block_id: @u64
## A process-unique id for new or rewritten contents.
pub func fresh_id() -> u64:
return last_block_id.add(1, .relaxed) + 1
## Elements start this far into the allocation: a cache line, which also
## satisfies every element type's alignment.
let header_bytes: usize = 64
pub struct Block:
## Owners on every thread; the release that drops it to zero frees it.
pub var users: @usize
## The change id of the contents.
pub var id: u64
## Elements, and the bytes they take.
pub var count: usize
pub var bytes: usize
## The block this one was derived from by editing some elements, or 0.
## Incremental caches (a GPU sub-range upload, a BVH refit) key on it.
pub var parent: u64 = 0
## The elements that may differ from the parent's: first..<end.
pub var changed_first: usize = 0
pub var changed_end: usize = 0
## The allocation's bytes, header included (a recycled one may be
## larger than the elements need).
pub var capacity: usize = 0
assert(memory.size_of(Block) <= 64, "the block header must fit before the elements")
## Large blocks just released, kept for the next allocation of about their
## size: a drag makes a new positions column per frame (12 MB for 1M
## points) and frees the last one, and handing that memory back to the
## system each time made every copy into a new one fault its pages in
## again (a boolean's 1M-face result dragged at 2.2 ms a frame instead of
## 1.2). At most `spare_most` blocks of `spare_least` bytes or more are
## kept, `spare_total` bytes in all.
struct Spare:
var storage: u8*?
var bytes: usize
let spare_least: usize = 4194304
let spare_most: usize = 4
let spare_total: usize = 268435456
var spare_lock: sync.Mutex
var spares: Spare[4]
var spare_bytes: usize = 0
## Free every kept block (tests with allocation trackers).
pub func clear_spares():
spare_lock.lock()
defer spare_lock.unlock()
for at in 0..<spare_most:
if let storage = spares[at].storage:
free(u8[](storage, spares[at].bytes)) in memory.heap
spares[at] = Spare(none, 0)
spare_bytes = 0
## A kept block of at least `bytes` and at most a quarter more, or none.
func take_spare(bytes: usize) -> (u8*, usize)?:
if bytes < spare_least: return none
spare_lock.lock()
defer spare_lock.unlock()
for at in 0..<spare_most:
let storage = spares[at].storage else continue
let size = spares[at].bytes
if size >= bytes and size - bytes <= bytes // 4:
spares[at] = Spare(none, 0)
spare_bytes -= size
return (storage, size)
return none
## Keep `storage` of `bytes` for a later allocation; false when it is not
## kept (small, or no room) and the caller frees it.
func keep_spare(storage: u8*, bytes: usize) -> bool:
if bytes < spare_least or bytes > spare_total: return false
spare_lock.lock()
defer spare_lock.unlock()
var slot = spare_most
for at in 0..<spare_most:
if spares[at].storage == none:
slot = at
break
if slot == spare_most or spare_bytes + bytes > spare_total: return false
spares[slot] = Spare(storage, bytes)
spare_bytes += bytes
return true
## A typed handle. Copying the handle does not share: `share()` does, and
## each share is released once. The zero value is an empty column.
pub struct Column[T]:
var block: Block*?
## `count` uninitialized elements, owned by the caller alone.
pub static func allocate(count: usize) -> Column[T]!:
let bytes = count * memory.size_of(T)
var capacity = header_bytes + bytes
var data: u8*? = none
if let spare = take_spare(capacity):
data = spare.0
capacity = spare.1
else:
let storage = memory.heap.allocate(capacity, 64) else error(memory.exhausted, "no memory for a column")
data = storage.data
let block = (Block*)(data else trap("column storage"))
block.capacity = capacity
block.users.store(1, .relaxed)
block.id = fresh_id()
block.count = count
block.bytes = bytes
block.parent = 0
block.changed_first = 0
block.changed_end = 0
return Column[T](block)
## A new column holding a copy of `values`.
pub static func copy_of(values: const T[]) -> Column[T]!:
var column = try Column[T].allocate(values.length)
if values.length > 0: memory.copy(column.span(), values, values.length)
return column
## `count` copies of `value`.
pub static func filled(count: usize, value: T) -> Column[T]!:
var column = try Column[T].allocate(count)
let items = column.span()
for at in 0..<count: items[at] = value
return column
pub func count() -> usize:
let block = self.block else return 0
return block.count
## The contents' change id; 0 for an empty handle.
pub func id() -> u64:
let block = self.block else return 0
return block.id
pub func parent() -> u64:
let block = self.block else return 0
return block.parent
pub func is_empty() -> bool:
return self.block == none
## Whether this handle is the only owner (writing needs no copy).
pub func unique() -> bool:
let block = self.block else return true
return block.users.load(.acquire) == 1
## Read access; valid while this handle holds its share.
pub func view() -> const T[]:
if let block = self.block:
return T[]((T*)((u8*)block + header_bytes), block.count)
var empty: T[]
return empty
## Another owner of the same contents: O(1), no copy.
pub func share() -> Column[T]:
if let block = self.block: _ = block.users.add(1, .relaxed)
return Column[T](self.block)
## Write access to contents only this handle owns (just allocated, or
## made writable). Writing a shared block would change other owners'
## data under them, so that traps.
pub func span() -> T[]:
if let block = self.block:
if block.users.load(.acquire) != 1: trap("writing a shared column")
return T[]((T*)((u8*)block + header_bytes), block.count)
var empty: T[]
return empty
## Copy on write: a private copy when others share the contents, then a
## fresh id either way, since the caller is about to change them. The
## new id's parent is the old one, for incremental caches.
pub func writable() -> T[]!:
let block = self.block else return self.span()
if block.users.load(.acquire) != 1:
var copy = try Column[T].copy_of(self.view())
copy.set_parent(block.id)
self.release()
self.block = copy.block
return self.span()
block.parent = block.id
block.changed_first = 0
block.changed_end = block.count
block.id = fresh_id()
return self.span()
## Record that these contents were derived from the block `id`.
pub func set_parent(id: u64):
if let block = self.block:
block.parent = id
block.changed_first = 0
block.changed_end = block.count
## Narrow what differs from the parent to elements first..<end (a local
## edit), so incremental caches copy only those.
pub func set_changed(first: usize, end: usize):
if let block = self.block:
block.changed_first = first if first < block.count else block.count
block.changed_end = end if end < block.count else block.count
if block.changed_end < block.changed_first: block.changed_end = block.changed_first
## The elements that may differ from the parent's (all, without one).
pub func changed() -> (usize, usize):
let block = self.block else return (0, 0)
if block.parent == 0: return (0, block.count)
return (block.changed_first, block.changed_end)
## This handle's share, moved out: the handle is left empty, so a later
## `release` of it (a defer) does nothing.
pub func take() -> Column[T]:
let moved = Column[T](self.block)
self.block = none
return moved
## Give up this share; the last one frees the block.
pub func release():
let block = self.block else return
self.block = none
if block.users.sub(1, .acq_rel) != 1: return
if keep_spare((u8*)block, block.capacity): return
free(u8[]((u8*)block, block.capacity)) in memory.heap
## Bytes this column holds, for memory budgets.
pub func bytes() -> usize:
let block = self.block else return 0
return block.capacity