Ваш вопрос уместен, но ваш тест не завершен и дает удивительные результаты.
Вот модифицированная и инструментальная версия вашего кода:
#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 и добавляет новую строку с отдельным системным вызовом.
Сравнительный анализ этой последовательности с вашим тестовым файлом, 30000-байтовым файлом с одной строкой символов ASCII, показывает очень отличную производительность от того, что вы измеряете: в зависимости от выбранной реализации strlen и настроек оптимизации компиляции, времени на моем ноутбуке диапазон от 15 микросекунд до 82 микросекунд на итерацию, нигде близко к 1 или 2 секундам, как вы наблюдаете.
Используя стандартную реализацию библиотеки C, я получаю 14,5 микросекунд на итерацию с оптимизацией или без нее.
Используя вашу strlen1 наивную реализацию, я получаю 82 микросекунды с отключенной оптимизацией и 25 микросекунд с -O3 оптимизациями.
При использовании развернутой реализации strlen2 скорость увеличивается до 30 микросекунд с -O0 и 20 микросекунд с -O3.
Наконец, более продвинутая реализация C, считывающая по 8 байт за раз strlen3, обеспечивает дальнейшее повышение производительности за 21 микросекунду с -O0 и 15,5 микросекундами с -O3.
Обратите внимание, что оптимизация компилятора влияет на производительность гораздо сильнее, чем ручная оптимизация.
Причина, по которой ваша развернутая версия работает лучше, состоит в том, что сгенерированный код увеличивает указатель один раз на байт, а безусловный переход выполняется один раз на байт, тогда как развернутая версия уменьшает их до одного раза каждые 9 байтов. Однако обратите внимание, что компилятор C получает почти такую же производительность с -O3 в простом коде, что и при развертывании цикла самостоятельно.
Продвинутая версия очень близка по производительности к реализации библиотеки C, которая может использовать язык ассемблера с инструкциями SIMD. Он считывает 8 байтов за раз и выполняет арифметический трюк, чтобы определить, не изменился ли старший из этих байтов с 0 на 1 при вычитании 1 из его значения. Дополнительные начальные шаги требуются для выравнивания указателя для чтения 64-битных слов, что позволяет избежать не выровненных операций чтения, которые имеют неопределенное поведение на некоторых архитектурах. Также предполагается, что защита памяти недоступна на уровне байтов. В современных системах x86 степень защиты памяти имеет степень детализации 4 КБ или более, но в некоторых других системах, таких как Windows 2.x, степень защиты была намного более тонкой, что полностью исключало эту оптимизацию.
Обратите внимание, однако, что тест также измеряет время для чтения из входного файла, найти новую строку и записать в выходной файл. Относительные показатели strlen и strlen3, вероятно, гораздо более значимы. Действительно, отдельный эталон для strlen(line) с вашей строкой 30000 байт показывает время 2,2 мкс для strlen3() и 0,85 мкс для strlen().
Выводы:
- бенчмаркинг - сложная игра.
- компиляторы хороши в оптимизации, когда им это сказано,
-O3 является хорошим значением по умолчанию.
- Переопределение библиотечных функций с целью их оптимизации бесполезно и рискованно.