How To Write Numerical Code
目录
1 Performance Optimization: The basics
1.1 Floating The Hotspots
- gprof
#include <stdio.h> float func1() { int i; float ret = 0; for (i = 0; i < 1000000; ++i) { ret += (1/i); } return ret; } float func2() { int i; float ret = 0; for (i = 0; i < 1000000; ++i) { ret += (1/(i + 1)); } return ret; } void func3() { } int main() { int i; printf("result: %.2f\n", func1()); printf("result: %.2f\n", func2()); func3(); return 0; }
Compile:
~$ gcc -O0 -g -pg -o hotspot hotspot.c ~$ gprof hotspot gmon.out Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls ms/call ms/call name 101.01 0.03 0.03 1 30.30 30.30 func2 0.00 0.03 0.00 1 0.00 0.00 func1 0.00 0.03 0.00 1 0.00 0.00 func3
1.2 Timing a Hotspot
1.2.1 Known Problems
- 指令太少时,时钟精度导致时间评估不准确;
- 指令太多,因系统事件(调度),导致时间评估不准确;
- 设备负载导致的边界效应;
- 任务并发导致互相影响;
- 输入输出数据对齐导致的缓存问题;
- 虚拟到物理内存翻译时间不可抑制;
- TSC溢出触发一个终端或产生无意义的结果;
- 读取TSC需要一定的cycles,这影响时间结果;
- 链接顺序导致本地静态常量变化导致缓存干扰;
- 设备长期运行导致的OS状态问题;
- 数字内核的控制流数据会被评估时间,但测试数据不具代表性;
- OS聪明处理“全零页”,导致更高的性能;
1.3 Analyzing the Measured Runtime
1.4 Exercises
2 Optimization for the Memory Hierarchy
2.1 Performance-Conscious Programming
使用C | 不用C++(面向对象的)或Java(字节码的) |
Arrays | 尽量使用一维的,或者编译器能确定大小的 |
Records | 避免复杂的struct和union,编译器无法处理最优的对齐 |
Dynamic data structures | 避免指针链表,多用数组 |
Control Flow | 减少分支,如while, for, switch, if |
2.2 Cache Optimization
- Blocking: data in chunks fit respective cache level;
- Loop Merging(循环归并,循环合并): 连续循环合并
- Buffering: 拷贝数据到连续缓冲区,客服缓存miss问题;