首页 > 代码库 > 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(NULL, "Elizabeth "); 9 return 0;10 }
其中，__nonnull__(1, 2)指示编译器对FastStrcat函数调用的第一个和第二个参数判空。
编译结果如下：
1 [wangxiaoyuan_@localhost test1]$ gcc -Wall -o test test.c2 test.c: In function ‘main‘:3 test.c:8: warning: null argument where non-null required (argument 1)
可见，除非将指针参数显式地置空，否则nonnull机制也检测不到。
三 性能比较
本节采用《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.c2 [wangxiaoyuan_@localhost test1]$ ./test3 [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库函数具有明显的速度优势。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。