summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSomhairle H. Marisol <[email protected]>2026-09-22 10:46:16 +0800
committerSomhairle H. Marisol <[email protected]>2026-09-22 10:46:16 +0800
commita0597455629618a282b582d13c23bfeab786e7d2 (patch)
tree5809eb48e9fcd7cba6823ba0b6c8ae5ae8a28ce2 /src
parent164f4749460a304c1aaad4900ef3facc29859eb0 (diff)
downloadliving-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')
-rw-r--r--src/LivingVillage.Kernel.Tests/RelationTests.fs4
-rw-r--r--src/LivingVillage.Kernel.Tests/RumorTests.fs2
-rw-r--r--src/LivingVillage.Kernel.Tests/TradeTests.fs2
-rw-r--r--src/LivingVillage.Kernel/Sim.fs73
-rw-r--r--src/LivingVillage.Kernel/WorldSave.fs3
5 files changed, 70 insertions, 14 deletions
diff --git a/src/LivingVillage.Kernel.Tests/RelationTests.fs b/src/LivingVillage.Kernel.Tests/RelationTests.fs
index b98252d..1a6d178 100644
--- a/src/LivingVillage.Kernel.Tests/RelationTests.fs
+++ b/src/LivingVillage.Kernel.Tests/RelationTests.fs
@@ -47,6 +47,8 @@ module RelationHarness =
Npcs = [| mkNpc 0 mem0; mkNpc 1 mem1 |]
Events = []
Rumors = []
+ RumorCount = 0
+ RumorOldestDay = System.Int64.MaxValue
Annals = [] }
let chatted (tick: int64) (partner: int) : MemoryEvent =
@@ -208,6 +210,8 @@ type RelationTests () =
Npcs = [| self; nearest; alternate |]
Events = []
Rumors = []
+ RumorCount = 0
+ RumorOldestDay = System.Int64.MaxValue
Annals = [] }
let next = Sim.step RelationHarness.zeroInput world
match List.tryHead next.Npcs.[0].Mind.Memory with
diff --git a/src/LivingVillage.Kernel.Tests/RumorTests.fs b/src/LivingVillage.Kernel.Tests/RumorTests.fs
index 2cbb189..e8cf07a 100644
--- a/src/LivingVillage.Kernel.Tests/RumorTests.fs
+++ b/src/LivingVillage.Kernel.Tests/RumorTests.fs
@@ -52,6 +52,8 @@ module private RumorHarness =
Npcs = Array.init count npc
Events = []
Rumors = []
+ RumorCount = 0
+ RumorOldestDay = System.Int64.MaxValue
Annals = [] }
let readyForChat (world: World) : World =
diff --git a/src/LivingVillage.Kernel.Tests/TradeTests.fs b/src/LivingVillage.Kernel.Tests/TradeTests.fs
index 77e5658..fa40ac3 100644
--- a/src/LivingVillage.Kernel.Tests/TradeTests.fs
+++ b/src/LivingVillage.Kernel.Tests/TradeTests.fs
@@ -56,6 +56,8 @@ module private TradeHarness =
npc 1 sellerMoney sellerHunger sellerFood sellerMemory None |]
Events = []
Rumors = []
+ RumorCount = 0
+ RumorOldestDay = System.Int64.MaxValue
Annals = [] }
let request quantity =
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