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++：將字節轉換爲無符號整型的最快方法

回答

相關問題