0%

[笔记] Three Optimization Tips for C++

发表于 更新于

原文：Three Optimization Tips for C++

建议：
* Prefer static linking and position-dependent code (as opposed to PIC, position-independent code).
* Prefer 64-bit code and 32-bit data.
* Prefer array indexing to pointers (this one seems to reverse every ten years).
* Prefer regular memory access patterns.
* Minimize control flow.
* Avoid data dependencies.

算术操作的开销顺序：
* comparisons
* (u)int add, subtract, bitops, shift
* floating point add, sub (separate unit!)
* indexed array access (caveat: cache effects)
* (u)int32 mul
* FP mul
* FP division, remainder
* (u)int division, remainder

后面在讨论怎么加速digits10和u64ToAsciiClassic：
1. digits10：输入一个int，返回它在10进制下的位数。
    1. 优化1：循环展开，减少使用除法的次数。
    1. 优化2：手动二分。
1. u64ToAsciiClassic：一个itoa实现。这里的优化点是尽量减少写内存的次数，宁肯先读一遍，此处用到了digits10。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
uint32_t digits10(uint64_t v) {
  if (v < P01) return 1;
  if (v < P02) return 2;
  if (v < P03) return 3;
  if (v < P12) {
    if (v < P08) {
      if (v < P06) {
        if (v < P04) return 4;
        return 5 + (v >= P05);
      }
      return 7 + (v >= P07);
    }
    if (v < P10) {
      return 9 + (v >= P09);
    }
    return 11 + (v >= P11);
  }
  return 12 + digits10(v / P12);
}

unsigned u64ToAsciiTable(uint64_t value, char* dst) {
  static const char digits[201] =
    "0001020304050607080910111213141516171819"
    "2021222324252627282930313233343536373839"
    "4041424344454647484950515253545556575859"
    "6061626364656667686970717273747576777879"
    "8081828384858687888990919293949596979899";
  uint32_t const length = digits10(value);
  uint32_t next = length - 1;
  while (value >= 100) {
    auto const i = (value % 100) * 2;
    value /= 100;
    dst[next] = digits[i + 1];
    dst[next - 1] = digits[i];
    next -= 2;
  }
  // Handle last 1-2 digits
  if (value < 10) {
    dst[next] = '0' + uint32_t(value);
  } else {
    auto i = uint32_t(value) * 2;
    dst[next] = digits[i + 1];
    dst[next - 1] = digits[i];
  }
  return length;
}

评论区有人贴了两个github项目，里面是很多种digits10和itoa的实现，和benchmark：
1. https://github.com/localvoid/cxx-benchmark-count-digits
1. https://github.com/localvoid/cxx-benchmark-itoa