LINUX.ORG.RU

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

 , ,


1

7

Изучая 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 раз озадачивает. То ли лыжи не едут, то ли я что-то неправильно делаю?

Ответ на: комментарий от VIT

Можно, вообще, строку нарезать по пробельным символам и знакам пунктуации с помощью strtok(), как в следующем примере:

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

int main () {
   char str[256] = "Раз, два, три, четыре - пять. ";
   const char *s = "-., ";
   char *token;
   
   /* get the first token */
   token = strtok(str, s);
   
   /* walk through other tokens */
   while( token != NULL ) {
      printf( " %s\n", token ); 
      token = strtok(NULL, s);
   }
   
   return(0);
}
Раз
два
три
четыре
пять

А потом уже эти слова проверять регексом.

Megaorcus
() автор топика
Ответ на: комментарий от Megaorcus

Ты на форуме ответы читаешь? Тут, конечно, балаболов полно, как и везде, но если ты ходишь на форум, надо уметь выделять из болтовни полезные вещи.

Обрати внимание на ответ utf8nowhere. Бсдишный флажок решает проблему. Сделано, конечно, в сишном стиле, но цели достигает и обратную совместимость не ломает. Вот переделанный фрагмент твоей проги на Си:

    size_t pos = 0; // начальная позиция поиска
    while ( pos < size_file ) {
        regmatch_t match = { .rm_so = pos, .rm_eo = size_file };
        if ( regexec(&regex, text, 1, &match, REG_STARTEND) ) {
            break;
        };
        int len = match.rm_eo - match.rm_so;
        // ограничение длины слова
        len = (len < MAXWORD) ? len : MAXWORD - 1;
        // извлечение слова
        memcpy(word, text + match.rm_so, len);
        word[len] = '\0';
        // смещаем начало следующего поиска
        pos = match.rm_eo;
        ++count;
        printf("%-7ld%s\n", count, word);
    }
debugger ★★★★★
()
Ответ на: комментарий от debugger

Знаешь, попробовал только что твой вариант. Вышло чуть-чуть быстрее моего последнего варианта со списком строк: 2.9 сек, вместо 3.0 сек. Но всё равно большое спасибо за советы.

Megaorcus
() автор топика
Ответ на: комментарий от debugger

Всё, извиняюсь, проблема оказалась в кривой библиотеке и/или компиляторе. Скомпилировал на другом компе через gcc и стало летать:

~/script/C$ time ./count3 voina-i-mir.fb2 
Всего слов: 531982

real 0m0,060s
user 0m0,049s
sys 0m0,011s
~/script/C$ time lua count.lua voina-i-mir.fb2 
Всего слов: 531982

real 0m0,132s
user 0m0,115s
sys 0m0,013s

Чистый C оказался в итоге быстрее всяких скриптов) Но мой изначальный вариант действительно очень медленный - 1 мин. 22 сек. Так что всем спасибо за советы и предложения. Вопрос решён.

Megaorcus
() автор топика
Ответ на: комментарий от Megaorcus

К тому же в Lua строки не изменяемые, а значит на каждую подстроку выделяется память, которая потом чистится сборщиком мусора…

Это как-то нелогично. Извлечение подстроки регексами наоборот от иммутабельности строк можно совершенно безопасно сделать через возврат ссылки на существующую строку.

Сомневаюсь, что разрабы Lua сделали как-то по-другому, это же выстрел себе в ногу на пустом месте.

theNamelessOne ★★★★★
()

Не совсем понятно, зачем тут регекспы. Ведь задача элементарно решается методом детерминированного конечного автомата.

count_fsm.c:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <ctype.h>

static inline int word_start(uint8_t byte) {
    return (byte == 0xD0 || byte == 0xD1);
}

static inline int inside_word(uint8_t byte) {
    return (byte >= 0x80 && byte <= 0xBF);
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <filename>\n", argv[0]);
        return 1;
    }

    FILE* file = fopen(argv[1], "r");
    if (!file) {
        perror("Error opening file");
        return 1;
    }

    fseek(file, 0, SEEK_END);
    long size_file = ftell(file);
    fseek(file, 0, SEEK_SET);

    char* text = malloc(size_file + 1);
    if (!text) {
        perror("Memory allocation failed");
        fclose(file);
        return 1;
    }

    fread(text, 1, size_file, file);
    text[size_file] = '\0';
    fclose(file);

    long count = 0;
    char* pos = text;
    int in_word = 0;

    while (*pos) {
        if (word_start(*pos)) { // начало слова
            if (!in_word) {
                in_word = 1;
                count++;
            }
            pos++;
            while (inside_word(*pos)) { // внутри слова
                pos++;
            }
        } else {
            in_word = 0;
            pos++;
        }
    }

    printf("Всего слов: %ld\n", count);
    free(text);
    return 0;
}
$ cc -O2 -Wall orig.c -o orig
$ /usr/bin/time ./orig voina-i-mir.fb2 
Всего слов: 70695
        2,53 real         2,53 user         0,00 sys

$ cc -O2 -Wall count_fsm.c -o count_fsm
$ /usr/bin/time ./count_fsm voina-i-mir.fb2
Всего слов: 70695
        0,00 real         0,00 user         0,00 sys
iron ★★★★★
()
Ответ на: комментарий от theNamelessOne
  1. gmatchgmatch_aux
  2. gmatch_auxpush_captures
  3. push_capturespush_onecapture
  4. push_onecapturelua_pushlstring
  5. lua_pushlstring создаёт новую строку (luaS_newlstr)
TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  if (l <= LUAI_MAXSHORTLEN)  /* short string? */
    return internshrstr(L, str, l);
  else {
    TString *ts;
    if (l_unlikely(l * sizeof(char) >= (MAX_SIZE - sizeof(TString))))
      luaM_toobig(L);
    ts = luaS_createlngstrobj(L, l);
    memcpy(getlngstr(ts), str, l * sizeof(char));
    return ts;
  }
}

вот и memcpy

utf8nowhere ★★★★
()

Ты неправильно полагаешь, что полноценный regex в glibc и паттерны в lua это одно и то же. И поиск паттерна в коротких строчках не то же самое, что полноценный regex по немаленькому файлу.

Stanson ★★★★★
()
Ответ на: комментарий от Megaorcus

Так что всем спасибо за советы и предложения. Вопрос решён.

Ты лучше скажи два слова — а зачем всё это? Я бы вот за это «регулярное выражение»:

    // шаблон слова на кириллице
    char* pattern =
        "[\xD0\xD1]" // первый байт
        "[\x80-\xBF]" //второй байт
        "[\x80-\xBF\xD0\xD1]*"; // остальныее, если есть

ручки поотрывал. Кто поручится что это и правду соответствует словам на кириллице? Какие ещё символы, кроме русских букв, заматчится на это выражение? Там вся кириллица покрыта? Кроме Cyrillic, который, походу, покрыт не весь, в юникоде есть ещё 4 блока Cyrillic Extended и блок Cyrillic Supplement. А что по поводу Combining Diactrical Marks? Кроме того, код заточен под кодировку UTF-8, но нигде (даже в каментах) этого не сказано. А если .fb2 файл будет в другой кодировке? Редко, но попадаются. Причём кодировка прописана в заголовке файла, и обычно программы это отрабатывают корректно, но твоя программа на этом сломается.

Если это какая-то одноразовая тулза или тулза для домашнего применения (я не имею ввиду именно дом, а, скорее, офис, организацию, короче, не для распространения), то лучше взять перл:

my $count = 0;
while ( $text =~ m/([ёа-я]+)/gi ) {
    say $1;
    ++ $count;
};

если нужны только русские буквы, или m/(\p{Script=Cyrillic}+)/gi если нужны символы из скрипта Cyrillic, или расширить до вообще любых букв: m/([\p{General_Category=Letter}]+)/ или до любых символов, которые встречаются в словах: m/(\w+)/. Кроме того, в перле легко отфильтровать из .fb2 файла все теги, преобразовать юникодный текст из одной нормализованной формы в другую и т. д. Скорость при этом будет не хуже сишной.

С сишкой имеет смысл связываться только если программа предназначена для распространения. Проще один раз скомпилировать программу, чем объяснять потребителям как устанавливать перловые модули (хотя это не трудно). Но в случае сишки я бы подобрал какую-нибудь либу для работы с юникодом, а не писал такие мутные регулярки.

debugger ★★★★★
()

я хотела было посмотреть, что там с парсером. он тормозил раньше, это я помню, я когда-то давно его тыкала палочкой. но не 4 минуты же. и я тупо не нашла ничего, что бы его загрузило так сильно. во-первых, книг в этом формате я у себя не нашла. я качнула самый жирный том БСЭ и ему скормила, но он его прожевал в доли секунды. качнула Толстого с флибусты (читать я его не хочу, чисто ради теста) - тоже результат в 0.086 секунды, нашёл 70695 слов. может, там какой-то другой вариант, я хз. в общем, не удалось мне повторить этот эксперимент, чтобы хоть что-то посмотреть perf'ом, например. да, у меня не шланг, а gcc обычный. компилила специально без оптимизации. всё равно всё выполняется слишком быстро, чтобы что-то там измерять.

может, сможешь сказать, откуда ты тот файл качнул (только чтобы без регистраций и смс, естессна). тогда, может, я посмотрю на досуге, что там не так.

но выше автор прав. регексп сам по себе странно выглядит. я к нему не придиралась, но вообще, в регекспах от формирования запроса результаты могут работать на порядки быстрее/медленнее, жрать больше ресурсов. так что это тоже особое искусство.

Iron_Bug ★★★★★
()
Последнее исправление: Iron_Bug (всего исправлений: 1)
Ответ на: комментарий от firkax

понятно. я всегда думала, что шланг - отстой. но что он настолько отстой, даже не догадывалась. я его даже не собираю у себя. только по работе его видела на серверах и он мне никогда не нравился.

Iron_Bug ★★★★★
()
Ответ на: комментарий от Lrrr

я про тупо передавать длину буфера

Зачем, для нуль-терминированной строки? Можешь 0 вставить, если хочешь ограничить))0)0

А также про потоко-небезопасный setenv

setenv наверняка до потоков появился. Ну и, ЕМНИП, так и не показали задачу где setenv из разных потоков нужен

У меня полное впечатление, что 20-30 лет назад люди клепали спеки, вообще не думая о том как это будет реализовано

Я думаю POSIX документировал что уже давно было реализовано, а не наоборот

utf8nowhere ★★★★
()
Ответ на: комментарий от debugger

а она, в свою очередь вычисляет длину строки полмиллиона раз.

а зачем она это делает? данный регексп, который уже до этого скомпилировали и соответственно всё про него знаем, замечательно можно «наложить» на строку любой длины без вычисления длины этой строки. Так что тут имно виновата дефолтная реализация движка регэкспа, которая считает длину строки, когда этого делать совсем не обязательно.

vtVitus ★★★★★
()
Ответ на: комментарий от vtVitus

Так что тут имно виновата дефолтная реализация движка регэкспа, которая считает длину строки, когда этого делать совсем не обязательно.

Нет. Как справедливо указал камрад utf8nowhere: во-первых, регэкспы умеют работать со строками, содержащими нули, а во-вторых, возможность передать длину строки в regexec таки есть.

Так что если кто и виноват, так это тот, кто не читает маны, или читает их невнимательно.

debugger ★★★★★
()
Ответ на: комментарий от Iron_Bug

понятно. я всегда думала, что шланг - отстой. но что он настолько отстой, даже не догадывалась. я его даже не собираю у себя. только по работе его видела на серверах и он мне никогда не нравился.

При чём тут вообще компилятор?? Куда тебя вообще понесло? Весь затык был в библиотечной функии regexec (вернее, в её параметрах) из библиотеки glibc, которую используют и gcc, и clang. От компилятора в этом примере вообще ничего не зависит. Я собирал пример и gcc, и clang, и с -02 и с -O0 — разницы вообще никакой, все четыре варианта работают с одной и той же скоростью. Что не мудрено — код маленький, тривиальный, развернуться оптимизатору там просто негде.

ТС что-то напутал — забыл какой-нибудь объекник перекомпилять или екзешник пересобрать, поэтому у него поначалу и не взлетело.

Нравится clang или не нравится — это твоё личное дело, но напраслину на компилятор зачем наводить?

debugger ★★★★★
()
Ответ на: комментарий от debugger

Да вроде я ещё писал что strlen не нужен.

В musl, strlen в файле regexec.c не находится, зато находится проверка на '\0':

	  /* Check for end of string. */
	  if (next_c == L'\0')
		goto backtrack;

Взял оригинальный код:

$ musl-gcc -o count count.c && time ./count voyna-i-mir.fb2
Всего слов: 457206

real	0m0.277s
user	0m0.265s
sys	0m0.012s

Результата с GNU libc не стал дожидаться, грохнул:

$ gcc -o count count.c && time ./count voyna-i-mir.fb2
^C
real	0m11.078s
user	0m11.064s
sys	0m0.013s
utf8nowhere ★★★★
()
Ответ на: комментарий от utf8nowhere

у меня, кстати musl. я не думала, что это имеет какое-то критическое значение. хотя он вроде менее жирен, чем gcc, но и более аскетичен и некоторых фич в нём нет, приходится патчить софт под него.

Iron_Bug ★★★★★
()