LINUX.ORG.RU

Сообщения Megaorcus

 

Очень медленные regex в GNU C Library. Или это я что-то неправильно делаю?

Форум — Development

Изучая C с удивлением заметил что стандартные POSIX регексы из glibc работают на порядок медленнее чем в Lua. Решил замерить на одинаковых по логике и шаблону программах. Вот программа на C для подсчёта количества слов на русском языке в тексте с кодировкой UTF-8:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <regex.h>

// максимальный размер слова
#define MAXWORD 100

int main (int argc, char* argv []) {
    FILE* file = fopen(argv[1], "r");
    // размер файла в байтах
    fseek(file, 0, SEEK_END);
    long size_file = ftell(file);
    fseek(file, 0, SEEK_SET);
    // выделение памяти под текст
    char* text = malloc(size_file + 1);
    // чтение всего файла
    fread(text, 1, size_file, file);
    text[size_file] = '\0';
    fclose(file);
    regex_t regex;
    // шаблон слова на кириллице
    char* pattern =
        "[\xD0\xD1]" // первый байт
        "[\x80-\xBF]" //второй байт
        "[\x80-\xBF\xD0\xD1]*"; // остальныее, если есть
    if (regcomp(&regex, pattern, REG_EXTENDED) != 0) {
        fputs("Ошибка компиляции regex\n", stderr);
        return 1;
    }
    regmatch_t match;
    char word [MAXWORD];
    long count = 0;
    // начальная позиция поиска
    char* pos = text;
    while (regexec(&regex, pos, 1, &match, 0) == 0) {
        int len = match.rm_eo - match.rm_so;
        // ограничение длины слова
        len = (len < MAXWORD) ? len : MAXWORD - 1;
        // извлечение слова
        memcpy(word, pos + match.rm_so, len);
        word[len] = '\0';
        // смещаем начало следующего поиска
        pos += match.rm_eo;
        ++count;
//      printf("%-7ld%s\n", count, word);
    }
    printf("Всего слов: %ld\n", count);
    regfree(&regex);
    free(text);
    return 0;
}

И похожий по логике и с таким же регексом скрипт на Lua:

file = io.open(arg[1], "r");
text = file:read("a")
file:close()
count = 0
pattern = "[\xD0\xD1][\x80-\xBF][\x80-\xBF\xD0\xD1]*"
for word in string.gmatch(text, pattern) do
--  print(word)
    count = count + 1
end
print("Всего слов: " .. count)

Компилируем и замеряем

~ $ clang -o count count.c
~ $ time ./count voina-i-mir.fb2
Всего слов: 531982

real    4m37.622s
user    4m37.228s
sys     0m0.032s
~ $ time lua count.lua voina-i-mir.fb2
Всего слов: 531982

real    0m0.464s
user    0m0.428s
sys     0m0.036s

Разница в 650 раз! И не в пользу glibc. Единственное объяснение, которое я пока вижу, что регексы в Lua реализованы очень просто. Об этом Роберту Иерузалимски (создатель Lua) в своей книге пишет следующее:

Типичная реализация POSIX-регулярных выражений занимает более 4000 строк кода, что превышает половину размера всех стандартных библиотек Lua вместе взятых. Для сравнения, реализация сопоставления с образцом в Lua занимает менее 600 строк.

Возможно именно из-за своей простоты они такие быстрые в Lua. Но всё равно разница в 650 раз озадачивает. То ли лыжи не едут, то ли я что-то неправильно делаю?

 , ,

Megaorcus
()

RSS подписка на новые темы