c - 我们什么时候应该关心缓存丢失？

Question

我想通过我在项目中遇到的一个实际问题来解释我的问题。

我正在编写一个 c 库(其行为类似于可编程 vi editor)，并且我计划提供一系列 API(总共 20 多个):

void vi_dw(struct vi *vi);
void vi_de(struct vi *vi);
void vi_d0(struct vi *vi);
void vi_d$(struct vi *vi);
...
void vi_df(struct vi *, char target);
void vi_dd(struct vi *vi);

这些 API 不执行核心操作，它们只是包装器。例如，我可以实现 vi_de()像这样:

void vi_de(struct vi *vi){
    vi_v(vi);  //enter visual mode
    vi_e(vi);  //press key 'e'
    vi_d(vi);  //press key 'd'
}

但是，如果包装器这么简单，我必须编写 20 多个类似的包装器函数。
所以，我考虑实现更复杂的包装器来减少数量:

void vi_d_move(struct vi *vi, vi_move_func_t move){
   vi_v(vi);
   move(vi);
   vi_d(vi);
}
static inline void vi_dw(struct vi *vi){
    vi_d_move(vi, vi_w);
}
static inline void vi_de(struct vi *vi){
    vi_d_move(vi, vi_e);
}
...

函数vi_d_move()是一个更好的包装函数，他可以将类似移动操作的一部分转换为API，但不是全部，如vi_f() ，它需要另一个带有第三个参数的包装器 char target .

我完成了从我的项目中挑选的示例的解释。上面的伪代码比实际情况简单，但足以表明:
包装器越复杂，我们需要的包装器就越少，它们的速度也会越慢。(它们会变得更加间接或需要考虑更多的条件)。

有两个极端:

仅使用一个包装器，但足够复杂以采用所有移动操作并将它们转换为相应的 API。

使用二十多个小而简单的包装。一个包装器就是一个 API。

对于案例 1，包装器本身很慢，但它有更多机会驻留在缓存中，因为它经常被执行(所有 API 共享它)。这是一条缓慢但炙手可热的道路。

对于案例 2，这些包装器简单快速，但驻留在缓存中的机会较小。至少，对于任何第一次调用的 API，都会发生缓存未命中。(CPU 需要从内存中获取指令，而不是 L1、L2)。

目前，我实现了五个包装器，每个包装器都比较简单和快速。这似乎是一种平衡，但似乎只是。我之所以选择五，是因为我觉得移动操作自然可以分为五组。我不知道如何评估它，我不是说分析器，我的意思是，理论上，在这种情况下应该考虑哪些主要因素？

在后期，我想为这些 API 添加更多细节:

这些 API 需要快速。因为这个库被设计成一个高性能的虚拟编辑器。删除/复制/粘贴操作旨在接近裸 C 代码。

基于此库的用户程序很少调用所有这些 API，仅调用其中的一部分，通常每个不超过 10 次。

在实际情况下，这些简单包装器的大小约为 80 字节，即使合并成一个复杂的包装器也不超过 160 字节。 (但会引入更多 if-else 分支)。

4、根据使用库的情况，我取lua-shell举个例子(有点跑题，但有些 friend 想知道我为什么这么关心它的性能):
lua-shell是一个 *nix shell，它使用 lua作为它的脚本。它的命令执行单元(执行 forks()、execute()..)只是一个注册到 lua 状态机的 C 模块。
Lua-shell将所有内容视为 lua .

因此，当用户输入时:

local files = `ls -la`

并按Enter .字符串输入首先被发送到 lua-shell 的预处理器——将混合语法转换为纯 lua 代码:

local file = run_command("ls -la")

run_command()是lua-shell的命令执行单元的入口，我之前说过，是一个C模块。

我们可以谈谈libvi现在。 lua-shell 的预处理器是我正在编写的库的第一个用户。这是它的相关代码(伪):

#include"vi.h"
vi_loadstr("local files = `ls -la`");
vi_f(vi, '`');
vi_x(vi);
vi_i(vi, "run_command(\"");
vi_f(vi, '`');
vi_x(vi);
vi_a(" \") ");

上面的代码是 luashell 的预处理器实现的一部分。
在生成纯 lua 代码后，他将其提供给 Lua 状态机并运行它。

shell 用户对 Enter 之间的时间间隔很敏感。和一个新的提示，在大多数情况下 lua-shell 需要更大尺寸和更复杂的混合语法的预处理脚本。

这是 libvi 的典型情况。用来。

Answer 1

我不太关心缓存未命中(尤其是在您的情况下)，除非您的基准测试(启用编译器优化，即使用 gcc -O2 -mtune=native 编译，如果使用 GCC ....)表明它们很重要。

如果性能如此重要，请启用更多优化(也许编译和链接整个应用程序或库与链接时优化的 gcc -flto -O2 -mtune=native)，并仅手动优化关键部分。你应该 相信你的optimizing compiler .

如果您处于设计阶段，请考虑让您的应用程序多线程或以某种方式并发和并行。小心，这可以比缓存优化更快。

目前尚不清楚您的图书馆是关于什么以及您的设计目标是什么。增加灵 active 的一种可能是在您的应用程序中嵌入一些解​​释器(如 lua 或 guile 或 python 等...)，从而通过脚本对其进行配置。在许多情况下，这种嵌入可能足够快(尤其是当应用程序特定的原语具有足够高的级别时)。另一种(更复杂的)可能性是提供 metaprogramming能力也许通过一些JIT compiling图书馆喜欢 libjit或 libgccjit (因此您可以将用户脚本“编译”成动态生成的机器代码)。

顺便说一句，您的问题似乎集中在指令缓存未命中上。我相信数据缓存未命中更重要(编译器更难以优化)，这就是为什么你更喜欢例如到链表的 vector (更普遍地关心低级数据结构，专注于使用顺序或缓存友好的访问)

(你可以找到 Herb Sutter 的一个很好的视频，它解释了最后一点；我忘记了引用)

在一些非常特殊的情况下，最近的 GCC或 Clang , 添加几个 __builtin_prefetch 可能会稍微提高性能(通过减少缓存未命中)，但也可能会严重损害它，所以我不建议一般使用它，但请参阅 this .