什么时候我们应该关心缓存缺失？

Question

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

我正在编写ac库(其行为类似于可编程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.

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

有两个极端:

1. 只使用一个包装器但复杂到足以采用所有移动操作并将它们转换为相应的API.

2. 使用超过二十个小而简单的包装.一个包装器是一个API.

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

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

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

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

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

2. 基于该库的用户程序很少调用所有这些API,只调用它们的一部分,并且每个API通常不超过10次.

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

4,与使用库的情况一样,我将以lua-shell例子为例(有点偏离主题,但有些朋友想知道为什么我如此关心它的性能):

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 State Machine并运行它.

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

这是使用的典型情况libvi.

Answer 1

我不会那么关心缓存未命中(特别是在你的情况下),除非你的基准测试(启用了编译器优化,即gcc -O2 -mtune=native使用GCC进行编译 ....)表明它们很重要.

如果性能非常重要,则可以进行更多优化(可能使用链接时优化来编译和链接整个应用程序或库gcc -flto -O2 -mtune=native),并仅手动优化最重要的内容.您应该相信您的优化编译器.

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

目前还不清楚你的图书馆是什么,你的设计目标是什么.增加灵活性的可能性可能是在您的应用程序中嵌入一​​些解​​释器(如lua或guile或python等等),因此通过脚本进行配置.在许多情况下,这种嵌入可能足够快(特别是当应用程序特定的基元具有足够高的水平时).另一种(更复杂的)可能性是通过某些JIT编译库(如libjit或libgccjit)提供元编程能力(因此您可以将用户脚本"编译"为动态生成的机器代码).

顺便说一下,你的问题似乎集中在指令缓存未命中.我相信数据缓存未命中更重要(并且编译器不太可以优化),这就是为什么你更喜欢向量链接列表(更普遍地关注低级数据结构,专注于使用顺序或缓存) - 友好 - 访问)

^{(你可以通过Herb Sutter找到一个很好的视频,它解释了最后一点;我忘记了参考)}

在一些非常特殊的情况下,对于最近的GCC或Clang,添加一些__builtin_prefetch可能会略微提高性能(通过减少缓存未命中),但它也可能会显着损害它,所以我不建议一般使用它,但请看这个.