03-字符串优化

引言

这一章聚焦于字符串的实现，主要对字符串的实现做了两点优化：

1. 性能优化：增加对短字符串和中等长度的字符串的支持。
2. 功能优化：增加对UTF-8的支持。

写下这章要实现的Lua代码：

local short_string = "A short string."
local middle_string = "This is a string that is a bit longer."
local long_string = "This is a long string that is longer than the middle one."

dbg_print(short_string)
dbg_print(middle_string)
dbg_print(long_string)

print("tab:\t-") -- tab    -
print("null: \0.") -- '\0'
print("\xE4\xBD") -- invalid UTF-8
print("\72\101\108\108\111") -- Hello
print("\xE7\xAB\xB9\xE7\x9F\xA5\xE5\x90\xBE\x0D") -- 竹知吾

实现

这么优化的目的非常明显，保证长字符串的功能性，同时针对短字符串做性能优化。就像《Rust程序设计》211页引用的高德纳的那句话——“计算机科学家倾向于处理非统一性结构（情形1、情形2、情形3），而数学家则倾向于找一个统一的公理来管理整个系统。”。接下来，一起详细分析一下这么实现的好处。

#[derive(Default, Clone)]
pub enum Value {
    Function(fn(&mut ExeState) -> i32),
    ShortString(u8, [u8; SHORT_STR_MAX]),
    MidString(Rc<(u8, [u8; MID_STR_MAX])>),
    LongString(Rc<Vec<u8>>),
    Integer(i64),
    Float(f64),
    Boolean(bool),
    #[default]
    Nil
}

贴上当前Value的定义，之前的Value::String(String)枚举被拆分成了3个枚举，分别适用于：

• 短字符串：适用长度为[0, 14]，Value枚举定义为Value::ShortString(u8, [u8; SHORT_STR_MAX])。
• 中等长度字符串：适用长度为[15, 47]，Value枚举定义为Value::MidString(Rc<(u8, [u8; MID_STR_MAX])>)。
• 长字符串：适用长度为[48, ∞)，Value枚举定义为Value::LongString(Rc<Vec<u8>>)。

在说为什么这么做之前，先分析一下之前Value的内存布局，Value::String(String)是最长的枚举类型，三字标头（指针、长度、容量）共占用3个usize的空间，在64位系统中占用3*8=24字节，其次是Integer(i64)和Float(f64)，固定占用8字节，加上枚举的tag会占用1字节，所以简单来看，Value的内存布局如下：

struct ValueRepr {
    data: [u64; 3],
    tag: u8
}

考虑对齐量为8字节，则Value的大小应当为32字节，但是实际上，因为String类型包含不可为空的指针，且枚举中不存在第二个类型包含不可为空的指针，如Box<T>、Vec<T>、String、&T和&mut T。因此Rust的编译器会针对Value::String(String)做优化，让tag以及空出的7字节成为Value::String(String)可使用的内存空间，使得Value的大小实际为24字节。参见死灵书的 repr(Rust) 小节的最后一段话。

在之前的设计中，Value::String(String)是对Rust内置类型String的简单包裹，当我需要将一个字符串的内容复制到另一个字符串时，要么发生所有权的转移，将当前字符串的内容移交给新的字符串，要么做一次深拷贝，显然非常不灵活而且深拷贝开销较高。因此首先第一步，将原来的Value::String(String)改成Value::String(Rc<String>)，这样在复制字符串的时候，只需要拷贝原来字符串的引用即可。但这么做是有代价的，原来访问字符串只用一次寻址，但是套上Rc后则需要两次。教程中，作者分析了使用String、Rc<String>、Rc<str>、Rc<(u8, [u8; 47])>和内联(u8, [u8; 14])五种方案，然后选择了Rc<String>作为长字符串的实现，Rc<(u8, [u8; 47])>和内联(u8, [u8; 14])分别作为中等字符串和短字符串的优化。Rc<(u8, [u8; 47])>是堆上存取字符串的折中方案，只需一次寻址即可访问字符串。而(u8, [u8; 14])则是将字符串的内容放在栈上，效率更高，至于为什么长度是14，有了之前对Value内存布局的分析，可以很轻松的知道，(u8, [u8; 14])本身的大小是15字节，加上tag的1字节，刚好和Value的长度一致为16字节。

至于UTF-8，得益于Rust内置的String已经提供了完善的支持，只需要把字符串的存储方式的改成u8数组，再实现相关的类型转换特型即可，不再赘述。

小结

本节主要对字符串类型做了一些适应动态类型语言的优化，顺便支持了UTF-8。同时教程中作者也在这节中选择了引用计数作为实现垃圾回收的方式，用Rust实现标记清除的垃圾回收实现方式看起来并不是一件容易的事。

本节代码：03-OptimizeString