Time it

在使用profiling之类的工具之前,更灵活简单的方式就是设置timer

concepts about time and performance

CPU bound vs IO bound

参考这里的解释,比较直接,或者说整个系统的bottleneck在哪里。

A program is CPU bound if it would go faster if the CPU were faster, i.e. it spends the majority of its time simply using the CPU (doing calculations). A program that computes new digits of π will typically be CPU-bound, it’s just crunching numbers.

解决cpu bound的问题一方面是优化算法本身,另一方面是采用并行算法。

A program is I/O bound if it would go faster if the I/O subsystem was faster. Which exact I/O system is meant can vary; I typically associate it with disk, but of course networking or communication in general is common too. A program that looks through a huge file for some data might become I/O bound, since the bottleneck is then the reading of the data from disk (actually, this example is perhaps kind of old-fashioned these days with hundreds of MB/s coming in from SSDs).

注意因为使用了memory hierachy,除了disk IO之外还有memory,cache,涉及到具体优化的时候除了提升本身hardware的IO性能在算法层面就是合理地利用memory hierachy,更多的细节可以参wiki cache oblivious algorithm

the goal of the optimizaiton is to change the CPU bound program into the IO bound program.

real time(wall time) vs user time vs sys time

Elapsed real time, real time, wall-clock time, or wall time is the actual time taken from the start of a computer program to the end (wall time 与 real time实际代表同样的含义). on linux,there is a command called time,use time <executable>可以得到sys,user,real time。一般说的cpu time 更多指的是cpu所花在这个程序上的时间,这里要注意用词的准确性,有几次把cpu time与wall time给弄混了。

real time就是实际的时间,比如一个program从1:00开始运行,到2:00结束,这个process的real time就是1h,但是在这个1h的时间中,可能这个程序并没有一直在cpu上运行,比如可能是0.5h在cpu上运行,另外0.5小时在sleep,这个时候就cpu time实际上就不是1h。user time 表示在用户态所花的时间,sys time 表示cpu在内核状态下所花费的时间。比如下面这个case:

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
//do some io operation
sleep(1.0);
return 0;
}

/*
real 0m1.011s
user 0m0.001s
sys 0m0.002s
*/

real time 花费掉了1s,然后user和sys很少,并且user和sys的总和也远小于real,这说明虽然程序从开始运行到结束是1s,但cpu的占用率在这个程序运行的这段时间还是比较低(0.003s in total)。

c中的timer方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//sample code
#include <time.h>
#include <stdio.h>
#include <unistd.h>
#define BILLION 1000000000L

int main()
{
struct timespec start, end;
double diff;
clock_gettime(CLOCK_REALTIME, &start); /* mark start time */
sleep(1.0);
//some functions here
clock_gettime(CLOCK_REALTIME, &end); /* mark end time */
diff = (end.tv_sec - start.tv_sec) * 1.0 + (end.tv_nsec - start.tv_nsec) * 1.0 / BILLION;
printf("time is %lf seconds \n", diff);
}

python 中的timer就和strightforware

1
2
3
4
import timeit
start = timeit.default_timer()
end = timeit.default_timer()
print("time span ", end-start)

c++中的timer方式

注意duration_cast的时候先转换成micro seconds再换算成seconds可以获得比较好的精确度。

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
#include <algorithm> 
#include <chrono>
#include <iostream>
#include <vector>
using namespace std;
using namespace std::chrono;

// For demonstration purpose, we will fill up
// a vector with random integers and then sort
// them using sort function. We fill record
// and print the time required by sort function
int main()
{

vector<int> values(10000);
// Generate Random values
auto f = []() -> int { return rand() % 10000; };
// Fill up the vector
generate(values.begin(), values.end(), f);
// Get starting timepoint
auto start = high_resolution_clock::now();
// Call the function, here sort()
sort(values.begin(), values.end());
// Get ending timepoint
auto stop = high_resolution_clock::now();
// Get duration. Substart timepoints to
// get durarion. To cast it to proper unit
// use duration cast method
auto duration_micro = duration_cast<microseconds>(stop - start);
auto duration_seconds = duration_cast<seconds> (stop - start);

cout << "Time taken by function: "
<< duration_micro.count() << " microseconds, " << duration_micro.count()*1.0/1000000 << " seconds" << endl;

cout << "Time taken by function: "
<< duration_seconds.count()*0.1 << " seconds" << endl;

return 0;

timer for distributed components

有一个case是需要测的timer间隔发生在不同的组件中,比如一个worklow,从component a 开始到 component z 结束,这个时候要测量a到z的执行时间。

这个时候需要设置一个middleware来专门处理这个case,之前用的一个单节点的prototype放在这里,消息通信是基于grpc,单节点一般负载的case就能cover了,grpc的好处是不论cpp或者是python或者是其他的主流code都有比较好的client库可以直接调用。

time 提供了两种方式 一种是tick record,每发一次请求记录一次时间,另一种是time span的形式,只记录开始和结束的时间。

除此之外这个工具还提供了两种用于测试的message communication pattern。一种是shared space,另外一种是message queue,具体在README中有介绍,这里就不再赘述。

总之用profile之前,针对性地设置timer然后运行bentchmark也是一种测量performance的方式。如果这个方法找不到bottleneck再使用profiling的工具。

timer in parallel processing

这里有两点需要注意,第一个是在time之前要使用barrier的primitives,这样才能确保不同thread/process的timer是准确的。第二个是求平均值的问题,经常使用的是reduce的primitives。比如MPI_Reduce把不同process的timer汇集到一个process中之后再求平均值。

关于timer的误区

量级的timer才有意义(算法优化上的意义),根据时间复杂度O(n)的定义,也是n在很大数量的时候O(n)才有意义。有几次是对于很小的几分几秒进行测量,就没什么意义,最起码在算法上没什么意义,这个时候的strategy就是把这个差异放大,比如这个operation执行了100或者1000次,这个时候的时间,或者是输入的data变得很大的时候,这个时候的时间比较有意义。

Reference

https://stackoverflow.com/questions/27618032/i-o-bound-performance-speedup/27618217

推荐文章