← 返回博客

Rope 优化，第一部分

Thorsten Ball

Thorsten Ball

Antonio Scandurra

Antonio Scandurra

2024 年 11 月 18 日

几周前，我偶然看到了 Antonio 的一个 PR，标题是“加速 Rope 中的 point 转换”——谁会不想停下来仔细看看这个标题的 PR 呢？

描述已经符合标题。它包含基准测试结果，告诉我 Rope 上的一个名为 point_to_offset 的方法现在速度提高了 70%。70%！吞吐量增加了 250%。 （我不记得了，但我确信当我看到这些数字时，我发出了一声印象深刻的口哨声。）

然后是代码。 我滚动浏览了 diff，在第四次移动鼠标滚轮时，我停在了这段代码上

#[inline(always)]
fn nth_set_bit_u64(v: u64, mut n: u64) -> u64 {
    let v = v.reverse_bits();
    let mut s: u64 = 64;
 
    // Parallel bit count intermediates
    let a = v - ((v >> 1) & (u64::MAX / 3));
    let b = (a & (u64::MAX / 5)) + ((a >> 2) & (u64::MAX / 5));
    let c = (b + (b >> 4)) & (u64::MAX / 0x11);
    let d = (c + (c >> 8)) & (u64::MAX / 0x101);
 
    // Branchless select
    let t = (d >> 32) + (d >> 48);
    s -= (t.wrapping_sub(n) & 256) >> 3;
    n -= t & (t.wrapping_sub(n) >> 8);
 
    // [...]
}

好的，好的，好的——“并行位计数中间值”，“无分支选择”，在一个 PR 中导致速度提高 75%——我加入了。 我需要知道整个故事。 绝对会很有趣。

所以我问 Antonio 位摆弄是怎么回事，他不仅主动带我了解他所做的优化，还说我们应该配对并添加另一个优化，使 Rope 在处理制表符时速度更快。

并且——幸运的是——我们正是这样做的。 我们记录了整个配对过程，所以您也可以观看它，现在我将与您分享我目前所学到的关于我们在 Rope 上进行位摆弄优化的所有知识。

配套视频

Rope 优化，第一部分

1.5 小时的配套视频是完整的配对会话，Antonio 和 Thorsten 首先在 Rope 上讲解了这些新的优化，然后又添加了一个优化来索引制表符。

在此处观看视频 →

加速 Point 转换

首先，我们来看看 Antonio 是如何加速 Rope 中的“point 转换”的，以及这到底意味着什么。

如果您阅读过我们关于 Rope & SumTree 的文章，您已经知道：我们的 Rope 不是一个 *真正的* Rope，而是一个穿了战壕风衣的 SumTree，在 Antonio 做出更改之前大致是这样的

struct Rope {
    chunks: SumTree<Chunk>
}
 
struct Chunk(ArrayString<128>);

它是 Chunk 的 B 树，而 Chunk 只是一个最大长度为 128 字节的堆栈分配字符串。

这就是您需要的所有背景知识——我们的 Rope 是一个 128 字节字符串的 B 树。

问题

那么什么是 point 转换？ 用代码表示，它大致相当于这样

struct Point {
    row: u32,
    column: u32,
}
 
impl Rope {
    fn offset_to_point(&self, offset: usize) -> Point;
}

Point 转换意味着：获取字符串（表示为 Rope）中的任意偏移量，并将其转换为 Point——如果光标移动到给定的偏移量，光标将落在的行和列。

您可以想象，此方法在文本编辑器中很受欢迎。 Zed 从各种来源获取偏移量，并且必须将它们转换为行和列——每秒数百次甚至数千次，当您在文件中移动和编辑时。

现在想象一下您将如何实现该 offset_to_point 方法。

从概念上讲，您必须做的是遍历文件中的每个字符，计算您遇到的换行符和字符，并在到达您的偏移量时停止。 然后您就知道您在哪一行了。

这正是我们的 Rope 所做的。

如果您调用 rope.offset_to_point(7234)，Rope 将遍历其 SumTree 以找到包含偏移量 7234 的 Chunk，然后在该 Chunk 上，它将再次调用 offset_to_point。 而 *该* 方法，在 Chunk 上，看起来与这段代码非常相似

fn offset_to_point(text: &str, offset: usize) -> Point {
    let mut point = Point { row: 0, column: 0 };
    for (ix, ch) in text.char_indices() {
        if ix == offset {
            break;
        }
        if ch == '\n' {
            point.column = 0;
            point.row += 1;
        } else {
            point.column += 1;
        }
    }
    point
}

这很简单：设置一个 Point 形式的计数器，循环遍历 128 字节字符串中的所有字符，并跟踪您遇到的换行符。

但这也是问题所在，对吧：虽然 Rope 可以以 O(log(n)) 的速度将我们带到正确的 Chunk，但我们仍然必须循环遍历 128 个字符并手动计算换行符——就像穴居人一样。

现在您可能会说 128 个字符不多，并且像这样的小循环有什么危害，但请记住：我们讨论的是一个支持多个光标并一次与多个语言服务器对话的文本编辑器——这个循环执行得非常频繁，以至于触手可及。 我们希望它尽可能快。

这正是 Antonio 所实现的。

优化

Antonio 发现的是，与其每次需要查找换行符时都循环遍历 128 个字符，不如我们做一次并记住它们的位置，有效地构建一个 Chunk 的索引。

而我们需要做的只是一个 u128。

u128 是 Rust 的 128 位无符号整数类型，嘿，128——这正是 Chunk 中的字节数。

一个 u128 足以记住 Chunk 中的给定字节是否具有特定属性。 例如，如果 Chunk 中的相应字节是换行符，我们可以在给定位置将 u128 中的一位设置为 1。 或者我们可以翻转位来记住一个字符占用多少字节——使用 UTF-8 和表情符号，这可能不止一个字节。

这就是 Antonio 的 PR 所做的事情。现在我们的 Chunk 看起来像这样了

struct Chunk {
    chars: u128,
    chars_utf16: u128,
    newlines: u128,
 
    text: ArrayString<128>,
}

但它是如何工作的？ 它为我们带来了什么好处？ 这真的比循环遍历字符更好吗？

为了说明这个想法，让我们只关注换行符，并使用 u8 而不是 u128 —— 展示和计算的位数更少，但原理相同。

在 u8 中索引换行符

假设我们有以下文本

ab\ncd\nef

我们可以使用以下代码来索引 u8 中换行符的位置

fn main() {
    let text = "ab\ncd\nef";
    let newlines = newline_mask(text);
    // ...
}
 
fn newline_mask(text: &str) -> u8 {
    let mut newlines: u8 = 0;
    for (char_ix, c) in text.char_indices() {
        newlines |= ((c == '\n') as u8) << char_ix;
    }
    newlines
}

当我们运行它时，我们会得到一个看起来像这样的 newlines 位掩码

Newlines mask diagram showing bits set at positions 3 and 6

现在，newlines 告诉我们 text 中的第 3 个和第 6 个字符是换行符。太棒了。 现在有了 newlines，回到我们最初的问题：将偏移量转换为 Point。

newlines 如何对此有所帮助？

假设我们的 offset 是 4，文本是 "ab\ncd\nef"。 我们想知道字符 d 在哪一行和哪一列。

以下是我们如何使用 newlines 来查找

struct Point { row: u8, column: u8 }
 
fn offset_to_point(newlines: u8, offset: usize) -> Point {
    let mask = if offset == MAX_LEN {
        u8::MAX
    } else {
        (1u8 << offset) - 1
    };
 
    let row = (newlines & mask).count_ones() as u8;
    let newline_ix = u8::BITS - (newlines & mask).leading_zeros();
    let column = (offset - newline_ix as usize) as u8;
 
    Point { row, column }
}

我们首先创建一个 mask，其中所有位都设置为 1，直到我们感兴趣的偏移量

Offset mask diagram showing bits set from 0 to 4

然后，我们将该 mask 与我们传入的 newlines 进行按位与运算

Diagram showing the result of bitwise AND between newlines and mask

这只会留下我们感兴趣的偏移量之前的换行位被设置。 现在，要找出我们的偏移量在哪一行，我们所要做的就是计算剩余设置为 1 的位数。 就像这一行

let row = (newlines & mask).count_ones() as u8; // row = 1

这就是偏移量所在的行 —— 在我们的例子中是 1。 它是从零开始索引的，这意味着在与人而不是计算机交谈时，我们会说字符 d 在第 2 行。

下一步是确定列。 为此，我们需要计算我们感兴趣的 offset 与最后一个换行符之间的距离，因为那就是列：来自最后一个换行符的字符数。

此行首先为我们提供了最接近我们偏移量的换行符的位置

let newline_ix = u8::BITS - (newlines & mask).leading_zeros();

在我们的例子中，newline_ix 是 3

Diagram showing newline_ix position at 3

然后我们将其插入到下一行

let column = (offset - newline_ix as usize) as u8;

这给了我们列 1。

结果： ab\ncd\nef 中的偏移量 4 转换为 Point { row: 1, column: 1 } —— 第二行，第二列。

它的美妙之处

再看看上面的这两行

let row = (newlines & mask).count_ones() as u8;
let newline_ix = u8::BITS - (newlines & mask).leading_zeros();

count_ones() 和 leading_zeros() —— 听起来很像有一些循环正在进行来计算那些 1 和 0，对吧？

但是不，这就是美妙之处！ count_ones 和 leading_zeros 都是用单个 CPU 指令实现的。 没有必要的循环。 事实证明，CPU 非常擅长处理零和一。

不仅仅是我们减少了指令的数量，我们现在也减少了分支指令，并且无分支编程通常可以在热循环中带来巨大的加速。

如果我们把两个版本的 offset_to_point——一个带有循环，一个带有位掩码——放入微基准测试，并使用实际的 u128 而不是 u8 来使结果更明显，我们可以看到无循环、无分支的版本快多少

Running benches/benchmark.rs (target/release/deps/benchmark-21888b29446a33c0)

offset_to_point_u128/loop_version
                   time:   [56.914 ns 57.001 ns 57.096 ns]

offset_to_point_u128/mask_version
                   time:   [1.0478 ns 1.0501 ns 1.0529 ns]

带有循环的是 57ns，带有位掩码的是 1ns —— 快 57 倍。 令人印象深刻的口哨声。

当然，所有关于微基准测试的免责声明都适用，并且在我们的生产代码中，结果并没有那么剧烈，但仍然非常好：我一开始提到的 70% 的速度提升是真实的。

索引制表符

受到所有这些的启发和激励，Antonio 和我随后开始为制表符添加相同的索引。

“制表符？”您可能会说，“我不使用制表符。” 是的，您不使用，但 Zed 不知道这一点，仍然必须检查您的行首是否有制表符，以便正确显示它们。

制表符很棘手。 您不能像显示其他字符一样显示制表符。 制表符是...动态的，因为缺少更好的词。

字符串 \t\tmy function 的显示方式取决于您配置的制表符大小：如果制表符大小为 4，则 \t\t 应显示为八个空格。 如果是 2，则是四个空格。

“可怜的文本编辑器开发者”，您可能会想，“他们必须乘以数字。” 感谢您的同情，但是，听着，这还不是全部。

考虑这段文字

ab\t\tline 1
\t\tline 2

如果制表符大小为 4 并且启用了硬制表符，则应如下显示

Showing tabs

没错 —— 第一行中的第一个制表符仅占用两个空格，其他制表符均占用四个空格。

您看：制表符很棘手，而且事实证明，也很昂贵。

在性能分析中，Antonio 看到我们花费大量时间来确定给定文件中制表符的位置和数量。 大量时间。

因此，我们在配对会话中所做的是为制表符添加一个索引，该索引的工作方式与换行符的索引完全相同

struct Chunk {
    chars: u128,
    chars_utf16: u128,
    newlines: u128,
 
    // We added this field:
    tabs: u128
 
    text: ArrayString<128>,
}

这是否使 Zed 更快？

我们会看到的。 这次我们只添加了索引，但我们实际上还没有更改更高层代码来使用它。 我们将在下一个 Zed Decoded 剧集中执行此操作。

在此之前，请观看配套视频中的完整配对会话，以了解所有螺母和螺栓是如何安装到位的。