为什么在 64 位机器上使用 uint8_t 运行 编写的这段代码比使用 uint32_t 或 uint64_t 编写的类似代码更快？
Why does this piece of code written using uint8_t run faster than analogous code written with uint32_t or uint64_t on a 64bit machine?
64 位系统上的数学运算 运行 在 32/64 位数据类型上比像 short 这样的较小数据类型由于隐式提升而更快，这不是常识吗？然而，在测试我的 bitset 实现时（大部分时间取决于按位运算），我发现使用 uint8_t 比 uint32_t 提高了约 40%。我特别惊讶，因为几乎没有任何复制可以证明差异是合理的。无论 clang 优化级别如何，都会发生同样的事情。
8位：
#define mod8(x) x&7
#define div8(x) x>>3
template<unsigned long bits>
struct bitset{
private:
uint8_t fill[8] = {};
uint8_t clear[8];
uint8_t band[(bits/8)+1] = {};
public:
template<typename T>
inline bool operator[](const T ind) const{
return band[div8(ind)]&fill[mod8(ind)];
}
template<typename T>
inline void store_high(const T ind){
band[div8(ind)] |= fill[mod8(ind)];
}
template<typename T>
inline void store_low(const T ind){
band[div8(ind)] &= clear[mod8(ind)];
}
bitset(){
for(uint8_t ii = 0, val = 1; ii < 8; ++ii){
fill[ii] = val;
clear[ii] = ~fill[ii];
val*=2;
}
}
};
32位：
#define mod32(x) x&31
#define div32(x) x>>5
template<unsigned long bits>
struct bitset{
private:
uint32_t fill[32] = {};
uint32_t clear[32];
uint32_t band[(bits/32)+1] = {};
public:
template<typename T>
inline bool operator[](const T ind) const{
return band[div32(ind)]&fill[mod32(ind)];
}
template<typename T>
inline void store_high(const T ind){
band[div32(ind)] |= fill[mod32(ind)];
}
template<typename T>
inline void store_low(const T ind){
band[div32(ind)] &= clear[mod32(ind)];
}
bitset(){
for(uint32_t ii = 0, val = 1; ii < 32; ++ii){
fill[ii] = val;
clear[ii] = ~fill[ii];
val*=2;
}
}
};
这是我使用的基准（只是从位置 0 迭代地移动一个 1 直到结束）：
const int len = 1000000;
bitset<len> bs;
{
auto start = std::chrono::high_resolution_clock::now();
bs.store_high(0);
for (int ii = 1; ii < len; ++ii) {
bs.store_high(ii);
bs.store_low(ii-1);
}
auto stop = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::microseconds>((stop-start)).count()<<std::endl;
}
Isn't the common knowledge that math operations on 64bit systems run faster on 32/64 bit datatypes than the smaller datatypes like short due to implicit promotion?
这不是普遍真理。一如既往，合身取决于细节。
Why does this piece of code written using uint_8 run faster than analogous code written with uint_32 or uint_64 on a 64bit machine?
标题与问题不符。没有 uint_X 这样的类型，您也没有使用 uintX_t。您正在使用 uint_fastX_t。 uint_fastX_t 是 至少 X 字节的整数类型的别名，语言实现者认为它提供最快的操作。
如果我们将您之前提到的假设视为理所当然，那么从逻辑上讲，语言实现者会选择使用 32/64 位类型作为 uint_fast8_t。也就是说，您不能假设他们已经这样做了，并且用于做出该选择的任何通用测量（如果有的话）不一定适用于您的情况。
也就是说，无论 uint_fast8_t 是哪种类型的别名，您的测试对于比较可能不同的整数类型的相对计算速度是不公平的：
uint_fast8_t fill[8] = {};
uint_fast8_t clear[8];
uint_fast8_t band[(bits/8)+1] = {};
uint_fast32_t fill[32] = {};
uint_fast32_t clear[32];
uint_fast32_t band[(bits/32)+1] = {};
不仅类型（可能）不同，数组的大小也不同。这肯定会影响效率。
TL:DR: 位集的大“桶”意味着您在线性迭代时重复访问同一个，创建更长的依赖链，out-of-order exec 不能有效重叠.
较小的存储桶提供 instruction-level 并行性，使对单独字节中的位的操作彼此独立。
可能的原因是您对位进行线性迭代，因此同一 band[] 元素内的所有操作形成了 &= 和 |= 操作的长依赖链，加上存储并重新加载（如果编译器无法通过循环展开来优化它）。
对于 uint32_t band[]，这是一个 2x 32 操作链，因为 ii>>5 将给出相同的索引。
Out-of-order exec 只能部分重叠执行这些长链，如果它们的延迟和 instruction-count 对于 ROB（重新排序缓冲区）和 RS（保留站，又名调度程序）来说太大。 64 个操作可能包括 store/reload 延迟（在现代 x86 上为 4 或 5 个周期），这是一个深度链长度可能为 6 x 64 = 384 个周期，可能至少由 128 微指令组成，具有一些并行加载（或更好地计算）1U<<(n&31) 或 rotl(-1U, n&31) 掩码可以“用完”管道中一些浪费的执行槽。
但是对于 uint8_t band[]，你移动到一个新元素的频率是 的 4 倍，仅经过 2x 8 = 16 次操作，所以 dep 链是 1/ 4 长度。
另请参阅 现代 x86 CPU 重叠两个长依赖链的另一种情况（一个简单的 imul 链，没有其他 instruction-level 并行性），特别是关于单个 dep 链变得比 RS（un-executed uops 的调度程序）更长的部分是我们开始失去一些独立工作执行重叠的点。 （针对没有lfence人为遮挡重叠的情况。）
另请参阅 现代微处理器
90 分钟指南！ 和 https://www.realworldtech.com/sandy-bridge/ 了解现代 OoO exec CPU 如何解码和查看指令的一些背景知识。
小桶与大桶
大桶仅在扫描第一个 non-zero 位或填充整个内容或其他内容时才有用 。当然，您真的希望使用 SIMD 对其进行矢量化，一次检查 16 或 32 个字节以查看其中是否存在 non-zero 元素。当前的编译器将在填充整个数组的循环中为您矢量化，但不会搜索循环（或任何无法在第一次迭代之前计算的 trip-count ），除了可以处理的 ICC。回复：在 bit-vectors 上使用快速操作，参见 Howard Hinnant's article（在 vector<bool> 的上下文中，这是 sometimes-useful 数据结构的不幸名称。）
不幸的是，C++ 通常并不能使对相同数据使用不同大小的访问变得容易，除非您使用 g++ -O3 -fno-strict-aliasing 或类似的东西进行编译。
虽然 unsigned char 总是可以为其他任何东西起别名，所以你可以将它用于你的 single-bit 访问，只使用 uintptr_t （它可能和寄存器一样宽，除了 ILP32-on-64 位 ISA）用于 init 或其他。或者在这种情况下，uint_fast32_t 在许多 x86-64 C++ 实现上是 64 位类型将使它对此有用，不像通常那样糟糕，当你只使用 [=119= 时浪费缓存空间] 的 32 位数字，在某些 CPU 上进行 non-constant 除法时速度较慢。
在 x86 CPU 上，字节存储自然是完全有效的，但即使在 ARM 或其他系统上，存储缓冲区中的合并仍然可以使相邻字节 RMW 完全有效。 ()。而且您仍然会获得 ILP；较慢的缓存提交仍然没有将负载耦合到如果更窄则可能独立的存储那么糟糕。在 lower-end CPU 具有较小 out-of-order 调度程序缓冲区的情况下尤其重要。
（x86 字节加载需要使用 movzx 到 zero-extend 来避免虚假依赖，但大多数编译器都知道这一点。Clang 对此不计后果，偶尔会造成伤害。）
（彼此接近的不同大小的访问会导致 store-forwarding 停顿，例如字节存储和与该字节重叠的 unsigned long 重新加载将有额外的延迟：What are the costs of failed store-to-load forwarding on x86?）
代码审查：
在大多数 CPU 上，存储掩码数组可能比仅根据需要计算 1u32<<(n&31)) 更糟糕。如果你真的很幸运，一个聪明的编译器可能会管理从构造函数到基准循环的不断传播，并意识到它可以在循环内旋转或移位以生成位掩码，而不是在已经执行其他内存操作的循环中索引内存.
（一些非 x86 ISA 有更好的 bit-manipulation 指令，并且可以廉价地实现 1<<n，尽管如果编译器很聪明，x86 也可以在 2 条指令中做到这一点。xor eax,eax / bts eax, esi，BTS 通过 operand-size 隐含地屏蔽了移位计数。但这只适用于 32 位 operand-size，而不适用于 8 位。没有 BMI2 shlx , x86 variable-count 移动 运行 为 3英特尔 CPUs，而 AMD 为 1。）
几乎肯定不值得同时存储 fill[] 和 clear[] 常量。一些 ISA 甚至有一个 andn 指令，它不能成为动态操作数之一，即在一条指令中实现 (~x) & y。例如，具有 BMI1 扩展名的 x86 具有 andn。 (gcc -march=haswell).
此外，您的宏是不安全的：将表达式包装在 () 中，这样 operator-precedence 就不会在您使用 foo[div8(x) - 1] 时攻击您。
如 #define div8(x) (x>>3)
但实际上，无论如何您都不应该将 CPP 宏用于此类内容。即使在现代 C 中，也只需定义 static const shift = 3; 移位计数和掩码。在 C++ 中，在 struct/class 范围内执行此操作，并使用 band[idx >> shift] 或其他内容。 （当我输入 ind 时，我的手指想输入 int；idx 可能是一个更好的名字。）
64 位系统上的数学运算 运行 在 32/64 位数据类型上比像 short 这样的较小数据类型由于隐式提升而更快，这不是常识吗？然而，在测试我的 bitset 实现时（大部分时间取决于按位运算），我发现使用 uint8_t 比 uint32_t 提高了约 40%。我特别惊讶，因为几乎没有任何复制可以证明差异是合理的。无论 clang 优化级别如何，都会发生同样的事情。
8位：
#define mod8(x) x&7
#define div8(x) x>>3
template<unsigned long bits>
struct bitset{
private:
uint8_t fill[8] = {};
uint8_t clear[8];
uint8_t band[(bits/8)+1] = {};
public:
template<typename T>
inline bool operator[](const T ind) const{
return band[div8(ind)]&fill[mod8(ind)];
}
template<typename T>
inline void store_high(const T ind){
band[div8(ind)] |= fill[mod8(ind)];
}
template<typename T>
inline void store_low(const T ind){
band[div8(ind)] &= clear[mod8(ind)];
}
bitset(){
for(uint8_t ii = 0, val = 1; ii < 8; ++ii){
fill[ii] = val;
clear[ii] = ~fill[ii];
val*=2;
}
}
};
32位：
#define mod32(x) x&31
#define div32(x) x>>5
template<unsigned long bits>
struct bitset{
private:
uint32_t fill[32] = {};
uint32_t clear[32];
uint32_t band[(bits/32)+1] = {};
public:
template<typename T>
inline bool operator[](const T ind) const{
return band[div32(ind)]&fill[mod32(ind)];
}
template<typename T>
inline void store_high(const T ind){
band[div32(ind)] |= fill[mod32(ind)];
}
template<typename T>
inline void store_low(const T ind){
band[div32(ind)] &= clear[mod32(ind)];
}
bitset(){
for(uint32_t ii = 0, val = 1; ii < 32; ++ii){
fill[ii] = val;
clear[ii] = ~fill[ii];
val*=2;
}
}
};
这是我使用的基准（只是从位置 0 迭代地移动一个 1 直到结束）：
const int len = 1000000;
bitset<len> bs;
{
auto start = std::chrono::high_resolution_clock::now();
bs.store_high(0);
for (int ii = 1; ii < len; ++ii) {
bs.store_high(ii);
bs.store_low(ii-1);
}
auto stop = std::chrono::high_resolution_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::microseconds>((stop-start)).count()<<std::endl;
}
Isn't the common knowledge that math operations on 64bit systems run faster on 32/64 bit datatypes than the smaller datatypes like short due to implicit promotion?
这不是普遍真理。一如既往，合身取决于细节。
Why does this piece of code written using uint_8 run faster than analogous code written with uint_32 or uint_64 on a 64bit machine?
标题与问题不符。没有 uint_X 这样的类型，您也没有使用 uintX_t。您正在使用 uint_fastX_t。 uint_fastX_t 是 至少 X 字节的整数类型的别名，语言实现者认为它提供最快的操作。
如果我们将您之前提到的假设视为理所当然，那么从逻辑上讲，语言实现者会选择使用 32/64 位类型作为 uint_fast8_t。也就是说，您不能假设他们已经这样做了，并且用于做出该选择的任何通用测量（如果有的话）不一定适用于您的情况。
也就是说，无论 uint_fast8_t 是哪种类型的别名，您的测试对于比较可能不同的整数类型的相对计算速度是不公平的：
uint_fast8_t fill[8] = {};
uint_fast8_t clear[8];
uint_fast8_t band[(bits/8)+1] = {};
uint_fast32_t fill[32] = {};
uint_fast32_t clear[32];
uint_fast32_t band[(bits/32)+1] = {};
不仅类型（可能）不同，数组的大小也不同。这肯定会影响效率。
TL:DR: 位集的大“桶”意味着您在线性迭代时重复访问同一个，创建更长的依赖链，out-of-order exec 不能有效重叠.
较小的存储桶提供 instruction-level 并行性，使对单独字节中的位的操作彼此独立。
可能的原因是您对位进行线性迭代，因此同一 band[] 元素内的所有操作形成了 &= 和 |= 操作的长依赖链，加上存储并重新加载（如果编译器无法通过循环展开来优化它）。
对于 uint32_t band[]，这是一个 2x 32 操作链，因为 ii>>5 将给出相同的索引。
Out-of-order exec 只能部分重叠执行这些长链，如果它们的延迟和 instruction-count 对于 ROB（重新排序缓冲区）和 RS（保留站，又名调度程序）来说太大。 64 个操作可能包括 store/reload 延迟（在现代 x86 上为 4 或 5 个周期），这是一个深度链长度可能为 6 x 64 = 384 个周期，可能至少由 128 微指令组成，具有一些并行加载（或更好地计算）1U<<(n&31) 或 rotl(-1U, n&31) 掩码可以“用完”管道中一些浪费的执行槽。
但是对于 uint8_t band[]，你移动到一个新元素的频率是 的 4 倍，仅经过 2x 8 = 16 次操作，所以 dep 链是 1/ 4 长度。
另请参阅 imul 链，没有其他 instruction-level 并行性），特别是关于单个 dep 链变得比 RS（un-executed uops 的调度程序）更长的部分是我们开始失去一些独立工作执行重叠的点。 （针对没有lfence人为遮挡重叠的情况。）
另请参阅 现代微处理器 90 分钟指南！ 和 https://www.realworldtech.com/sandy-bridge/ 了解现代 OoO exec CPU 如何解码和查看指令的一些背景知识。
小桶与大桶
大桶仅在扫描第一个 non-zero 位或填充整个内容或其他内容时才有用 。当然，您真的希望使用 SIMD 对其进行矢量化，一次检查 16 或 32 个字节以查看其中是否存在 non-zero 元素。当前的编译器将在填充整个数组的循环中为您矢量化，但不会搜索循环（或任何无法在第一次迭代之前计算的 trip-count ），除了可以处理的 ICC。回复：在 bit-vectors 上使用快速操作，参见 Howard Hinnant's article（在 vector<bool> 的上下文中，这是 sometimes-useful 数据结构的不幸名称。）
不幸的是，C++ 通常并不能使对相同数据使用不同大小的访问变得容易，除非您使用 g++ -O3 -fno-strict-aliasing 或类似的东西进行编译。
虽然 unsigned char 总是可以为其他任何东西起别名，所以你可以将它用于你的 single-bit 访问，只使用 uintptr_t （它可能和寄存器一样宽，除了 ILP32-on-64 位 ISA）用于 init 或其他。或者在这种情况下，uint_fast32_t 在许多 x86-64 C++ 实现上是 64 位类型将使它对此有用，不像通常那样糟糕，当你只使用 [=119= 时浪费缓存空间] 的 32 位数字，在某些 CPU 上进行 non-constant 除法时速度较慢。
在 x86 CPU 上，字节存储自然是完全有效的，但即使在 ARM 或其他系统上，存储缓冲区中的合并仍然可以使相邻字节 RMW 完全有效。 (
（x86 字节加载需要使用 movzx 到 zero-extend 来避免虚假依赖，但大多数编译器都知道这一点。Clang 对此不计后果，偶尔会造成伤害。）
（彼此接近的不同大小的访问会导致 store-forwarding 停顿，例如字节存储和与该字节重叠的 unsigned long 重新加载将有额外的延迟：What are the costs of failed store-to-load forwarding on x86?）
代码审查：
在大多数 CPU 上，存储掩码数组可能比仅根据需要计算 1u32<<(n&31)) 更糟糕。如果你真的很幸运，一个聪明的编译器可能会管理从构造函数到基准循环的不断传播，并意识到它可以在循环内旋转或移位以生成位掩码，而不是在已经执行其他内存操作的循环中索引内存.
（一些非 x86 ISA 有更好的 bit-manipulation 指令，并且可以廉价地实现 1<<n，尽管如果编译器很聪明，x86 也可以在 2 条指令中做到这一点。xor eax,eax / bts eax, esi，BTS 通过 operand-size 隐含地屏蔽了移位计数。但这只适用于 32 位 operand-size，而不适用于 8 位。没有 BMI2 shlx , x86 variable-count 移动 运行 为 3英特尔 CPUs，而 AMD 为 1。）
几乎肯定不值得同时存储 fill[] 和 clear[] 常量。一些 ISA 甚至有一个 andn 指令，它不能成为动态操作数之一，即在一条指令中实现 (~x) & y。例如，具有 BMI1 扩展名的 x86 具有 andn。 (gcc -march=haswell).
此外，您的宏是不安全的：将表达式包装在 () 中，这样 operator-precedence 就不会在您使用 foo[div8(x) - 1] 时攻击您。
如 #define div8(x) (x>>3)
但实际上，无论如何您都不应该将 CPP 宏用于此类内容。即使在现代 C 中，也只需定义 static const shift = 3; 移位计数和掩码。在 C++ 中，在 struct/class 范围内执行此操作，并使用 band[idx >> shift] 或其他内容。 （当我输入 ind 时，我的手指想输入 int；idx 可能是一个更好的名字。）