杂谈 - markdown-it-rs

怎么这么快就过去一周了? 是不是谁偷偷摁到 Ctrl 键了. 又到了要更新博客的时间了, 放心, 我怎么会鸽你呢. 但是我这周好像什么都没做啊, 再水一篇吧.

说起来, 这里之前好像是周更的来着, 现在好像变成半月更了.

Markdown-it-rs

最近一直在忙这个, 给他重写一个新的后端引擎. 这部分可能涉及一些比较复杂的编程内容, 看不懂就直接跳过吧, 咕~

起因

起因是之前闲得没事, 秉着赛博斗蛐蛐的想法, 让 AI 帮我快速搭了一个 benchmark, 链接. 然后就发现了, 为什么 markdown-it-rs 的性能这么羸弱, 跟 GitHub 的 cmark-gfm 相比差了 2.2x. 一般来说, Rust 的性能与 C 是比较接近的, 会差这么多肯定是代码写的有问题了.

然后我又让 AI 仔细的对比了一下其他的竞品, 发现确实是要慢. 深入分析之后发现根本原因是内存的分配太不节制了, 渲染同一份 Markdown 文件, 某竞品只分配了 1.7k 次, 但是它却分配了 30k 次. 这种编译型语言写起来是真的头大, 我不要性能了, 快放我回去写 Py.

那么为什么会有这么多的内存分配呢, 有一部分是为可扩展性做出的妥协, 还有一部是分受限于 Rust 的所有权机制, 在原本的 Markdown-it.js 里简单直观的操作被搬到 Rust 里之后就直接过不了编译了.

举个🌰, 之前的智能引号 (smartquotes) 插件^[1], 因为受限于所有权规则, 根本拿不到 AST 节点属性的所有权, 导致他只能使用一种非常 "神奇" 的方式来解决问题. 大致分为三步, 1. 先对整个 AST 跑一遍深度优先遍历 (DFS), 把原本的树形结构拍平成一个数组 (Vec<FlatToken<'_>>), 代码; 2. 根据前后的内容, 计算需要替换的内容并存起来, 代码; 3. 最后再遍历一次 AST, 拿到每个节点的引用, 替换里面的文本, 代码.

那么用 N 表示 AST 的节点数量的话, 那么这个插件的时间复杂度就是 $O(N)$ 的, 并且, 他的空间复杂度因为数组的原因, 也是 $O(N)$.

这也就是说光是这个插件, 就会导致内存分配接近翻倍. 让他与原有的 $O(N)$ 合并一下就变成 $O(2N)$ 了, 然后简化一下... 等等? 怎么变回 $O(N)$ 了??? 肯定是我没睡醒. 总之差不多就行了, 又不是造飞机火箭.

新后端

因为现有架构的限制 (那个词怎么说来着? 阻抗失配?), 现有的优化已经到头了, 要想进一步的优化的话就只能完全重构了, 换成一个更加适合 Rust 的结构.

新的后端使用的是 "事件驱动" + "Arena" 的结构 (Arena 这个术语翻译过来好像叫 "内存池分配器"). 事件驱动应该就不需要我解释了, 写 JS 的时候应该 addEventListener() 方法没少用, 这个就是事件驱动的, 只有来活的时候才工作, 其余时间都在摸鱼.

把原来的 "智能引号" 插件搬到这个新的 "事件驱动" 结构上, 原本的 $O(N)$ 的空间复杂度瞬间就可以优化为 $O(1)$. 只需要记录前一个符号, 后一个符号, 和一个负责记录开括号的栈就行了. 代码.

那么 "Arena" 呢? 这个主要是为了解决刚刚提到的 30k 次内存分配的问题. 先来解释一下 "Arena" 的工作原理吧, 他的本质就是一块在内存上连续的结构 (Vec<_>), 但是与普通的 malloc/free 机制不同的是, 内存一旦被申请就不会被轻易的释放掉, 就算数据已经过期了, 也还是拿着. 在有新的内容加入到 "Arena" 里的时候, 如果有过期的数据, 直接把过期的数据原地修改成新的, 这样就可以减少内存的分配了. 当然, 为了实现他, 一般都需要附加一个单向链表来存储过期数据的位置.

struct NodeId {
	/// 指向 Arena 里槽位的指针
	slot: u32,
	/// 代际号, 用来判断是否过期
	generation: u32,
}

struct Slot<T> {
	/// 代际号, 用来判断是否过期
	generation: u32,
	/// 指向下一个过期节点的指针
	next_free: Option<u32>,
	/// 实际数据
	value: Option<T>,
}

struct Arena<T> {
	/// 实际数据
	slots: Vec<Slot<T>>,
	/// 链表头
	free_head: Option<u32>,
	/// 有效数据长度 (在这个例子里没什么用)
	len: usize,
}

impl<T> Arena<T> {
	fn new() -> Self {
		// ...
	}

	fn get(&self, id: NodeId) -> Option<&T> {
		let slot = self.slots.get(id.slot as usize)?;
		// 判断代际是否匹配, 避免拿到过期的数据
		if slot.generation == id.generation {
			slot.value.as_ref()
		} else {
			None
		}
	}

	fn get_mut(&self, id: NodeId) -> Option<&mut T> {
	    // 跟 get 差不多, 只不过返回可变的数据 (借出所有权)
	}

	fn remove(&self, id: NodeId) -> Option<T> {
		let slot = self.slots.get_mut(id.slot as usize)?;
		if slot.generation != id.generation {
			return None;
		}

		let value = slot.value.take()?;
		self.len -= 1;

		if let Some(next_generation) = slot.generation.checked_add(1) {
			// 插入到链表的最前面
			slot.generation = next_generation;
			slot.next_free = self.free_head;
			self.free_head = Some(id.slot);
		}

		Some(value)
	}

	fn insert_with(&mut self, make_value: impl FnOnce(NodeId) -> T) -> NodeId {
		// 拿到一个空闲的槽位
		let id = if let Some(slot_index) = self.free_head {
			let slot = &mut self.slots[slot_index as usize];
			self.free_head = slot.next_free.take();
			NodeId {
                slot: slot_index,
                generation: slot.generation,
            }
		} else {
			// 拿不到就创建一个新的
			let slot = u32::try_from(self.slots.len()).expect("document contains too many nodes");
			self.slots.push(Slot {
                generation: 0,
                next_free: None,
                value: None,
            });
            NodeId {
                slot,
                generation: 0,
            }
		};

		self.slots[id.slot as usize].value = Some(make_value(id));
		self.len += 1;
		id
	}
}

除此之外, 集中的内存管理还可以减轻内存碎片化和 TLB 缓存命中问题, 不过这些东西就太接近硬件了, 一般都不需要特别关注.

最值得关注的还是抽象层的运行时开销. 原来的插件系统是直接把对应的字符串内容传给插件, 让插件自己用循环来遍历; 在新的结构里, 这种方式是不被允许的, 所有插件都需要监听统一的事件, 但是, 这个事件流发生器也是有开销的, 他可能需要拉起某些分类器或者是回调函数, 并统一封装成状态机. (说好的 Rust 零成本抽象呢)

抽象层这个东西, 在应用层里出现可能没有什么问题, 但是在基础设施层出现的话, 一个不小心就可能导致性能雪崩, 毕竟随便某个地方都可能在实际使用的过程中被反复循环成千上万次, 可能少算一次哈希表, 性能就会直接翻倍.

那么这个开销有多大呢? 普通事件大概慢 2-3 倍, 逐字符事件差不多慢 6 倍. 毕竟是原来是直接用 for 循环遍历字符串, 这要是能再快的话计算机学就不存在了. (在渲染实测里大概慢 13-25%, 别急, 代码还没写完, 等我启动. 现在代码里全是脚手架, 怎么可能快的起来. 但是在面对智能引号这些场景的时候, 差不多能够快出 50%, 这些就是纯粹的算法优势了.)

当然, 上述的这些设计都是在 AI 的帮助下完成的. 很难想象, 古人在没有 AI 的时候是如何写出怎么复杂的代码的.

现在的 AI 的能力有点过于的恐怖了, 就一个单纯的工具而言, 他的能力已经远超我现在的认知了, 如果不是我一直在限制他的操作, 可能这些代码我自己就完全看不懂了. 我这些写了一周多的内容, 全部丢给他写的话, 可能几个小时就完成了. 没能让 AI 大人尽兴, 真是抱歉

我使用的模型是 GPT-5.6 Sol, 据说新的 GPT-6 Astra 在各方面都是断档式的领先, 我也稍微体验了一下, 使用中等的思考强度. 分给了他一个任务, 花了几分钟就完成了, 用了 10% 的上下文, 但是我的 5h 限额少了 43%. 嗯, 价格也是断档领先, 我还是用 5.6 算了.

我也不知道为什么我当初要写这个东西, 他对我而言有点太复杂了, 现在看到 AST 就头疼.

あなたの周りの世界は…あなたが思うより、ちょっとだけ、優しいよ ^[2]

とける風花とシロうさぎ, 上篇文章里提到的那个游戏, 怎么说呢? 有点失望, 但是又有点意外? 毕竟前作是《星白》 那个晚上玩完, 准备睡觉却发现枕头都湿了一半的游戏

说到宝物, 就想起来这首歌. 好温柔的声线, p😭q

按照白玉社的 "老传统", 在进行角色设计的时候多多少少都会对历史上的某些作品进行致敬. 星白就是对《银河铁道之夜》的致敬, 光看名字应该都看得出来. 甚至剧情结构和结局都是相似的 (是不是有点剧透?)

其中, "火车迷" 鹰世还单独致敬了《麦田里的守望者》, 或者说其实这也是主题之一? 这本书我在之前看的时候是完全读不懂的 (毕竟是面向成人的), 只记得主角满口脏话了, 然后处处碰壁, 在精神快要崩溃的时候和妹妹菲比一起回家了. (菲比简直就是天使! 在星白里对应的角色应该就是音理了, 音理也是天使!)

那么这次的 "风白" 呢? (缩写应该叫这个吧, VNDB 上有 "風シロ" 的别名) 这次致敬的是一部电影, Harvey, 讲的是主角的 "隐形朋友", 一个名叫 "Harvey" 的 "Pooka", 是一只 "兔子". (正好风白游戏里的那只半透明的兔子就叫 Harvey · Pooka) 关于这部电影, 具体的我就不展开了, 总之绝对不是我没看过.

与星白继承了银河铁道之夜淡淡的悲剧色彩不同的是, Harvey 是一部喜剧, 比起星白的震撼, 风白也更像是一个温馨的童话故事, 相比之下, 银河铁道之夜也能算作是童话? 不怕给小朋友造成什么心理阴影吗? 并且女主角普卡在某些方面总是让人幻视音理, 特别是在某些屑屑的语气的时候. 四舍五入也算是补上了星白里音理出场次数太少的遗憾了?

大致的情节是围绕着一群失去了什么的人, 如何在这个世界上继续活下去展开. 毕竟官方给的介绍最后一句就是 "なにかを失った人たちが、もう一度前を向く物語". 故事整体上还是挺温馨的, 就是有点太短了, 我差不多花了六个小时就玩完了. 并且他还有一个很长的后日谈, 好评.

正好在麦田里的守望者里也有类似的内容:

一个不成熟的人的标志是他愿意为了某个理而轰轰烈烈的死去, 而一个成熟的人的标志是他愿意为了某个理由而谦恭的活着.

虽然但是, 这样不会硌得慌吗, 全是骨头 (逃)

剩下的我就不剧透了, 感兴趣的话可以自己去玩玩, 剧情还是挺有意思的, 并且还有意料之外的转折, 最后还是 he, 虽说星白也是大团圆结局.

说到 he, 就不得不点名一下 key 社了, 我问你, 你这 he 他真的保熟吗. 我的 sp 自从过了姆Q线之后就再也没有打开过了, 年纪大了, 看不得这些, 现在就只想看点甜甜的. (很难不让人怀疑, key 社的编剧是不是有什么心理创伤)

もしかしたらすれ違うきみは今でも
あの日の眩しさでいたりして
ポケットもまだ膨らんだままで

当我们再次擦肩而过的时候, 你的口袋里一定装满了幸福吧.

为什么要用这么平淡的语气唱出这样的词. p😭q

其实这篇文章本来昨天就可以发出来的, 但是被音乐播放器卡住了, 要怪就怪阿斯特拉, 让他照着原来的写都写错了, 写出个死循环把我的浏览器都卡住了. 也可能是我的这个需求太罕见了, 没有什么训练数据吧, 之前那份代码也是我自己手写的来着.