核心系统数据库组 褚霸(余锋) http://blog.yufeng.info 2013-5-7 CPU高效编程技术 核心系统数据库组 褚霸(余锋) http://blog.yufeng.info 2013-5-7

微处理器的核心技术 流水线处理 运算器高速化 RISC和CISC 超标量执行 乱序执行 分支预测 缓存 多核心

了解处理器Nehalem E5620 长流水线 >= 15级 X86指令解释为微指令后乱序执行 等待执行的微指令放在Reserveration Station 多个ALU运算单元并发、乱序执行 Reorder Buffer中实现串行化 Instruction Retirement

Pipeline 示例：4级和8级的流水线

Intel的长流水线

Front End 读入x86指令， 每个时钟周期 16字节 x86指令解析为微指令（μop） 微指令（μop）缓存

乱序执行-1 寄存器重命名 分配临时寄存器 微指令进入保留站 发射指令 EU EU EU 各种运算 Load/Store

乱序执行-2 按指令顺序写出结果 指令生效，真正写入 内存和物理寄存器 存入临时寄存器 触发具有数据依赖的指令执行 EU中计算结果 Load/Store

指令量化分析 取指令，每个16字节/cycle X86指令解析为微指令 保留站到EU的Port，总共6个 简单指令3条/cycle P0，P1，P5到ALU单元 P2，P3，P4到Load/Store单元 Instruction Retirement，4条μop/cycle Dependency Chain长度

指令优化 长流水线 >= 15级 充分发挥Intel处理器乱序执行的能力 Branch prediction miss性能损耗大 减少/消除conditional branch Bit运算代替比较 Comvg指令代替比较 充分发挥Intel处理器乱序执行的能力 避免指令间存在long dependency chain 避免指令间隐性的依赖关系，例如对eflags的依赖

CPU内部各部件访问速度

充分利用寄存器 # define LZ4_COPYSTEP(s,d) A64(d) = A64(s); d+=8; s+=8; # define LZ4_COPYPACKET(s,d) LZ4_COPYSTEP(s,d) #define LZ4_WILDCOPY(s,d,e) do { LZ4_COPYPACKET(s,d) } while (d<e);

位运算 int r; if (!(val>>32)) { r=4; } else { r=0; val>>=32; } if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } r += (!val); return r;

并行执行 *op++ = *ref++;

消除Conditional Branch 如何消除这个if语句 if (a < b) { r = c; } else { r = d; Bit运算版本1 int mask = (a-b) >> 31; r = (mask & c) | (~mask & d); Bit运算版本2 r = d + mask & (c-d); cmovg版本 r = (a < b) ？c : d;

分支可能性提示 #define likely(expr) expect((expr) != 0, 1) #define unlikely(expr) expect((expr) != 0, 0) while likely(ip<matchlimit-(STEPSIZE-1)) { … }

The Blocking Technique

The Blocking Technique // Increasing memory usage improves compression ratio // Reduced memory usage can improve speed, due to cache effect // Default value is 14, for 16KB, which nicely fits into Intel x86 L1 cache #define MEMORY_USAGE 14 #define HASH_LOG (MEMORY_USAGE-2) #define HASHTABLESIZE (1 << HASH_LOG) struct refTables { HTYPE hashTable[HASHTABLESIZE]; };

memchr magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff; /* Set up a longword, each of whose bytes is C. */ charmask = c | (c << 8); charmask |= charmask << 16; charmask |= charmask << 32; /* Instead of the traditional loop which tests each character, we will test a longword at a time. The tricky part is testing if *any of the four* bytes in the longword in question are zero. */ while (n >= sizeof (longword)) { longword = *longword_ptr++ ^ charmask; if ((((longword + magic_bits) & ~magic_bits) != 0) … }

memchr续 { const unsigned char *cp = (const unsigned char *) (longword_ptr - 1); if (cp[0] == c) return (__ptr_t) cp; ... if (cp[7] == c) return (__ptr_t) &cp[7]; } n -= sizeof (longword);

False sharing

对齐cacheline typedef union { GFAllctr_t gfa; char align_gfa[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(GFAllctr_t))]; } ErtsAllocatorState_t; char *states = erts_sys_alloc(0, … + ERTS_CACHE_LINE_SIZE - 1)); states = ((((UWord) states) & ERTS_CACHE_LINE_MASK) ? (char *) ((((UWord) states) & ~ERTS_CACHE_LINE_MASK) + ERTS_CACHE_LINE_SIZE) : (char *) states);

perf list RAW HARDWARE EVENT DESCRIPTOR Even when an event is not available in a symbolic form within perf right now, it can be encoded in a per processor specific way. For instance For x86 CPUs NNN represents the raw register encoding with the layout of IA32_PERFEVTSELx MSRs (see [Intel(R) 64 and IA-32 Architectures Software Developer's Manual Volume 3B: System Programming Guide] Figure 30-1 Layout of IA32_PERFEVTSELx MSRs) or AMD's PerfEvtSeln (see [AMD64 Architecture Programmer's Manual Volume 2: System Programming], Page 344, Figure 13-7 Performance Event-Select Register (PerfEvtSeln)).

致谢 部分图片和代码来自鸣嵩 《treelink比赛分享》

Gtalk: mryufeng@gmail.com 多谢大家! Questions？ QQ:526275 新浪微博:@淘宝褚霸 Gtalk: mryufeng@gmail.com