首页 > 代码库 > strcat的几种实现及性能比较
strcat的几种实现及性能比较
一 原型说明
strcat()为C语言标准库函数，用于字符串拼接。函数原型声明在string.h头文件中：
|
char *strcat(char *dest, const char *src); |
该函数将参数src所指字符串拷贝到参数dest所指字符串的结尾处(覆盖dest结尾处的‘\0‘)并添加‘\0‘。其返回值为参数dest所指字符串的起始地址。注意，dest必须有足够的空间来容纳要拷贝的src字符串。
本文将给出strcat函数的几种实现，并比较其执行效率。代码运行环境如下：
二 代码实现
2.1 汇编实现
1 char *AssemStrcat(char *pszDest, const char *pszSrc)
2 {
3 int d0, d1, d2, d3;
4 __asm__ __volatile__(
5 "repne\n\t"
6 "scasb\n\t"
7 "decl %1\n"
8 "1:\tlodsb\n\t"
9 "stosb\n\t"
10 "testb %%al,%%al\n\t"
11 "jne 1b"
12 : "=&S" (d0), "=&D" (d1), "=&a" (d2), "=&c" (d3)
13 : "0" (pszSrc), "1" (pszDest), "2" (0), "3" (0xffffffff):"memory");
14 return pszDest;
15 }
2.2 模拟C库
1 char *SimuStrcat(char *pszDest, const char *pszSrc)
2 {
3 char *pszOrigDst = pszDest;
4
5 while(*pszDest)
6 pszDest++;
7 while((*pszDest++ = *pszSrc++) != ‘\0‘)
8 ;
9
10 return pszOrigDst;
11 }
因strcat的C标准库函数的实现方式未知，故使用SimuStrcat函数模拟标准库实现。
2.3 快速拼接
由strcat函数的原型说明可知，每次调用时都必须扫描整个目的字符串(以寻找结束符)。这会降低该函数的执行效率，尤其是在频繁拼接时。
FastStrcat函数每次返回拼接后的字符串尾部，即指向结束符所在位置。下次调用时便不再需要扫描整串，从而提高执行效率。
1 char *FastStrcat(char *pszDest, const char* pszSrc)
2 {
3 while(*pszDest)
4 pszDest++;
5 while((*pszDest++ = *pszSrc++));
6 return --pszDest;
7 }
注意，第二个while循环若不加双层括号则会报”suggest parentheses around assignment used as truth value”的警告。因返回时对pszDest作减法运算，故单次执行时FastStrcat慢于SimuStrcat。
为提高执行速度，本节函数实现均未对指针参数做判空处理。若兼求安全性，可在函数内使用assert断言指针合法性。Gcc编译器还对函数声明提供一种nonnull扩展属性，可在编译时进行有限的判空保护：
1 char *FastStrcat(char *pszDest, const char* pszSrc)__attribute__((__nonnull__(1, 2)));
2 char *NullPtr(void){return NULL;}
3 int main(void)
4 {
5 char *pszBuf = NULL;
6 FastStrcat(pszBuf, "Elizabeth ");
7 FastStrcat(NullPtr(), "Elizabeth ");
8 FastStrcat(NullPtr()?pszBuf:NULL, "Elizabeth ");
9 FastStrcat(NULL, "Elizabeth ");
10 return 0;
11 }
其中，__nonnull__(1, 2)指示编译器对FastStrcat函数调用的第一个和第二个参数判空。
编译结果如下：
1 [wangxiaoyuan_@localhost test1]$ gcc -Wall -o test test.c 2 test.c: In function ‘main‘: 3 test.c:8: warning: null argument where non-null required (argument 1)
4 test.c:9: warning: null argument where non-null required (argument 1)
可见，除非将指针参数显式地置空，否则nonnull机制也检测不到。此外，使用nonnull机制时，若打开编译优化选项-O2，则函数内关于指针参数的校验将被优化掉。
三 性能比较
本节采用《Linux用户态程序计时方式详解》一文的TIME_ELAPSED()宏进行程序计时。
1 #define TIME_ELAPSED(codeToTime) do{ 2 struct timeval beginTime, endTime; 3 gettimeofday(&beginTime, NULL); 4 {codeToTime;} 5 gettimeofday(&endTime, NULL); 6 long secTime = endTime.tv_sec - beginTime.tv_sec; 7 long usecTime = endTime.tv_usec - beginTime.tv_usec; 8 printf("[%s(%d)]Elapsed Time: SecTime = %lds, UsecTime = %ldus!\n", __FILE__, __LINE__, secTime, usecTime); 9 }while(0)
基于该宏，编写测试代码如下：
1 #ifdef strcat //检查标准库strcat是否用宏实现
2 #warning strcat has been defined!
3 #endif
4 int main(void)
5 {
6 char szCatBuf[1000];
7 szCatBuf[0] = ‘\0‘; //字符串快速初始化
8
9 char *pszBuf = szCatBuf;
10 TIME_ELAPSED(
11 pszBuf = FastStrcat(pszBuf, "Abraham, ");
12 pszBuf = FastStrcat(pszBuf, "Alexander, ");
13 pszBuf = FastStrcat(pszBuf, "Maximilian, ");
14 pszBuf = FastStrcat(pszBuf, "Valentine ")
15 );
16 printf(" [FastStrcat]szCatBuf = %s\n", szCatBuf);
17
18 szCatBuf[0] = ‘\0‘;
19 TIME_ELAPSED(
20 SimuStrcat(szCatBuf, "Abraham, ");
21 SimuStrcat(szCatBuf, "Alexander, ");
22 SimuStrcat(szCatBuf, "Maximilian, ");
23 SimuStrcat(szCatBuf, "Valentine ")
24 );
25 printf(" [SimuStrcat]szCatBuf = %s\n", szCatBuf);
26
27 szCatBuf[0] = ‘\0‘;
28 TIME_ELAPSED(
29 AssemStrcat(szCatBuf, "Abraham, ");
30 AssemStrcat(szCatBuf, "Alexander, ");
31 AssemStrcat(szCatBuf, "Maximilian, ");
32 AssemStrcat(szCatBuf, "Valentine ")
33 );
34 printf(" [AssemStrcat]szCatBuf = %s\n", szCatBuf);
35
36 szCatBuf[0] = ‘\0‘;
37 TIME_ELAPSED(
38 strcat(szCatBuf, "Abraham, ");
39 strcat(szCatBuf, "Alexander, ");
40 strcat(szCatBuf, "Maximilian, ");
41 strcat(szCatBuf, "Valentine ")
42 );
43 printf(" [LibStrcat]szCatBuf = %s\n", szCatBuf);
44
45 szCatBuf[0] = ‘\0‘;
46 TIME_ELAPSED(
47 sprintf(szCatBuf, "%s%s%s%s","Abraham, ", "Alexander, ", "Maximilian, ", "Valentine ")
48 );
49 printf(" [LibSprintf]szCatBuf = %s\n", szCatBuf);
50
51 return 0;
52 }
除上节三种strcat实现外，代码还对齐库实现及sprintf方式进行测试。测试结果如下：
1 [wangxiaoyuan_@localhost test1]$ gcc -Wall -o test test.c 2 [wangxiaoyuan_@localhost test1]$ ./test 3 [test.c(15)]Elapsed Time: SecTime = 0s, UsecTime = 2us! 4 [FastStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 5 [test.c(24)]Elapsed Time: SecTime = 0s, UsecTime = 2us! 6 [SimuStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 7 [test.c(33)]Elapsed Time: SecTime = 0s, UsecTime = 1us! 8 [AssemStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 9 [test.c(42)]Elapsed Time: SecTime = 0s, UsecTime = 1us! 10 [LibStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 11 [test.c(48)]Elapsed Time: SecTime = 0s, UsecTime = 6us! 12 [LibSprintf]szCatBuf = Abraham, Alexander, Maximilian, Valentine
因每次测试仅调用一次待测函数，故计时不太精准。对比另一次测试结果：
1 [wangxiaoyuan_@localhost test1]$ ./test 2 [test.c(15)]Elapsed Time: SecTime = 0s, UsecTime = 4us! 3 [FastStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 4 [test.c(24)]Elapsed Time: SecTime = 0s, UsecTime = 4us! 5 [SimuStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 6 [test.c(33)]Elapsed Time: SecTime = 0s, UsecTime = 3us! 7 [AssemStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 8 [test.c(42)]Elapsed Time: SecTime = 0s, UsecTime = 2us! 9 [LibStrcat]szCatBuf = Abraham, Alexander, Maximilian, Valentine 10 [test.c(48)]Elapsed Time: SecTime = 0s, UsecTime = 15us! 11 [LibSprintf]szCatBuf = Abraham, Alexander, Maximilian, Valentine
可见，单次执行时，strcat库函数最快，FastStrcat居中，sprintf库函数最慢。
接着，比较批量执行时strcat库函数和FastStrcat的速度。测试代码如下：
1 int main(void)
2 {
3 #define ROUND (unsigned short)1000
4 char szCatBuf[sizeof("Elizabeth ")*ROUND];
5 szCatBuf[0] = ‘\0‘;
6
7 char *pszBuf = szCatBuf;
8 TIME_ELAPSED(
9 unsigned short wIdx = 0;
10 for(; wIdx < ROUND; wIdx++)
11 pszBuf = FastStrcat(pszBuf, "Elizabeth ");
12 );
13
14 szCatBuf[0] = ‘\0‘;
15 TIME_ELAPSED(
16 unsigned short wIdx = 0;
17 for(; wIdx < ROUND; wIdx++)
18 strcat(szCatBuf, "Elizabeth ");
19 );
20
21 return 0;
22 }
测试结果如下：
1 [wangxiaoyuan_@localhost test1]$ gcc -Wall -o test test.c 2 [wangxiaoyuan_@localhost test1]$ ./test 3 [test.c(12)]Elapsed Time: SecTime = 0s, UsecTime = 99us! 4 [test.c(19)]Elapsed Time: SecTime = 0s, UsecTime = 3834us!
可见，批量执行时，FastStrcat远快于strcat库函数。
四 总结
单次拼接时，strcat库函数最快，FastStrcat居中，sprintf库函数最慢(若非格式化需要不建议用于字符串拼接)。
频繁拼接时，FastStrcat相比strcat库函数具有明显的速度优势。
strcat的几种实现及性能比较
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。