Comments / Profile of yleo / Habr

habr is dead. @yleo

/dev/null

Побеждая C двадцатью строками Haskell: пишем свой wc

yleo Feb 21 2020 at 11:11

Дисклаймер: Этот комментарий добавлен не для того чтобы показать "тормознутось" Хаскеля или "превосходство" C (ибо у каждого языка свое назначение), но чтобы обратить внимание что чуть менее чем все подобные "хайповые" бенчмарки и сравнения содержат достаточно недочетов чтобы не принимать их всерьез. При этом всё же уместно напомнить тезис, что языки без zero cost abstraction никогда не смогут конкурировать по скорости кода с теми, где zero cost abstraction есть.

Ниже под спойлером чистый "сишный" функциональный аналог кода на Haskell, без SIMD и прочей "магии". На моём пристарелом ноуте c i7-4600U 2.10GHz он отрабатывает за секунду:

$ clang -Wall -Wextra -Wpedantic -Ofast -march=native naive_wc.c -o naive_wc

$ ./naive_wc /dev/shm/test.txt
lines 15000000, words 44774631, chars 1871822210
took 1.038524 seconds

$ clang --version
clang version 8.0.1- (branches/release_80)
Target: x86_64-pc-linux-gnu

$ grep "model name" /proc/cpuinfo | head -n1 
model name  : Intel(R) Core(TM) i7-4600U CPU @ 2.10GHz

Для проверке результаты запуска системного wc c теми-же данными:

$ time /usr/bin/wc /dev/shm/test.txt 
  15000000   44774631 1871822210 /dev/shm/test.txt
19.24user 0.27system 0:19.52elapsed 99%CPU (0avgtext+0avgdata 2140maxresident)k
0inputs+0outputs (0major+80minor)pagefaults 0swaps

Файл test.txt был получен ровно как описано в статье, только я сразу разместил его в /dev/shm.
Компилятор clang с -march=native использован чтобы создать максимально равные условия с ghc из статьи. У меня уже была 8-я версия clang, и тратить время на установку более новой я не стал.

Мой ноут с i7-4600U CPU @ 2.10GHz медленнее использованного в статье i7-4770 @ 3.40GHz. Разница как минимум в 1.6 раза, а если судить по времени работы системного wc, то почти в два раза. При этом наивный, но равноценный вариант на C отрабатывает в два раза быстрее. Соответственно нормированная разница, с учетом скорости машин, получается где-то 3-4 раза.

Итого: Наивный код на C быстрее фукционального аналога на Haskell в 3-4 раза.
У меня всё, но прошу перепроверить результаты.

Желающие могут написать статью "Побеждаем Хаскель-флеша 15 строками на С" ;)

Спойлер

#include <fcntl.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <time.h>
#include <unistd.h>

/* begin */
typedef struct {
  size_t chars, words, lines;
} wc_result;

static wc_result process(const unsigned char *text, const size_t bytes) {
  wc_result r = {bytes, 0, 0};
  unsigned char prev = 0;
  for (size_t i = 0; i < bytes; ++i) {
    r.lines += text[i] == '\n';
    r.words += text[i] > ' ' && prev <= ' ';
    prev = text[i];
  }
  return r;
}
/* end */

int main(int argc, const char *argv[]) {
  int fd = STDIN_FILENO;
  if (argc > 1) {
    fd = open(argv[1], O_RDONLY);
    if (fd < 0) {
      perror("open");
      return EXIT_FAILURE;
    }
  }

  off_t length = lseek(fd, 0, SEEK_END);
  if (length < 0 || length > INTPTR_MAX)
    return EXIT_FAILURE;

  const void *ptr = mmap(NULL, (size_t)length, PROT_READ, MAP_PRIVATE, fd, 0);
  if (ptr == MAP_FAILED) {
    perror("mmap");
    return EXIT_FAILURE;
  }

  wc_result r = process((const unsigned char *)ptr, (size_t)length);

  struct timespec ts = {0, 0};
  if (clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts))
    perror("clock_gettime(CLOCK_PROCESS_CPUTIME_ID)");

  printf("lines %zu, words %zu, chars %zu\ntook %.6f seconds\n", r.lines,
         r.words, r.chars, ts.tv_nsec * 1e-9 + ts.tv_sec);
  return EXIT_SUCCESS;
}

P.S. 15 строк имеется в виду непосредственно сам подсчет, между /* begin */ и /* end */