一、从算法复杂度都程序性能

我们第一次接触关于代码性能相关概念，应该是在学数据结构中的算法时间复杂度上面。

算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。因此，作为程序员，掌握基本的算法时间复杂度分析方法是很有必要的。
算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

一、事后统计的方法

这种方法可行，但不是一个好的方法。该方法有两个缺陷：一是要想对设计的算法的运行性能进行评测，必须先依据算法编制相应的程序并实际运行；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优势。

二、事前分析估算的方法

因事后统计方法更多的依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。

在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

(1). 算法采用的策略、方法；(2). 编译产生的代码质量；(3). 问题的输入规模；(4). 机器执行指令的速度。
一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

三、求解算法的时间复杂度的具体步骤

求解算法的时间复杂度的具体步骤是：

⑴ 找出算法中的基本语句；

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

⑵ 计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。

⑶ 用大Ο记号表示算法的时间性能。

将基本语句执行次数的数量级放入大Ο记号中。

四、算法复杂度和程序性能之间的关系

首先从整体上来说，算法复杂度是针对代码片段的执行次数的一个量级估计的方法，只能从量级的角度评估该代码片段的性能。程序性能则是从实际运行的角度来衡量一个程序的性能。

算法复杂度只影响局部代码的性能，程序性能是对整个程序性能的评估。

算法复杂度是否会对整体程序性能有影响要视情况而定，还收到其他代码片段性能、执行次数、执行语句是否耗时等影响。

五、执行什么语句耗时？不同语句执行时间量级分析

之前写的一些博客可以拿来补充：

VxWorks实时性能探究

测试C语言中打印一句 hello world需要耗费多少时间

这次继续深入探究一下执行不同语句的耗时情况。

在我们的代码中，存在的比较典型的代码语句包括，算术运算，循环，逻辑判断，函数调用，打印，文件IO等。下面我们就测试一下这些语句在我电脑编译环境下的耗时情况。(注意不同的编译器和硬件配置会有不同的结果)

整型加和减：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    
	clock_t begin, end;
	double cost;
	//开始记录
	begin = clock();
	/*待测试程序段*/
	int a = 1;
	for (int i = 0; i < 100000000; i++) {
    
		a = a + 1;//a = a - 1;
	}

	//结束记录
	end = clock();
	cost = (double)(end - begin)/CLOCKS_PER_SEC;
	printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf secs", CLOCKS_PER_SEC, cost);
}

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.055000 secs

55 ms/ 100000000 = 55000 us/100000000 = 0.00055 us = 0.55 ns

整型乘 和 整型加和减也差不多。

整型除 相比上面会更耗时，但量级差不多。

浮点型加和减

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    
	clock_t begin, end;
	double cost;
	//开始记录
	begin = clock();
	/*待测试程序段*/
	double a = 1.0;
	for (int i = 0; i < 100000000; i++) {
    
		a = a + 1;//a = a-1;
	}

	//结束记录
	end = clock();
	cost = (double)(end - begin)/CLOCKS_PER_SEC;
	printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf secs", CLOCKS_PER_SEC, cost);
}

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.273000 secs

可以看出浮点型的加和减耗时大概是整型加减的5倍

浮点乘除：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    
	clock_t begin, end;
	double cost;
	//开始记录
	begin = clock();
	/*待测试程序段*/
	double a = 1.0;
	for (int i = 0; i < 100000000; i++) {
    
		a = a / i;
	}

	//结束记录
	end = clock();
	cost = (double)(end - begin)/CLOCKS_PER_SEC;
	printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf secs", CLOCKS_PER_SEC, cost);
}

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.509000 secs

浮点型的乘和除耗时大概是浮点型的加和减耗时的2倍。

但总体来看进行算术运算的耗时还是比较小的。

测试打印printf

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    
	clock_t begin, end;
	double cost;
	//开始记录
	begin = clock();
	/*待测试程序段*/
	
	for (int i = 0; i < 1000; i++) {
    
		printf("h");
	}

	//结束记录
	end = clock();
	cost = (double)(end - begin)/CLOCKS_PER_SEC;
	printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf secs", CLOCKS_PER_SEC, cost);
}

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.025000 secs

25 ms/ 1000 = 0.025 ms =25 us

测试还发现一个有趣的现象，打印语句耗时和打印的内容中字符的长短有关。

如果 printf(“h”) 改成 printf(“hh”) 、printf(“hhh”)、printf(“hhhh”)、printf(“hhhhh”)。则耗时分别变成

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.053000 secs

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.076000 secs

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.108000 secs

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.142000 secs

差不多和字符的长度成正比。

函数调用

其实在C语言中，我们都会把经常要调用的代码不长的函数弄成宏或内联函数，这样可以提高运行效率。

这篇博客讲解了一下函数调用耗时的情况：函数调用太多了会有性能问题吗？

下面我们来测试一下函数调用：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int callme(int a) {
    
	a = a + 1;
	return a;
}

int main()
{
    
	clock_t begin, end;
	double cost;
	//开始记录
	begin = clock();
	/*待测试程序段*/
	int b;
	for (int i = 0; i < 1000000000; i++) {
    
		b = callme(i);
	}

	//结束记录
	end = clock();
	cost = (double)(end - begin)/CLOCKS_PER_SEC;
	printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf secs", CLOCKS_PER_SEC, cost);
}

constant CLOCKS_PER_SEC is: 1000, time cost is: 1.198000 secs

1.198s = 1198000000 ns / 1000000000 =1.19 ns

可以看到和上面那篇博客的计算的耗时是差不多的。

二、程序性能分析工具

1.gprof

gprof是一款 GNU profile工具，可以运行于linux、AIX、Sun等操作系统进行C、C++、Pascal、Fortran程序的性能分析，用于程序的性能优化以及程序瓶颈问题的查找和解决。

gprof介绍

gprof(GNU profiler)是GNU binutils工具集中的一个工具，linux系统当中会自带这个工具。它可以分析程序的性能，能给出函数调用时间、调用次数和调用关系，找出程序的瓶颈所在。在编译和链接选项中都加入-pg之后，gcc会在每个函数中插入代码片段，用于记录函数间的调用关系和调用次数，并采集函数的调用时间。

gprof安装

gprof是gcc自带的工具，一般无需额外安装步骤。

首先检查工具是否已经安装在系统上。 为此，只需在终端中运行以下命令即可。

$ gprof

如果您收到以下错误：

$ a.out: No such file or directory

那么这意味着该工具已经安装。 否则可以使用以下命令安装它：

$ apt-get install binutils

gprof使用步骤

1. 用gcc、g++、xlC编译程序时，使用-pg参数

如：g++ -pg -o test.exe test.cpp

编译器会自动在目标代码中插入用于性能测试的代码片断，这些代码在程序运行时采集并记录函数的调用关系和调用次数，并记录函数自身执行时间和被调用函数的执行时间。

2. 执行编译后的可执行程序，生成文件gmon.out

如：./test.exe

该步骤运行程序的时间会稍慢于正常编译的可执行程序的运行时间。程序运行结束后，会在程序所在路径下生成一个缺省文件名为gmon.out的文件，这个文件就是记录程序运行的性能、调用关系、调用次数等信息的数据文件。

3. 使用gprof命令来分析记录程序运行信息的gmon.out文件

如：gprof test.exe gmon.out

可以在显示器上看到函数调用相关的统计、分析信息。上述信息也可以采用gprof test.exe gmon.out> gprofresult.txt重定向到文本文件以便于后续分析。

实战一：用gprof测试基本函数调用及控制流

测试代码

#include <stdio.h>

void loop(int n){
    
    int m = 0;
    for(int i=0; i<n; i++){
    
        for(int j=0; j<n; j++){
    
            m++;    
        }   
    }
}

void fun2(){
    
    return;
}

void fun1(){
    
    fun2();
}

int main(){
    
    loop(10000);

    //fun1callfun2
    fun1(); 

    return 0; 
}

操作步骤

liboxuan@ubuntu:~/Desktop$ vim test.c
liboxuan@ubuntu:~/Desktop$ gcc -pg -o test_gprof test.c 
liboxuan@ubuntu:~/Desktop$ ./test_gprof 
liboxuan@ubuntu:~/Desktop$ gprof ./test_gprof gmon.out
# 报告逻辑是数据表 + 表项解释
Flat profile:

# 1.第一张表是各个函数的执行和性能报告。
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
101.20      0.12     0.12        1   121.45   121.45  loop
  0.00      0.12     0.00        1     0.00     0.00  fun1
  0.00      0.12     0.00        1     0.00     0.00  fun2

 %         the percentage of the total running time of the
time       program used by this function.

cumulative a running sum of the number of seconds accounted
 seconds   for by this function and those listed above it.

 self      the number of seconds accounted for by this
seconds    function alone.  This is the major sort for this
           listing.

calls      the number of times this function was invoked, if
           this function is profiled, else blank.

 self      the average number of milliseconds spent in this
ms/call    function per call, if this function is profiled,
       else blank.

 total     the average number of milliseconds spent in this
ms/call    function and its descendents per call, if this
       function is profiled, else blank.

name       the name of the function.  This is the minor sort
           for this listing. The index shows the location of
       the function in the gprof listing. If the index is
       in parenthesis it shows where it would appear in
       the gprof listing if it were to be printed.


Copyright (C) 2012-2015 Free Software Foundation, Inc.

Copying and distribution of this file, with or without modification,
are permitted in any medium without royalty provided the copyright
notice and this notice are preserved.


# 2.第二张表是程序运行时的
             Call graph (explanation follows)


granularity: each sample hit covers 2 byte(s) for 8.23% of 0.12 seconds

index % time    self  children    called     name
                0.12    0.00       1/1           main [2]
[1]    100.0    0.12    0.00       1         loop [1]
-----------------------------------------------
                                                 <spontaneous>
[2]    100.0    0.00    0.12                 main [2]
                0.12    0.00       1/1           loop [1]
                0.00    0.00       1/1           fun1 [3]
-----------------------------------------------
                0.00    0.00       1/1           main [2]
[3]      0.0    0.00    0.00       1         fun1 [3]
                0.00    0.00       1/1           fun2 [4]
-----------------------------------------------
                0.00    0.00       1/1           fun1 [3]
[4]      0.0    0.00    0.00       1         fun2 [4]
-----------------------------------------------

 This table describes the call tree of the program, and was sorted by
 the total amount of time spent in each function and its children.

 Each entry in this table consists of several lines.  The line with the
 index number at the left hand margin lists the current function.
 The lines above it list the functions that called this function,
 and the lines below it list the functions this one called.
 This line lists:
     index  A unique number given to each element of the table.
        Index numbers are sorted numerically.
        The index number is printed next to every function name so
        it is easier to look up where the function is in the table.

     % time This is the percentage of the `total' time that was spent
        in this function and its children.  Note that due to
        different viewpoints, functions excluded by options, etc,
        these numbers will NOT add up to 100%.

     self   This is the total amount of time spent in this function.

     children   This is the total amount of time propagated into this
        function by its children.

     called This is the number of times the function was called.
        If the function called itself recursively, the number
        only includes non-recursive calls, and is followed by
        a `+' and the number of recursive calls.

     name   The name of the current function.  The index number is
        printed after it.  If the function is a member of a
        cycle, the cycle number is printed between the
        function's name and the index number.


 For the function's parents, the fields have the following meanings:

     self   This is the amount of time that was propagated directly
        from the function into this parent.

     children   This is the amount of time that was propagated from
        the function's children into this parent.

     called This is the number of times this parent called the
        function `/' the total number of times the function
        was called.  Recursive calls to the function are not
        included in the number after the `/'.

     name   This is the name of the parent.  The parent's index
        number is printed after it.  If the parent is a
        member of a cycle, the cycle number is printed between
        the name and the index number.

 If the parents of the function cannot be determined, the word
 `<spontaneous>' is printed in the `name' field, and all the other
 fields are blank.

 For the function's children, the fields have the following meanings:

     self   This is the amount of time that was propagated directly
        from the child into the function.

     children   This is the amount of time that was propagated from the
        child's children to the function.

     called This is the number of times the function called
        this child `/' the total number of times the child
        was called.  Recursive calls by the child are not
        listed in the number after the `/'.

     name   This is the name of the child.  The child's index
        number is printed after it.  If the child is a
        member of a cycle, the cycle number is printed
        between the name and the index number.

 If there are any cycles (circles) in the call graph, there is an
 entry for the cycle-as-a-whole.  This entry shows who called the
 cycle (as parents) and the members of the cycle (as children.)
 The `+' recursive calls entry shows the number of function calls that
 were internal to the cycle, and the calls entry for each member shows,
 for that member, how many times it was called from other members of
 the cycle.


Copyright (C) 2012-2015 Free Software Foundation, Inc.

Copying and distribution of this file, with or without modification,
are permitted in any medium without royalty provided the copyright
notice and this notice are preserved.
# 第三张表是函数与其在报告中序号的对应表

Index by function name

   [3] fun1                    [4] fun2                    [1] loop