Кеширование отрезков charset'а.

[Valeriy Streltsov]

Originally reported on Google Code with ID 130

На данный момент charset реализован следующим образом. Внутри него в виде ДНФ хранятся
флаги. При матчинге дизъюнктов вызываются функции, возвращающие отрезки unicode-кодов.
То же самое происходит и при генерации следующего символа.

Предлагаю во флажках хранить сразу отрезки и пересекать их, а не ДНФ. Это дает преимущество:
с точки зрения отрезков не имеет значения что пересекать - та огромная таблица пересечений
перестанет быть нужной (пересечения для юникод-свойств она вообще не содержит, иначе
в ней было бы 10 000 элементов). Ну и код пересечения\отрицания отрезков проще и потенциально
будет иметь меньше багов. При этом во флажках останется информация о том, чем они были
изначально - для отладочной печати. По идее, это даже даст некоторый прирост производительности
в ДКА (поскольку будут пересекаться сразу отрезки, а не ДНФ перед ними).

Касательно структуры данных - элементарный отрезок представлен в виде array(int, int),
для флага требуется массив таких отрезков - как возвращается из preg_unicode. Преобразовать
массив отрезков в негативный вариант нетрудно - они изначально сгенерированы отсортированными,
и это будет сделано за O(n).

Интересует вопрос, как такой вариант совместим с ДКА, и мнения за\против.

Reported by vostreltsov on 2012-07-14 18:15:00

[Valeriy Streltsov]

Reported by `vostreltsov` on 2012-07-14 18:15:28

[Oleg Sychev]

``` А пересечение двух отрезков длиной N и M чему будет пропорционально? Вопрос не праздный, ибо N в некоторых юникод-свойствах немаленькое...

ДНФ для отладочной печати все равно надо пересекать, но можно обойтись без таблицы по идее... ```

Reported by `oasychev` on 2012-07-14 18:24:18

[Valeriy Streltsov]

``` По сути пересечение двух элементарных отрезков сводится к проверке, что левая часть правого находится внутри левого отрезка, а правая часть левого отрезка - внутри правого отрезка. Получается, нужно сделать N*M проверок для пересечения двух юникод-отрезков, или около того...

Я не думаю, что это будет сильно сказываться на производительности: тест на генерацию строки, состоящий из 80 символов, с юникод-свойством, posix-классом и \h работал меньше секунды. Аналогичный тест, но на матчинг символа, находящегося в конце отрезка юникод-свойства работал уже около 3 секунд, но если СРАЗУ пересечь отрезки (как при генерации) он тоже будет работать меньше секунды.

Вдобавок к этому я же уже написал, что пересечения и так вызываются при генерации символов - вопрос стоит о пересечении отрезков сразу, при первом обращении к флажку, и об удалении ДНФ как промежуточного звена... ```

Reported by `vostreltsov` on 2012-07-14 18:46:12

[Oleg Sychev]

``` Можно уменьшить учитывая что отрезки упорядочены, отсекая заведомо неподходящие и используя метод деления пополам для поиска подходящего места для пересечения. По идее что-то типа O(N*logM) должно быть почти достижимо. Аналогично матчинг.

В тесте было использовано юникод-свойство с самым большим количеством отрезков? Если произвольное, то это не показатель.

С ДНФ все не так просто. В ней в роли флажка может оказаться ассерт в ДКА - как вы его собираетесь в отрезок перевести? ```

Reported by `oasychev` on 2012-07-14 20:48:40 - Labels added: Component-Preg

[Valeriy Streltsov]

``` Я брал \p{C}, в котором 1000 или чуть больше отрезков, для матчинга брал последний символ из диапазонов - наихудший вариант.

Относительно ассертов - насколько я разобрался в коде, там сейчас параллельные массивы используются... Прямо оно не пересекается... ```

Reported by `vostreltsov` on 2012-07-14 20:52:53

[Oleg Sychev]

``` По результатам обсуждения было решено: 1) попадание символа во флаг со множеством отрезков реализовать дихотомичным поиском 2) пересечение и объединение множеств отрезков возможны за "примерно линейное" время, используя алгоритм аналогичный слиянию двух упорядоченных массивов; удобнее всего вид операции (объединение, пересечение или что еще) передавать в виде четырех логических флажков. 3) данные об отрезках дополнить списками флагов с заведомо пустым (или непустым, что короче суммарно выйдет) пересечением, который может быть легко сгенерирован и использован для упрощения ДНФ 4) хранить ли ДНФ или сразу вычислять отрезки решить после реализации пунктов 1-3.

```

Reported by `oasychev` on 2012-07-14 22:19:03

[Oleg Sychev]

``` Issue 76 has been merged into this issue. ```

Reported by `oasychev` on 2012-09-23 21:48:05

[Valeriy Streltsov]

``` Провел эксперимент с операцией. -пересечение 500 отрезков с 15 отрезками 30 раз заняло 1.1 секунды -пересечение 500 отрезков с 500 отрезками 30 раз заняло 1.9 секунды

500 отрезков это у нас максимум на одно юникод-свойство, и более 30 раз пересекать вряд ли придется... Вдобавок к этому, если будет несколько юникод-свойст в одном чарсете, они сразу объединятся и там будет около 10 отрезков в результате, что очень быстро будет пересекаться в дальнейшем. ```

Reported by `vostreltsov` on 2012-10-04 06:47:47

[Oleg Sychev]

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

Для начала не мешало бы кешировать результаты совпадения на случай наличия тождественных
узлов-листьев. Можно в статическом массиве в классе листа. Что можно использовать как
ключ? Userinscription?

Ну и в общем я бы склонялся к ленивому переводу в отрезки, т.к. не все узлы актуально
используются при матчинге. Разумеется, тот кошмар что в ДНФ надо переписать и привести
к человеческому виду. Только ивот его автор чего-то от меня скрывается. Дмитрий, что
там происходит?!

Reported by oasychev on 2012-10-10 07:44:37

[Valeriy Streltsov]

Я потратил вечер на набросок чарсета без ДНФ и прогнал все тесты. Вот результаты:

С ДНФ:
NUMBER OF PASSED REGEX-STRING PAIRS: 1669
NUMBER OF FAILED REGEX-STRING PAIRS: 65

Time: 13 seconds, Memory: 75.25Mb

Без ДНФ:
NUMBER OF PASSED REGEX-STRING PAIRS: 1675
NUMBER OF FAILED REGEX-STRING PAIRS: 59

Time: 10 seconds, Memory: 73.00Mb

Т.е. прирост скорости 23%, кода значительно меньше и он проще.
Изменения можно посмотреть в клоне: http://code.google.com/r/vostreltsov-preg-24-ranges/source/detail?r=f41edfd044f74941cdea823eab3d2cacb7bd7617

Reported by vostreltsov on 2013-01-02 09:37:19

[Oleg Sychev]

А вариант с ДНФ но без ее оптимизации пробовали? Надо точно выяснить источник заразы...


И для ДКА матчера тоже надо замеры производить, у него может быть отличное от НКА распределение...

Reported by oasychev on 2013-01-02 10:37:40

[Valeriy Streltsov]

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

Reported by vostreltsov on 2013-01-02 11:30:01

[Oleg Sychev]

А что за 6 тестов которые начинают проходить без ДНФ? Можете хоть один найти?

Reported by oasychev on 2013-01-02 11:35:09

[Valeriy Streltsov]

Я параллельно пофиксил ошибку в лексере, которая у нас под номером 4.

Reported by vostreltsov on 2013-01-02 11:37:38

[Oleg Sychev]

Я бы минимизацию ДНФ убрал, а вот с самой - не торопился.

Эксперимент пока не очень показателен: сейчас не активно используется пересечение -
ни НКА (при ассертах), ни ДКА (при ЧСК) - а это планируется сделать. По ДКА замеры
тоже не сделаны.  В итоге мы имеем замеры только на НКА без пересечения, а это тот
случай когда ДНФ нужна меньше всего.

Предлагаю сделать функцию в матчере use_dnf() в зависимости от которой она использовалась
бы или нет...

И кстати еще одной частью "нормального" чарсета должно бы быть кеширование сложных
чарсетов - например по userinscription, чтобы если юзер один чарсет несколько раз написал
(или они от конечного квантификатора размножились), не строить отрезки каждый раз...

Reported by oasychev on 2013-01-02 13:24:50

[Valeriy Streltsov]

Ну, вообще говоря, универсальная операция активно использовалась при создании чарсета
- каждая новая часть добавлялась объединением. И при этом оно все-таки работало быстрее.

Reported by vostreltsov on 2013-01-03 19:31:53

[Oleg Sychev]

Ну что вам так хочется ее поскорее прибить вовсе? Слить ветки сложно? Восстановить сложнее
будет если понадобится, а убрать использованием специальной функции в матчере практически
не скажется на производительности - НКА будет работать без ДНФ. Количество пересечений
при построении ДКА может быть намного выше, чем относительно небольшое количество объединений
в чарсетах. А вы даже текущий вариант ДКА не замерили. Зато мы сможем потом, реализовав
ассерты (и, возможно, ДКА в новом варианте) произвести серию замеров и поставить хоть
условие - при наличии ассертов использовать ДНФ, при отсутствии - нет. Или еще как-то.
Есть предложение отложить этот вопрос на следующую предрелизную подготовку, сейчас
есть конкретно ситуация, где оно мешает? Интерфейс чарсета внешний должен быть одинаков,
а как он внутри работает - его проблемы. Оптимизацию ДНФ удаляем, и необходимый ей
страшноватый массив - тоже. Остается не так много кода...

Лучше бы проблемы 1-3 отладили, там ведь баги скорее всего.

P.S. Что мне не нравится в двух последних коммитах. Во-первых, нет описания того, в
чем состоял баг. Во-вторых, нет добавленных юнит-тестов на случаи багов, ведь прежними
то тестами они не были замечены. Добавление тестов гарантирует нас от повторного возникновения
этих багов...

Reported by oasychev on 2013-01-06 16:47:02

[Oleg Sychev]

Консенсус по ДНФ достигнут, оптимизация с ее сложным аппаратом удалена.

Но issue не закрываю в связи с тем, что над "нормальным" чарсетом еще стоит поработать.
Для сложных чарсетов может оказаться полезным кеширование. Но необязательно браться
за него прямо сейчас...

Reported by oasychev on 2013-01-06 18:38:20

[Oleg Sychev]

Вопрос еще - операция объединения для чарсетов может быть нужна?

Reported by oasychev on 2013-01-27 15:54:53

[Oleg Sychev]

Issue 35 has been merged into this issue.

Reported by oasychev on 2013-01-27 15:55:44

[Valeriy Streltsov]

Сделал тест скорости юникод-пересечений. 600 с 500 отрезками пересекаются 100 раз за
12 секунд, т.е. 0.12 секунды на одно пересечение. Тестировал на виртуалке, которой
отдал одно 3 ГГц ядро. Думаю, что имеет смысл разбить этот метод на пересечение и объединение
отдельно, потому что их можно будет оптимизировать - вроде бы в 2 раза меньше шагов
по массивам будет (сейчас берется всегда минимальный шаг до след. общей точки; для
объединения можно брать наоборот максимальный шаг, а для пересечения взятый отрезок
может не попадать на параллельный массив, это тоже можно оптимизировать).

Касательно скорости матчинга: пересечение отрезков и затем 10000 матчингов заняли 1
секунду; пересечение ДНФ (пренебрежимое, из 2 узлов) и 10000 матчингов заняли 3 секунды.

Reported by vostreltsov on 2013-03-03 15:50:38

[Oleg Sychev]

А при пересечении ДНФ отрезки вычислялись каждый раз при матчинге или только однажды?

Reported by oasychev on 2013-03-03 19:30:40

[Valeriy Streltsov]

Пока что каждый раз, т.к. это было бы переписывание кода узлов, я пока не хотел трогать

Reported by vostreltsov on 2013-03-03 19:32:06

[Oleg Sychev]

Тогда мы не можем судить об эффективности ДНФ по этим результатам, условия не равны.
Надо пересечь ДНФ и вычислять отрезки при первом матчинге, после чего - кешировать
- о том и issue.

Но на таком тесте тогда особой разницы не будет. Нужны более комплексные тесты для
таких выводов...

Reported by oasychev on 2013-03-03 19:34:02

[Valeriy Streltsov]

Кэширование уже давным-давно реализовано и работает.

Reported by vostreltsov on 2014-12-04 18:35:42 - Status changed: Done