C语言编程技巧

说明

C语言编程语法、技巧、经典库。

语法

定义变量时初始化

struct hash_param hash_param = {
    .entries = size,
    .reserved = 0,
    .key_len = sizeof(param.id),
    .hash_func = DEKHash,
    .hash_func_init_val = 0,
};

编码时优化

《深入理解计算机系统》书中的第五章：优化程序性能。非常非常棒的讲解了程序优化的过程。之前对程序优化存在一个误解，以为这些事情交给编译器就可以了，第五章在第一节中就指出了编译器的能力和局限性。性能优化有两个层面，一个是设计层面的，选择高效的算法和数据结构，另一个是编码层面，好的编码可以充分利用硬件的性能。这里是关于编码层面的。

消除循环低效率

如果在循环条件中，可以不使用函数调用，就不要使用。

例如:

for(i=0;i<length(aa);i++){    //编译器不能判断lenght(aa)的值是否会发生变化
	//do something
}

修改为:

int len = length(aa);
for(i=0;i<len;i++){
	//do something
}

减少过程调用

特别在C语言中，在对数组或者其他相邻的结果进行操作时，如果可以通过指针的增减获取下一个成员，不要通过函数调用方式。

例如:

for(i=0;i<len;i++){
	sum+=postion(target,i);	//postion中通常要做有效性检查,即使申明为inline，还是要多执行指令
}

修改为:

for(i=0;i<len;i++){
	sum+=target[i];
}

消除不必要的存储器引用

将计算过程中的中间值存在一个临时变量中，计算结束后写入最终位置，特别在最终位置是指针所指的内存的时候。

例如:

for(i=0;i<len;i++){
	*target=(*target)+i;
}

修改为:

int sum;            //sum的值存储在寄存器中，对寄存器的操作要被对内存的操作快得多
for(i=0;i<len;i++){
	sum+=i;
}
*target=sum;

降低循环开销 – 循环展开技术

循环展开技术减少了条件转移的次数，降低了循环开销。编译器可以完成这项工作，例如gcc的-funroll-loops选项。

例如:

for(i=0;i<len;i++){
	sum+=array[i];
}

修改为:

for(i=0;i<len;i+=3){
	sum+=array[i]+array[i+1]+array[i+2];
}

提高并行性 – 循环分割

循环分割减少对相同CPU内组件的竞争(例如使用同一个寄存器)，使指令可以被流水线执行。

例如:

for(i=0; i<len; i++){
	sum+=array[i];
}

修改为:

for(i=0;i<len;i+=2){
	sum1+=array[i];
	sum2+=array[i+1];
}
sum=sum1+sum2;

存储和加载

CPU内部，如果加载和存储的是不同地址，加载可以不等待存储完成之际执行，否则需要等待。

函数参数

如果函数的参数过多，寄存器不够用，多的参数会被存放在栈中，所以要避免函数参数过多。

64位：整数或指针参数，最多为6个。浮点参数最多为8个。

32位: 参数全部被分配到栈中。

参考：C程序性能优化:20个实验与达人技巧。2.10 32/64位环境中不同函数的调用

编译时优化

likely unlikely

定义：

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

__built_expect()函数是gcc(version >= 2.96)的内建函数,提供给程序员使用的，
目的是将"分支转移"的信息提供给编译器，这样编译器对代码进行优化，以减少指令跳转带来的性能下降。
编译器在编译过程中，会将可能性更大的代码紧跟着后面的代码，从而减少指令跳转带来的性能上的下降。

__buildin_expect((x), 1)表示x的值为真的可能性更大。
__buildin_expect((x), 0)表示x的值为假的可能性更大。

gcc attribute: unused/used

unused：

This attribute, attached to a function, means that the function is meant to be
possibly unused. GCC will not produce a warning for this function.

used:

This attribute, attached to a function, means that code must be emitted for the
function even if it appears that the function is not referenced. This is useful,
for example, when the function is referenced only in inline assembly.

example:

static inline uint32_t DEKHash(const void *key, uint32_t key_len, \
                               __attribute__((unused))void *arg){
    uint32_t hash =  key_len;
    int i = 0;
    char *str = (char *)key;
    for(i = 0; i < key_len; i++){
        hash = ((hash << 5) ^ (hash >>27)) ^ str[i];
    }
    return hash;
}

技巧

条件为真时编译不通过

出处: dpdk-1.6.0r1 rte_common.h

作用: 当condition为真时, 触发一个编译错误

看点1: condition为真时, sizeof(char[-1])编译不通过

看点2: 对condition两次取反, 限定结果只能是0或者1

示例:

/*********** Macros for compile type checks ********/

/**
 * Triggers an error at compilation time if the condition is true.
 */
#ifndef __OPTIMIZE__
#define RTE_BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
#else
extern int RTE_BUILD_BUG_ON_detected_error;
#define RTE_BUILD_BUG_ON(condition) do {             \       
		((void)sizeof(char[1 - 2*!!(condition)]));   \
		if (condition)                               \       
				RTE_BUILD_BUG_ON_detected_error = 1; \
} while(0)
#endif

比较数值大小

出处: dpdk-1.6.0r1 rte_common.h

作用: 比较数值大小

看点1: 定义局部变量保存a和b的值, 如果a或b是表达式, 减少了表达式运算次数

/*********** Macros for calculating min and max **********/

/**
 * Macro to return the minimum of two numbers
 */
#define RTE_MIN(a, b) ({ \
				typeof (a) _a = (a); \
				typeof (b) _b = (b); \
				_a < _b ? _a : _b; \
		})

计算数组成员数量

出处: dpdk-1.6.0r1 rte_common.h

看点1: sizeof((a)[0])

/** Number of elements in the array. */
#define RTE_DIM(a)      (sizeof (a) / sizeof ((a)[0]))

判断一个数是不是2的次方

出处: dpdk-1.6.0r1 rte_common.h

作用: 判断一个数字是否是2的次方

看点1: 如果n是2的次方, n的二进制表示中只有1个1, 减去1后, 原先的1变为0, 后续的0全变为1

/*********** Macros to work with powers of 2 ********/

/**
 * Returns true if n is a power of 2
 * @param n
 *     Number to check
 * @return 1 if true, 0 otherwise
 */
static inline int
rte_is_power_of_2(uint32_t n)
{
		return ((n-1) & n) == 0;
}

找出一个数邻近的2的次方(往增长方向)

出处: dpdk-1.6.0r1 rte_common.h

作用: 找出一个数邻近的2的次方(往增长方向)

看点1: 将减去1的后的数值的二进制表示中的最高位1后续的位全部变为1, 然后在此加上1

看点2: 右移一位相或后，在最高位1处有两个相连的1, 继续右移两位相或后，最高位1处有四个相连的1

/**
 * Aligns input parameter to the next power of 2
 *
 * @param x
 *   The integer value to algin
 *
 * @return
 *   Input parameter aligned to the next power of 2
 */
static inline uint32_t
rte_align32pow2(uint32_t x)
{
		x--;
		x |= x >> 1;
		x |= x >> 2;
		x |= x >> 4;
		x |= x >> 8;
		x |= x >> 16;
		
		return x + 1;
}

基础数据结构

整数(integral)

/usr/include/stdint.h

使用：

#include <stdint.h>

exact integral types, 严格按照名称定义

int8_t
int16_t
int32_t
int64_t

uint8_t
uint16_t
uint32_t
uint64_t

small types, 占空空间最小

int_least8_t
int_least16_t
int_least32_t
int_least64_t

uint_least8_t
uint_least16_t
uint_least32_t
uint_least64_t

fast types, 通过多分配空间，加快速度

int_fast8_t
int_fast16_t
int_fast32_t
int_fast64_t

uint_fast8_t
uint_fast16_t
uint_fast32_t
uint_fast64_t

Types for void * pointers

intptr_t
uintptr_t

Largest integral types

intmax_t
uintmax_t

Limit:

INT8_MIN
INT16_MIN
INT32_MIN
INT64_MIN

INT8_MAX
INT16_MAX
INT32_MAX
INT64_MAX

UINT8_MAX
UINT16_MAX
UINT32_MAX
UINT64_MAX

INTPTR_MIN
INTPTR_MAX
UINTPTR_MAX

INTMAX_MIN
INTMAX_MAX
UINTMAX_MAX

small、fast类型也有对应的limit，可以到/usr/include/stdint.h中查看，这里不给出，

队列(Queue)

/usr/include/sys/queue.h

使用：

#include <sys/queue.h>

手册：

man 3 QUEUE

基础算法

Hash函数

常见Hash函数

//from Knuth, 《编程的艺术 第三卷》第六章排序和搜索
static inline uint32_t DEKHash(const void *key, uint32_t key_len, \
                               __attribute__((unused))void *arg){
    uint32_t hash =  key_len;
    int i = 0;
    char *str = (char *)key;
    for(i = 0; i < key_len; i++){
        hash = ((hash << 5) ^ (hash >>27)) ^ str[i];
    }
    return hash;
}