From ea6e59862dbdb607b9bcb221212a85ee3e4bd84a Mon Sep 17 00:00:00 2001 From: Lukasz Kasprzak Date: Mon, 24 Aug 2026 21:42:48 +0200 Subject: perf(calendar): memoise the EF transfer plan across a shared calendar computeEF calls efTransferPlan once per day, but the plan is pure in (year, the merged sanctoral content, Selection) and identical for every day sharing those three -- e.g. every date in one mobile.Days week. Rebuilding it per day was a real cost: efTransferPlan walks every merged entry looking for class-1 candidates, and for each one it considers, occupiedByClass1/Or2 (an occurrence check it also uses) walks merged AGAIN -- confirmed by CPU profile, not just by reading the code (github.com/lukaszkasprzak/lectio/internal/calendar.computeEF.func1, the occupiedByRank closure, at ~62% of BenchmarkDays7EF's total time before this fix, almost all of it inside buildCelebration). efTransferPlanCached (transfer_plan_cache.go) wraps efTransferPlan with a small, bounded, thread-safe LRU (container/list + sync.Mutex, capped at 64 entries -- gomobile may call in from multiple goroutines, and an unbounded map keyed by year would grow as a user scrolls through decades). The cache key is (year, Selection, a SHA-256 of merged's full content): merged is a map, so it cannot be a map key field itself, and Go's randomised map iteration order means two calls with identical content can visit it differently, so the hash sorts slugs and, within each entry, its Fields/Variant keys before hashing, and covers every field of every entry -- not just Rank/Date, the ones efTransferPlan's own read path happens to touch today, because which entries even qualify as class-1 is itself computed from that data, and occupiedByClass1/Or2 scan ALL of merged, not just the class-1 subset. Selection is included even though EF date resolution ignores it today (resolveDate never reads its sel parameter) -- keying on it costs nothing (four small strings) and protects a future change from silently poisoning a cache that never accounted for it. The returned map is always a fresh copy (clonePlan), never the cached instance, so sharing it across goroutines needs no further synchronisation. Verified the key is complete rather than trusted: with the content hash temporarily dropped from the key (mutation test, not committed), TestEFTransferPlanCacheInvalidatesOnOverlay failed immediately -- a plan warmed for the shipped 2008 calendar was wrongly served back for the same year with a user overlay applied (the Annunciation suppressed, which changes where the RG 96(a)/97/98 collision sends St Joseph: 31 March instead of 1 April, empirically confirmed against the pre-cache code before the test was written). TestEFTransferPlanCacheInvalidatesOnYear is a lighter companion covering the year field. TestEFTransferPlanCacheConcurrentUse hammers the cache from 12 goroutines across two different keys and reasserts correctness afterward; clean under `go test -race`. Benchmarked (interleaved before/after, same method as the readings.Prepare commit, to control for machine thermal drift): BenchmarkDays7EF drops from ~48-51ms to ~32-35ms/op (allocs 253810 -> 208639, -18%; bytes 28.1MB -> 16.1MB, -43%), roughly a third faster. BenchmarkDaysWeek (OF, which never calls efTransferPlan at all) is unaffected, ~3.5-4.1ms/op both before and after -- within noise, confirming this change is EF-only as intended. EF remains well outside OF's range (~32ms vs ~4ms), and a fresh CPU profile after this fix places the dominant remaining cost precisely: it is the SAME occupiedByClass1/Or2 pattern, but living OUTSIDE efTransferPlan -- transferIfImpededEF's own fallback path, called once per day for every class-1 candidate NOT already resolved by the (now cached) plan, i.e. the ordinarily-unimpeded ones (~15-20 of them), each triggering another O(len(merged)) scan. That call site was not part of what this task named, and memoising it is a materially different change (it is keyed per-candidate, not once per day), so it is reported here rather than folded into this commit. Output identity re-verified: a 492-case sweep of mobile.Day/mobile.Days (both forms, both UI languages, all four corpora, a leap day, the Sacred Triduum, a Requiem day, Christmas/Pentecost/Assumption/All Souls windows, and the three Joseph/Annunciation transfer-collision years this fix specifically touches -- 2008, 2035, 2046) produced byte-identical (SHA-256-equal) JSON before and after. go test ./... and make ci (both build tags, oracle/differential suite included) are green. --- internal/calendar/transfer_plan_cache.go | 187 +++++++++++++++++++++++++++++++ 1 file changed, 187 insertions(+) create mode 100644 internal/calendar/transfer_plan_cache.go (limited to 'internal/calendar/transfer_plan_cache.go') diff --git a/internal/calendar/transfer_plan_cache.go b/internal/calendar/transfer_plan_cache.go new file mode 100644 index 0000000..fdf62f7 --- /dev/null +++ b/internal/calendar/transfer_plan_cache.go @@ -0,0 +1,187 @@ +package calendar + +import ( + "container/list" + "crypto/sha256" + "io" + "sort" + "sync" + "time" +) + +// efTransferPlanCacheCap bounds the memoised EF transfer-plan cache (below) +// so a long-running gomobile process cannot grow it without bound as a user +// scrolls through many years -- capacity 8417 (the whole 1583-9999 domain) +// would be a real, if small, leak risk over a long enough session; 64 keeps +// memory negligible (each entry is a handful of time.Time values) while +// still giving a warm cache for the realistic access pattern, a week/month +// 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: +// +// - year: efTransferPlan's own first argument (Easter, the transfer +// window, every celebrationDate call). +// - sel: passed through to celebrationDate on every candidate, which +// currently ignores it (resolveDate never reads its sel parameter) -- +// so it is a dead dependency TODAY. It is still part of the key: the +// parameter exists on the signature for a reason, and keying on it now +// costs nothing (Selection is four small strings) while protecting +// against a future change that makes EF date resolution +// Selection-sensitive silently poisoning a cache that never accounted +// for it. +// - a content hash of merged: efTransferPlan's real data dependency. +// merged is a map -- not itself comparable, so cannot be a map key +// field -- and mergeLayers rebuilds a brand-new map with fresh Go map +// iteration order on every call even when the underlying layers are +// unchanged, so identity/pointer comparison cannot be used either only +// a hash of merged's actual content is both correct (invalidates +// whenever the content genuinely differs -- a user overlay edited, a +// different layer stack) and cache-friendly (hits whenever it does not, +// regardless of which Layer objects or map iteration produced it). See +// hashMergedForPlan for what is and is not hashed. +type efTransferPlanCacheKey struct { + year int + sel Selection + hash [32]byte +} + +// efTransferPlanCacheEntry is one memoised plan, doubling as the LRU list's +// payload so eviction and lookup share one map. +type efTransferPlanCacheEntry struct { + key efTransferPlanCacheKey + plan map[string]time.Time +} + +// efTransferPlanCache is a small, bounded, thread-safe LRU in front of +// efTransferPlan. gomobile may call Day/Days in from multiple goroutines, so +// the map and list are guarded by one mutex; efTransferPlan itself (the +// expensive part) runs OUTSIDE the lock so concurrent misses on different +// keys do not serialise behind each other -- see efTransferPlanCached. +var efTransferPlanCache = struct { + mu sync.Mutex + entries map[efTransferPlanCacheKey]*list.Element + 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 { + + 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 + efTransferPlanCache.mu.Unlock() + return clonePlan(plan) + } + 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) + + efTransferPlanCache.mu.Lock() + defer efTransferPlanCache.mu.Unlock() + if el, ok := efTransferPlanCache.entries[key]; ok { + // Lost a race: another goroutine populated this exact key while we + // 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) + } + el := efTransferPlanCache.order.PushFront(&efTransferPlanCacheEntry{key: key, plan: plan}) + 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) +} + +func clonePlan(plan map[string]time.Time) map[string]time.Time { + out := make(map[string]time.Time, len(plan)) + for k, v := range plan { + out[k] = v + } + return out +} + +// hashMergedForPlan hashes merged's full content deterministically. Go's map +// iteration order is randomised per-process, so slugs (and, within each +// entry, its Fields and Variant keys) are sorted before hashing -- the same +// 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 +// 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. +func hashMergedForPlan(merged map[string]RawCelebration) [32]byte { + slugs := make([]string, 0, len(merged)) + for slug := range merged { + slugs = append(slugs, slug) + } + sort.Strings(slugs) + + h := sha256.New() + for _, slug := range slugs { + rc := merged[slug] + io.WriteString(h, "slug=") + io.WriteString(h, slug) + h.Write([]byte{0}) + writeSortedFields(h, rc.Fields) + variants := make([]string, 0, len(rc.Variants)) + for v := range rc.Variants { + variants = append(variants, v) + } + sort.Strings(variants) + for _, v := range variants { + io.WriteString(h, "variant=") + io.WriteString(h, v) + h.Write([]byte{0}) + writeSortedFields(h, rc.Variants[v]) + } + h.Write([]byte{1}) // record separator, so "ab"+"c" cannot collide with "a"+"bc" + } + var sum [32]byte + copy(sum[:], h.Sum(nil)) + return sum +} + +// writeSortedFields writes fields into h as sorted "key=value\x00" records +// (see hashMergedForPlan). +func writeSortedFields(h io.Writer, fields map[string]string) { + keys := make([]string, 0, len(fields)) + for k := range fields { + keys = append(keys, k) + } + sort.Strings(keys) + for _, k := range keys { + io.WriteString(h, k) + h.Write([]byte{'='}) + io.WriteString(h, fields[k]) + h.Write([]byte{0}) + } +} -- cgit v1.3