C++：将字节转换为无符号整型的最快方法

我有一个必须转换为整数的字节数组（unsigned char *）。整数用三个字节表示。这是我做了什么C++：将字节转换为无符号整型的最快方法

//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]++; 
}

这段代码做它的工作很好，但它是慢得令人难以置信，由于在内存中的三次访问（expecially为size_tot大值，在3000000顺序）。有没有办法更快地做到这一点，并提高性能？

来源

2016-01-02 J.kol

您确定要每次覆盖'number'，并且只有3个字节是一个整数吗？ – deviantfan

除非您在没有缓存且没有预取器的CPU上运行此代码，否则此代码不会生成大量实际内存读取。你有没有向我们展示什么？（就像你实际上不会覆盖'number'几十万次？） – Mat

而且，转换之后还需要字节数据吗？ – deviantfan

假设你想要做的所有不同值的计数（代码：intBuffer[number]++;）（具有2^24个项目intBuffer），你可以尝试做一些loop unrolling：

相反的：

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的最后部分。

结账Instruction Pipelining。

指令流水线是实现的并行称为指令级并行性的单个处理器内的形式的技术。因此它允许在给定的时钟速率下更快的CPU吞吐量（可以在一个单位时间内执行的指令的数量）。基本的指令周期被分解成一个称为管道的系列。（而不是按顺序处理每条指令（在开始下一条指令之前完成一条指令），每条指令被分成一系列步骤，因此可以并行执行不同的步骤，并且可以同时处理指令。（在完成前一个指令之前开始一条指令一）。

更新：

却是慢得令人难以置信

实际上，对于3MB这应该是有些瞬间，即使你原来的代码（考虑到数据已经被缓存）。 bytes如何定义？难道是operator[]正在做一些额外的边界检查？

来源

2016-01-02 14:12:30

你是在暗示一种循环展开？我认为这件事是通过硬件优化或编译器完成的，我不知道......我不想多说，因为我不是这个主题的专家;） –

@ J.kol - 是的，这就是我说的在我的答案:)不知道编译器会自动做到这一点，因为你每次都重复使用'数字'。你也可以用你的编译器和数据做一个快速测试。（当然也取决于CPU）。 –

@ J.kol - 但请记住，在您的代码中，您正在制作某种直方图。如果你需要所有整数的列表，你将不得不改变你的代码。（但看起来你可能正在阅读RGB值，所以直方图可能在这里有意义）。 –

首先确保编译器优化转向最高级别。

我想我会试试这个：

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]; 
}

编译我会检查所产生的汇编代码是什么样子，看看是否改实际上是由一个差异后。

来源

2016-01-02 14:28:10 4386427

正确的答案几乎都是：

写正确的代码，启用的优化，相信你的编译器。

给出：

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

答：什么 - 它只是为有效。

这课？没有真的！相信你的编译器！

来源

2016-01-02 14:42:53

我认为你的答案基本上是正确的，但“相信你的编译器”正在夸大一点。虽然这很少见，但我发现很多情况下，一些非直接的代码比直接的代码更快。 “不要以为你可以做技巧来提高性能”。 –

@VaughnCato我听说过你，当然在30年的写作代码中，我有时也必须手工编写代码。但其中大部分时间都在15年以前。现在这是最后的选择 - 当选择正确的算法，优雅和正确地实现时，没有其他可能的性能瓶颈（如I/O，缓存未命中，错过了并行化机会等等）。），并且用户仍然告诉我该程序很慢......只有这样才可以推出套件并预测编译器。如果我们不需要，为什么要支付自定义代码的维护成本？ –

“_Trust your compiler !!! _” - 同意，但由于我遇到'uint var/2'比'uint var >> 1'（几年前）慢，我失去了一点信心。在编译器变得越来越好的时候，有时我们可能会尝试并帮助他们（在某些情况下，编译器甚至不允许优化某些部分）。 –

尝试一次读取4或8个字节，然后合并字节以获得所需的值。无论这是否更快或者不需要基准测试。

这将适用于大端架构。对于little-endian的，必须改变一些算术，并且必须使用反向的字节顺序。

unsigned char *bp = bytes; 

while ((uintptr_t)bp % 4) // make sure that the pointer is properly aligned 
{ 
    num = (bp[0] << 16) | (bp[1] << 8) | bp[2]; 
    intBuffer[num]++; 
    bp += 3; 
} 

unsigned int num1, num2, num3; 
unsigned int* ip = (unsigned int*)b; 
while (ip+12 < bytes+size_tot) 
{ 
    num1 = *ip++; 
    num2 = *ip++; 
    num3 = *ip++; 

    intBuffer[num1 >> 8]++; 
    intBuffer[((num1 & 0xFF) << 16) | (num2 >> 16)]++; 
    intBuffer[((num2 & 0xFFFF) << 8) | (num3 >> 24)]++; 
    intBuffer[num3 & 0xFFFFFF]++; 
} 

bp = (unsigned char*)ip; 
while (bp < bytes+size_tot) 
{ 
    num = (bp[0] << 16) | (bp[1] << 8) | bp[2]; 
    intBuffer[num]++; 
    bp += 3; 
}

来源

2016-01-02 15:48:31

modulo on pointers ?! – curiousguy

@curiousguy没有注意到 –

@LưuVĩnhPhúc在一个未发现的指针上，这可能是一个编译器错误。在这里，代替'％4'，'＆3'应该比任何地方更快（呃，也许你的编译器优化已经做到了） – deviantfan

C++：将字节转换为无符号整型的最快方法

回答

相关问题