所谓系统编程，顾名思义，指的是有关操作系统的代码编写，如 Windows、Unix 系统编程。和我们常见的应用编程有所不同，系统编程更接近硬件，且它使用的函数库和库函数调用方法也有所不同，那么，在面对更加复杂的系统编程时，作为开发者，又有哪些较好的优化措施呢？

作者 | Paul Cavallaro

译者 | 苏本如，责编 | 屠敏

出品 | CSDN（ID：CSDNnews）

以下为译文：

本篇文章中，将会概述一些常用的优化技术和“系统编程”的一些妙招。不管今天的“系统编程”意味着什么，我们将介绍一些方法，以便你的代码运行更快、更加高效，并能让你从你得到的任何知识中收获更多的好处。

这篇文章里讨论的所有示例可以在GitHub的这个地方获取：paulcavallaro/systems-programming。

缓存线和伪共享

在现代对称多处理（SMP）系统上，“伪共享”（False sharing）是一个非常容易理解的多线程代码优化的问题。对于这个问题的讨论已经相当广泛了。一个基本的思想是机器上的物理内存不是无限粒度的，也就是说，你不能仅仅读取一个字节。相反，当你想要读取一个字节的内存时，处理器不仅会读入并缓存这个字节，而且会读入并缓存该字节周围的数据，因为它假设这些数据也可能被使用。这个被读取和缓存的数据单元被称为“缓存线”，本质上它是可以访问的最小内存块。

截至2019年，缓存线的大小都是2 的乘方，通常介于32到256个字节之间，其中最常见的大小是64个字节。

现在，为了支持一台机器上的多个处理器以一致的方式从同一块内存中读和写，这台机器上必须只有一个处理器可以独占地访问给定的缓存线。

“伪共享”是指意外地将两个不相关的数据块放在同一缓存行中。当有两个处理器分别更新这两个不同的数据块中的数据时，比如多个计数器的值，就会产生互相干扰，因为每个处理器都试图以独占的方式访问包含这两个数据块的缓存线。

对“伪共享”这个名称的解释是，尽管这两个计数器从理论上来讲不应该互相影响，但它们没有任何好的理由地“错误地共享”了一个缓存线。

一种解决方案是将强行将数据写入到分开的缓存行上，在C/C++语言中，这可以通过强制结构体/类（struct/class）成员的对齐来实现。在这个示例examples/cache-lines.cc中，我们使用abseil（注：谷歌内部使用多年的 C++ 代码库，现已开源）宏ABSL_CACHELINE_ALIGNED来实现这一点。

为了证明实际效果，我们针对两个不同的结构体NormalCounters和CacheLineAwareCounters 中的std::atomic<int64> 类型的计数器做了基准测试。

// NormalCounters is straight forward naive implementation of a struct of
// counters.
// Note: We also use ABSL_CACHELINE_ALIGNED on the NormalCounters struct, but
// not its members, so that the entire struct will be aligned to a cache line.
// Otherwise the struct might be placed towards the end of a cache line,
// accidentally straddling two cache lines, thereby improving its performance.
struct ABSL_CACHELINE_ALIGNED NormalCounters {
std::atomic<int64> success{0};
std::atomic<int64> failure{0};
std::atomic<int64> okay{0};
std::atomic<int64> meh{0};
};
// CacheLineAwareCounters forces each counter onto a separate cache line to
// avoid any false sharing between the counters.
// Note: We must use ABSL_CACHELINE_ALIGNED for each member, since we want to
// pad every single counter so it will be forced onto its own separate cache
// line.
struct ABSL_CACHELINE_ALIGNED CacheLineAwareCounters {
ABSL_CACHELINE_ALIGNED std::atomic<int64> success{0};
ABSL_CACHELINE_ALIGNED std::atomic<int64> failure{0};
ABSL_CACHELINE_ALIGNED std::atomic<int64> okay{0};
ABSL_CACHELINE_ALIGNED std::atomic<int64> meh{0};
};

这个基准测试分别测试了在运行1个，2个，3个和4个线程的情况。每个线程会触发结构体内一个单独的原子计数器65,536次。以下是在带有Haswell处理器的2013 MacBook Pro计算机上的处理结果：

Executing tests from //examples:cache-lines
-----------------------------------------------------------------------------
Cache Line Size: 64
sizeof(NormalCounters) = 64
sizeof(CacheLineAwareCounters) = 256
2019-08-13 01:16:18
Run on (4 X 2800 MHz CPU s)
CPU Caches:
L1 Data 32K (x2)
L1 Instruction 32K (x2)
L2 Unified 262K (x2)
L3 Unified 4194K (x1)
---------------------------------------------------------------------------
Benchmark Time CPU Iterations
---------------------------------------------------------------------------
BM_NormalCounters/threads:1 389 us 387 us 1812
BM_NormalCounters/threads:2 1264 us 2517 us 234
BM_NormalCounters/threads:3 1286 us 3718 us 225
BM_NormalCounters/threads:4 1073 us 3660 us 204
BM_CacheLineAwareCounters/threads:1 386 us 385 us 1799
BM_CacheLineAwareCounters/threads:2 200 us 400 us 1658
BM_CacheLineAwareCounters/threads:3 208 us 581 us 1152
BM_CacheLineAwareCounters/threads:4 193 us 721 us 1008

对上述结果作个注释：Time代表每个线程的从开始到结束的挂钟时间(wall clock time)，而CPU则代表每个线程使用的CPU时间。

我们可以看到两个结构体的大小是不同的，其中：sizeof(NormalCounters)=64 ，而 sizeof(CacheLineAwareCounters)=256。这是因为我们对单个字段施加了对齐约束，这样每个成员都在自己的缓存线上。因此，它不是像往常的Int64那样占用8个字节，而是占用一个完整的缓存线，在我的机器上是64个字节。

我们还看到对于单线程的情况，NormalCounters与CacheLineWareCounters的性能差别微乎其微。但是当我们添加更多线程时，CacheLineAwareCounters的表现要比那些易受“伪共享”错误影响的简单的普通计数器的实现要好得多。

有趣的是，在单线程的情况下，CacheLineAwareCounters需要的挂钟时间(wall clock time)比多线程情况下要长，这可能指向一些微妙的基准测试问题，或者可能有一个固定的延迟量，但是在多线程时这个延迟量被分散到多个线程中，因此每个线程的延迟量看上去更小了。

神奇的2的乘方（幂）

在当前的硬件中，除法是最昂贵的操作之一，这里的昂贵意味着“最长延迟”。Agner Fog的指令延迟列表列出了英特尔公司Skylake处理器的DIV指令在两个64位寄存器上运行，其延迟为35-88个周期，而在相同的两个64位寄存器上运行ADD指令的延迟只有1个周期。因此，在其它操作能够完成相同工作的地方，我们应该尽量避免使用除法操作。

除了实际做除法外，除法操作常用的一个地方是取模运算（%）。而取模运算的一个常用的地方是hash表：要从一个hash表转到一个存储桶(bucket)，需要进行HASH % TABLE_SIZE这样的取模运算。取模运算的另一个更加频繁使用的地方是开放寻址算法，因为我们需要不断地将值重新映射回hash表存储桶空间。

那么，取模运算如何帮助我们从hash表转到存储桶呢？这就要讲到有点无聊但是很神奇的2的乘方了！

首先，让我透露答案：我们将强制所有hash表的大小为2的N次方（幂）。

我们可以利用这个特性用更快的位运算（bit twiddling）来代替除法运算。另外，这个特性很容易维护，每当我们需要增加hash表的大小以摊销rehashing的成本时，我们都会将hash表的大小增加一倍，因此随着hash表的增长，它的大小将保持为2的幂。

现在，我们使用除法运算或者取模运算，将hash值映射到hash表中的bucket索引上。bucket索引必须严格小于hash表的大小，并且这个映射的散列值应该是无序状态。

为了不使用除法运算，我们将使用位掩码（bitmask）来“屏蔽”所有的设置位,除了那些严格小于2的幂的设置位之外。这种方式可以将所有的entropy保持在最低有效位，就像取模运算一样，但它要快得多。Agner Fog在相同的英特尔 Skylake体系结构中把这种运算放在1周期延迟的指令列表中。

作为关于位运算（bit twiddling）和解释如何选择位掩码（bitmask）的一个简单回顾，让我们来看看一些位模式（bit patterns）。

因为数字是用二进制表示的，所以我们知道每一个2的幂（数值N）只有一个位集。例如：

Decimal | Binary
2 | 00 00 00 10
8 | 00 00 10 00
32 | 00 10 00 00
128 | 10 00 00 00

这意味着所有的N-1的值都比log2（N）的有效位低一位。例如：

Decimal | Binary
1 | 00 00 00 01
7 | 00 00 01 11
31 | 00 01 11 11
127 | 01 11 11 11

因此，为了在HASH % N计算中替代我们的取模运算符，我们使用“按位和（bitwise AND）”运算来计算HASH &(N-1)的值。这将只保留比我们的log_2(N)位低的设置位，将任何HASH值映射到一个[0，N]之间的数字。如果需要，我们甚至可以缓存这个位掩码，这样以后就不必重新计算它了。

为了展示使用“位掩码”技巧比使用普通的取模运算的速度要快，我编写了一个小基准测试来比较执行一百万次取模运算和一百万次“位掩码”运算的结果。

Executing tests from //examples:power-of-two
-----------------------------------------------------------------------------
2019-08-13 02:24:03
Run on (4 X 2800 MHz CPU s)
CPU Caches:
L1 Data 32K (x2)
L1 Instruction 32K (x2)
L2 Unified 262K (x2)
L3 Unified 4194K (x1)
--------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------
BM_Mod 9261 us 9234 us 75
BM_BitMask 325 us 324 us 1984

从上面的测试结果我们可以看到，使用取模操作符执行DIV指令要比使用“位掩码”大约慢28倍，这个结果接近Agner Fog的慢35倍的预测值。

因为这个技巧很容易做到，并且提供了一个很好的例子，它已经被许多高性能的hash表使用，比如abseil Swiss Tables的flat_hash_set和flat_hash_map，以及ConcurrencyKit’s ck_ht_map。

寻址空间高位(Top Bit)用途的调整

通常情况下，你想在一个指针上存储一两个额外的信息。事实上，这种做法非常常见，以至于维基百科有一篇专门关于它的文章。实现这一点的一种方法是利用许多64位系统（如Linux）上的虚拟内存地址空间只有48位的这个特性，尽管我们使用8个字节来存储它们。

这意味着，我们可以把任何我们想要的旧东西放在前16位，当我们真正不想引用它时，就可以屏蔽掉它。下面是一些使用指针的高位(top bit)来存储底层数据是否“脏了”的C++代码示例。

constexpr uintptr_t kDirtyBit = 0x8000000000000000;
constexpr uintptr_t kPtrMask = 0x7fffffffffffffff;
static_assert(sizeof(uintptr_t) == 8, "Only works on 64-bit systems");
template <typename T>
uintptr_t MarkDirty(T* t) {
return reinterpret_cast<uintptr_t>(t) | kDirtyBit;
}
template <typename T>
T* GetPointer(uintptr_t t) {
return reinterpret_cast<T*>(t & kPtrMask);
}

不过，有趣的是，由于这是Linux内存管理/虚拟地址空间的一个特性，所以它可能会发生变化，而且实际上已经发生了变化！

LWN（Linux Weekly News）在2017年发布了补丁集，实现了五级页表，以支持更大数量的可寻址内存空间。如果启用这个更改的话，Linux的虚拟内存寻址空间将从现在48位提高到57位，从而将虚拟内存寻址空间的大小从256 TiB增加到128 PiB，这对于每个人来说都足够了。

默认情况下这个更改无法启用。部分原因是各种高性能程序，特别是各种JavaScript引擎和 LuaJIT，对寻址空间高位用途的调整会导致一些额外的数据被打包到指针中。

锁定条带化(Lock Striping)

当你希望多个线程以独占方式访问共享数据时，锁可以用于互斥。但缺点是，如果共享数据被频繁访问，而且这是系统的关键部分的话，那么线程可能会将大部分时间花在锁的争用上，而不是实际工作上。

解决这个问题的一个常见方法是引入更多的锁。你说什么？等一下！

好吧，我想说的是：不是一个保护所有数据的锁，而是有许多只负责一部分数据的锁。通过这种方式，我们将数据分成独立的、互不竞争的存储桶。假设数据访问方式都倾向于一致的，增加数据的切分会按比例减少争用锁的线程数。

下面是用C++写的一个小例子，提供了线程安全的hash-set的两种实现。第一个实现ThreadSafeHashSet使用单个锁来保护单个基础hash-set（absl::flat_hash_set）。第二个实现LockStripedHashSet有N个单独的锁，保护N个单独的基础hash-set（abs::flat_hash_sets）。

// Simple thread-safe single-lock hash set
class ThreadSafeHashSet {
public:
void Insert(uint64 i) {
absl::MutexLock lock(&mu_);
hash_set_.insert(i);
}
bool Contains(uint64 i) {
absl::MutexLock lock(&mu_);
return hash_set_.contains(i);
}
private:
absl::Mutex mu_;
absl::flat_hash_set<uint64> hash_set_;
};
// Chunk the data into `kNumChunks` separate hash sets, guarded by separate
// locks.
template <size_t kNumChunks>
class LockStripedHashSet {
public:
void Insert(uint64 i) {
// Mod the data to calculate which hash_set/lock to use
const size_t idx = i % kNumChunks;
absl::MutexLock lock(&mu_[idx]);
hash_set_[idx].insert(i);
}
bool Contains(uint64 i) {
const size_t idx = i % kNumChunks;
absl::MutexLock lock(&mu_[idx]);
return hash_set_[idx].contains(i);
}
private:
std::array<absl::Mutex, kNumChunks> mu_;
std::array<absl::flat_hash_set<uint64>, kNumChunks> hash_set_;
};

为了说明锁定条带化的好处，我们在多个线程存在的情况下对两个线程安全的hash-set性能进行了基准测试，每个线程都插入了一百万项。对于LockStripedHashSet，我们尝试将数据拆分成4块和8块。结果如下：

Executing tests from //examples:lock-striping
-----------------------------------------------------------------------------
2019-08-24 22:24:37
Run on (4 X 2800 MHz CPU s)
CPU Caches:
L1 Data 32K (x2)
L1 Instruction 32K (x2)
L2 Unified 262K (x2)
L3 Unified 4194K (x1)
--------------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------------
BM_SingleLock/threads:1 65 ms 65 ms 11
BM_SingleLock/threads:2 140 ms 254 ms 2
BM_SingleLock/threads:3 140 ms 332 ms 3
BM_SingleLock/threads:4 142 ms 405 ms 4
BM_LockStriping_4_Chunks/threads:1 71 ms 69 ms 9
BM_LockStriping_4_Chunks/threads:2 90 ms 178 ms 4
BM_LockStriping_4_Chunks/threads:3 89 ms 248 ms 3
BM_LockStriping_4_Chunks/threads:4 82 ms 299 ms 4
BM_LockStriping_8_Chunks/threads:1 70 ms 69 ms 10
BM_LockStriping_8_Chunks/threads:2 74 ms 143 ms 4
BM_LockStriping_8_Chunks/threads:3 71 ms 198 ms 3
BM_LockStriping_8_Chunks/threads:4 60 ms 200 ms 4

同样地，Time代表每个线程的挂钟时间(wall clock time)，CPU代表每个线程使用的CPU时间。另外请注意，由于我的机器只有4个逻辑内核，所以这个测试最多只能运行4个线程，因为超出这个范围的任何线程实际上都不会导致任何额外的争用。

从上面我们可以看到，在单线程的情况下，LockStripedHashSet无论是分块或不分块，挂钟时钟和CPU时间上的表现都比简单的ThreadSafeHashSet稍差。

然而，随着线程数量的增加，对锁的争用增加，LockStripedHashSet在这种情况下性能要好得多。在线程数较高的情况下，将数据拆分成8块优于拆分成4块的情况。

虽然锁定条带化可以帮助减轻对锁的争用，但它的缺点是增加了锁的存储开销。在我们的示例中，7个额外的锁和额外的absl::flat_hash_set簿记的开销对于我们的基准中的一个实例来说是很小的，但是如果你在一个应用程序中用一个8路条带化的线程安全的hash-set替换所有这些散列集，那么你可能会使其内存使用量大大增加。

结束语

虽然以上还远远不是最常见的系统编程技巧的详尽列表，但希望它能激发你进一步学习的欲望，掌握更多的工具来提高你自己的应用程序的性能，或者至少它能让你更容易地理解为什么性能敏感的代码在做它正在做的事情。

原文：

本文为 CSDN 翻译，转载请注明来源出处。

【End】