内存拷贝（memcpy()）和异或（bit-wise XOR）是程序中运行最快的操作之一，其速度受到CPU、内存和编译器（GCC版本）的影响。

内存拷贝memcpy(des, src, len) 则是将长度为len 的数据从地址src 拷贝到地址des 。

按位异或（异或）可以分为几类：

1. a^b：两个数值的异或。相当于两个寄存器内值在CPU 中计算异或，大多数CPU 中一个时钟周期完成。速度取决于CPU 的频率，频率越高，速度越快。
2. a^Region：一个数值与一块内存Region 中的每个值异或，结果保存在Region 中，速度相当于顺序访存。
3. RegionA = RegionA^RegionB：两块内存中对应位置上的值异或。
4. RegionC = RegionA^RegionB：两块内存中对应位置上的值异或，结果保存在另一块内存中。

四类异或速度依次递减。平常中越到的是第3 种，本文中异或速度也是第3 种。

继续阅读 →

CPU Cache 是CPU 中用于减少平均访问内存时间的高速存储器件。较内存使用的DRAM ，cache 使用的SRAM 速度更快、价格也更高，所以cache 容量一般较小。与cache 相关的概念有：cache line，associativity（相连性），L1 cache，L2 cache ，cache 命中，cache 失效等。

cache 按层次分为L1、L2 甚至L3级cache，速度依次递减，容量依次增大。CPU 直接能够读取的只有L1 cache。在大多数处理器包括Intel CPU 中，cache按照缓存的指令或者数据分为数据缓存和指令缓存（如L1d 和L1i） 。在多核的CPU 中，每个核心具有独立的L1 级cache，往往公用L2 级cache。公用cache 可能存在多线程缓存污染等问题。

cache 和内存传输的最小单位是cache line，一般大小为64 bytes。cache 每次从内存读取或者写入cache line 大小的数据，而不是我们在程序中定义的数据结构的大小。cache lines 之间的替换常用的是LRU 算法。如果CPU 读取的数据在cache 中，则cache 命中（cache hit），否则cache 失效（cache miss）。每一级的cache 失效将到下一级cache 中寻找数据，直至内存。cache miss 是有开销的，小于访存时间，大于cache hit 时间。每次cache 失效，CPU 就会处于停滞（stall）状态，直至缓存读取到所需要的数据。

因为cache 容量远小于内存（有种说法是1:1000），内存和cache 之间存在映射关系（associativity）。按照映射关系不同，分为：全相连映射（fully associative），多路组相连映射（N-way set associative）和直接映射（directly mapped）。全相连映射缓存和内存是全映射关系，内存中任何一块数据都可以没有限制地放的任何一个cache line 中，缓存利用率高，但设计复杂未被采用；直接映射将一块内存地址映射到一个cache line（the number of cache line = memory address%number of cache lines，其中内存地址以cache line 大小为单位），直接映射设计起来简单，但利用率低；多路组相连映射缓存更为常见，是设计复杂度和性能的权衡。它将一块内存映射到不同路上的cache lines 中，如果是8-路组相连，则一块内存映射到8-路上的cache lines 上（the number of cache line = memory address%(number of cache lines/number of ways)。不同路上的负责缓存相同内存的缓存构成一个集合set，不同set 缓存不同内存地址的数据。number of set = cache size/(ways of associativity * size of cache line)。

继续阅读 →