From b24702cc9b8d7f2e408bb92032e8f7fa2aaa836b Mon Sep 17 00:00:00 2001 From: Lukasz Kasprzak Date: Mon, 24 Aug 2026 22:02:39 +0200 Subject: perf(calendar): precompute the EF occupancy index alongside the transfer plan The prior commit (ea6e598) memoised efTransferPlan but left the SAME occupiedByClass1/Or2 O(len(merged)) scan pattern in a second place: transferIfImpededEF's own fallback path, called from computeEF once per day for every class-1 candidate the (now cached) plan does not resolve -- confirmed by CPU profile, not assumed: computeEF.func1 (the old occupiedByRank closure) was ~62% of BenchmarkDays7EF's total time, almost all of it inside buildCelebration, called from BOTH efTransferPlan internally AND this second, uncached site. Before optimising, established precisely what "occupied" depends on, per the coordinator's warning that occupancy might genuinely mutate during planning (efTransferPlan's own `claimed` map suggested as much). It does not: occupiedByRank asks only "does some OTHER entry's ORIGINAL, untransferred date (buildCelebration + celebrationDate, which never considers a transfer) equal d" -- a pure function of (merged content, year, sel) alone, identical to what the transfer-plan cache already keys on. `claimed`, by contrast, genuinely mutates during one planning pass (it tracks which TARGET days a transfer walk has already assigned) and is NOT part of occupiedByRank's computation at all -- it remains computed fresh inside efTransferPlan every call, untouched by this change. These are independent, not the same thing wearing two names: efTransferPlan's own forward-walk loop already checks both, plus a third condition (the target day's own temporal class), as separate disjuncts. Given that, an occupancy INDEX -- not a second cache, and not a "we already know the answer" shortcut derived from plan's absence (which would have been correct for the transferIfImpededEF fallback's own control flow ONLY by coincidence: it ignores the unconditional All Souls Sunday-transfer special case that runs before the class-1 check on ANY rank, so a shortcut skipping straight past it would misfire the moment a user overlay retagged All Souls class-1, however unlikely on shipped data) -- is the safe fix: buildEFOccupancyIndex does the same merged-scan ONCE, into date -> []{slug, rank}, and .occupied does the exact O(1)-ish lookup + tiny-list filter occupiedByRank always computed, just precomputed. transferIfImpededEF's own signature, control flow and All Souls handling are completely unchanged; only what its two closure parameters read from changed. The index shares the transfer-plan cache's existing key (year, Selection, SHA-256 of merged) rather than adding a new one -- both are pure in exactly those three inputs, built in the same pass, so one key correctly covers both. Only the plan is copied per call (clonePlan); the index, which can hold one entry per merged slug (~330 on shipped data), is returned uncopied and documented immutable-after-construction -- safe under Go's concurrent-read guarantee since nothing anywhere writes to a returned index. New TestEFOccupancyIndexDetectsSameDateClass1Collision covers a path no existing test reached: two class-1 SANCTORAL entries sharing one ORIGINAL date (St Joseph/the Annunciation, covered by the prior commit's tests, collide via HOLY WEEK's temporal precedence on DIFFERENT dates, never with each other). A synthetic overlay (Compute's own public API, same style as the existing tests) puts two class-1 entries on the same otherwise-ordinary date: alone, either is simply observed; both together, RG 97/98 transfer both forward and the shared date reverts to its temporal office. Mutation-proved: dropping the index's exceptSlug self-exclusion (reverted after) made the test fail immediately -- every class-1 entry saw itself in the index and wrongly self-impeded, even the single-entry case. TestEFTransferPlanCacheConcurrentUse gained a third, disjoint key exercising this same collision path from goroutines alongside the two existing ones; `go test -race` on the whole package is clean. Benchmarked (interleaved before/after, same method throughout this branch): BenchmarkDays7EF drops from ~46-48ms (the prior commit's own plan-cache-only state) to ~15-18ms/op (allocs 208639 -> 98727, -53%; bytes 16.1MB -> 4.2MB, -74%) -- roughly a further 3x, ~4.6x cumulative against the original ~74ms. BenchmarkDaysWeek (OF, which never touches any of this) is unaffected: ~4.9-5.9ms/op both before and after, with byte-for-byte identical allocs/bytes in every run -- the ms-level wobble is machine noise, not a regression. A fresh CPU profile confirms the new remaining bottleneck precisely: writeSortedFields/hashMergedForPlan (the cache key's own SHA-256 of merged, ~330 entries) is now ~35% of total time, because it still runs on EVERY day (7x/week) to know whether a call is a cache hit, even though the work it gates now mostly isn't. Not fixed here: hoisting the key computation itself up to mobile.Days's batch level (mirroring the first commit on this branch, b6ee8f0) would need Compute's public signature to accept a precomputed key, a bigger surface change than this task's scope, reported rather than taken unilaterally. Output identity re-verified: the same 492-case sweep (both forms, both UI languages, all four corpora, the leap day/Triduum/Requiem/season- boundary dates, and the three Joseph/Annunciation years) is byte-identical (SHA-256-equal) before and after -- the same SHA-256 as the prior commit's own sweep, confirming zero output drift across the whole chain. go test ./... and make ci (both build tags, oracle/differential suite included) are green; go test -race on the whole internal/calendar package is clean. --- internal/calendar/transfer_plan_cache.go | 154 +++++++++++++++++++++++-------- 1 file changed, 118 insertions(+), 36 deletions(-) (limited to 'internal/calendar/transfer_plan_cache.go') 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 { -- cgit v1.3