我的程序输入是一个大字符串,大约30,000个字符。下面是我自己的strlen的代码:
size_t strlen(const char *c)
{
int i;
i = 0;
while (c[i] != '\0')
i++;
return (i);
}
上面的strlen版本需要大约2.1秒才能执行。通过不同的版本,我能够达到~1.4秒。
我的问题是,为什么多个if语句比执行while循环更快?
size_t strlen(const char *str)
{
const char *start;
start = str;
while (1)
{
if (str[0] == '\0')
return (str - start);
if (str[1] == '\0')
return (str - start + 1);
if (str[2] == '\0')
return (str - start + 2);
if (str[3] == '\0')
return (str - start + 3);
if (str[4] == '\0')
return (str - start + 4);
if (str[5] == '\0')
return (str - start + 5);
if (str[6] == '\0')
return (str - start + 6);
if (str[7] == '\0')
return (str - start + 7);
if (str[8] == '\0')
return (str - start + 8);
str += 9; //
}
}
我的问题是,为什么,很多if语句比运行循环更快?
编辑:使用标准库,大约1.25规格。
您的问题是相关的,但您的基准测试不完整且结果令人惊讶。
以下是代码的修改和检测版本:
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>
#define VERSION 3
#define TRIALS 100
#define ITERATIONS 100
#if VERSION == 1
size_t strlen1(const char *c) {
size_t i;
i = 0;
while (c[i] != '\0')
i++;
return (i);
}
#define strlen(s) strlen1(s)
#elif VERSION == 2
size_t strlen2(const char *str) {
const char *start;
start = str;
while (1) {
if (str[0] == '\0')
return (str - start);
if (str[1] == '\0')
return (str - start + 1);
if (str[2] == '\0')
return (str - start + 2);
if (str[3] == '\0')
return (str - start + 3);
if (str[4] == '\0')
return (str - start + 4);
if (str[5] == '\0')
return (str - start + 5);
if (str[6] == '\0')
return (str - start + 6);
if (str[7] == '\0')
return (str - start + 7);
if (str[8] == '\0')
return (str - start + 8);
str += 9;
}
}
#define strlen(s) strlen2(s)
#elif VERSION == 3
size_t strlen3(const char *str) {
const uint64_t *px, sub = 0x0101010101010101, mask = 0x8080808080808080;
const char *p;
for (p = str; (uintptr_t)p & 7; p++) {
if (!*p)
return p - str;
}
for (px = (const uint64_t *)(uintptr_t)p;;) {
uint64_t x = *px++;
if (((x - sub) & ~x) & mask)
break;
}
for (p = (const char *)(px - 1); *p; p++)
continue;
return p - str;
}
#define strlen(s) strlen3(s)
#endif
int get_next_line(int fd, char **pp) {
char buf[32768];
char *line = NULL, *new_line;
char *p;
ssize_t line_size = 0;
ssize_t nread, chunk;
while ((nread = read(fd, buf, sizeof buf)) > 0) {
p = memchr(buf, '\n', nread);
chunk = (p == NULL) ? nread : p - buf;
new_line = realloc(line, line_size + chunk + 1);
if (!new_line) {
free(line);
*pp = NULL;
return 0;
}
line = new_line;
memcpy(line + line_size, buf, chunk);
line_size += chunk;
line[line_size] = '\0';
if (p != NULL) {
lseek(fd, chunk + 1 - nread, SEEK_CUR);
break;
}
}
*pp = line;
return line != NULL;
}
int main() {
char *line = NULL;
int fd, fd2, count, trial;
clock_t min_clock = 0;
fd = open("one_big_fat_line.txt", O_RDONLY);
if (fd < 0) {
printf("cannot open one_big_fat_line.txt\n");
return 1;
}
fd2 = open("output.txt", O_WRONLY | O_CREAT | O_TRUNC, S_IREAD | S_IWRITE);
if (fd2 < 0) {
printf("cannot open output.txt\n");
return 1;
}
for (trial = 0; trial < TRIALS; trial++) {
clock_t t = clock();
for (count = 0; count < ITERATIONS; count++) {
lseek(fd, 0L, SEEK_SET);
lseek(fd2, 0L, SEEK_SET);
while (get_next_line(fd, &line) == 1) {
write(fd2, line, strlen(line));
write(fd2, "\n", 1);
free(line);
}
}
t = clock() - t;
if (min_clock == 0 || min_clock > t)
min_clock = t;
}
close(fd);
close(fd2);
double time_taken = (double)min_clock / CLOCKS_PER_SEC;
printf("Version %d time: %.3f microseconds\n", VERSION, time_taken * 1000000 / ITERATIONS);
return 0;
}
该程序打开一个文件,使用自定义函数read_next_line()
从中读取行,该函数使用unix系统调用,malloc
返回任意大小的行。然后它使用unix系统调用write
写入这些行,并附加一个带有单独系统调用的换行符。
使用您的测试文件(带有单行ASCII字符的30000字节文件)对此序列进行基准测试,显示出与您测量的内容完全不同的性能:取决于所选的strlen
实现和编译优化设置,笔记本电脑上的时间范围从每次迭代15微秒到82微秒,你观察到的任何地方都不会接近1或2秒。
strlen1
天真实现,我得到82微秒的优化禁用和25微秒与-O3
优化。strlen2
展开的实现,使用-O0
时速度提高到30微秒,使用-O3
提高20微秒。strlen3
,使用-O0
在21微秒时提供了进一步改善的性能,在-O3
时提供了15.5微秒的性能。请注意编译器优化如何比手动优化更能影响性能。
您的展开版本执行得更好的原因是生成的代码每个字节增加指针一次,每个字节执行一次无条件跳转,而展开版本每9个字节减少一次。但请注意,C编译器在天真代码上与-O3
的性能几乎相同,就像你自己展开循环一样。
高级版本与C库实现的性能非常接近,可以使用汇编语言和SIMD指令。它一次读取8个字节并执行算术技巧,以检测当从其值中减去0
时,这些字节中的任何一个是否将其最高位从1
更改为1
。需要额外的初始步骤来将指针对齐以读取64位字,从而避免在某些体系结构上具有未定义行为的未对齐读取。它还假定在字节级别没有内存保护。在现代x86系统上,内存保护具有4K或更大的粒度,但是其他一些系统(如Windows 2.x)的保护程度要细得多,完全阻止了这种优化。
但请注意,基准测试还测量从输入文件中读取的时间,找到换行符并写入输出文件。 strlen
和strlen3
的相对表现可能更为重要。实际上,只有strlen(line)
与30000字节线的单独基准显示strlen3()
的时间为2.2微秒,strlen()
的时间为0.85微秒。
结论:
-O3
是一个很好的默认值。