將9個字符數字轉換為int或unsignedint的最瘋狂最快的方法

#include <stdio.h>
#include <iostream>
#include <string>
#include <chrono>
using namespace std;

const int p[9] =   {1, 10, 100, 
                    1000, 10000, 100000, 
                    1000000, 10000000, 100000000};
                    
class MyTimer {
 private:
  std::chrono::time_point<std::chrono::steady_clock> starter;
  std::chrono::time_point<std::chrono::steady_clock> ender;

 public:
  void startCounter() {
    starter = std::chrono::steady_clock::now();
  }

  double getCounter() {
    ender = std::chrono::steady_clock::now();
    return double(std::chrono::duration_cast<std::chrono::nanoseconds>(ender - starter).count()) /
           1000000;  // millisecond output
  }
};
                    
int convert1(char *a) {
    int res = 0;
    for (int i=0; i<9; i  ) res = res * 10   a[i] - 48;
    return res;
}

int convert2(char *a) {
    return (a[0] - 48) * p[8]   (a[1] - 48) * p[7]   (a[2] - 48) * p[6]
              (a[3] - 48) * p[5]   (a[4] - 48) * p[4]   (a[5] - 48) * p[3]
              (a[6] - 48) * p[2]   (a[7] - 48) * p[1]   (a[8] - 48) * p[0];
}

int convert3(char *a) {
    return (a[0] - 48) * p[8]   a[1] * p[7]   a[2] * p[6]   a[3] * p[5]
              a[4] * p[4]   a[5] * p[3]   a[6] * p[2]   a[7] * p[1]   a[8]
            - 533333328;
}

const unsigned pu[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
    100000000};

int convert4u(char *aa) {
  const unsigned char *a = (const unsigned char*) aa;
  return a[0] * pu[8]   a[1] * pu[7]   a[2] * pu[6]   a[3] * pu[5]   a[4] * pu[4]
        a[5] * pu[3]   a[6] * pu[2]   a[7] * pu[1]   a[8] - (unsigned) 5333333328u;
}

int convert5(char* a) {
    int val = 0;
    for(size_t k =0;k <9;  k) {
        val = (val << 3)   (val << 1)   (a[k]-'0');
    }
    return val;
}

const unsigned pu2[9] = {100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};

int convert6u(char *a) {
  return a[0]*pu2[0]   a[1]*pu2[1]   a[2]*pu2[2]   a[3] * pu2[3]   a[4] * pu2[4]   a[5] * pu2[5]   a[6] * pu2[6]   a[7] * pu2[7]   a[8] - (unsigned) 5333333328u;
}

using ConvertFunc = int(char*);    

volatile int result = 0; // do something with the result of function to prevent unexpected optimization
void benchmark(ConvertFunc converter, string name, int numTest=10000) {
    MyTimer timer;
    const int N = 100000;
    char *a = new char[9*N   1];
    double runtime = 0;
    
    for (int t=1; t<=numTest; t  ) {        
        // change something to prevent unexpected optimization
        for (int i=0; i<9*N; i  ) a[i] = rand() % 10   '0'; 

        timer.startCounter();
        for (int i=0; i<9*N; i = 9) result = converter(a i);
        runtime  = timer.getCounter();
    }
    cout << name << ": " << runtime << "ms\n";
}   

int main() {        
    benchmark(convert1, "slow");
    benchmark(convert2, "normal");    
    benchmark(convert3, "fast");
    benchmark(convert4u, "unsigned");
    benchmark(convert5, "shifting");
    benchmark(convert6u, "reverse");
    return 0;
}

我想找到最快的方式轉char a[9]成int。完整的問題是將char a[15]格式 HHMMSSxxxxxxxxx 時間戳轉換為納秒，其中x分配了大約 50 個位元組后可以安全讀取（但不能寫入）。我們只關心這個問題的最后 9 位數字。

版本 1 是基本的，版本 2,3 嘗試節省一些計算。我使用 -O3 標志進行編譯，并且在陣列中存盤 10s 的冪很好，因為它被優化掉了（使用 Godbolt 檢查）。

我怎樣才能讓它更快？是的，我知道這聽起來像是過早的優化，但讓我們假設我需要最后 2-3% 的提升。

版本 3 明顯更快，而版本 2 由于代碼大小而較慢。但是我們能比版本 3 做得更好嗎？無效的基準

編輯 2：該函式可以回傳unsigned int而不是int（即

unsigned convert1(char *a);

編輯 3：我注意到新代碼是一個無效的基準，因為convert(a)只執行一次。使用原始代碼，差異僅為~1%。

編輯 4：新基準。使用 unsigned (convert4u, convert6u) 始終比使用 int 快 3-5%。我將運行一個長時間（10 分鐘以上）的基準測驗，看看是否有贏家。我已經編輯了代碼以使用新的基準測驗。它生成大量資料，然后運行轉換器功能。

編輯 5：結果：4.19, 4.51, 3.82, 3.59, 7.64, 3.72秒。未簽名的版本最快。是否可以僅在 9 個位元組上使用 SIMD？如果沒有，那么我想這是最好的解決方案。我仍然希望有一個更瘋狂的解決方案

uj5u.com熱心網友回復：

替代候選人

使用unsigned數學來避免 UBint溢位并允許將所有內容- 48取出然后放入一個常量中。

const unsigned p[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
    100000000};

int convert4u(const char *aa) {
  const unsigned char *a = (const unsigned char*) aa;
  return a[0] * p[8]   a[1] * p[7]   a[2] * p[6]   a[3] * p[5]   a[4] * p[4]
        a[5] * p[3]   a[6] * p[2]   a[7] * p[1]   a[8] - (unsigned) 5333333328u;
}

也許也可以嘗試p[9]像a[]. 也許更容易并行計算。我認為重新訂購沒有任何不利之處。也許是一個好處，也許不是。

const unsigned p[9] = {100000000, 10000000, ..., 1};

int convert4u(const char *aa) {
  const unsigned char *a = (const unsigned char*) aa;
  return a[0]*p[0]   a[1]*p[1] ... a[1]*p[1]   a[8] - (unsigned) 5333333328u;
}

標籤：C 数学 部件 优化 x86-64

上一篇：GOLANG解組動態JSON

下一篇：找出填充魔方的多種方法