compact.gno

  1package ulist
  2
  3// Compaction: turning soft deletes back into refunded storage.
  4//
  5// Delete is a soft delete. It clears the element's data but leaves the tree
  6// node in place, because the node's position IS the index: indices are the
  7// public addressing scheme, and moving a live element would silently
  8// invalidate an index some other realm is holding.
  9//
 10// That leaves reclaimable storage behind. On gno.land every byte of realm
 11// state locks GNOT, refunded to whoever signs the transaction that frees it,
 12// so those dead nodes are money sitting in the structure.
 13//
 14// Compact reclaims them without moving anything live, by dropping whole
 15// subtrees that contain no live element. Nothing live moves, so every index
 16// stays valid.
 17//
 18// # Which deletions can actually be compacted
 19//
 20// This is the counterintuitive part, and it decides whether compaction is
 21// worth anything at all. Index 0 is the root and index i sits at depth
 22// bitlen(i+1)-1, so the OLDEST indices are the ANCESTORS of the newest. A node
 23// is only freeable when its whole subtree is dead. Therefore:
 24//
 25//   - Deleting the oldest entries frees no nodes at all, however many you
 26//     delete, because every newer entry keeps their ancestors alive. An expiry
 27//     queue reaping oldest-first is exactly this case.
 28//   - Deleting the newest entries frees nodes immediately, because they are
 29//     the leaves.
 30//
 31// Measured on chain, 32 entries of 512 bytes each: deleting the oldest 16
 32// refunded 8,896 bytes and left Compactable at zero. Deleting the newest 16
 33// instead refunded the same 8,896 bytes and then Compact returned a further
 34// 27,679, because a ulist node costs far more than the payload it holds. The
 35// structure is roughly two thirds of the total cost, so being unable to
 36// compact leaves most of the money on the table.
 37//
 38// The practical rule: compaction pays in proportion to how much of the
 39// deepest layer is dead. Delete from the top down, or wait until a run of
 40// deletions reaches the leaves.
 41//
 42// Whether it is worth doing is not a question this package can answer, since
 43// it depends on the gas price of the day. Compactable reports the size of the
 44// prize as a free read so a caller can decide; gno.land/p/moul/x/storagecost/v0
 45// turns that count into a verdict in GNOT.
 46
 47// Compactable reports how many tree nodes Compact would free right now.
 48//
 49// It reads and mutates nothing, so a caller can poll it to decide whether
 50// compaction is worth its gas before paying for it. Zero means every dead node
 51// still shares a subtree with a live element, and compacting would cost gas to
 52// free nothing.
 53func (l *List) Compactable() int {
 54	if l == nil || l.root == nil {
 55		return 0
 56	}
 57	// The root is never freed, so only its subtrees are counted.
 58	n, _ := prunableNodes(l.root)
 59	return n
 60}
 61
 62// Compact frees every tree node whose subtree holds no live element, and
 63// returns the number of nodes freed.
 64//
 65// Indices are preserved exactly: TotalSize is unchanged, Size is unchanged,
 66// and every live element keeps the index it had. Appends continue from the
 67// same number.
 68//
 69// Deleted elements swept up by a Compact become permanently unrestorable:
 70// Set on such an index returns ErrOutOfBounds where before it would have
 71// restored the value. That is the trade the refund pays for, and it is the
 72// reason this behaviour is v1 rather than an addition to v0.
 73func (l *List) Compact() int {
 74	if l == nil || l.root == nil {
 75		return 0
 76	}
 77	// The root is deliberately never freed. findNode treats a nil root as an
 78	// empty list and returns the root for every index, so a tree that still
 79	// has a totalSize but no root would write index 0 on the next append.
 80	// Keeping one node costs a few dozen bytes and keeps that unreachable.
 81	freed, _ := pruneDead(l.root)
 82	return freed
 83}
 84
 85// pruneDead drops n's fully dead subtrees, returning how many nodes were freed
 86// and whether n's own subtree is now dead. A dead subtree is one in which no
 87// node holds data.
 88func pruneDead(n *treeNode) (freed int, dead bool) {
 89	if n == nil {
 90		return 0, true
 91	}
 92	leftFreed, leftDead := pruneDead(n.left)
 93	rightFreed, rightDead := pruneDead(n.right)
 94	freed = leftFreed + rightFreed
 95
 96	// A dead child's own descendants have already been counted and unlinked by
 97	// the recursive call, so the child itself is the one node left to free.
 98	if leftDead && n.left != nil {
 99		n.left = nil
100		freed++
101	}
102	if rightDead && n.right != nil {
103		n.right = nil
104		freed++
105	}
106	return freed, n.data == nil && n.left == nil && n.right == nil
107}
108
109// prunableNodes is pruneDead without the mutation, so Compactable and Compact
110// can never disagree about the count.
111func prunableNodes(n *treeNode) (prunable int, dead bool) {
112	if n == nil {
113		return 0, true
114	}
115	leftPrunable, leftDead := prunableNodes(n.left)
116	rightPrunable, rightDead := prunableNodes(n.right)
117	prunable = leftPrunable + rightPrunable
118
119	if leftDead && n.left != nil {
120		prunable++
121	}
122	if rightDead && n.right != nil {
123		prunable++
124	}
125	return prunable, n.data == nil &&
126		(n.left == nil || leftDead) &&
127		(n.right == nil || rightDead)
128}