lean tricks
这里记录一下一些简短有效的代码，值得参考。
计算对齐
template<typename U> static inline char* align_for(char* ptr) { const std::size_t alignment = std::alignment_of<U>::value; return ptr + (alignment - (reinterpret_cast<std::uintptr_t>(ptr) % alignment)) % alignment; }
获得最接近且不小于当前数的二次幂
这个是获得比最小的不小于x的\(2^n\) 。
template<typename T> static inline T ceil_to_pow_2(T x) { static_assert(std::is_integral<T>::value && !std::numeric_limits<T>::is_signed, "ceil_to_pow_2 is intended to be used only with unsigned integer types"); // Adapted from http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 --x; x |= x >> 1; x |= x >> 2; x |= x >> 4; for (std::size_t i = 1; i < sizeof(T); i <<= 1) { x |= x >> (i << 3); } ++x; return x; }
三个数获得最小值或最大值
避免判断分支的stall，于是直接用标志位来计算了。出处见pbrt。
int a[3]; int bits = ((a[0] < a[1]) << 2) + ((a[0] < a[2]) << 1) + (a[1] < a[2] const int smallest[8] = [2, 1, 2, 1, 2, 2, 0, 0] int smallest_v = a[smallest[bits]] int bits = ((a[0] > a[1]) << 2) + ((a[0] > a[2]) << 1) + (a[1] > a[2] const int biggest[8] = [2, 1, 2, 1, 2, 2, 0, 0] int biggest_v = a[biggest[bits]]
整数常量除法优化
Intel Haswell 架构的 DIV 32位除法指令的延迟（latency）是 28 个周期，吞吐率是 10 个周期。作为比较，同一架构下 MUL 32位乘法指令的延迟只是 4 个周期，吞吐率只是半个周期。所以对于常见的除以10的计算更好的方法是转化为乘法。
int a = 3728463; int b = a/10; int64_t c = 3435973837; int d = static_cast<int32_t>((static_cast<int64_t>(a) * c)>>35) assert( b == d)
这里的b == d之所以会成立是因为c>>35 = 0.10000000058 ，在精度范围内没有误差。编译器内部维护了很多小整数的除法优化表，对于常量整数的除法都可以转换为64位乘法然后右移的方式。所以下面的这段代码的两个除法热点就可以被优化了：
uint32_t p1 = /*...*/; int kappa = 10; uint32_t div = 1000000000; while (kappa > 0) { d = p1 / div; // 第一个除法 if (d || *len) buffer[(*len)++] = static_cast<char>('0' + static_cast<char>(d)); p1 %= div; kappa--; div /= 10; // 第二个除法 // ... }
这里的div并不是常量，在循环过程中会变，转化为常量之后就可以很大程度的提高性能。
while (kappa > 0) { uint32_t d = 0; switch (kappa) { case 9: d = p1 / 100000000; p1 %= 100000000; break; case 8: d = p1 / 10000000; p1 %= 10000000; break; case 7: d = p1 / 1000000; p1 %= 1000000; break; case 6: d = p1 / 100000; p1 %= 100000; break; case 5: d = p1 / 10000; p1 %= 10000; break; case 4: d = p1 / 1000; p1 %= 1000; break; case 3: d = p1 / 100; p1 %= 100; break; case 2: d = p1 / 10; p1 %= 10; break; case 1: d = p1; p1 = 0; break; default:; } if (d || *len) buffer[(*len)++] = static_cast<char>('0' + static_cast<char>(d)); kappa--; // ... }
这里不需要担心case里的两个除法，现代的编译器针对取模运算和除法运算右边的数相同时，会优化为一条指令。相关资料来自于Milo 的blog
utf8的parse优化
utf8 的字节编码是变长的，实际使用过程中经常需要parse之后转变为定长的来处理。这里的热点就是扫描分割边长编码， 这里我们为了简单起见只处理最长为4字节的变长编码。最简单的实现是这样的：
vector<uint32_t> utf8_to_uint(const string& text) const { unsigned char u, v, w, x, y, z; vector<uint32_t> utf8_result; int num_chars = 0; uint32_t num_bytes = text.length(); long iii = 0; while (iii < num_bytes) { uint32_t cur_utf8_char = 0; z = text[iii]; if (z <= 127) { cur_utf8_char = z; } if (z >= 192 && z <= 223) { iii++; y = text[iii]; cur_utf8_char = (z - 192) * 64 + (y - 128); } if (z >= 224 && z <= 239) { iii++; y = text[iii]; iii++; x = text[iii]; cur_utf8_char = (z - 224) * 4096 + (y - 128) * 64 + (x - 128); } if ((240 <= z) { iii++; y = text[iii]; iii++; x = text[iii]; iii++; w = text[iii]; cur_utf8_char = (z - 240) * 262144 + (y - 128) * 4096 + (x - 128) * 64 + (w - 128); } utf8_result.push_back(cur_utf8_char); iii++; } return utf8_result; }
下面有一些比较好的代码可以参考：
do { c = pStr[0]; if (globals::s_parse_flags[c] & 1) { ++pStr; break; } c = pStr[1]; if (globals::s_parse_flags[c] & 1) { pStr += 2; break; } c = pStr[2]; if (globals::s_parse_flags[c] & 1) { pStr += 3; break; } c = pStr[3]; pStr += 4; } while (!(globals::s_parse_flags[c] & 1));
这段代码粗看起来很诡异，事实上他利用了循环展开，直接让cpu有了一次性装载四个字节并判断的能力。对于第一个版本的改动就是对z <= 127进行循环展开，也试图判断四个字节。
空白字符的parse优化
在很多lex程序中都需要跳过空白字符，例如\t \n \r这四个。简单的实现会涉及到很多的branch，例如下面的代码:
template<typename InputStream> void SkipWhitespace(InputStream& is) { internal::StreamLocalCopy<InputStream> copy(is); InputStream& s(copy.s); while (s.Peek() == ' ' || s.Peek() == '\n' || s.Peek() == '\r' || s.Peek() == '\t') { s.Take(); } }
此时可以利用intel sse4.2 pcmpistrm指令来加速比较，这个指令可以一次对一组16个字符与另外一组字符做比较，最多支持1616， 虽然对于空白字符来说我们只有16 4, 不过也算加速很大了。具体实现如下:
inline const char *SkipWhitespace_SIMD(const char* p) { // ... 非对齐处理 static const char whitespace[16] = " \n\r\t"; const __m128i w = _mm_load_si128((const __m128i *)&whitespace[0]); for (;; p += 16) { const __m128i s = _mm_load_si128((const __m128i *)p); const unsigned r = _mm_cvtsi128_si32(_mm_cmpistrm(w, s, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ANY | _SIDD_BIT_MASK | _SIDD_NEGATIVE_POLARITY)); if (r != 0) { // some of characters is non-whitespace #ifdef _MSC_VER // Find the index of first non-whitespace unsigned long offset; _BitScanForward(&offset, r); return p + offset; #else return p + __builtin_ffs(r) - 1; #endif }
这里还有一个可以优化的地方，就是第一个字符串已经是非空白字符了，此时再去调用sse其实消耗很大，所以可以优化第一个字节的判断：
inline const char *SkipWhitespace_SIMD(const char* p) { // Fast return for single non-whitespace if (*p == ' ' || *p == '\n' || *p == '\r' || *p == '\t') ++p; else return p; // ... }
获取一个整数10进制字符数量
核心思想是生成二进制位对应的表，然后根据这个数字的leading zero count 来读表判断多少位。
array<array<uint64_t, 2>, 64> generate_delimit() // 生成分隔数组 { array<array<uint64_t, 2>, 64> result = {}; int _pre = 1; uint64_t temp_2 = 0; uint64_t temp_10 = 10; for (int i = 0; i < 64; i++) { temp_2 = (temp_2 << 1) + 1; uint64_t current_bit = ceil(log10(temp_2)); if (current_bit <= _pre) { result[i][0] = temp_2; result[i][1] = _pre; } else { result[i][0] = temp_10 - 1; result[i][1] = _pre; _pre = current_bit; temp_10 = temp_10 * 10; } } return result; }; uint32_t digits10(uint64_t v) { const static array<array<uint64_t, 2>, 64> bit_table = generate_delimit(); if (v == 0) { return 1; } auto cur_index = 63 - __lzcnt64(v);// 这行指令是msvc特有的 其他平台的名字不同 return bit_table[cur_index][1] + (v > bit_table[cur_index][0]); }