diff options
Diffstat (limited to 'internal/calendar/transfer_plan_cache.go')
| -rw-r--r-- | internal/calendar/transfer_plan_cache.go | 154 |
1 files changed, 118 insertions, 36 deletions
diff --git a/internal/calendar/transfer_plan_cache.go b/internal/calendar/transfer_plan_cache.go index fdf62f7..f03e17b 100644 --- a/internal/calendar/transfer_plan_cache.go +++ b/internal/calendar/transfer_plan_cache.go @@ -18,9 +18,12 @@ import ( // view moving through nearby dates. const efTransferPlanCacheCap = 64 -// efTransferPlanCacheKey is everything efTransferPlan's result actually -// depends on, established by reading efTransferPlan, celebrationDate, -// temporalEF and resolveDate rather than assumed: +// efTransferPlanCacheKey is everything efTransferPlan's result -- and, since +// ef_transfer_plan_cache.go v2, efOccupancyIndex's result -- actually depend +// on, established by reading efTransferPlan, celebrationDate, temporalEF and +// resolveDate rather than assumed. Both the plan and the occupancy index are +// pure functions of exactly these three inputs (see efOccupancyIndex's own +// doc comment for occupancy specifically), so one key correctly covers both: // // - year: efTransferPlan's own first argument (Easter, the transfer // window, every celebrationDate call). @@ -48,11 +51,14 @@ type efTransferPlanCacheKey struct { hash [32]byte } -// efTransferPlanCacheEntry is one memoised plan, doubling as the LRU list's -// payload so eviction and lookup share one map. +// efTransferPlanCacheEntry is one memoised (plan, occupancy index) pair, +// doubling as the LRU list's payload so eviction and lookup share one map. +// The two are cached together because they are built from the same data in +// one pass and share the same cache key -- see efTransferPlanCacheKey. type efTransferPlanCacheEntry struct { - key efTransferPlanCacheKey - plan map[string]time.Time + key efTransferPlanCacheKey + plan map[string]time.Time + occupancy efOccupancyIndex } // efTransferPlanCache is a small, bounded, thread-safe LRU in front of @@ -66,34 +72,109 @@ var efTransferPlanCache = struct { order *list.List // front = most recently used }{entries: map[efTransferPlanCacheKey]*list.Element{}, order: list.New()} -// efTransferPlanCached is efTransferPlan, memoised by (year, sel, merged -// content). It is safe and correct to share across every caller in the -// process: two calls with the SAME key are, by construction of the key, -// calls efTransferPlan itself would resolve identically (same year, same -// Selection, same sanctoral content), so returning a cached result changes -// nothing about what is computed -- only when. The returned map is a fresh -// copy per call (clonePlan), never the cached instance itself, so no caller -// can mutate shared cache state even though computeEF's own use of the -// result is read-only today. -func efTransferPlanCached(year int, merged map[string]RawCelebration, sel Selection, - occupiedByClass1, occupiedByClass1Or2 func(time.Time, string) bool) map[string]time.Time { +// efOccupancyEntry is one merged entry's slug and rank, indexed under its own +// ORIGINAL (untransferred) date -- see efOccupancyIndex. +type efOccupancyEntry struct { + slug string + rank Rank +} + +// efOccupancyIndex answers exactly the question computeEF's old +// occupiedByRank closure scanned all of merged for on every single call: +// "does some entry other than exceptSlug, with a rank `allowed` accepts, +// resolve to date d this year?" -- but as a precomputed lookup instead of a +// fresh O(len(merged)) scan. +// +// BE PRECISE ABOUT WHAT "OCCUPIED" DEPENDS ON, because this is the question +// that decides whether precomputing it is safe: an entry's ORIGINAL date +// (buildCelebration + celebrationDate, exactly as this index computes it) is +// a pure function of (merged content, year, sel) alone -- it never considers +// whether that entry has since been TRANSFERRED (celebrationDate calls +// resolveDate directly; nothing about transfer resolution feeds into it) and +// never depends on `date`, the day computeEF happens to be resolving. That +// is what makes one index, built once per (year, merged, sel) and reused for +// every day and every candidate resolved against it, correct. +// +// This is a DIFFERENT question from efTransferPlan's own `claimed` map, +// which tracks which TARGET days a transfer walk has already assigned +// DURING one planning pass -- claimed genuinely mutates as planning +// proceeds and has no meaning outside that single call, so it is (correctly) +// still computed fresh inside efTransferPlan every time, never cached here. +// Conflating the two -- treating "is some entry's ORIGINAL date d" as if it +// captured "has some transfer already CLAIMED d" -- would be the exact +// silent-wrong-answer failure mode this comment exists to rule out; they are +// checked as three independent conditions everywhere they are used +// together (see efTransferPlan's own forward-walk loop). +type efOccupancyIndex map[string][]efOccupancyEntry // "2006-01-02" -> entries + +// buildEFOccupancyIndex computes the index in one O(len(merged)) pass. +func buildEFOccupancyIndex(merged map[string]RawCelebration, year int, sel Selection) efOccupancyIndex { + idx := efOccupancyIndex{} + for slug, rc := range merged { + cel := buildCelebration(slug, rc) + when, ok := celebrationDate(cel, year, sel) + if !ok { + continue + } + key := when.Format("2006-01-02") + idx[key] = append(idx[key], efOccupancyEntry{slug: slug, rank: cel.Rank}) + } + return idx +} + +// occupied reports whether some entry other than exceptSlug at date d has a +// rank allowed accepts -- computeEF's former occupiedByRank closure's exact +// semantics, read from the precomputed index instead of a fresh scan. Safe +// to call concurrently: idx is never mutated after buildEFOccupancyIndex +// returns it (Go's map type permits unlimited concurrent reads with no +// concurrent write). +func (idx efOccupancyIndex) occupied(d time.Time, exceptSlug string, allowed func(Rank) bool) bool { + for _, e := range idx[d.Format("2006-01-02")] { + if e.slug == exceptSlug { + continue + } + if allowed(e.rank) { + return true + } + } + return false +} + +// efTransferPlanCached is (efTransferPlan, buildEFOccupancyIndex), memoised +// together by (year, sel, merged content). It is safe and correct to share +// across every caller in the process: two calls with the SAME key are, by +// construction of the key, calls efTransferPlan/buildEFOccupancyIndex +// themselves would resolve identically (same year, same Selection, same +// sanctoral content), so returning a cached result changes nothing about +// what is computed -- only when. The returned plan is a fresh copy per call +// (clonePlan), never the cached instance, so no caller can mutate shared +// cache state even though computeEF's own use of it is read-only today. The +// occupancy index is returned WITHOUT copying (unlike plan, it can hold one +// entry per merged slug, up to ~330 on shipped data, so copying it on every +// call -- most of them hits -- would give back a real slice of the win this +// exists to capture); this is safe only because it is genuinely immutable +// after construction (see efOccupancyIndex's own doc comment) and no code +// anywhere writes to a returned index. +func efTransferPlanCached(year int, merged map[string]RawCelebration, sel Selection) (map[string]time.Time, efOccupancyIndex) { key := efTransferPlanCacheKey{year: year, sel: sel, hash: hashMergedForPlan(merged)} efTransferPlanCache.mu.Lock() if el, ok := efTransferPlanCache.entries[key]; ok { efTransferPlanCache.order.MoveToFront(el) - plan := el.Value.(*efTransferPlanCacheEntry).plan + entry := el.Value.(*efTransferPlanCacheEntry) + plan, occ := entry.plan, entry.occupancy efTransferPlanCache.mu.Unlock() - return clonePlan(plan) + return clonePlan(plan), occ } efTransferPlanCache.mu.Unlock() - // Compute outside the lock: efTransferPlan is the expensive call this - // cache exists to avoid repeating, and holding the mutex across it would - // serialise every concurrent miss on DIFFERENT keys, not just protect - // the shared map/list. - plan := efTransferPlan(year, merged, sel, occupiedByClass1, occupiedByClass1Or2) + // Compute outside the lock: building the index and the plan is the + // expensive work this cache exists to avoid repeating, and holding the + // mutex across it would serialise every concurrent miss on DIFFERENT + // keys, not just protect the shared map/list. + occ := buildEFOccupancyIndex(merged, year, sel) + plan := efTransferPlan(year, merged, sel, occ) efTransferPlanCache.mu.Lock() defer efTransferPlanCache.mu.Unlock() @@ -102,16 +183,17 @@ func efTransferPlanCached(year int, merged map[string]RawCelebration, sel Select // were computing our own copy unlocked. Same key => same result by // construction, so keep the existing entry and just bump recency. efTransferPlanCache.order.MoveToFront(el) - return clonePlan(el.Value.(*efTransferPlanCacheEntry).plan) + entry := el.Value.(*efTransferPlanCacheEntry) + return clonePlan(entry.plan), entry.occupancy } - el := efTransferPlanCache.order.PushFront(&efTransferPlanCacheEntry{key: key, plan: plan}) + el := efTransferPlanCache.order.PushFront(&efTransferPlanCacheEntry{key: key, plan: plan, occupancy: occ}) efTransferPlanCache.entries[key] = el if efTransferPlanCache.order.Len() > efTransferPlanCacheCap { oldest := efTransferPlanCache.order.Back() efTransferPlanCache.order.Remove(oldest) delete(efTransferPlanCache.entries, oldest.Value.(*efTransferPlanCacheEntry).key) } - return clonePlan(plan) + return clonePlan(plan), occ } func clonePlan(plan map[string]time.Time) map[string]time.Time { @@ -128,16 +210,16 @@ func clonePlan(plan map[string]time.Time) map[string]time.Time { // logical content always hashes identically, regardless of which Layer // stack produced it or what order ranging over it visits entries. // -// EVERY field of every entry is hashed, not just the ones efTransferPlan's -// own read path happens to touch today (Rank, Date via celebrationDate). -// occupiedByClass1/Or2 (closures over merged, passed in by computeEF) scan -// ALL of merged looking for competing entries of any rank, and which -// entries even qualify as class-1 in the first place is ITSELF computed -// from this data (buildCelebration's "rank" field) -- so hashing only a -// subset of fields would risk exactly the silent-stale-cache bug this +// EVERY field of every entry is hashed, not just the ones the plan's or the +// occupancy index's own read paths happen to touch today (Rank, Date via +// celebrationDate). efOccupancyIndex indexes ALL of merged at every rank +// (not just class-1/2 -- occ.occupied's `allowed` parameter is arbitrary), +// and which entries even qualify as class-1 in the first place is ITSELF +// computed from this data (buildCelebration's "rank" field) -- so hashing +// only a subset of fields would risk exactly the silent-stale-cache bug this // function exists to prevent: a user overlay that changes, say, a // "suppress" or an unrelated feast's rank would not change the hash, and a -// stale plan would keep being served. +// stale plan or index would keep being served. func hashMergedForPlan(merged map[string]RawCelebration) [32]byte { slugs := make([]string, 0, len(merged)) for slug := range merged { |