CppCon 2025 学习:Building a High-Performance Binary Serialization Format with In-Place Modification

你有一个内存中的数据结构，你希望：序列化 = 把“结构化数据”变成“字节序列”反过来：这是一个典型“看起来很适合 memcpy”的结构体为什么这是“no good”（非常重要）问题 1：Endianness（字节序）不同 CPU 的整数存储顺序不同：架构字节序x86Little Endian网络协议Big Endian例如：0x123456780x123456780x12345678在内存中可能是

虾球xz

610人浏览 · 2026-01-12 18:31:22

虾球xz · 2026-01-12 18:31:22 发布

一、什么是 Serialization（序列化）？

1⃣ 问题背景

你有一个内存中的数据结构，你希望：

通过网络发送
保存到文件或数据库
在不同进程之间共享
但问题是：

内存 ≠ 字节流
网络、文件、进程间通信只认识：

0x01 0xAF 0x3C 0x00 ...

序列化 = 把“结构化数据”变成“字节序列”
反过来：

反序列化 = 把字节重新还原成原始数据结构

二、示例数据结构：Trade

struct Trade {
    unsigned      price;       // 成交价格
    unsigned      volume;      // 成交数量
    unsigned long timestamp;   // 时间戳
    char          tradeId[20]; // 交易ID
    char          buyBroker[5];// 买方券商
    char          sellBroker[5];// 卖方券商
    unsigned      flags;       // 标志位
};

这是一个典型“看起来很适合 memcpy”的结构体

三、最直觉的“错误做法”

✗ 直接 memcpy 整个结构体

size_t serialize(char *buffer, const Trade& trade)
{
    // ✗ 直接把内存拷贝到 buffer
    memcpy(buffer, &trade, sizeof(trade));
    return sizeof(Trade);
}

为什么这是“no good”（非常重要）

问题 1：Endianness（字节序）

不同 CPU 的整数存储顺序不同：

架构	字节序
x86	Little Endian
网络协议	Big Endian

例如：
$0 x 12345678$
在内存中可能是：

78 56 34 12   // 小端
12 34 56 78   // 大端

直接 memcpy 会导致接收方解读错误

问题 2：类型大小不一致

unsigned       // 可能是 4 字节
unsigned long  // 可能是 4 字节，也可能是 8 字节

平台	unsigned long
32-bit	4 bytes
Linux x64	8 bytes
嵌入式	4 bytes

序列化必须跨平台，不能依赖“本机类型大小”

问题 3：结构体填充（Padding）

编译器为了对齐，会插入不可见字节：

struct Example {
    char  a;   // 1 byte
    int   b;   // 4 bytes
};

内存布局可能是：

[a][pad][pad][pad][b][b][b][b]

Padding：

内容未定义
平台相关
memcpy 会把“垃圾字节”一起拷走

✗ 总结一句话

memcpy(struct) = 序列化灾难三件套：字节序 + 类型大小 + padding

四、正确的思路：显式序列化

核心原则（必背）

✓ 使用固定大小类型
✓ 明确字段顺序
✓ 明确字节序（统一为网络序）
✓ 不依赖编译器布局

五、一个“工程级正确”的序列化示例

#include <cstdint>
#include <cstring>
#include <arpa/inet.h> // htonl / ntohl
// 返回写入的字节数
size_t serialize(char* buffer, const Trade& trade)
{
    char* start = buffer;
    // ---- price ----
    uint32_t price = htonl(trade.price);   // 转为网络字节序
    memcpy(buffer, &price, sizeof(price));
    buffer += sizeof(price);
    // ---- volume ----
    uint32_t volume = htonl(trade.volume);
    memcpy(buffer, &volume, sizeof(volume));
    buffer += sizeof(volume);
    // ---- timestamp ----
    uint64_t timestamp = htobe64(trade.timestamp); // 64位显式转换
    memcpy(buffer, &timestamp, sizeof(timestamp));
    buffer += sizeof(timestamp);
    // ---- tradeId ----
    memcpy(buffer, trade.tradeId, sizeof(trade.tradeId));
    buffer += sizeof(trade.tradeId);
    // ---- buyBroker ----
    memcpy(buffer, trade.buyBroker, sizeof(trade.buyBroker));
    buffer += sizeof(trade.buyBroker);
    // ---- sellBroker ----
    memcpy(buffer, trade.sellBroker, sizeof(trade.sellBroker));
    buffer += sizeof(trade.sellBroker);
    // ---- flags ----
    uint32_t flags = htonl(trade.flags);
    memcpy(buffer, &flags, sizeof(flags));
    buffer += sizeof(flags);
    // 返回总长度
    return buffer - start;
}

六、为什么这个版本是“好”的？

使用固定宽度类型

uint32_t
uint64_t

➡ 保证：
$\text{字段大小在所有平台一致}$

显式字节序转换

htonl   // host → network (32-bit)
htobe64 // host → big endian (64-bit)

网络协议统一使用 Big Endian

完全避免 padding

每个字段单独写
顺序固定
没有隐含字节

七、反序列化（概念对称）

反序列化 = 反向操作：

price = ntohl(price);
timestamp = be64toh(timestamp);

记忆法则：

serialize：hton*
deserialize：ntoh*

八、什么时候“memcpy 整个 struct”才安全？

几乎只有这三种情况同时满足才行：

同一编译器
同一平台
同一进程 / 同一机器
即使这样，也极度不推荐

九、一句话总结（面试 / 工程）

Serialization 不是“拷贝内存”，而是“定义协议”。

一、手写序列化：为什么“更好，但仍然不够好”

你已经从：

memcpy(&trade, sizeof(trade))

升级到了：

htonl / 固定宽度类型 / 显式写字段

这是巨大进步，但问题依然存在。

1⃣ 大量样板代码（Boilerplate）

uint32_t price = htonl(trade.price);
memcpy(buffer, &price, sizeof(price));
buffer += sizeof(price);

每个字段都要：

定义临时变量
转换字节序
memcpy
移动指针
字段越多 → 错误概率指数上升

2⃣ 发送端和接收端必须 100% 严格一致

你实际上在隐式定义协议：

[price][volume][timestamp][tradeId][buyBroker][sellBroker][flags]

但这个协议：

✗ 没有版本号
✗ 没有字段标识
✗ 没有自描述能力
一旦顺序、长度、字段数量不一致：

数据不会报错，但会被“错误解析” —— 最危险

【schema】 n. 概要, 图解, 略图 [计] 模式名词复数形式: schemata;

3⃣ Schema 无法演进（Schema Evolution）

假设你现在想加一个字段：

unsigned brokerId;

结果：

情况	后果
新发送端 → 老接收端	数据错位
老发送端 → 新接收端	数据缺失
双方不同版本	✗ 灾难

旧系统无法忽略新字段

4⃣ 难以表达复杂/嵌套结构

例如：

struct Trade {
    Price price;
    std::vector<Order> legs;
};

你需要手写：

vector 长度
每个元素序列化
错误处理
回滚逻辑
维护成本极高

二、如何改进？两条根本路线

两种序列化世界观

┌──────────────┐     ┌──────────────┐
│ Schema-based │ vs  │ Schemaless   │
└──────────────┘     └──────────────┘

1⃣ Schema-based（基于 Schema）

接收方“事先知道数据长什么样”
特点：

有明确字段定义
通常使用 DSL（领域描述语言）
自动生成代码
常见代表：
Protobuf
Thrift
Avro
Cap’n Proto

2⃣ Schemaless（无 Schema）

数据本身携带“描述信息”
特点：

自描述
灵活
体积更大、性能较低
常见代表：
JSON
BSON
MessagePack（半 Schema）

三、Schema-Based 格式的核心思想

1⃣ 用 DSL 定义“数据契约”

message Trade {
    optional uint32 price     = 1;
    optional uint32 volume    = 2;
    optional uint64 timestamp = 3;
    optional string tradeId   = 4;
}

这不是代码，而是：

发送方 & 接收方之间的“协议合同”

2⃣ 从 Schema 自动生成代码

trade.proto
    ↓
protoc
    ↓
trade.pb.h / trade.pb.cc

你得到：

Trade::SerializeToString()
Trade::ParseFromArray()
不再手写 memcpy、字节序、长度管理

3⃣ 双方“部分”一致即可

关键点在于：字段是“编号”的，不是“位置”的

price     = 1;
volume    = 2;
timestamp = 3;
tradeId   = 4;

四、Schema 如何“安全演进”

添加新字段（向前/向后兼容）

message Trade {
    optional uint32 price     = 1;
    optional uint32 volume    = 2;
    optional uint64 timestamp = 3;
    optional string tradeId   = 4;
    optional string brokerId  = 5; // 新字段
}

结果：

版本	行为
老接收端	自动忽略 `brokerId`
新接收端	老数据中该字段为“未设置”

无需修改老系统

禁止的操作（会破坏兼容性）

✗ 重用字段编号：

price = 1;   // ✗ 不能改成别的含义

✗ 改变字段类型：

uint32 → string // ✗

五、Protobuf 在“线上”是如何编码的？

不是“按顺序写”的！

Protobuf 在 wire 上是：

(tag, value) 对

Tag 的组成

$tag=(field_number≪3)∣wire_type \text{tag} = (\text{field\_number} \ll 3) | \text{wire\_type}$
例如：

price = 1;   // field number = 1

编码时会包含：

[字段编号 + 类型][字段值]

所以：

字段顺序可以改变
字段可以缺失
字段可以新增

接收方解码逻辑

读 tag →
  看 field number →
    找到对应字段 →
      解码 value
    不认识？
      跳过

这就是 Schema Evolution 的数学基础

六、为什么这解决了“手写序列化”的所有痛点？

手写序列化问题	Schema-based 解决方案
大量样板代码	自动生成
顺序依赖	Tag-based
不能演进	字段编号
难嵌套	DSL 支持
易出错	编译期检查

七、一句话总结（非常重要）

Schema-based serialization 把“内存布局问题”升级成了“协议设计问题”。
这是专业系统和玩具代码的分水岭。

一、Schema-Based 编码（以 Protobuf 为例）

1⃣ 回顾：Trade 的 schema

message Trade {
    optional uint32 price     = 1; // 字段号 = 1
    optional uint32 volume    = 2; // 字段号 = 2
    optional uint64 timestamp = 3; // 字段号 = 3
    optional string tradeId   = 4; // 字段号 = 4
    ...
}

核心不是字段名，而是字段号（field number）

2⃣ 第一张 SVG：Protobuf 在线编码的含义

你画的第一张图，逻辑上可以抽象成：

① 字段 1：price = 100

[ field = 1, wire_type = VARINT ] [ 100 ]

解释：

1 → 字段号（field number）
VARINT → 编码方式（整数）
100 → 实际值
uint32 / uint64 都是 VARINT

② 字段 2：volume = 5000

[ field = 2, wire_type = VARINT ] [ 5000 ]

③ 字段 3：timestamp = 1738473049

[ field = 3, wire_type = VARINT ] [ 1738473049 ]

VARINT 是变长整数编码
值越大，占用字节越多，但小整数很省空间。

④ 字段 4：tradeId = “TRADEID_1234837ZZ”

[ field = 4, wire_type = LEN ] [ length ][ bytes... ]

LEN = length-delimited
先写长度
再写字符串字节内容

3⃣ Tag 是如何编码的（关键数学点）

Protobuf 的 tag 本身也是一个整数：
$tag=(field_number≪3)∣wire_type \text{tag} = (\text{field\_number} \ll 3)|\text{wire\_type}$
例如：

price = 1
VARINT = 0
$\ll 3) | 0 = 8$
这就是“字段号 + 类型”被压缩进一个整数里的原因

4⃣ 为什么说 Protobuf “有点自描述”

即使不知道 schema，也可以遍历整个消息
原因：

每个字段都有 tag
tag 告诉你：
- 字段编号
- 编码方式
你可以：
- 读
- 跳过
- 定位下一个字段
  但问题是：
  ✗ 你不知道：
1 叫不叫 price
4 是不是字符串、含义是什么
所以：能“解析结构”，但不能“理解语义”

5⃣ Schema-Based 的本质总结

能力	是否需要 schema
找到字段边界	✗
跳过未知字段	✗
知道字段含义	✓
知道字段名字	✓
类型安全访问	✓

Schema = 语义说明书

二、如果我事先不知道数据长什么样？

这正是你后半部分提出的问题：

数据是任意嵌套的？

map / array / object 混合？

字段完全动态？
这就进入 Schemaless 世界

三、Schemaless 格式的核心思想

1⃣ 不需要双方约定 schema

Schemaless 格式：

不需要 .proto
不需要代码生成
不需要字段号
字段名直接写进数据里

2⃣ 提供“字典式 API”

你给出的接口本质是：

class Value {
public:
    int asInt() const;                 // 把当前值当 int
    std::string asString() const;       // 把当前值当 string
    Value get(std::string key);         // 访问 map/object 中的字段
    void set(std::string key, int value);
    void set(std::string key, std::string value);
};

这是典型的：

运行期类型 + 动态访问

3⃣ Schemaless 常见格式

类型	特点
JSON	文本，可读性强
BSON	JSON 的二进制版
MsgPack	高效二进制 JSON
CBOR	标准化二进制对象
FlexBuffers	无 schema + 零拷贝

四、JSON / MsgPack 示例文档

{
  "price": 100,
  "volume": 5000,
  "timestamp": 1756309296041,
  "tradeId": "137A649ZZ0"
}

字段名是数据的一部分

五、第二张 SVG：Schemaless（二进制）如何编码？

你画的是一个 MsgPack 风格的 tag-value 流。

1⃣ 最外层：一个 map

0x84

含义：

0x80 → map
0x04 → 4 个键值对
容器类型 + 元素数量直接写入数据

2⃣ `"price": 100`

0x45 "price" 100

解释：

0x45 → 字符串，长度 = 5
"price" → key
100 → value（整数）

3⃣ `"volume": 5000`

"volume" 0xCD 5000

0xCD → 16 位整数
5000 → value
值本身带类型

4⃣ `"timestamp": 1756309296041`

"timestamp" 0xCF 1756309296041

0xCF → 64 位整数

5⃣ `"tradeId": "137A649zz0"`

0xA9 "tradeId" 0xB1 "137A649zz0"

0xA9 → key 字符串
0xB1 → value 字符串

6⃣ Schemaless 的本质

信息	在哪里
字段名	数据里
类型	数据里
结构	数据里
schema	不存在

数据 = 自描述文档

六、Schema-Based vs Schemaless 对比总结

维度	Schema-Based	Schemaless
需要 schema	✓	✗
编码体积	小	大
解析速度	快	慢
可读性	低	高
演进能力	强	天然支持
类型安全	强	弱
适合场景	RPC / 内部协议	文档 / 日志 / API

七、一句话理解两种世界

Schema-based 把“结构”放在代码里，把“值”放在线上。
Schemaless 把“结构 + 值”全部放进数据本身。

一、Schemaless 示例：同一份文档

原始数据（逻辑层）：

{
  "price": 100,
  "volume": 5000,
  "timestamp": 1756309296041,
  "tradeId": "137A649ZZ0"
}

这是“人类视角”的结构化对象

二、MsgPack 中的编码直觉

Schemaless 二进制格式（MsgPack / CBOR）通常是：

[tag][value][tag][value]...

1⃣ 顶层：一个 map（对象）

0x84

含义：

0x80 → map 类型
0x04 → 4 个键值对
类型 + 元素数量合并在一个字节里

2⃣ `"price": 100`

key：“price”

0xA5 "price"

0xA0 → fixstr
0x05 → 长度 = 5

value：100

小整数（< 128）
直接编码为自身
✗ 没有额外 tag
这是 MsgPack 的空间优化技巧

3⃣ `"volume": 5000`

key：“volume”

0xA6 "volume"

value：5000

0xCD 5000

0xCD → uint16
后面跟 2 字节小端整数
整数大小决定编码方式

4⃣ `"timestamp": 1756309296041`

0xA9 "timestamp"
0xCF 1756309296041

0xCF → uint64
后面跟 8 字节

5⃣ `"tradeId": "137A649ZZ0"`

0xA9 "tradeId"
0xB1 "137A649ZZ0"

0xB1 → str，长度 = 17

三、为什么说 tagged schemaless 格式“很聪明”

1⃣ 不需要额外 tag 的值

MsgPack 中：

值	编码
`true`	`0xC3`
`false`	`0xC2`
`0 ~ 127`	直接一个字节
`-32 ~ -1`	直接一个字节

这使得小数据极其紧凑

2⃣ 对比 JSON

格式	表示 `100`
JSON	`"100"` → 3 字节
MsgPack	`0x64` → 1 字节

二进制 schemaless 并不“臃肿”

四、Schemaless 的代价是什么？

这是你后半部分的核心问题。

1⃣ 典型处理流程（慢）

bytes
 ↓ decode
in-memory tree (map / array / value)
 ↓ process
modified tree
 ↓ encode
bytes

两次完整遍历 + 大量内存分配

2⃣ 对 CPU 和内存的影响

解码：
- 分配对象
- 构造字符串
- 建立树结构
编码：
- 重新遍历
- 重新计算大小
- 重新写字节
  对高性能系统很不友好

五、典型痛点场景

1⃣ 只改一个字段，却要全量重编

{
  "price": 100,   ← 只想改这里
  "volume": 5000,
  "timestamp": ...
}

现实却是：

decode entire document
modify price
re-encode entire document

✗ 浪费

2⃣ 只读取一个字段

例如：

“我从网络收到 10 万条消息，只想读 price”
结果：

每条都完整 decode
每条都构建对象树
这是 schemaless 最大的性能痛点

六、问题升级：能不能“原地修改”？

你后面的幻灯片抛出了一个关键问题：

能不能设计一种 schemaless 格式：

不用 schema

支持快速遍历

支持 in-place 修改

尽量避免反复序列化？
这正是 FlatBuffers / FlexBuffers / 自定义格式 的动机。

七、Baseline Serialization Format（基线格式）

这是在“做优化之前”的参考设计。

1⃣ 设计目标

功能完整
结构清晰
性能不是第一优先

2⃣ 支持的类型

string
int
float
map
array

3⃣ 编码规则（非常重要）

tag + value

[tag][value]

tag：
- 类型
- 长度（如果需要）
value：
- 实际数据

little-endian

整数 / 浮点 → 小端

原因：

x86 / ARM 都是小端
避免字节翻转
提升解析性能

map

[key1][value1][key2][value2]...

array

[value1][value2][value3]...

4⃣ 伪代码示例（带注释）

enum TagType {
    TAG_INT,
    TAG_STRING,
    TAG_FLOAT,
    TAG_MAP,
    TAG_ARRAY
};
struct Tag {
    TagType type;
    uint32_t size; // 如果是 string / array / map
};

这是“最朴素的 schemaless 编码”

八、这一阶段的总结

一句话总结当前阶段

我们有了一个功能正确、结构清晰，但“修改成本高”的 schemaless 序列化格式。

接下来要解决的问题

问题	方向
避免全量 decode	零拷贝
快速跳字段	offset / index
原地修改	padding / growth space
高效遍历	自底向上布局

一、Schemaless Tagged 格式为什么这么“紧凑”

1⃣ 小值压缩（packing small values）

Tagged schemaless 格式（MsgPack / CBOR）并不是每个值都用「tag + value」。

例子 1：布尔值

语义值	编码
`true`	`0xC3`
`false`	`0xC2`

1 个字节同时表示“类型 + 值”

例子 2：小整数

整数满足：
$\le x < 128$
编码方式：

0x00 ~ 0x7F

没有 tag
值本身就是编码

对比：朴素 tagged 编码

[TAG_INT][0x64]

MsgPack：

0x64

✓ 少 1 字节
✓ 更少分支
✓ CPU 更友好

2⃣ 为什么这样做可行？

因为：

低位区间没有被其他类型占用
编码空间是精心设计过的
解码器只看第一个字节就知道：
- 是“值”还是“tag”
  这是二进制格式设计的艺术

二、Schemaless 的真正代价（重点）

1⃣ 典型处理流程

几乎所有 schemaless 格式都会经历：

serialized bytes
   ↓ decode
in-memory data structure (tree)
   ↓ process
modified tree
   ↓ encode
serialized bytes

问题不在“编码格式”，而在“使用方式”

2⃣ 中间态：内存对象树

解码后通常得到：

Map
 ├─ String("price") → Int(100)
 ├─ String("volume") → Int(5000)
 ├─ String("timestamp") → Int(…)
 └─ String("tradeId") → String("137A649ZZ0")

这一步的成本包括：

动态内存分配（malloc/new）
构造字符串对象
构造 map / vector
指针跳转（cache miss）
这是 CPU 和内存的大头

3⃣ 即使只改一点点，也要全量重来

例子：只改一个字段

"price": 100 → 101

现实中却是：

解码整个文档
构建完整对象树
修改一个 int
再编码整个文档
✗ O(N) 的代价换 O(1) 的修改

三、为什么要“避免反复序列化”

1⃣ 数据库场景

从数据库取出一个 JSON / BSON
改一个字段
再写回去
当前做法：

disk → decode → modify → encode → disk

非常浪费

2⃣ 网络消息场景

每秒处理几十万条消息
只读取 price
当前做法：

decode full message → read one field → discard

绝大多数工作都是无用的

四、关键问题（这一页的核心）

能不能做一个：

schemaless（不用预先知道结构）

支持快速遍历

支持 in-place 修改

尽量避免 decode → encode
这是后面所有设计的起点

五、Baseline Serialization Format（基线格式）

这是为了做对比用的“最简单版本”。

1⃣ 为什么先做 baseline？

不追求极致性能
结构清晰
作为 benchmark 对照组
后续优化都以它为基础
没有 baseline，谈不上“优化”

2⃣ 支持的类型

string
int
float
map
array

这是 JSON / MsgPack 的最小子集。

3⃣ 编码规则（非常关键）

编码方式

[tag][value][tag][value]...

tag 包含的信息

[tag]
 ├─ 类型（int / string / map / array）
 └─ 长度（如果需要）

小端存储（little-endian）

整数 / 浮点 → little-endian

原因：

x86 / ARM 原生
不需要 bswap
解析速度更快
网络字节序（big-endian）是历史包袱

map 的表示方式

[key][value][key][value]...

key 通常是 string
顺序不重要（逻辑层）

array 的表示方式

[value][value][value]...

六、`Value` 接口的真正含义

你给出的接口是逻辑 API，不是实现。

1⃣ 访问接口（读）

float asFloat() const;  // 将当前值解释为 float
int   asInt() const;    // 将当前值解释为 int

当前 Value 是“类型擦除”的

2⃣ 结构变换

void makeArray();  // 把当前 Value 变成数组
void makeMap();    // 把当前 Value 变成 map

Value 本身是“可变形”的

3⃣ 赋值（写）

Value operator=(auto value);

等价于：

v = 123;
v = 3.14f;
v = "hello";

写入时决定 tag + value

4⃣ array 操作

Value append(auto value);

语义：

arr.append(1);
arr.append(2);
arr.append(3);

底层必须能增长

5⃣ map 操作

Value set(std::string_view key, auto value);

obj.set("price", 100);
obj.set("volume", 5000);

6⃣ 下标访问

Value operator[](std::string_view key) const;
Value operator[](int index) const;

像 JSON 一样用

七、这一页的核心总结

一句话总结

我们先做了一个“好理解但不好改”的 schemaless 序列化格式，作为性能基线。

接下来要解决的问题

问题	后续方向
全量 decode	零拷贝
修改要重写	in-place mutation
查字段慢	offset / index
cache 不友好	contiguous layout

Value doc(buf);
Value ts = doc[“timestamp”];
int64_t value = ts.asInt();

一、背景回顾：Baseline Serialization Format 是什么？

这是一个无 schema（Schemaless）、带 tag 的二进制序列化格式，特点是：

数据是 顺序编码 的
没有预先定义的 schema

Map / Object 结构本质是：

[key1, value1, key2, value2, key3, value3, ...]

类似于：
- JSON（二进制版）
- MsgPack
- CBOR

二、读取数据的核心思想：线性扫描（Linear Search）

你给出的关键说明是：

To implement read operations, we will do a linear search through the document, looking for the right key
为：
为了实现读操作，我们会 从头到尾线性扫描整个文档，查找匹配的 key。
没有索引、没有哈希表、没有偏移表。

三、使用示例代码（逐行解释）

Value doc(buf);

1⃣ 构造根 Value

buf：指向一整段 序列化后的二进制数据
doc：一个 Value 视图对象
注意：
没有反序列化
没有拷贝
Value 只是“指向 buffer 的一个解析视图”

Value ts = doc["timestamp"];

2⃣ 访问 Map 中的字段 `"timestamp"`

这一步 非常关键，内部会发生什么？

内部逻辑（伪代码）：

Value Value::operator[](string_view key) const {
    assert(this->isMap());
    ptr = map_begin;
    for (i = 0; i < map_size; ++i) {
        read key_i;
        if (key_i == key) {
            return corresponding_value;
        }
        skip value_i;
    }
    return null;
}

也就是说：

从 Map 的第一个 key 开始
一个一个比对字符串
找到 "timestamp" 才返回

int64_t value = ts.asInt();

3⃣ 把 Value 转成整数

检查 tag 是否是 Int
读取整数值（小端）
返回 int64_t

四、结合 SVG 图来理解“线性搜索”

1⃣ 整体结构（第一张图）

Map (size 4)
 ├── "price"     → Int(100)
 ├── "volume"    → Int(5000)
 ├── "timestamp" → Int(1756309296041)
 └── "tradeId"   → String("137A649zz0")

在 内存 / buffer 中的真实布局是线性的：

Map
  String("price")     Int(100)
  String("volume")    Int(5000)
  String("timestamp") Int(1756309296041)
  String("tradeId")   String("137A649zz0")

2⃣ SVG 中红色高亮的含义

在你给的多张 SVG 中：

绿色：类型 tag（String / Int / Map）
蓝色：实际数据
红色：当前正在被扫描 / 比较的字段

查找 `"timestamp"` 的过程：

1⃣ 比较 "price" ✗
2⃣ 比较 "volume" ✗
3⃣ 比较 "timestamp" ✓
4⃣ 返回对应的 Int
这就是线性搜索

五、时间复杂度（重要）

假设：

Map 中有 $N$ 个字段
那么：
查找一个 key 的时间复杂度是：
$O (N)$
如果你连续访问多个字段：

doc["price"];
doc["volume"];
doc["timestamp"];

每一次都是 从头开始扫描
总复杂度接近 $O(N^2)$

六、为什么 Baseline 设计成这样？

这是有意为之的设计：

✓ 优点

不需要额外索引
编码简单
内存占用小
可以 直接在 buffer 上操作
非常适合作为：
- 基线实现
- 教学
- 性能对比的起点

✗ 缺点

查找慢（线性）
多次访问同一字段成本高
不适合：
- 大对象
- 高频随机访问
- OLTP 场景

七、为什么要强调“Baseline”？

因为后续设计目标通常是：

在保持 schemaless 的前提下
实现：
- 快速跳转
- 就地修改（in-place mutation）
- 不完整反序列化
  例如后面可能会引入：
Offset table
Key directory
跳表 / B-tree
SIMD 扫描
Cache-friendly layout

八、总结（一句话版本）

Baseline Serialization Format 的读操作，本质上是：
在一段线性排列的 key-value 序列中，从头开始逐个比较 key，直到找到目标字段。

修改前的数据结构（第一张 SVG）

原始文档逻辑结构：

{
  "price":     100,
  "volume":    5000,
  "timestamp": 1756309296041,
  "tradeId":   "137A649zz0"
}

序列化后在 buffer 中是线性排列的：

Map(size=4)
  String "price"     Int 100
  String "volume"    Int 5000
  String "timestamp" Int 1756309296041
  String "tradeId"   String "137A649zz0"

没有指针，没有 offset 表，没有索引

三、代码逐行解释（非常关键）

Value doc(buf);

1⃣ 创建文档视图

buf：一整块序列化好的内存
doc：
- 不是反序列化结果
- 只是一个 轻量级“视图对象”

Value price = doc["price"];

2⃣ 线性扫描找到 `"price"`

内部行为：

从 Map 起始位置开始
比较 "price" → 命中
返回指向 value=100 的 Value
这时 price 指向的是：

Int 100

price.makeMap();

四、关键转折点：Int → Map

1⃣ 语义含义

把 "price" 的值
从 Int(100)
原地变成一个 Map
也就是说，逻辑结构变为：

"price": { }

2⃣ 实际内存中发生了什么？

✗ 原来占用空间

[Int tag][100]

✓ 现在需要

[Map tag][size=0]

Map 头通常比 Int 大
所以：

必须把后面的所有数据整体后移
这正是你看到 SVG 中：

"volume"
"timestamp"
"tradeId"
整体往后“推开”的原因

3⃣ SVG 中的红色块含义

红色区域：正在被修改 / 新写入的区域
斜线背景：被整体 memmove 的区域

五、第一次 set：插入 mantissa

price.set("mantissa", 100);

1⃣ 语义层面

现在 "price" 变成：

"price": {
  "mantissa": 100
}

2⃣ 内存层面的动作（一步不省）

① Map(size=0 → size=1)

更新 Map 的 size 字段

② 插入键值对

String "mantissa"
Int    100

③ 空间从哪里来？

继续向后 memmove

[volume ... tradeId]

再次整体后移

3⃣ 对应 SVG 变化

你看到：

"mantissa" 的 String / Int 是红色
原来的字段被整体下推到更后面

六、第二次 set：插入 exponent

price.set("exponent", -2);

1⃣ 逻辑结构最终变成

"price": {
  "mantissa": 100,
  "exponent": -2
}

2⃣ 内存操作再次发生

完全同样的三步：

Map size： $\rightarrow 2$
写入：
```
String "exponent"
Int    -2
```
再次 memmove 后续所有字段

3⃣ 最终 buffer 结构（逻辑视角）

Map(size=4)
  String "price"
    Map(size=2)
      String "mantissa" Int 100
      String "exponent" Int -2
  String "volume"    Int 5000
  String "timestamp" Int 1756309296041
  String "tradeId"   String "137A649zz0"

七、为什么要这样设计？（Baseline 的意义）

✓ 优点

不需要：
- 中间 AST
- 完整反序列化
- 重写整个对象
可以：
- 直接在 buffer 上修改
- 适合“少量、局部修改”

✗ 致命缺点

1⃣ 修改成本极高

假设：

文档总大小 $N$
修改位置在前部
那么：

一次插入 ≈ $O (N)$ memmove
多次插入：
总成本接近 $O(N^2)$

2⃣ cache / TLB / NUMA 都不友好

大量内存拷贝
破坏 cache 局部性
大对象修改会非常慢

八、这正是后续优化的“对照组”

这套 Baseline 设计的目的只有一个：

作为后续高级格式的性能对照
后面通常会引出：

Offset table（避免整体移动）
Append-only + indirection
Rope / Piece table
Hybrid schema + schemaless
BSON / FlexBuffers / FlatBuffers 的对比

九、一句话总结（你可以直接记）

Baseline Serialization Format 的“就地修改”本质是：
在原 buffer 中写新内容，并通过整体 memmove 后续字节来腾出空间。

一、Benchmark 到底在测什么？

1⃣ Benchmark 的目的

So, how does this perform?
不是要跑一个“真实业务”，而是要回答三个问题：

Baseline 方案能不能用？
瓶颈在哪？
后续优化有没有量化对照？
所以这是一个 “对照实验基线” benchmark。

2⃣ Benchmark 参数化设计

可控变量（非常关键）

① 文档规模

Number of fields in document
- Map 里有多少 key-value
- 直接影响 线性扫描成本

② 操作次数

Number of operations to perform
- 决定 benchmark 的总工作量

③ 操作类型分布（核心）

Reads（只读）
Writes to existing values（改值，不改结构）
Structural modifications（结构变化）
用比例来控制：

Reads:                X%
Writes (same size):   Y%
Structural changes:   Z%

这是现实系统中最重要的三类操作。

3⃣ 为什么要区分 “写值” vs “结构修改”？

操作类型	是否 memmove	复杂度
Read	✗	$O (n)$
Write same size	✗	$O (1)$
Structural modify	✓	$O (n)$

结构修改才是 Baseline 的致命弱点。

二、Benchmark 环境为什么要写这么详细？

硬件 & 软件环境

Linux 3.10
72-core Intel Xeon Gold 6240 @ 2.6GHz
gcc 13.1.1
-O2 -march=native -std=c++23
Machine load < 1%

这不是炫配置，而是为了：

排除干扰因素
确保 CPU 成为瓶颈
保证数据可复现

特别强调的一句

These benchmarks are synthetic
意思是：

✗ 不是生产性能
✓ 用来 比较设计优劣

三、性能问题出现了：搜索太慢

1⃣ 问题从哪来？

Faster Searches – How do we make searches faster?
当字段数增加：

每一次 doc["key"]
都要 从 Map 起点一路扫描
Baseline 是纯线性 Map。

2⃣ 搜索流程回顾（重要）

对 doc["timestamp"]：

for each (key, value) in map:
    read key length
    skip key bytes
    read value tag
    skip value bytes
    compare key string

核心问题：
“跳过 value” 本身是昂贵操作

四、Profiler 给了什么证据？

1⃣ 最大热点函数（惊人）

第一名：`sizeofMap`

41.85%  TaggedUtil::sizeofMap

第二名：`sizeofValue`

129.72% TaggedUtil::sizeofValue

百分比 >100% 是因为多线程采样累计
两者本质相同：
为了跳过一个 value，不断计算它的大小

2⃣ 为什么 sizeofValue 这么慢？

sizeofValue 要做什么？

伪代码：

size_t sizeofValue(ptr) {
    tag = *ptr;
    switch(tag.type) {
        case INT:
            return sizeof(int);
        case STRING:
            len = readLength(ptr);
            return tag + len;
        case MAP:
            for each element:
                size += sizeof(key) + sizeof(value);
        case ARRAY:
            for each element:
                size += sizeof(value);
    }
}

递归 + 分支 + cache miss

3⃣ 真正的性能地狱在哪里？

Map 中搜索一个 key 的真实成本：

假设：

Map 有 $n$ 个字段
平均 value 复杂度是 $k$
那么一次查找成本：
$O\left(\sum_{i=1}^{n} sizeof(value_i)\right)≈O(n \cdot k)$

4⃣ 为什么 memcmp 反而占比很低？

1.82% memcmp_sse4_1

说明：

字符串比较不是瓶颈
真正慢的是：
为了“走到”那个字符串，要不停算前面值的长度

五、其它热点的含义（快速解码）

函数	含义
`mapElementAt`	Map 中按 index 定位
`Value::operator[]`	触发线性搜索
`_memmove_ssse3_back`	结构修改时的整体移动
`_int_malloc`	临时分配（bench scaffolding）

memmove 不是最大热点，因为：

benchmark 中 结构修改比例可能较低
搜索是 每次操作都会发生

六、核心结论（非常重要）

✗ Baseline 最大瓶颈不是“写”

而是：

读之前的“跳过”成本

用一句话总结 profiler

Baseline 序列化格式中，搜索的主要成本来自对 value 大小的反复计算，而不是字符串比较或拷贝。

七、这为后续优化指明了方向

从 profiler 可以直接得出三条优化路线：

优化方向 1：缓存 size / offset

在 Map 头部存：
- 每个元素的 offset
- 或 value size
  ➡ 搜索降为 $O (n)$ 的纯指针跳转

优化方向 2：跳表 / 索引结构

在不反序列化的前提下
构建轻量级 index

优化方向 3：Append-only + indirection

修改不动原数据
新值追加
老值标记无效

八、Baseline 在这里的“教学意义”

它不是失败设计
它是一个 “问题暴露器”
它清楚地展示了：

✗ 线性 tagged 格式的问题
✗ recursive sizeof 的灾难
✗ schemaless + in-place 的代价

九、一句话总结（你可以直接引用）

Benchmark 显示，Baseline Serialization Format 的主要性能瓶颈不在写入或 memmove，而在于搜索过程中对 value 大小的反复计算，这使得查找成本随文档复杂度快速上升。

一、问题回顾：为什么搜索这么慢？

1⃣ 性能瓶颈的根源

在 Baseline Serialization Format 中：

Map 是：

[ key1 | value1 | key2 | value2 | ... ]

key、value 都是变长
查找一个 key 时：
- 必须从头开始
- 不断 跳过前面的 value
  profiler 已经证明：

大量时间耗在“跳过元素（sizeofValue）”上

2⃣ 数学复杂度回顾

假设：

Map 有 $n$ 个元素
平均 value 大小为 $k$
那么一次查找的成本是：
$O\left(\sum_{i=1}^{n} sizeof(value_i)\right) \approx O(n \cdot k)$

二、第一步优化：Key 排序

1⃣ 核心想法

What if we put our keys in sorted order?
如果 Map 中 key 是排序的：

"aa", "b", "c"

而不是插入顺序：

"b", "aa", "c"

2⃣ 排序能带来什么？

好处

可以提前终止搜索
比线性扫描更友好

图中含义（你给的 SVG）

每个 entry 是：

[ key(type + size) | key bytes | value(type) | value bytes ]

现在 key 在逻辑上是有序的

3⃣ 关键问题：能不能二分查找？

Now can we do binary search?

理论上

有序数组 → 二分查找 → $O(log⁡n)O(\log n)$

实际上 ✗

Not quite
原因：

key 是变长
value 也是变长
没有 index，无法 O(1) 跳到中间
二分查找的前提是：

能快速定位第 i 个元素

4⃣ 本质问题

即使 key 排序了：

你还是得：
- 从头算到中间
- 反复 sizeof(key + value)
  排序 ≠ 可随机访问

三、第二步优化：Hash 表头（关键转折）

1⃣ 新思路

Store an array of hashes at the start of our map
结构变为：

[ MapHeader
  ├── size
  ├── hashes[]   // uint32_t
  ├── offsets[]  // uint32_t
]
[ key1 | value1 | key2 | value2 | ... ]

2⃣ 为什么 hashes 很重要？

对比成本

操作	成本
比较字符串	慢（cache miss + memcmp）
比较整数 hash	快（寄存器 + cache line）

perf 视角

hash 数组：
- 连续内存
- 非常 cache-friendly

3⃣ offsets 的作用

Offsets: [6, 0, 13]
含义：

第 i 个 key-value 对
在正文区的起始偏移
这一步直接消灭了：

递归 sizeofValue

4⃣ 搜索流程（现在）

1. 在 hashes[] 中查找目标 hash
2. 命中 → 用 offset 定位 key
3. 最终字符串比较确认（防 hash 冲突）

5⃣ 新的复杂度

hash 搜索：
$O(log⁡n)O(\log n)$ 或 $O (n)$ （取决于是否排序）
实际 key 比较次数：极少
搜索从 “跳 value” 变成 “跳 offset”

四、但性能还没到极限

1⃣ 新热点出现了

perf shows that a lot of the cost is in std::lower_bound
也就是说：

hashes 排序了
用的是 二分查找
新瓶颈：CPU 分支预测失败

五、Binary Search 的隐藏成本

1⃣ 标准 lower_bound 的核心逻辑

if (begin[step] < value) {
    begin = &begin[step + 1];
    len -= step + 1;
} else {
    len = step;
}

2⃣ 为什么分支预测失败？

CPU 视角

每一轮：
- “去左半边还是右半边？”
对随机 key：
- 概率 ≈ 50%
  这是 最差的分支预测场景

3⃣ perf + 汇编印证了这一点

cmp   edi,r15d
jle   ...
sub   ersi,%rax   ← 这条很便宜

cmp + jle：高 miss
sub：便宜，说明 CPU 大部分时间在 flush pipeline

4⃣ 数学直觉解释

二分查找虽然是：
$O(\log n)$
但每一步：

都可能 清空 pipeline
实际延迟 >> 指令数

六、最终优化：Branchless Binary Search

1⃣ 核心思想

Remove the branch, use conditional move
即：

不用 if
用 cmov（条件移动）

2⃣ Branchless 版本思想

伪代码（概念）：

bool cond = begin[step] < value;
begin = cond ? &begin[step + 1] : begin;
len   = cond ? len - step - 1 : step;

编译器可生成：

cmp
cmovl

没有跳转

3⃣ 为什么这样快？

没有分支预测
pipeline 不会被 flush
对随机数据性能稳定

4⃣ 工程上的 trade-off

优点	缺点
稳定低延迟	指令略多
cache 友好	可读性略差
适合 hot path

七、这一整套优化的演进总结

阶段	瓶颈
Baseline	sizeofValue + memmove
Sorted keys	仍然无法跳转
Hash + Offset	lower_bound 分支预测
Branchless search	接近硬件极限

八、一句话总结（可直接写在 slide 里）

通过对 key 排序、引入 hash/offset 表以及消除二分查找中的分支预测失败，我们将 schemaless 文档的搜索成本从“跳过变长结构”转化为“cache 友好的整数比较”，并最终逼近 CPU 的执行极限。

一、`cmovl` 是什么？

cmovl 是 x86 指令集中的一条：

条件移动指令（conditional move）

全名

CMOVL = Conditional MOVe if Less

含义（一句话）

如果“有符号比较中 < 成立”，就把源寄存器的值移动到目标寄存器；否则什么也不做
关键点：

不会跳转
不会改变控制流
只是在 数据流 上做选择

二、`cmovl` 的“条件”是怎么判断的？

cmovl 依赖 CPU 状态寄存器 EFLAGS，通常由 cmp 指令设置。

1⃣ 常见搭配

cmp   eax, ebx      ; 比较 eax - ebx
cmovl ecx, edx      ; 如果 eax < ebx (有符号)，ecx = edx

判断规则（有符号）

SF != OF   → Less

SF：Sign Flag
OF：Overflow Flag

2⃣ 对比无符号版本

指令	含义
`cmovl`	signed `<`
`cmovg`	signed `>`
`cmovb`	unsigned `<`
`cmova`	unsigned `>`

三、和 `if + jmp` 的本质区别

1⃣ 有分支的写法

cmp   eax, ebx
jl    L1
mov   ecx, eax
jmp   L2
L1:
mov   ecx, ebx
L2:

问题

需要 分支预测
预测失败 → pipeline flush
成本：~15–20 cycles

2⃣ `cmovl` 的写法（无分支）

cmp    eax, ebx
mov    ecx, eax     ; 默认值
cmovl  ecx, ebx     ; 条件成立才覆盖

优点

没有跳转
没有预测
CPU pipeline 不会被清空

四、为什么 `cmovl` 在二分查找里特别重要？

1⃣ 二分查找是“分支预测地狱”

二分查找每一层都是：

if (a[mid] < key)
    go right;
else
    go left;

对随机 key：

$P(\text{branch taken}) \approx 50%$
最差的预测场景

2⃣ lower_bound 的核心逻辑

if (first[mid] < value) {
    first = first + mid + 1;
    len -= mid + 1;
} else {
    len = mid;
}

每一轮都要：

cmp
jl / jge

3⃣ Branchless 版本（概念）

bool cond = first[mid] < value;
first = cond ? first + mid + 1 : first;
len   = cond ? len - mid - 1   : mid;

编译后核心就是：

cmp
cmovl

五、`cmovl` 为什么在你的 benchmark 里显著加速？

对比两种成本

操作	代价
分支错误	~15–20 cycles
`cmovl`	~1 cycle

当循环次数是 $log_2(n)$ ，比如 20 次：

分支版：
$20 \times 15 = 300 \text{ cycles}$
cmov 版：
$20 \times 1 = 20 \text{ cycles}$

六、重要但容易忽略的细节

1⃣ `cmov` 不是“免费”的

它 仍然会执行
即使条件不成立，也要：
- 读取寄存器
- 走执行单元
  所以：

只有在分支不可预测时，cmov 才是赢家

2⃣ 编译器什么时候会用 `cmov`？

-O2 / -O3
条件表达式足够简单
没有副作用
例如：

x = cond ? a : b;

3⃣ 什么时候不要用？

场景	原因
条件高度可预测	`if` 更快
分支体很大	cmov 无法省工作
有函数调用	不能 cmov

七、结合你这个序列化项目的总结

cmovl 把“结构遍历中的控制流选择”转化成“纯数据流选择”，从而避免了在随机 key 搜索中反复触发 CPU 的最坏分支预测路径。
一句工程化理解：
不是算法变快了，而是 CPU 不再被你折腾了。

八、一个最小示例（你可以直接实验）

int min_branch(int a, int b) {
    if (a < b)
        return a;
    return b;
}
int min_cmov(int a, int b) {
    int r = b;
    if (a < b)
        r = a;
    return r;
}

在 -O2 下：

min_cmov 很可能生成 cmovl
min_branch 可能生成 jl

一、为什么要做 Branchless Binary Search？

1⃣ 传统二分查找的问题

经典二分查找的核心是：

if (a[mid] < key)
    go right;
else
    go left;

问题不在算法复杂度
时间复杂度仍然是：
$O(\log n)$
问题在 CPU 执行层面：

每一轮循环都有一个 条件分支
当 key 是随机的：
$P(\text{branch taken}) \approx 50%$
这是 分支预测最差情况
➡ 导致：
分支预测失败
pipeline flush
一次错误 ≈ 15–20 cycles

二、什么是 Branchless（无分支）思想？

把“控制流选择”变成“数据流选择”

传统方式（有分支）

if (cond)
    x = a;
else
    x = b;

Branchless 方式（无分支）

x = cond ? a : b;

编译器可能生成：

cmp
cmov

而不是：

cmp
jl / jge

三、Khuong & Morin 的 Branchless Binary Search

论文：

“Array Layouts for Comparison-Based Searching”
提供了一个非常经典、实用的实现。

四、代码逐行理解（重点）

原始代码

const T *search(const T *begin, const T *end, T key)
{
    const T *base = begin;
    int64_t len = end - begin;
    while (len > 1) {
        const int64_t half = len / 2;
        if (base[half] < key) {
            base += half;
        }
        len -= half;
    }
    return *base < key ? base + 1 : base;
}

逐行解释 + 注释版

const T* search(const T* begin, const T* end, T key)
{
    // 当前搜索区间的起点
    const T* base = begin;
    // 当前区间长度
    int64_t len = end - begin;
    // 只要区间里还有两个或以上元素，就继续
    while (len > 1) {
        // 区间的一半
        const int64_t half = len / 2;
        // 如果中点元素小于 key
        //  只做“一个赋值”
        if (base[half] < key) {
            base += half;
        }
        // 不管走哪边，区间长度都减半
        len -= half;
    }
    // 最终只剩 1 个元素
    // 判断是 base 还是 base + 1
    return *base < key ? base + 1 : base;
}

五、这个实现“像 branchless，但又不是完全没有 if”？

这是非常聪明的地方。

核心技巧

if 里只做一件事：一个简单赋值

if (base[half] < key) {
    base += half;
}

这样做的效果是：

编译器 很容易识别成条件赋值
更容易生成：
```
cmov
```
而不是：
```
jcc
```

六、最终生成的关键汇编（解释）

你给出的 perf 片段中，关键是这一行：

cmp
r11w,(r14,rsi,2)
cmovb  rsi, rax

含义

cmp   element, key     ; 比较 base[half] 与 key
cmovb rsi, rax         ; 如果 element < key（无符号），更新 base

cmovb：

b = below
表示 无符号 <
不跳转
不破坏 pipeline

七、为什么这能显著提升性能？

对比成本

操作	代价
分支预测失败	~15–20 cycles
cmov	~1 cycle

每次二分查找

$\log_2(n) \approx 20$
如果是随机 key：

传统分支：
$20 \times 15 = 300 \text{ cycles}$
branchless：
$20 \times 1 = 20 \text{ cycles}$
数量级差距

八、最后的 return 也是 branchless 的

return *base < key ? base + 1 : base;

编译后几乎一定是：

cmp
cmov

而不是跳转。

九、为什么不是“完全没有分支”？

while (len > 1)

这个分支：

高度可预测
循环次数固定（ $log_2 n$ ）
分支预测命中率 ≈ 100%
所以保留它是 完全合理的

十、和你前面 benchmark 的直接关系

你之前 profiling 显示：

大量时间花在：
- 查找 map key
- 比较字段名
- 遍历有序结构
  使用 branchless binary search 的直接效果：

减少随机 key 搜索中的分支预测失败
不是算法变了，而是：
让 CPU 不再频繁 flush pipeline

十一、工程级总结（一句话）

Branchless Binary Search 用 cmov 把不可预测的控制流，变成了可预测的数据流，从而在现代乱序 CPU 上大幅降低搜索延迟。

十二、如果你愿意，我可以继续帮你：

手写一个 100% branchless 的 lower_bound
对比 branch / cmov 在 perf 里的事件差异
把这个 search 嵌进你的序列化 map 结构
你只要说一句：
“继续讲完全 branchless 的版本”

一、问题背景：为什么要重新思考搜索算法？

我们要解决的问题是：

在一个“很小的有序数组”中，找到第一个 ≥ key 的元素（lower_bound）
理论上：

二分搜索： $O(log⁡N)O(\log N)$
线性搜索： $O (N)$
但在 现代 CPU（乱序 + 深流水线 + SIMD） 上：

渐进复杂度 ≠ 实际性能

二、针对“小 N”，算法设计目标是什么？

作者总结得非常到位（这是全文的“性能设计哲学”）：

小规模数据的 4 条铁律

避免分支（尤其是不可预测分支）
减少数据依赖（dependency chain）
使用简单、连续的数据访问（方便向量化）
避免复杂算法（小 N 下“做太多事”反而慢）

三、分支消除的二分搜索（Branchless Binary Search）

3.1 基本思想

经典二分：

if (a[mid] < key)
    l = mid + 1;
else
    r = mid;

问题：分支不可预测
解决：用 cmov（条件移动）代替 jmp

3.2 Branchless 二分代码（核心）

int binary_search_branchless (const int *arr, int n, int key) {
    intptr_t pos = -1;
    intptr_t logstep = bsr(n);
    intptr_t step = intptr_t(1) << logstep;
    while (step > 0) {
        // 如果 arr[pos + step] < key，就更新 pos
        // 否则 pos 保持不变
        pos = (arr[pos + step] < key ? pos + step : pos);
        step >>= 1;
    }
    return pos + 1;
}

解释

pos：当前“最右侧 < key 的位置”
每一轮：
- 试探 pos + step
- 用 条件赋值（不是 if 跳转）
编译器会生成：

cmp
cmovl

而不是：

cmp
jl

3.3 关键汇编（核心循环）

cmp DWORD PTR [rdi+rax*4], r8d
cmovl rdx, rax

含义：

比较数组元素与 key
如果 < key，更新位置
没有分支跳转

3.4 二分搜索的根本瓶颈

即使没有分支，二分搜索仍然是“强串行”的：

load -> compare -> cmov -> 下一次 load

后一步 必须等前一步完成
这是不可打破的数据依赖链
结论：

二分搜索的瓶颈不是分支，而是 依赖链长度

四、IACA 分析与真实硬件差距

IACA 给出：

单轮 ≈ 2.15 cycles
但现实中：
L1 load latency ≈ 4 cycles
实测：
- 吞吐 ≈ 4–5 cycles / step
- 延迟 ≈ 8–10 cycles / step
  原因：
  IACA 假设“理想并行”，但 依赖链使其不可能

五、完全展开（Unrolled）的二分搜索

template<intptr_t MAXN>
int binary_search_branchless_UR(const int *arr, int n, int key) {
    intptr_t pos = -1;
    pos = (arr[pos + 32] < key ? pos + 32 : pos);
    pos = (arr[pos + 16] < key ? pos + 16 : pos);
    pos = (arr[pos + 8]  < key ? pos + 8  : pos);
    pos = (arr[pos + 4]  < key ? pos + 4  : pos);
    pos = (arr[pos + 2]  < key ? pos + 2  : pos);
    pos = (arr[pos + 1]  < key ? pos + 1  : pos);
    return pos + 1;
}

结论

吞吐略快（减少 loop overhead）
延迟几乎没变
依赖链依然存在

六、线性搜索：真正的反击开始

6.1 传统线性搜索（带 break）

int linearX_search_scalar(const int *arr, int n, int key) {
    int i = 0;
    while (i < n) {
        if (arr[i] >= key)
            break;
        ++i;
    }
    return i;
}

✗ 问题：

最后一次 break 是 不可预测分支
小 N 下代价很大（≈ 10 cycles）

6.2 “计数型”线性搜索（核心思想）

答案 = 数组中 < key 的元素个数

标量版

int linear_search_scalar(const int *arr, int n, int key) {
    int cnt = 0;
    for (int i = 0; i < n; i++)
        cnt += (arr[i] < key);  // true = 1, false = 0
    return cnt;
}

无分支
可向量化
每一轮完全独立

6.3 SSE 向量化版本（核心代码）

int linear_search_sse(const int *arr, int n, int key) {
    __m128i vkey = _mm_set1_epi32(key);
    __m128i cnt = _mm_setzero_si128();
    for (int i = 0; i < n; i += 16) {
        __m128i m0 = _mm_cmplt_epi32(_mm_load_si128((__m128i*)&arr[i+0]),  vkey);
        __m128i m1 = _mm_cmplt_epi32(_mm_load_si128((__m128i*)&arr[i+4]),  vkey);
        __m128i m2 = _mm_cmplt_epi32(_mm_load_si128((__m128i*)&arr[i+8]),  vkey);
        __m128i m3 = _mm_cmplt_epi32(_mm_load_si128((__m128i*)&arr[i+12]), vkey);
        __m128i sum = _mm_add_epi32(_mm_add_epi32(m0, m1),
                                   _mm_add_epi32(m2, m3));
        cnt = _mm_sub_epi32(cnt, sum); // mask 是 -1
    }
    // 水平求和
    cnt = _mm_add_epi32(cnt, _mm_shuffle_epi32(cnt, _MM_SHUFFLE(2,3,0,1)));
    cnt = _mm_add_epi32(cnt, _mm_shuffle_epi32(cnt, _MM_SHUFFLE(1,0,3,2)));
    return _mm_cvtsi128_si32(cnt);
}

6.4 为什么线性搜索突然变强了？

特性	二分搜索	计数线性搜索
分支	无	无
数据依赖	强	几乎无
SIMD	不可	极易
cache 访问	稀疏	连续

SIMD + 无依赖 = CPU 爆发式吞吐

七、关键实验结论（精华总结）

7.1 二分 vs 线性（吞吐）

$N < 64$ ：
向量化线性搜索更快
$N \geq 64$ ：
branchless 二分更快

7.2 二分 vs 线性（延迟）

二分依赖链长
延迟 ≈ 吞吐 × 2
线性搜索延迟 ≈ 吞吐
真实系统更关心延迟

7.3 “带 break 的线性搜索”是最差选择

单个不可预测分支 ≈ 10 cycles
小 N 下影响巨大

八、MSVC vs GCC 的“血泪教训”

MSVC 的灾难指令

or r9, -1   ; 伪装成 mov r9, -1

✗ 问题：

产生 假依赖（false dependency）
下一次函数调用必须等待上一轮结果
吞吐 → 退化成延迟
修复：

intptr_t MINUS_ONE = -1;
intptr_t pos = MINUS_ONE; // 强制 mov

这说明：

C++ 层面“看起来正确”，CPU 层面可能完全不同

九、最终结论（非常重要）

一句话版

在现代 CPU 上，小规模搜索的胜负，取决于“分支 + 依赖 + SIMD”，而不是 O(N) vs O(log N)。

实用建议

场景	最佳方案
极小 N（≤32）	计数型 SIMD 线性搜索
小 N（64–128）	branchless 二分
中大 N	branchless 二分
通用库	二分（确保无分支）

一、回顾：Baseline Format 是怎么“修改”的？

1⃣ Baseline 的核心特征

在最初的（baseline）格式中：

所有数据是顺序排布的
没有 offset / 指针
元素之间的关系依赖物理位置

修改 = 把后面的数据整体往后 / 往前挪
例如：

[String][Int][Int][String][Int]

如果把某个 Int 改成 Double：

体积变大
后面的内容整体 memcpy 一次
不需要维护任何额外元数据
时间复杂度：
$O(\text{文档大小})$
虽然慢，但逻辑简单

二、引入 Offset 后，问题出现了

你现在的格式中，每个 Map 有：

[Header | Hashes[] | Offsets[] | Entry Data...]

offset 的语义

Offsets[i] = 第 i 个 entry 相对于数据区起始位置的偏移
entry 不再靠“顺序”，而靠 offset 定位
图中：

Offsets: [6, 0, 13]

意思是（简化）：

entry[1] 在 data + 6
entry[2] 在 data + 0
entry[3] 在 data + 13

三、为什么“移动数据”变得困难？

关键问题一句话总结

offset 把“位置”变成了显式依赖

场景：把 `100 (Int)` 改成 `100.1 (Double)`

1⃣ 发生了什么？

Int → Double
size 变化（比如 4B → 8B）
entry 1 物理长度变大
图中红色部分：
Value type: Double
Value: 100.1

2⃣ 直接后果：后面的 entry 被挤走

Entry 1 变大后：

[Entry 1][Entry 2][Entry 3]

变成：

[Entry 1 (bigger)][Entry 2 shifted][Entry 3 shifted]

✗ 问题来了：Offsets 全错了

原来：

Offsets: [6, 0, 13]

现在 Entry 2、Entry 3 的 起始位置发生变化：

Offsets: [6, 0, 17]  ← 必须更新

你不仅要 memcpy 数据
还要修正 offset 表

3⃣ 修改的代价从“局部”变成“全局”

原本你以为：

我只改一个 value
实际你必须：

移动 entry 后面的所有数据
更新当前 map 的 offsets
保证 hash ↔ offset 的对应关系仍然正确

四、真正的灾难：嵌套 Map / Array

这部分是最关键的痛点

看你给的嵌套示例

JSON 结构：

{
  "a": {
    "b": {
      "c": 100.0
    }
  },
  "d": 200
}

对应的二进制结构（右图）

外层 Map（a, d）
a → Map
b → Map
c → Double

现在修改最内层的 `100.0`

假设：

100.0 (Double) → 100.123456 (Double, 更长编码)

会发生什么？

第 1 层（c 所在 map）

entry size 改变
offsets 需要更新

第 2 层（b 所在 map）

子 map 整体 size 变了
b 的 offset 需要更新

第 3 层（a 所在 map）

b 所在 entry 位置变了
a 的 offsets 需要更新

最外层 map

a 的 entry size 改变
最外层 offsets 也要更新

修改成本随嵌套深度线性增长

如果嵌套深度是 $d$ ：
$\text{修改代价} = O(d + \text{后续数据大小})$
如果文档很大、嵌套很深：

每次修改都要向上回溯
修改路径上所有 parent

五、实现层面的额外复杂度

你在 slide 里点到但非常重要的一点：

我需要追踪我经过了哪些 parent

两种实现方式（都很痛）

方案 1：Traversal 栈

在解析 / 查找时维护一个 parent 栈
修改时逐层回溯更新 offsets
缺点：
修改逻辑极复杂
易出 bug

方案 2：存 parent 指针

每个 node 记录父节点位置
缺点：
额外存储开销
parent pointer 本身也会因为移动而失效
形成“指针更新地狱”

六、核心结论（你这组 slide 的“takeaway”）

✗ Offset + 连续布局 ≠ 可修改格式

Offset 引入了“位置依赖”

嵌套结构会把一次局部修改，放大成多层全局修改

本质问题

你现在的数据格式是：

紧凑
cache-friendly
读取快
但：
✗ 修改成本高
✗ 嵌套下指数级放大复杂度

七、为后续内容埋的伏笔（你后面大概率会讲）

典型解决思路包括：

间接层（indirection）
- offset 指向指针表，而不是直接数据
分段 / chunk 化
- 子对象独立存储
Append-only + delta
- 修改不覆盖原数据
Arena / page-based layout
- 类似你之前提到的 allocator 设计
Persistent / copy-on-write 结构
这些方案的目标只有一个：

让修改的影响范围局限在局部

一、核心想法回顾：为什么要 Out-of-line？

之前的问题（Inline layout）

在之前的设计中：

Map 的 entries 紧挨着 header
offset = “相对于 map 起始位置的偏移”
子 map 是 物理嵌套 在父 map 里的

修改一个值的代价

如果修改了一个 entry 的 size：

后续 entries 被移动
当前 map 的 offsets 要更新
所有祖先 map 的 offsets 也要更新
嵌套深度 $d$ 时：
$\text{修改代价} = O(d + \text{后续数据量})$
这是不可接受的。

二、Idea 1：把元素“移出”父对象（Out-of-line）

什么是 Out-of-line？

不再要求子元素的物理位置必须在父对象内部
也就是说：

Map 的 header 仍然在一块
真正的 key / value / 子 map 可以放在 buffer 的任意位置
offsets 不再是“局部偏移”，而是：

“指向 buffer 中任意位置的小指针”

从 Offset → Pointer 的本质转变

你 slide 里的这句话非常关键：

Our offsets have essentially become small pointers

对比一下语义变化

之前	现在
offset = 相对 map 的偏移	offset ≈ 指向 buffer 的地址
父子靠物理嵌套	父子靠“引用”
修改会波及父	修改只影响被指向对象

三、如何理解你这张大图（逐行解释）

你这张图其实是在表达：

“逻辑嵌套 ≠ 物理嵌套”

第一行（绿色 Map）

Map (size 1)
Offsets: [166]

含义是：

offset[0] = 166
→ 指向 buffer 中 offset = 166 的位置

这个 offset 指向的 不是紧挨着它的下一行，而是：
粉色 Map（第二行）

第二行（粉色 Map）

Map (size 1)
Offsets: [...]

这是第一层子 map
它本身也不要求子元素就在它后面
offsets 再次“跳转”到别的位置

第三行（空白 / hatched）

这是一个很重要的隐喻：

buffer 中存在“未使用 / 空闲 / 碎片”区域

之前 inline layout 几乎不会有洞
out-of-line layout 天然会产生空洞

第四行（蓝色 Map）

Map (size 1)
Offsets: [64]

这是另一个被引用的 map
它可能被多个父对象指向
它的位置和父 map 完全解耦

虚线箭头的含义

虚线箭头表示：

offset 指向的是 逻辑关系
而不是 物理相邻
你现在的数据结构更像：

Graph / DAG

而不是一棵“物理嵌套树”。

四、Out-of-line 布局解决了什么问题？

1⃣ 修改局部化

如果你修改最底层的 map：

它的大小变化
只要它自己的 offset 不变
父 map 完全不需要修改
修改代价变成：
$O(\text{被修改对象自身})$

2⃣ 嵌套不再放大修改成本

之前：

改 c → 改 b → 改 a → 改 root

现在：

改 c → 完

逻辑嵌套仍然存在，但物理隔离了

3⃣ 支持共享 / 复用（潜在）

因为对象是 out-of-line 的：

多个 map 可以指向同一个子对象
这为 结构共享 / copy-on-write 打开了大门

五、但代价来了：内存管理问题（你 slide 的最后一页）

你最后一句非常关键：

Now we have another problem

新问题 1：空间怎么分配？

之前（inline）

append 即可
所有数据天然紧凑
类似：

write(ptr); ptr += size;

现在（out-of-line）

子对象可以出现在 buffer 任意位置
需要：

find_free_space(size)

这直接变成了：

一个内存分配器问题

新问题 2：空间怎么释放？

当一个对象被删除 / 替换：

它原来的空间变成“洞”
这些洞大小不一
如果不处理：
buffer 会快速膨胀
实际使用率很低

这就是经典的：外部碎片问题

定义

空闲空间存在
但 不连续
无法满足新的分配请求

数学化一点的描述

设：

buffer 总大小 = $B$
已使用空间 = $U$
空闲空间 = $F = B - U$
即使：
$\ge S$
（ $S$ 是新对象需要的大小）
也可能因为 碎片化：
$\max(\text{free block}) < S$
分配失败

六、你已经进入“Allocator 设计”的领域了

到这一步，你的数据格式已经不再只是“序列化格式”，而是：

一个带对象引用的内存布局系统
你接下来几页大概率会讨论：

free list
size class
arena / slab
compaction
copy-on-write
indirection table

七、和真实系统的对应关系（帮助你建立直觉）

系统	对应点
操作系统堆	out-of-line + allocator
jemalloc / tcmalloc	size class + arena
JVM / Go heap	object relocation
Arrow / Parquet	out-of-line column chunks
Protobuf Arena	批量释放

八、一句话总结（slide takeaway）

Out-of-line 布局把“修改复杂度”问题，转化成了“内存管理复杂度”问题

修改变快了 ✓
布局更灵活了 ✓
但你现在必须：
- 管理空间
- 处理碎片
- 设计 allocator ✗

一、什么是 Bump Allocator（线性分配器）

核心思想一句话：

在一块连续内存里，只维护一个“当前空闲起点指针”，
每次分配就是把这个指针向前“顶（bump）”一下。

基本结构

一块大缓冲区：

+----------------------------------------------------+
| 已使用 | 已使用 | 已使用 |     空闲空间            |
+----------------------------------------------------+
                          ↑
                    free_space_start

free_space_start：当前可分配内存的起点
分配 = 返回 free_space_start，然后指针前移

二、第一张图：初始化状态

图中元素含义

Root node
→ 根节点，指向当前文档/数据结构的入口
Free space start
→ bump allocator 的核心指针
下面斜线填充区域
→ 整块可用内存（buffer）
此时：

buffer:
[ root ][            free space                ]
          ↑
   free_space_start

三、第二张图：把 Root node 变成一个 Map

Map 的内存布局（图中粉色块）

+------------------------------------------------+
| Map Header | size | capacity | offsets[]      |
+------------------------------------------------+

你图中写的是：

Size: 0/2
Offsets: [0, 0]
说明：
当前 map 有 0 个元素
预留 2 个 key-value
offsets 数组记录 key/value 在 buffer 中的偏移

分配 Map 的过程（伪代码）

// bump allocator 的状态
struct BumpAllocator {
    uint8_t* buffer;          // 整块内存起点
    size_t capacity;          // buffer 总大小
    size_t offset;            // 当前 bump 指针
};
// 分配函数
void* bump_alloc(BumpAllocator* alloc, size_t size) {
    // 简单粗暴：只前移指针
    void* ptr = alloc->buffer + alloc->offset;
    alloc->offset += size;
    return ptr;
}

注意：

没有 free

没有回收

没有碎片管理

四、第三张图：加入第一个 key-value

例如：

{
  "aa": 100
}

实际发生的事情

1⃣ 分配字符串 `"aa"`

char* key = bump_alloc(&alloc, 3); // 'a','a','\0'

2⃣ 分配整数 `100`

int* value = bump_alloc(&alloc, sizeof(int));
*value = 100;

3⃣ Map 记录偏移量

Offsets: [ offset_key0, offset_value0 ]
Size: 1/2

图中绿色（String）和蓝色（Int）块就是这些对象。

五、第四张图：加入第二个 key-value

{
  "aa": 100,
  "b": 500.0
}

"b" → 新分配 String
500.0 → 新分配 Double
Map size → 2/2（满了）

此时内存像这样

| Map | "aa" | 100 | "b" | 500.0 | free... |

所有数据都在 buffer 中，严格线性增长

六、关键问题出现：Map 满了

你图里的文字：

Now I want to add another key and value, but I’m out of space in my map
So I need to allocate more space for a larger map

为什么“满了”？

Map 本身也是一次性分配的定长结构：

Map(capacity=2)

不能原地扩容，因为：

bump allocator 不能回退
后面已经分配了别的对象

七、只能这样做：重新分配一个更大的 Map

操作流程（非常重要）

1⃣ 分配一个新 Map（容量更大，比如 4）

Map* new_map = bump_alloc(&alloc, sizeof(Map) + 4 * sizeof(Entry));

2⃣ 把旧 Map 的内容复制过去

memcpy(new_map->entries, old_map->entries,
       old_map->size * sizeof(Entry));
new_map->size = old_map->size;
new_map->capacity = 4;

3⃣ Root node 指向新 Map

root = new_map;

4⃣ 旧 Map 永远留在内存里

✗ 不能释放
✗ 不能复用
✗ 变成“死内存”

图中灰色 Map = 旧 Map（垃圾）

粉色 Map = 新 Map（有效）

八、再加入新的 key-value

现在容量是 4，可以继续：

{
  "aa": 100,
  "b": 500.0,
  "aa": 567
}

流程和之前一样：

bump 分配字符串
bump 分配整数
更新 offsets
size → 3/4

九、最终状态总结（你最后一张图）

buffer:
| old Map(2) | "aa" | 100 | "b" | 500 | new Map(4) | "aa" | 567 | free |

问题非常明显：

旧 Map 占着空间
再也不会被用
buffer 里充满“历史垃圾”

十、为什么 Bump Allocator 会浪费空间？

根本原因

只能前进，不能回退
不能释放单个对象
变长结构（Map / Vec / String）必须整体重分配
每次扩容都会留下一个“尸体结构”

空间浪费模型（直觉）

假设 map 每次容量翻倍：

2 → 4 → 8 → 16

那么总浪费空间接近：
$\text{浪费空间} \approx \text{当前有效数据量}$
即：你用了 1 倍数据，却至少浪费 1 倍内存

十一、唯一的补救：Compaction（整体压缩）

你最后一句话说得非常关键：

I will need to compact the whole buffer once I run out of space

Compaction 是什么？

分配一个新 buffer
只复制仍然可达的数据
重新计算所有偏移
一次性丢掉所有垃圾

// 非常昂贵的操作
void compact(Buffer* old, Buffer* new) {
    // 遍历 root
    // 拷贝所有活对象
    // 修正所有 offset
}

十二、什么时候适合用 Bump Allocator？

✓ 适合：

构建 AST / IR
解析器
临时数据
一次性生成、一次性释放
✗ 不适合：
长生命周期数据
频繁扩容的 Map / Vec
在线服务

十三、一句话总结

Bump Allocator 的哲学是：
“快到极致，蠢到极致。”

分配： $O (1)$
释放：不存在
碎片：靠整体压缩解决

Free List Allocator 的核心数据结构

最简单的实现是 单向空闲链表：

// 表示一块空闲内存
struct FreeBlock {
    size_t size;            // 当前空闲块大小（字节数）
    struct FreeBlock* next; // 指向下一块空闲内存
};
// 分配器整体状态
struct FreeListAllocator {
    void*  heap_start;      // 堆起始地址
    size_t heap_size;       // 堆总大小
    FreeBlock* free_list;   // 空闲块链表头
};

设计要点

free_list 中只存“还没被用的内存”
已分配的内存对 allocator 来说是“黑盒”
free block 的 metadata 直接存放在空闲内存内部

三、初始化阶段（对应 SVG 第一张）

初始状态

整个 heap 还没有任何分配
所有内存都是一个大 free block

void init_allocator(FreeListAllocator* alloc,
                    void* heap,
                    size_t heap_size)
{
    alloc->heap_start = heap;
    alloc->heap_size  = heap_size;
    // 整个堆本身就是一个空闲块
    alloc->free_list = (FreeBlock*)heap;
    alloc->free_list->size = heap_size;
    alloc->free_list->next = NULL;
}

此时逻辑上是：

[ FreeBlock(size = heap_size) ]

四、内存分配过程（allocate）

1⃣ 分配目标

请求分配大小： $S$
从 free list 中找一个大小 $≥S\ge S$ 的空闲块

2⃣ 最简单策略：First-Fit

void* alloc(FreeListAllocator* alloc, size_t size)
{
    FreeBlock* prev = NULL;
    FreeBlock* curr = alloc->free_list;
    while (curr != NULL) {
        // 如果当前空闲块足够大
        if (curr->size >= size) {
            // 找到了可用块
            break;
        }
        prev = curr;
        curr = curr->next;
    }
    if (curr == NULL) {
        // 没有任何空闲块能满足需求
        return NULL;
    }
    // 从 curr 这个空闲块中分配
    return split_and_allocate(alloc, prev, curr, size);
}

3⃣ 切分空闲块（split）

这是 Free List Allocator 的关键步骤。

void* split_and_allocate(FreeListAllocator* alloc,
                         FreeBlock* prev,
                         FreeBlock* curr,
                         size_t size)
{
    // 如果剩余空间还能形成一个新的 FreeBlock
    if (curr->size >= size + sizeof(FreeBlock)) {
        // 在当前空闲块后面切出一个新的空闲块
        FreeBlock* new_block =
            (FreeBlock*)((char*)curr + size);
        new_block->size = curr->size - size;
        new_block->next = curr->next;
        // 更新 free list
        if (prev != NULL) {
            prev->next = new_block;
        } else {
            alloc->free_list = new_block;
        }
    } else {
        // 剩余空间太小，直接整个块分配掉
        if (prev != NULL) {
            prev->next = curr->next;
        } else {
            alloc->free_list = curr->next;
        }
    }
    // 返回分配给用户的内存起点
    return (void*)curr;
}

对应 SVG 的变化

一个大 free block
→ 被切成：
- 一块 已分配
- 一块 更小的 free block

五、释放内存（free）

1⃣ 为什么 free 这么危险？

Free List Allocator 无法自动判断：

你传进来的指针是否：
- 曾经分配过
- 是否已经被释放过
- 是否大小正确
  这也是为什么 free 是 bug 重灾区。

2⃣ 基本 free 操作

void free_block(FreeListAllocator* alloc,
                void* ptr,
                size_t size)
{
    FreeBlock* block = (FreeBlock*)ptr;
    block->size = size;
    // 头插法：直接放回 free list
    block->next = alloc->free_list;
    alloc->free_list = block;
}

释放后：

[ NewFree ] -> [ OldFree ] -> ...

六、碎片问题（SVG 中最重要的部分）

1⃣ 外部碎片（External Fragmentation）

随着不断的：

alloc
free
再 alloc
heap 可能变成：

[Used][Free 8][Used][Free 16][Used][Free 4]

数学描述

设：

空闲总量 = $F$
最大连续空闲块 = $M$
即使：
$\ge S$
也可能因为：
$M < S$
导致 分配失败。

2⃣ 碎片增长的根本原因

分配大小不一致
释放顺序不一致
空闲块无法自动合并

七、空闲块合并（Coalescing）

为缓解碎片，必须做 相邻空闲块合并。

1⃣ 维护地址有序 free list

void free_block_sorted(FreeListAllocator* alloc,
                       void* ptr,
                       size_t size)
{
    FreeBlock* block = (FreeBlock*)ptr;
    block->size = size;
    FreeBlock* curr = alloc->free_list;
    FreeBlock* prev = NULL;
    // 找到插入位置（按地址排序）
    while (curr && curr < block) {
        prev = curr;
        curr = curr->next;
    }
    block->next = curr;
    if (prev) {
        prev->next = block;
    } else {
        alloc->free_list = block;
    }
    // 尝试与前后合并
    coalesce(prev, block);
}

2⃣ 合并逻辑

void coalesce(FreeBlock* prev, FreeBlock* curr)
{
    // 向后合并
    if (curr->next &&
        (char*)curr + curr->size == (char*)curr->next) {
        curr->size += curr->next->size;
        curr->next = curr->next->next;
    }
    // 向前合并
    if (prev &&
        (char*)prev + prev->size == (char*)curr) {
        prev->size += curr->size;
        prev->next = curr->next;
    }
}

八、时间复杂度与权衡

1⃣ 分配复杂度

First-Fit： $O (n)$
Best-Fit： $O (n)$
Worst-Fit： $O (n)$

2⃣ 优点

支持真正的 free
空间利用率高于 bump allocator
实现简单

3⃣ 缺点

分配慢
碎片不可避免
并发下非常困难
易产生安全问题

九、为什么现代 allocator 很少“纯 free list”

现实系统（jemalloc / tcmalloc）：

size class
多个 arena
thread-local cache
后台整理
Free list 是：

基础模型，而不是最终形态

十、一句话总结

Free List Allocator = 用时间和复杂度，换取“可释放”和“空间利用率”。

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

【运维】阿里云ARMS全解析：从技术原理到企业级落地实践

摘要：阿里云ARMS（应用实时监控服务）是一站式全链路可观测平台，通过无侵入采集、实时分析与智能告警，帮助开发者解决分布式系统监控难题。其核心架构包含数据采集层（基于Java Agent字节码增强）、传输存储层（流式计算引擎）、分析可视化层（服务拓扑与链路追踪）及告警联动层。ARMS支持快速接入Java应用，提供业务自定义监控能力，并集成RASP安全防护。企业案例显示，ARMS能显著缩短故障恢复时

2048 AI社区

基于yolo11的校园人流检测方法和系统实现（源码+定制+开发)

2048 AI社区

MySQL EXPLAIN 执行计划全解析

2048 AI社区

所有评论(0)

查看更多评论

虾球xz

@TM1695648164

已为社区贡献26条内容

CppCon 2025 学习:Building a High-Performance Binary Serialization Format with In-Place Modification

虾球xz

一、什么是 Serialization（序列化）？

1⃣ 问题背景

二、示例数据结构：Trade

三、最直觉的“错误做法”

✗ 直接 memcpy 整个结构体

为什么这是“no good”（非常重要）

问题 1：Endianness（字节序）

不同 CPU 的整数存储顺序不同：

问题 2：类型大小不一致

问题 3：结构体填充（Padding）

✗ 总结一句话

四、正确的思路：显式序列化

核心原则（必背）

五、一个“工程级正确”的序列化示例

六、为什么这个版本是“好”的？

使用固定宽度类型

显式字节序转换

完全避免 padding

七、反序列化（概念对称）

八、什么时候“memcpy 整个 struct”才安全？

九、一句话总结（面试 / 工程）

一、手写序列化：为什么“更好，但仍然不够好”

1⃣ 大量样板代码（Boilerplate）

2⃣ 发送端和接收端必须 100% 严格一致

3⃣ Schema 无法演进（Schema Evolution）

结果：

4⃣ 难以表达复杂/嵌套结构

二、如何改进？两条根本路线

两种序列化世界观

1⃣ Schema-based（基于 Schema）

2⃣ Schemaless（无 Schema）

三、Schema-Based 格式的核心思想

1⃣ 用 DSL 定义“数据契约”

2⃣ 从 Schema 自动生成代码

3⃣ 双方“部分”一致即可

四、Schema 如何“安全演进”

添加新字段（向前/向后兼容）

结果：

禁止的操作（会破坏兼容性）

五、Protobuf 在“线上”是如何编码的？

不是“按顺序写”的！

Tag 的组成

接收方解码逻辑

六、为什么这解决了“手写序列化”的所有痛点？

七、一句话总结（非常重要）

一、Schema-Based 编码（以 Protobuf 为例）

1⃣ 回顾：Trade 的 schema

2⃣ 第一张 SVG：Protobuf 在线编码的含义

① 字段 1：price = 100

② 字段 2：volume = 5000

③ 字段 3：timestamp = 1738473049

④ 字段 4：tradeId = “TRADEID_1234837ZZ”

3⃣ Tag 是如何编码的（关键数学点）

4⃣ 为什么说 Protobuf “有点自描述”

5⃣ Schema-Based 的本质总结

二、如果我事先不知道数据长什么样？

三、Schemaless 格式的核心思想

1⃣ 不需要双方约定 schema

2⃣ 提供“字典式 API”

3⃣ Schemaless 常见格式

四、JSON / MsgPack 示例文档

五、第二张 SVG：Schemaless（二进制）如何编码？

1⃣ 最外层：一个 map

2⃣ "price": 100

3⃣ "volume": 5000

4⃣ "timestamp": 1756309296041

5⃣ "tradeId": "137A649zz0"

6⃣ Schemaless 的本质

六、Schema-Based vs Schemaless 对比总结

七、一句话理解两种世界

一、Schemaless 示例：同一份文档

二、MsgPack 中的编码直觉

1⃣ 顶层：一个 map（对象）

2⃣ "price": 100

key：“price”

value：100

3⃣ "volume": 5000

key：“volume”

2⃣ `"price": 100`

3⃣ `"volume": 5000`

4⃣ `"timestamp": 1756309296041`

5⃣ `"tradeId": "137A649zz0"`

2⃣ `"price": 100`

3⃣ `"volume": 5000`

4⃣ `"timestamp": 1756309296041`

5⃣ `"tradeId": "137A649ZZ0"`

六、`Value` 接口的真正含义

2⃣ 访问 Map 中的字段 `"timestamp"`