UP | HOME

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问题;

2.3 CPU and Register Level Optimization