unsigned char *我有一个必须转换为整数的字节数组（ ）。整数用三个字节表示。这就是我所做的
//bytes array is allocated and filled
//allocating space for intBuffer (uint32_t)
unsigned long i = 0;
uint32_t number;
for(; i<size_tot; i+=3){
uint32_t number = (bytes[i]<<16) | (bytes[i+1]<<8) | bytes[i+2];
intBuffer[number]++;
}
这段代码很好地完成了它的工作，但是由于内存中的三个访问（特别是对于大的值size_tot，按顺序3000000），它非常慢。有没有办法更快地做到这一点并提高性能？
正确答案几乎总是：
编写正确的代码，启用优化，相信你的编译器。
给定：
void count_values(std::array<uint32_t, 256^3>& results,
const unsigned char* from,
const unsigned char* to)
{
for(; from != to; from = std::next(from, 3)) {
++results[(*from << 16) | (*std::next(from, 1) << 8) | *(std::next(from,2))];
}
}
编译-O3
产量（内嵌解释性评论）：
__Z12count_valuesRNSt3__15arrayIjLm259EEEPKhS4_: ## @_Z12count_valuesRNSt3__15arrayIjLm259EEEPKhS4_
.cfi_startproc
## BB#0:
pushq %rbp
Ltmp0:
.cfi_def_cfa_offset 16
Ltmp1:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Ltmp2:
.cfi_def_cfa_register %rbp
jmp LBB0_2
.align 4, 0x90
LBB0_1: ## %.lr.ph
## in Loop: Header=BB0_2 Depth=1
# dereference from and extend the 8-bit value to 32 bits
movzbl (%rsi), %eax
shlq $16, %rax # shift left 16
movzbl 1(%rsi), %ecx # dereference *(from+1) and extend to 32bits by padding with zeros
shlq $8, %rcx # shift left 8
orq %rax, %rcx # or into above result
movzbl 2(%rsi), %eax # dreference *(from+2) and extend to 32bits
orq %rcx, %rax # or into above result
incl (%rdi,%rax,4) # increment the correct counter
addq $3, %rsi # from += 3
LBB0_2: ## %.lr.ph
## =>This Inner Loop Header: Depth=1
cmpq %rdx, %rsi # while from != to
jne LBB0_1
## BB#3: ## %._crit_edge
popq %rbp
retq
.cfi_endproc
请注意，没有必要偏离标准构造或标准调用。编译器产生完美的代码。
为了进一步证明这一点，让我们疯狂地编写一个自定义迭代器，允许我们将函数简化为：
void count_values(std::array<uint32_t, 256^3>& results,
byte_triple_iterator from,
byte_triple_iterator to)
{
assert(iterators_correct(from, to));
while(from != to) {
++results[*from++];
}
}
这是这样一个迭代器的（基本）实现：
struct byte_triple_iterator
{
constexpr byte_triple_iterator(const std::uint8_t* p)
: _ptr(p)
{}
std::uint32_t operator*() const noexcept {
return (*_ptr << 16) | (*std::next(_ptr, 1) << 8) | *(std::next(_ptr,2));
}
byte_triple_iterator& operator++() noexcept {
_ptr = std::next(_ptr, 3);
return *this;
}
byte_triple_iterator operator++(int) noexcept {
auto copy = *this;
_ptr = std::next(_ptr, 3);
return copy;
}
constexpr const std::uint8_t* byte_ptr() const {
return _ptr;
}
private:
friend bool operator<(const byte_triple_iterator& from, const byte_triple_iterator& to)
{
return from._ptr < to._ptr;
}
friend bool operator==(const byte_triple_iterator& from, const byte_triple_iterator& to)
{
return from._ptr == to._ptr;
}
friend bool operator!=(const byte_triple_iterator& from, const byte_triple_iterator& to)
{
return not(from == to);
}
friend std::ptrdiff_t byte_difference(const byte_triple_iterator& from, const byte_triple_iterator& to)
{
return to._ptr - from._ptr;
}
const std::uint8_t* _ptr;
};
bool iterators_correct(const byte_triple_iterator& from,
const byte_triple_iterator& to)
{
if (not(from < to))
return false;
auto dist = to.byte_ptr() - from.byte_ptr();
return dist % 3 == 0;
}
现在我们有什么？
但是它对我们的目标代码做了什么？（用 编译-O3 -DNDEBUG）
.globl __Z12count_valuesRNSt3__15arrayIjLm259EEE20byte_triple_iteratorS3_
.align 4, 0x90
__Z12count_valuesRNSt3__15arrayIjLm259EEE20byte_triple_iteratorS3_: ## @_Z12count_valuesRNSt3__15arrayIjLm259EEE20byte_triple_iteratorS3_
.cfi_startproc
## BB#0:
pushq %rbp
Ltmp3:
.cfi_def_cfa_offset 16
Ltmp4:
.cfi_offset %rbp, -16
movq %rsp, %rbp
Ltmp5:
.cfi_def_cfa_register %rbp
jmp LBB1_2
.align 4, 0x90
LBB1_1: ## %.lr.ph
## in Loop: Header=BB1_2 Depth=1
movzbl (%rsi), %eax
shlq $16, %rax
movzbl 1(%rsi), %ecx
shlq $8, %rcx
orq %rax, %rcx
movzbl 2(%rsi), %eax
orq %rcx, %rax
incl (%rdi,%rax,4)
addq $3, %rsi
LBB1_2: ## %.lr.ph
## =>This Inner Loop Header: Depth=1
cmpq %rdx, %rsi
jne LBB1_1
## BB#3: ## %._crit_edge
popq %rbp
retq
.cfi_endproc
答案：什么都没有——它同样有效。
课程？真的没有！相信你的编译器！！！
假设您想要计算所有不同的值（您的代码：intBuffer[number]++;）（intBuffer 有 2^24 个项目），您可以尝试做一些循环展开：
代替：
for(; i<size_tot; i+=3){
uint32_t number = (bytes[i]<<16) | (bytes[i+1]<<8) | bytes[i+2];
intBuffer[number]++;
}
做：
for(; i<size_tot; i+=12){ // add extra ckeck here..
intBuffer[(bytes[i]<<16) | (bytes[i+1]<<8) | bytes[i+2]]++;
intBuffer[(bytes[i+3]<<16) | (bytes[i+4]<<8) | bytes[i+5]]++;
intBuffer[(bytes[i+6]<<16) | (bytes[i+7]<<8) | bytes[i+8]]++;
intBuffer[(bytes[i+9]<<16) | (bytes[i+10]<<8) | bytes[i+11]]++;
}
// Add a small loop for the remaining bytes (no multiple of 12)
这将允许 cpu在一个时钟周期内执行多条指令（确保将编译器优化设置为最高级别）。
您还需要额外检查bytes.
查看指令流水线。
指令流水线是一种在单个处理器内实现称为指令级并行性的并行性形式的技术。因此，它允许比在给定时钟速率下可能实现的更快的 CPU 吞吐量（单位时间内可以执行的指令数）。基本指令周期被分解成一系列称为流水线的序列。不是按顺序处理每条指令（在开始下一条指令之前完成一条指令），而是将每条指令分成一系列步骤，以便可以并行执行不同的步骤并且可以同时处理指令（在完成前一条指令之前开始一条指令） .
更新：
但速度非常慢
实际上，对于 3MB，这应该是即时的，即使使用您的原始代码（考虑到数据已经缓存）。如何bytes定义？会不会operator[]是在做一些额外的边界检查？
尝试一次读取一个单词，然后提取所需的值。这应该比逐字节读取更有效
这是 64 位 little-endian 系统上的示例实现，它将一次读取 3 个 64 位值
void count(uint8_t* bytes, int* intBuffer, uint32_t size_tot)
{
assert(size_tot > 7);
uint64_t num1, num2, num3;
uint8_t *bp = bytes;
while ((uintptr_t)bp % 8) // make sure that the pointer is properly aligned
{
num1 = (bp[2] << 16) | (bp[1] << 8) | bp[0];
intBuffer[num1]++;
bp += 3;
}
uint64_t* ip = (uint64_t*)bp;
while ((uint8_t*)(ip + 2) < bytes + size_tot)
{
num1 = *ip++;
num2 = *ip++;
num3 = *ip++;
intBuffer[num1 & 0xFFFFFF]++;
intBuffer[(num1 >> 24) & 0xFFFFFF]++;
intBuffer[(num1 >> 48) | ((num2 & 0xFF) << 16)]++;
intBuffer[(num2 >> 8) & 0xFFFFFF]++;
intBuffer[(num2 >> 32) & 0xFFFFFF]++;
intBuffer[(num2 >> 56) | ((num3 & 0xFFFF) << 8)]++;
intBuffer[(num3 >> 16) & 0xFFFFFF]++;
intBuffer[num3 >> 40]++;
}
bp = (uint8_t*)ip;
while (bp < bytes + size_tot)
{
num1 = (bp[2] << 16) | (bp[1] << 8) | bp[0];
intBuffer[num1]++;
bp += 3;
}
}
您可以在Compiler Explorer上检查编译器输出。当然，聪明的编译器可能已经知道如何做到这一点，但大多数都不知道。正如您从 Godbolt 链接中看到的那样，编译器将使用一堆movzx来读取单独的字节，而不是读取整个寄存器。ICC 会做更多的循环展开，但 Clang 和 GCC 不会
类似地，对于 32 位架构，您还将在每次迭代中读取 3 个“单词”。此外，您可能需要进行一些手动循环展开，而不是依赖编译器来执行此操作。这是 32 位小端机器上的示例。它可以很容易地适应这样的大端
intBuffer[num1 >> 8]++;
intBuffer[((num1 & 0xFF) << 16) | (num2 >> 16)]++;
intBuffer[((num2 & 0xFFFF) << 8) | (num3 >> 24)]++;
intBuffer[num3 & 0xFFFFFF]++;
但为了获得更高的性能，您可能需要寻求 SSE 或 AVX 等 SIMD 解决方案
首先确保将编译器优化调到最高级别。
我想我会试试这个：
unsigned char* pBytes = bytes;
uint32_t number;
for(unsigned long i = 0; i<size_tot; i+=3){
number = *pBytes << 16;
++pBytes;
number = number | (*pBytes << 8);
++pBytes;
number = number | *pBytes;
++pBytes;
++intBuffer[number];
}
编译后，我会检查生成的汇编代码的外观，看看更改是否真的产生了影响。