Blog

什么是SFINAE

什么是SFINAE #

替换失败非错(substitution failure is not an error),英文简称为 SFINAE。

函数模板的重载决议 #

我们之前已经讨论了不少模板特化。我们今天来着重看一个函数模板的情况。当一个函数名称和某个函数模板名称匹配时,重载决议过程大致如下:

  1. 根据名称找出所有适用的函数和函数模板
  2. 对于适用的函数模板,要根据实际情况对模板形参进行替换;替换过程中如果发生错误,这个模板会被丢弃
  3. 在上面两步生成的可行函数集合中,编译器会寻找一个最佳匹配,产生对该函数的调用
  4. 如果没有找到最佳匹配,或者找到多个匹配程度相当的函数,则编译器需要报错

我们还是来看一个具体的例子(改编自参考资料 [1])。虽然这例子不那么实用,但还是比较简单,能够初步说明一下。

#include <stdio.h>
struct Test {
  typedef int foo;
};
template <typename T>
void f(typename T::foo)
{
  puts("1");
}
template <typename T>
void f(T)
{
  puts("2");
}
int main()
{
  f<Test>(10);
  f<int>(10);
}

输出为: 12

我们来分析一下。首先看 f<Test>(10); 的情况:

  1. 我们有两个模板符合名字 f
  2. 替换结果为 f(Test::foo) 和 f(Test)
  3. 使用参数 10 去匹配,只有前者参数可以匹配,因而第一个模板被选择

再看一下 f<int>(10) 的情况:

  1. 还是两个模板符合名字 f
  2. 替换结果为 f(int::foo) 和 f(int);显然前者不是个合法的类型,被抛弃
  3. 使用参数 10 去匹配 f(int),没有问题,那就使用这个模板实例了

在这儿,体现的是 SFINAE 设计的最初用法:如果模板实例化中发生了失败,没有理由编译就此出错终止,因为还是可能有其他可用的函数重载的。

...

优化和执行顺序

优化和执行顺序 #

假设我们有三个全局 int 变量 x、y 和 a,然后我们执行下面的代码:

x = a;
y = 2;

那是不是编译器会产生先写入 x、再写入 y 的代码呢?

我想你猜到了,答案为“不一定”。下面是某些编译器实际产生的汇编代码(参见 https://godbolt.org/z/zsfvsf63E%EF%BC%89%EF%BC%9A

mov     eax, DWORD PTR a
mov     DWORD PTR y, 2
mov     DWORD PTR x, eax

我们可以看到,编译器产生的代码是:先读入 a,再写入 y,最后写入 x。

为什么要这样?一样,是因为优化。读入 a 的数值到 eax 寄存器里,跟写入 2 到 y 里是两个不相关操作,可以同时执行。这样的代码,比起完全按程序员指定的执行顺序产生的代码,可望得到更高的性能。

Viewpoint #

From #

优化和未定义行为

优化和未定义行为 #

假如我们有一个 int 类型的变量 x,那 x * 2 / 2 的结果是几?如果 C++ 把有符号整数运算溢出的结果定义为补码的内存表示,也就是说,32 位正整数 0x40'00'00'00(230)乘以 2 的结果就是 0x80'00'00'00(−231),再除以 2 的话,我们就不能得回原先的数值,而是得到了 0xC0'00'00'00(−230)。这样的话,x * 2 / 2 就不能优化为 x!

那能不能使用异常呢?也不行。跟除零不一样,整数运算溢出不会产生硬件中断。而如果我们在每条加法、减法、乘法、除法(对,除法也可能溢出—— INT_MIN / -1 就会)上都加入指令来检查是否发生溢出、并在发生溢出时报告异常的话,性能的退步将是不可接受的 [5]。

所以,C++ 的处理方式就是,规定有符号整数运算溢出为未定义行为 [6],即程序员需要保证这种情况不会发生,否则后果自负。这在允许编译器把 x * 2 / 2 优化成 x 的同时,也意味着,下面这样的代码返回的结果可能会跟程序员预想的不同(参见 https://godbolt.org/z/Ex5ad6vM9%EF%BC%89%EF%BC%9A

bool test(int n)
{
  return (n + 1) == INT_MIN;
}

你想的是,如果 n + 1 溢出了,应该会得到 INT_MIN 这个特殊的结果。但编译器可以认为溢出是永远不会发生的(因为正确的程序里不应该有未定义行为),因此可以直接返回 false。——这也是实际可以在 GCC 和 Clang 上测到的结果。

Viewpoint #

From #

阅读论文的基本功

阅读论文的基本功 #

那这种基本功从何而来呢?总结起来,我觉得可以从以下三个方面来获得这些基本功。

  1. 自己撰写论文,然后努力发表。这个办法比较奢侈也比较痛苦,而且见效较慢。但是一旦成功,效果往往是其他办法不能比的。即便没有成功发出论文来,你也可以从论文的写作过程中学到很多知识。所以,在有条件发表论文的情况下,一定要不惜代价地尝试。即使最后一篇论文也没发出来,但这种尝试也绝对有好处。最明显的好处就是,可以帮助你理解论文写作过程中要展现好的一面、掩藏坏的一面,理解作者在论文中没写的那部分到底是什么。
  2. 找到两篇可以比较的论文:后者引用前者,和前者的方法进行比较,并在前者的基础上有所提高。这时,你可以拿着前者的文章,看看作者是如何“吹牛”的、又是如何避免谈缺陷的,而后者又是如何表明自己弥补了前者不足的。通过比较前后两篇论文的内容,可以有效地提高你用批判性思维阅读论文的能力。但是,这个方法对系统性的文章,比如谷歌的“三驾马车”这类的文章,不是特别适用。主要原因是,这类文章表述的系统往往是从无到有的原创性系统,也只有谷歌这样的大型科技公司才有能力去开发这样的系统。一般来说,是无法找到可以相比较的文章的。
  3. 一定要认识到论文中一般只交代作者成功的故事,而对于成功背后无数次失败的尝试这样的内容绝少出现。这就意味着,你看到的只是作者成功的解决方案。有过基础研究的人很清楚地知道,任何一篇论文背后都隐藏着无数次失败的尝试。对于系统论文、大数据论文,这个规律依然适用。比如,在微软、百度、阿里巴巴做过类似于谷歌“三驾马车”的系统开发人员,这些人虽然还没有成功,但是经历了多次类似的失败,已经足够体会到经验背后的教训了,因而可以比较轻松地读懂这些论文。而对其他没有类似体验的人来说,就很难了。

所以有些论文你读不懂,其实是因为论文中缺乏对系统研究过程中失败尝试的描述,而你也没有过开发类似系统的体验。因此,从这个角度来讲,最能读懂论文的,往往都是那些从事过类似系统开发的人。

关于这一点,我认为比较好的解决办法只有两个。

  1. 加入一个团队进行类似的系统开发,毕竟“纸上得来终觉浅”。
  2. 找到这篇论文在各大网站上的相关解读,以及论文作者此后演讲的相关材料,这些资料往往是帮助你理解论文的最佳途径。在这些演讲材料中,作者往往会更自由地分享一些成功的经验、失败的教训。而在论文发表时,因为同行评审等压力,往往会有所忌讳,所以不会分享的太全面。

写到这里,我需要特别指出一类比较特殊的论文,就是综述性质的论文。这种论文,往往是由业界大佬就这个领域在某段时间内的所有研究工作汇总而成,是最接近教科书的论文。

Viewpoint #

From #

论文的两个特点

论文的两个特点 #

理解了“论文到底是写给谁看的”这个问题,我们再来看下一个问题:论文通常都是怎么写出来的?这是个非常复杂的问题,我会一点一点地分解剖析。

首先,论文作者对同行的知识结构是有假设的。 和教科书非常不同,论文作者首先会假设同行对这个领域的基础性研究和相关知识都已经非常熟悉了,因此只在非常必要或者特殊情况下才会去介绍特定的知识。而在大部分情况下,论文作者给出一个引用已经是很奢侈的事情了。这意味着什么呢?如果你连这个领域的基础知识都不懂,是没有办法一上手就读懂论文的。

举个例子,如果你去看大数据基础架构的论文,比如谷歌的“三驾马车”的论文,倘若你连最基本的分布式系统知识都没有,那无异于是“小孩子读微积分”;倘若机器学习的知识你一点儿都不懂,那一篇讨论深度学习的论文对你来说,无异于“天书”。

因此,作为一个读者,你能不能读懂一篇论文,直接取决于你自己在这个领域中的基础知识积累。所以,想要有阅读论文的能力,首先要把基础知识补好。

其次,论文里面的内容都是“化了妆”的。 学术圈有一个基本规则,简单地说就是:不可以在论文里面说谎。然而,“不说谎”不代表作者要把自己做的系统的方方面面都说出来,换个说法就是:作者可以对系统的缺点轻描淡写,能简单就简单;而对系统的优点和先进性大书特书,极力营造为“天上没有,人间极品”的效果。因此,在不违背基本原则的前提下,作者在论文里有选择性地写作,是学术圈里公认的套路。

这就意味着,读者要带着批判性去读论文,而不能按照读教科书的思路去读。教科书的作者在写作时一般都会做到客观公正、深入浅出,而这很显然不是论文作者的写作方法。 因此,对于作者语焉不详的地方要多问几个为什么,对于作者自夸的地方要认真思考一下是不是真的牛。其实,这些都是读懂论文的基本功。

Viewpoint #

From #

伪共享(C示例)

Content #

伪共享(false-sharing)的意思是说,当两个线程同时各自修改两个相邻的变量,由于缓存是按缓存块来组织的,当一个线程对一个缓存块执行写操作时,必须使其他线程含有对应数据的缓存块无效。这样两个线程都会同时使对方的缓存块无效,导致性能下降。

例子:

#include <stdio.h>
#include <pthread.h>

struct S{
   long long a;
   long long b;
} s;

void *thread1(void *args)
{
    for(int i = 0;i < 100000000; i++){
        s.a++;
    }
    return NULL;
}

void *thread2(void *args)
{
    for(int i = 0;i < 100000000; i++){
        s.b++;
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t t1, t2;
    s.a = 0;
    s.b = 0;
    pthread_create(&t1, NULL, thread1, NULL);
    pthread_create(&t2, NULL, thread2, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("a = %lld, b = %lld\n", s.a, s.b);
    return 0;
}

在这个例子中,main 函数中创建了两个线程,分别修改结构体 S 中的 a 、b 变量。a 、b 均为 long long 类型,都占 8 字节,所以 a 、b 在同一个 cache line 中,因此会发生为伪共享的情况。

...

查看CPU缓存信息

查看CPU缓存信息 #

通过 getconf 命令查看缓存的信息:

# getconf -a | grep CACHE
LEVEL1_ICACHE_SIZE                 32768
LEVEL1_ICACHE_ASSOC                8
LEVEL1_ICACHE_LINESIZE             64
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64
LEVEL2_CACHE_SIZE                  262144
LEVEL2_CACHE_ASSOC                 4
LEVEL2_CACHE_LINESIZE              64
LEVEL3_CACHE_SIZE                  3145728
LEVEL3_CACHE_ASSOC                 12
LEVEL3_CACHE_LINESIZE              64
LEVEL4_CACHE_SIZE                  0
LEVEL4_CACHE_ASSOC                 0
LEVEL4_CACHE_LINESIZE              0

在这个缓存的信息中,L1Cache(LEVEL1_ICACHE 和 LEVEL1_DCACHE 分别表示指令缓存和数据缓存,这里我们只关注数据缓存)的 cache line 大小为 64 字节,路数为 8 路,大小为 32K,可以计算出缓存的组数为 64 组(32K÷8÷64=64)。

Viewpoint #

From #

14 | CPU Cache:访存速度是如何大幅提升的?

缓存的三种映射方式

缓存的三种映射方式 #

根据缓存中组数和路数的不同,我们将缓存的映射方式分为三类:

  1. 直接相连映射缓存只有一个路,一个内存块只能放置在特定的组上;
  2. 全相连映射缓存只有一个组,所有的内存块都放在这一个组的不同路上;
  3. 组组相连映射缓存同时由多个组和多个路。

对于直接相连映射,当多个内存块映射到同一组时,会产生冲突,因为只有一列,这个时候就需要将旧的缓存块换出,同时将新的缓存块放入,所以直接相连映射会导致缓存块被频繁替换。

而全相连映射可以在很大程度上避免冲突,不过,当要查询某个缓存块时,需要逐个遍历每个路,而且电路实现也比较困难。一个折中的办法就是,采用组组相连映射。这种方式与直接相连映射相比,产生冲突的可能性更小,与全相连映射相比,查询效率更高,实现也更简单。

假设缓存的组数一直是 2^n,这种形式虽然有利于查询和定位,但是如果一个程序刚好以 2^n 间隔寻址,就会导致地址更多的被映射到同一个组,而另外一些组就会被映射得很少。因此,也有些缓存的组数会设计成一个质数,这样即便程序以 2^n 间隔寻址,落到相同组的可能性会大大减小,这样一来,缓存各个组的利用率就会相对均衡。

Viewpoint #

From #

14 | CPU Cache:访存速度是如何大幅提升的?

缓存块替换策略

缓存块替换策略 #

缓存块替换策略需要达到的一个目标是:被替换出的数据块应该是将来最晚会被访问的块。然而,对将来即将发生的事情是没有办法预测的,因为处理器并不知道程序将来会访问哪个地址。因此,现在的缓存替换策略都采用了最近最少使用算法(Least Recently Used ,LRU)或者是类似 LRU 的算法。

LRU 的原理很简单,比如程序要顺序访问 B1 、B2、B3、B4、B5 这几个地址块,并且这几个缓存块都映射到缓存的同一个组,同时我们假设缓存采用 4 路组组相连映射,那么当访问 B5 时,B1 就需要被替换出来。要实现这一点,有很多种方式,其中最简单也最容易实现的是利用位矩阵来实现。

首先,我们定义一个行、列都与缓存路数相同的矩阵。当访问某个路对应的缓存块时,先将该路对应的行置为 1,然后再将该路对应的列置为 0。最终结果体现为,缓存块访问时间的先后顺序,由矩阵行中 1 的个数决定,最近最常访问缓存块对应行 1 的个数最多。

假设现在一个四路相连的缓存组包含数据块 B1、B2、B3、B4, 数据块的访问顺序为 B2、B3、B1、B4,那么 LRU 矩阵在每次访问后的变化如下图所示:

你会发现,最终 B2 对应行的 1 的个数最少,所以 B2 将会被优先替换。

Viewpoint #

From #

14 | CPU Cache:访存速度是如何大幅提升的?