什么时候应该关注缓存未命中?

7
我将通过我在项目中遇到的一个实际问题来解释我的问题。
我正在编写一个类似可编程vi编辑器的c库,并计划提供一系列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是一个使用lua作为脚本的*nix shell。它的命令执行单元(执行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的典型情况。

3
你正在编写一个真正的源代码编辑器吗?如果是,性能就不那么重要了。或者你的库做了什么?为什么性能如此关键?你是否进行过基准测试(启用编译时优化)和剖析?请编辑你的问题以更好地解释真正的动机以及你打算使用它的应用程序。 - Basile Starynkevitch
1
将您的代码组织成最易于理解和维护的方式。除非您的代码非常频繁地执行,例如每秒60次,因为它必须针对每个图形帧执行,否则通过为指令缓存进行优化节省的时间在整个程序生命周期内可能会比您花费的优化和随后的额外维护时间少。例如,如果您花费一小时进行优化,从而节省了一微秒的时间,则您的代码必须执行36亿次才能收回那一小时的时间。 - JeremyP
1
除了@JeremyP所说的,情况实际上比那更糟。为了避免优化尝试对未来产生负面影响,您可能需要在每个新版本的编译器、操作系统、硬件环境等中重新测试,因此Jeremy的设计/测试/调试/测量的“标准时间”必须不断重复 :( - ThingyWotsit
1
为什么这被标记为C++?void vi_dw(struct vi *vi); 明显是C语言,如果是C++的话应该是 void vi::dw( ) - MSalters
不要滥用标签!C++不是C。 - too honest for this site
1个回答

12

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

如果性能如此重要,请启用更多优化(也许使用gcc -flto -O2 -mtune=native编译和链接您的整个应用程序或库,即使用链接时间优化),并仅对关键部分进行手动优化。您应该相信您的优化编译器

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

不清楚您的库是关于什么以及您的设计目标是什么。增加灵活性的一种可能性是在应用程序中嵌入某些解释器(例如luaguilepython等),从而通过脚本进行配置。在许多情况下,这样的嵌入可能足够快(特别是当应用程序特定的原语足够高级时)。另一个(更复杂的)可能性是通过一些JIT编译库(例如libjitlibgccjit)提供元编程能力(因此将用户脚本“编译”成动态生成的机器代码)。

顺便提一句,你的问题似乎集中在指令高速缓存未命中上。我认为数据高速缓存未命中更加重要(且编译器无法优化),这就是为什么你会更喜欢使用向量而非链表(以及更广泛地关注低级别的数据结构,专注于使用连续或者缓存友好的访问)。

(你可以找到Herb Sutter的一个很好的视频来解释上述观点;我忘了参考文献)

在一些非常特定的情况下,使用最近的GCCClang,添加一些__builtin_prefetch可能会稍微提高性能(通过减少高速缓存未命中),但也可能会严重影响性能,因此我不建议通常使用它,但请查看this


谢谢。也许我想知道的不是如何优化它,而是其他人将如何处理这种情况。你的“我不在乎”对我来说也是一个很好的回答。PS:我在帖子末尾更新了这个库的应用场景,在项目4中。 - weiweishuo

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接