diff options
| author | Somhairle H. Marisol <[email protected]> | 2026-09-22 10:46:16 +0800 |
|---|---|---|
| committer | Somhairle H. Marisol <[email protected]> | 2026-09-22 10:46:16 +0800 |
| commit | a0597455629618a282b582d13c23bfeab786e7d2 (patch) | |
| tree | 5809eb48e9fcd7cba6823ba0b6c8ae5ae8a28ce2 /src/LivingVillage.Kernel | |
| parent | 164f4749460a304c1aaad4900ef3facc29859eb0 (diff) | |
| download | living-village-a0597455629618a282b582d13c23bfeab786e7d2.tar.gz | |
perf(kernel): P27 第二步 — Rumor 扫描去装箱 + 裁剪判定 O(1)
两条互相独立、均不改变保留集合与查询结果的优化:
1) 扫描去装箱:latestRumorFor / rumorIsDuplicate 用 `=` 比较 [<Struct>] 的
NpcId/RumorId(含 RumorId option)会走泛型结构相等并逐条装箱(实测 ~24 B/条,
Sim.chat 单独测得 N=16000 时 393,736 B/次、随 N 线性)。改为先解构底层
int/int64 再比较;Parent 用 int64 option 比较替代 RumorId option 结构相等。
语义完全等价,扫描不再逐条分配。
2) 裁剪判定 O(1):World 新增派生镜像 RumorCount/RumorOldestDay(不参与存档,
读档由列表经 rumorWorkingSetStats 重建)。appendRumor 用「count+1>capacity
或 min(oldest,day)<cutoff」O(1) 判定,仅真需裁剪时才走 trimRumors;旧 consRumor
每次追加都 rumorsNeedTrim 全表扫一遍。条件与 needTrim 逐字等价,保留集合相同。
等价性验证:5 天 2000 聊天/天跑两遍 WorldSave.save 逐字节相同,
RumorCount/RumorOldestDay 与对列表重算一致(count=8000、oldest_day=1)。
Kernel 长跑基准 30 NPC × 2000 聊天/天(--rumor-bench D 30 2000):
days 修复前 alloc / ms 修复后 alloc / ms
3 930,716,456 / 1626.7 482,716,192 / 1511.3
30 13,419,045,864 / 12182.5 4,884,067,640 / 8879.6
60 27,297,668,608 / 23769.7 9,774,660,360 / 17078.2
60 天分配 -64%、耗时 -28%,retained_id_checksum=927964000 前后一致。
门槛:final_digest=953775FAEB2F... 三次一致、performance_determinism=PASS;
Kernel 92 / Desktop 143 全绿;--cost-probe 1/5 天 18.7s/18.8GB、90.4s/94.6GB
(全模拟分配由逐 tick NPC 快照主导,谣言子系统占比很小,故全模拟基本持平)。
Diffstat (limited to 'src/LivingVillage.Kernel')
| -rw-r--r-- | src/LivingVillage.Kernel/Sim.fs | 73 | ||||
| -rw-r--r-- | src/LivingVillage.Kernel/WorldSave.fs | 3 |
2 files changed, 62 insertions, 14 deletions
diff --git a/src/LivingVillage.Kernel/Sim.fs b/src/LivingVillage.Kernel/Sim.fs index cedadfa..5c4e107 100644 --- a/src/LivingVillage.Kernel/Sim.fs +++ b/src/LivingVillage.Kernel/Sim.fs @@ -192,6 +192,12 @@ module Sim = Npcs: Npc[] Events: InteractionEvent list Rumors: RumorEvent list + /// 派生镜像:工作集条数(= Rumors.Length)。不参与存档序列化,读档由列表重建; + /// 用于把每追加一条都要全表扫描的裁剪判定降为 O(1)。 + RumorCount: int + /// 派生镜像:工作集内最小 DayIndex(空表为 Int64.MaxValue)。语义等价于 + /// `rumorsNeedTrim` 的「存在早于保留窗口的条目」判定。 + RumorOldestDay: int64 Annals: AnnalEntry list } type DialogueFailure = @@ -481,6 +487,8 @@ module Sim = Npcs = [| npc |] Events = [] Rumors = [] + RumorCount = 0 + RumorOldestDay = System.Int64.MaxValue Annals = [] } let initialWorldN (seed: uint64) (count: int) : World = @@ -680,19 +688,49 @@ module Sim = else rumors - /// 追加一条谣言并顺手裁剪工作集;容量内且新鲜时等价于 `rumor :: rumors`。 - let private consRumor (nowTick: int64) (rumor: RumorEvent) (rumors: RumorEvent list) : RumorEvent list = - trimRumors nowTick (rumor :: rumors) + /// 工作集派生统计:(条数, 最小 DayIndex;空表为 Int64.MaxValue)。仅裁剪/读档等非热路径调用。 + let rumorWorkingSetStats (rumors: RumorEvent list) : int * int64 = + rumors.Length, + (rumors |> List.fold (fun acc rumor -> min acc rumor.DayIndex) System.Int64.MaxValue) + + let private oldestRumorDay (rumors: RumorEvent list) : int64 = snd (rumorWorkingSetStats rumors) + + /// 追加一条谣言并维护派生元数据。容量内且新鲜时等价于 `rumor :: rumors`,且**不再全表扫描** + /// 判断是否需要裁剪(旧 `consRumor` 每次追加都会 `rumorsNeedTrim` 走一遍工作集); + /// 仅当条数超容量或存在早于保留窗口的条目时才走 `trimRumors`,保留集合与旧实现逐条相同。 + let private appendRumor (nowTick: int64) (rumor: RumorEvent) (world: World) : World = + let cutoffDay = max 0L (rumorDayIndex nowTick - rumorRetentionDays) + let nextCount = world.RumorCount + 1 + let nextOldest = min world.RumorOldestDay rumor.DayIndex + if nextCount > rumorCapacity || nextOldest < cutoffDay then + let trimmed = trimRumors nowTick (rumor :: world.Rumors) + { world with + Rumors = trimmed + RumorCount = trimmed.Length + RumorOldestDay = oldestRumorDay trimmed } + else + { world with + Rumors = rumor :: world.Rumors + RumorCount = nextCount + RumorOldestDay = nextOldest } + + /// `NpcId`/`RumorId` 是 `[<Struct>]` 单例判别联合:直接用 `=` 比较会走泛型结构相等并 + /// 在每次比较时为两侧装箱(实测 ~24 B/次)。在按 tick 全表扫描的热路径里逐条比较, + /// 这是 Rumor 分配的主要来源。这里改为先解构出底层 int/int64 再比较(语义完全等价, + /// 仅去掉装箱),扫描不再产生逐条分配。 + let inline private npcIdValue (NpcId id) : int = id + let inline private rumorIdValue (RumorId id) : int64 = id let private latestRumorFor (receiver: NpcId) (world: World) : RumorEvent option = // 工作集最新在前且 Tick 非递增:第一条命中的即“Tick 最大、Id 最大”,与原实现 // (filter 后 sortByDescending 取头)等价;窗口外无分配提前返回。 + let receiverId = npcIdValue receiver let rec loop (rest: RumorEvent list) : RumorEvent option = match rest with | [] -> None | rumor :: tail -> if world.Tick - rumor.Tick > rumorFreshnessTicks then None - elif rumor.Receiver = receiver + elif npcIdValue rumor.Receiver = receiverId && rumor.Tick <= world.Tick && rumorStrengthAt world.Tick rumor >= rumorMinimumStrength then Some rumor else loop tail @@ -783,11 +821,13 @@ module Sim = let avatarMemory = recordMemory world.Tick (Dialogue(target, intent, response)) world.Avatar.Mind.Memory let event = { Tick = world.Tick; Kind = DialogueEvent outcome } let updated = - { world with - Avatar = { world.Avatar with Mind = { world.Avatar.Mind with Memory = avatarMemory } } - Npcs = newNpcs - Events = world.Events @ [ event ] - Rumors = consRumor world.Tick rumor world.Rumors } + appendRumor + world.Tick + rumor + { world with + Avatar = { world.Avatar with Mind = { world.Avatar.Mind with Memory = avatarMemory } } + Npcs = newNpcs + Events = world.Events @ [ event ] } let withRumorAnnal = appendAnnal { Tick = world.Tick @@ -826,16 +866,21 @@ module Sim = RecentMemory = List.truncate 8 npc.Mind.Memory }) let private rumorIsDuplicate (request: ChatRequest) (parent: RumorEvent option) (world: World) : bool = - let parentId = parent |> Option.map (fun rumor -> rumor.Id) + let parentId = parent |> Option.map (fun rumor -> rumorIdValue rumor.Id) + let narratorId = npcIdValue request.Narrator + let receiverId = npcIdValue request.Receiver // 窗口外条目强度必 < rumorMinimumStrength,与原全表 exists 等价;命中或越窗即无分配返回。 + // `Parent` 用底层 int64 比较而非 `RumorId option` 结构相等,避免逐条装箱。 let rec loop (rest: RumorEvent list) : bool = match rest with | [] -> false | rumor :: tail -> if world.Tick - rumor.Tick > rumorFreshnessTicks then false - elif rumor.Narrator = request.Narrator - && rumor.Receiver = request.Receiver - && rumor.Parent = parentId + elif npcIdValue rumor.Narrator = narratorId + && npcIdValue rumor.Receiver = receiverId + && (match rumor.Parent with + | Some parentRumor -> parentId = Some(rumorIdValue parentRumor) + | None -> parentId.IsNone) && rumor.Tick <= world.Tick && rumorStrengthAt world.Tick rumor >= rumorMinimumStrength then true else loop tail @@ -936,7 +981,7 @@ module Sim = { npc with Mind = { npc.Mind with Memory = recordMemory world.Tick (Rumor rumor.Id) npc.Mind.Memory } } { chatted with Npcs = newNpcs } - let updated = { withReceiverRumor with Rumors = consRumor world.Tick rumor world.Rumors } + let updated = appendRumor world.Tick rumor withReceiverRumor ChatSucceeded( Some rumor, appendAnnal diff --git a/src/LivingVillage.Kernel/WorldSave.fs b/src/LivingVillage.Kernel/WorldSave.fs index f1b0be3..b3bdfa9 100644 --- a/src/LivingVillage.Kernel/WorldSave.fs +++ b/src/LivingVillage.Kernel/WorldSave.fs @@ -645,6 +645,7 @@ module WorldSave = let events = List.init eventCount (fun index -> readInteraction reader (sprintf "event[%d]" index)) let rumorCount = readCount reader "rumors" let rumors = List.init rumorCount (fun index -> readRumor reader (sprintf "rumor[%d]" index)) + let rumorStats = rumorWorkingSetStats rumors let annalCount = readCount reader "annals" let annals = List.init annalCount (fun index -> readAnnal reader (sprintf "annal[%d]" index)) let todayTask = @@ -667,6 +668,8 @@ module WorldSave = Npcs = npcs Events = events Rumors = rumors + RumorCount = fst rumorStats + RumorOldestDay = snd rumorStats Annals = annals }, occupation) with |
