【C语言最佳实践】为性能编码

您所在的位置：网站首页 › atom运行c语言 › 【C语言最佳实践】为性能编码

【C语言最佳实践】为性能编码

2023-05-27 14:22| 来源: 网络整理| 查看: 265

【C语言最佳实践】为性能编码 作者：wallace-lai 时间：2022-08-04 一、什么是性能

性能的两层含义：

（1）空间复杂度（越低越好）

（2）时间复杂度（越低越好）

优化性能：空间复杂度和时间复杂度的平衡

简单案例：编写函数返回一个字节中位值为一的位的个数

（1）版本一

没有废话，就硬算，然而效率不高。

int count_one_bits(unsigned char byte) { int n = 0; for (int i = 0; i > i) & 0x01) { n++; } } return n; }

（2）版本二

空间换时间，一个字节共有256个值，打一个256大小的表，然后直接返回即可。尽管时间复杂度下降为O(1)，但是还有两个不足的地方：

一个字节的比特位为1的个数最多不超过8，然而使用了int来存储，大量空间被浪费了

我们真的需要打一个256这么大的表吗，会不会存在好多浪费？

static int nr_one_bits[] = { 0, 1, 1, 2, 1, 2, 2, 3, // ... }; static inline int count_one_bits(unsigned char byte) { return nr_one_bits[byte]; }

（3）版本三

将一个字节拆分成高四位和低四位分开处理，我们只需要打一张16大小的表即可。内存空间从1K（256* 4B）下降到了16B，运行时间几乎不变。完美！

static unsigned char nr_one_bits_half_byte[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, }; static inline int count_one_bits(unsigned char byte) { return nr_one_bits_half_byte[byte & 0x0F] + nr_one_bits_half_byte[(byte & 0xF0) >> 4]; } 二、提高性能的两个基本原则

两个原则

（1）不做无用功：不要有无意义的代码

（2）杀鸡莫用牛刀：如果使用牛刀的收益覆盖不了牛刀的成本，那么就不该用牛刀

常见的无用功

（1）没必要的初始化

（2）多余的函数调用

void foo(void) { char buf[64] = {0}; memset(buf, 0, sizeof(buf)); strcpy(buf, "foo"); }

既然本意是做strcpy，为啥还要初始化？

做了初始化还不够，还要调memset做甚？

杀鸡用牛刀

（1）滥用STDIO接口，下面的例子中，往buffer中拷贝字符串完全没有必要使用STDIO这种“重量级”的api，直接使用字符串拷贝就好了。

// use strcpy and strcat instead sprintf(a_buffer, "%s%s", a_string, b_string); // use aoti, aotl, atoll, strtol instead sscanf(a_string, "%d", &i);

（2）滥用高级数据结构，比如，总共就10个数据非要用红黑树、哈希表等等，属实是没必要。

三、常见方法和技巧

提升软件性能的常用方法和技巧

（1）动态缓冲区分配

版本一：不管怎样，我始终钟情于malloc和free

void foo(size_t len) { char *buff = malloc(len); // ... free(buff); }

版本二：malloc的时间代价很大，能不用就不用。在绝大多数的情况下能用栈内存就不用堆内存

void foo(size_t len) { char stack_buff[PATH_MAX + 1]; char *buff; if (len > sizeof(stack_buff)) { buff = malloc(len); } else { buff = stack_buff; } // ... if (buff && buff != stack_buff) { free(buff); } }

（2）字符串匹配

版本一：逐个匹配即可

int get_locale_category_by_keyword(const char *keyword) { if (strcasecmp(keyword, "ctype") == 0) { return LC_CTYPE; } else if (strcasecmp(keyword, "collate") == 0) { return LC_COLLATE; } else if (strcasecmp(keyword, "numeric") == 0) { return LC_NUMERIC; } else if (strcasecmp(keyword, "monetary") == 0) { return LC_MESSAGES; } else if (strcasecmp(keyword, "time") == 0) { return LC_TIME; } // ... }

上面的代码有问题吗？没有问题，但就是性能还可以有一丢丢地提升。什么！还能提升？是的！

版本二：手工哈希一下，妙哉！

int get_locale_category_by_keyword(const char *keyword) { const char *head = keyword + 1; switch (keyword[0]) { case 'c': case 'C': if (strcasecmp(head, "ctype" + 1) == 0) { return LC_TYPE; } else if (strcasecmp(head, "collate" + 1) == 0) { return LC_COLLATE; } break; case 'n': case 'N': if (strcasecmp(head, "numeric" + 1) == 0) { return LC_NUMERIC; } else if (strcasecmp(head, "name" + 1) == 0) { return LC_NAME; } // ... } }

版本三：牛刀版本

如果字符串的情况比较多，那么干脆就用哈希表吧！牢记不要杀鸡用牛刀的原则。如果用牛刀的收益无法覆盖用牛刀的成本，那么就不要用牛刀。

// 注意定义正确的 SIZEOF_SIZE_T #if SIZEOF_SIZE_T == 8 // 2^40 + 2^8 + 0xb3 = 1099511628211 #define FNV_PRIME ((size_t)0x100000001b3ULL) #define FNV_INIT ((size_t)0xcbf29ce484222325ULL) #else // 2^24 + 2^8 + 0x93 = 16777 #define FNV_PRIME ((size_t)0x01000193) #define FNV_INIT ((size_t)0x811c9dc5) #endif static size_t str2Key(const char *str, size_t length) { const unsigned char *s = (const unsigned char *)str; size_t hval = FNV_INIT; if (str == NULL) { return 0; } if (length == 0) { length = strlen(str); } // FNV-1a hash each octet in the buffer while (*s && length) { // xor the bottom with the current octet hval ^= (size_t)*s++; length--; // multiply by the FNV magic prime #ifdef __GUNC__ #if SIZEOF_SIZE_T == 8 hval += (hval

【本文地址】

【C语言最佳实践】为性能编码

【C语言最佳实践】为性能编码

今日新闻

推荐新闻