Strict Alias and Type Punning

最近在看代码的时候老感觉自己的基础不够扎实，加上最近比较摸鱼，于是想灌灌水。事情的起因是早上看到社区的一个优化：https://github.com/apache/arrow/pull/39397

这个优化的修改大概是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  // Read definition and repetition levels. Also return the number of definition levels
  // and number of values to read. This function is called before reading values.
  void ReadLevels(int64_t batch_size, int16_t* def_levels, int16_t* rep_levels,
                  int64_t* num_def_levels, int64_t* values_to_read) {
    batch_size =
        std::min(batch_size, this->num_buffered_values_ - this->num_decoded_values_);
    // If the field is required and non-repeated, there are no definition levels
    if (this->max_def_level_ > 0 && def_levels != nullptr) {
      *num_def_levels = this->ReadDefinitionLevels(batch_size, def_levels);
      // TODO(wesm): this tallying of values-to-decode can be performed with better
      // cache-efficiency if fused with the level decoding.
-      for (int64_t i = 0; i < *num_def_levels; ++i) {
-        if (def_levels[i] == this->max_def_level_) {
-          ++(*values_to_read);
-        }
-      }
+			 *values_to_read +=
+          std::count(def_levels, def_levels + *num_def_levels, this->max_def_level_);
    } else {
      // Required field, read all values
      *values_to_read = batch_size;
    }

实际上，这个地方 std::count 比循环效率高吗？否，虽然我们可以认为 std::count 和循环大概可以产生等价的代码，那么是什么东西让这样效果好一点呢？答案是编译器无法确定 num_def_levels, values_to_read 是不是一个东西，在循环中：

1
2
3
if (def_levels[i] == this->max_def_level_) {
  (*values_to_read);
}

会生成下面的代码：

1
2
3
4
5
6
7
8
0xc0c2f0 <ReadLevels()+96> inc %rdx
0xc0c2f3 <ReadLevels()+99> cmp %rax,%rdx
0xc0c2f6 <ReadLevels()+102> jge 0xc0c30c <ReadLevels()+124>
0xc0c2f8 <ReadLevels()+104> cmp %cx,(%r14,%rdx,2)
0xc0c2fd <ReadLevels()+109> jne 0xc0c2f0 <ReadLevels()+96>
0xc0c2ff <ReadLevels()+111> incq 0x0(%rbp)
0xc0c303 <ReadLevels()+115> mov (%rbx),%rax
0xc0c306 <ReadLevels()+118> jmp 0xc0c2f0 <ReadLevels()+96>

这段很简单的代码在循环中反而显得判断很多余。根据我们之前介绍的内容，编译器可以很好的优化这种场景，甚至做一些向量化的优化。

这里我们会了解到的部分就是 strict aliasing，这部分的 cppreference 可以见：https://en.cppreference.com/w/cpp/language/object#Strict_aliasing 。Strict Aliasing 大概就是，什么之后能够判断变量（想象循环里的 def_levels, max_def_level_ , values_to_read ）指向不同的区域。

那么，根据我们上面的 cppreference （也可以参考博文 https://zhuanlan.zhihu.com/p/595286568 ）。类型上大家都是 int64_t，并不好判断两边不是同一个 alias！

杂余

告诉编译器好好工作

本 patch 的 solving 用了个很简单的方法：直接把变量拷出来！你两个本地内存你能飞到哪去呢？

除此之外，这里还提到了很多方法

  1. RESTRICT
  2. https://en.cppreference.com/w/cpp/language/attributes/assume
  3. gnu::pure
  4. …

这些方法主要是告诉编译器好好干活不要胡思乱想！具体可以参考这个系列：https://developers.redhat.com/blog/2020/06/02/the-joys-and-perils-of-c-and-c-aliasing-part-1#

Strict Aliasing 和 UB

在 Strict Aliasing 的情况下，这里其实很容易写出一些相关的 ub: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int foo( float *f, int *i ) { 
    *i = 1;               
    *f = 0.f;            
   
   return *i;
}

int main() {
    int x = 0;
    
    std::cout << x << "\n";   // Expect 0，Output 0
    x = foo((float*)(&x), &x);
    std::cout << x << "\n";   // Expect 0, But Output 1
}

函数 foo( float *f, int *i )，编译器根据 strict aliasing rule 会认为 *f 和 *i 指向不同的内存区域，并以此进行优化，但实际上指向了相同的内存区域，因此产生了错误的结果。

嘛这个虽然 -fno-strict-aliasing 可以阻止一些错误，但是实际也可以参考 Type Punning

Type Punning

最早看 LevelDB 代码的时候，发现它从 buffer 中读取整数走了一个 memcpy。这个我当时还没理解，后来才知道是 Type Punning 的玄机。我们可以介绍一下 Strict Aliasing 之类的允许的类型转化和一些奇怪的问题。

Whenever an attempt is made to read or modify the stored value of an object of type DynamicType through a glvalue of type AliasedType, the behavior is undefined unless one of the following is true:

  • AliasedType and DynamicType are similar.
  • AliasedType is the (possibly cv-qualified) signed or unsigned variant of DynamicType.
  • AliasedType is std::byte,(since C++17) char, or unsigned char: this permits examination of the object representation of any object as an array of bytes.

此外，还有下面的图：比如说 int32_t 的 object representation 可能很多，但转成同样位数的 float，却可能是 cb，因为它可能有些 value representation 是没有的！

9C554F6D-AEC1-4758-A462-3B3D75F0ABCC

这里具体也可以参考 https://www.youtube.com/watch?v=_qzMpk-22cc&ab_channel=CppCon

Reference

  1. Type punning in modern C++ - Timur Doumler - CppCon 2019 https://www.youtube.com/watch?v=_qzMpk-22cc&ab_channel=CppCon
  2. 严格别名（Strict Aliasing）规则是什么，编译器为什么不做我想做的事？ - Atled的文章 - 知乎
    https://zhuanlan.zhihu.com/p/595286568
  3. https://developers.redhat.com/blog/2020/06/02/the-joys-and-perils-of-c-and-c-aliasing-part-1#
  4. https://gist.github.com/shafik/848ae25ee209f698763cffee272a58f8