Оболочки / Регулярные выражения внутри bash

в 3:09, , рубрики: Новости, метки: , , ,

    Занялся я как-то оптимизацией скорости работы своего скрипта. Алгоритм был уже вовсю отполирован, распараллелен и выполнялся уже более чем за сносное время. Лишь изредка, облизывая части кода, шебурша места, использующие внешние команды и приводя в благоухающую гармонию встроенными командами оболочки, обращал внимание на застоявшуюся роль труженика — потокового редактора sed, всё так же старательно обрабатывавшего регулярные выражения в моём расцветающем скрипте.
Существует множество мест, где люди грызут друг другу глотки и отстаивают честь своего любимого редактора в грозной войне sed vs awk vs grep vs …
Тем не менее, большинство знает, что замена вызовов внешних команд на внутренние зачастую значительно ускоряет критические места скрипта, заставляет улыбаться автора, тратя меньше его времени на ожидание за чашкой кофе «пока закончится обработка». Это, в некотором смысле, некоторая неадекватность, если он знает язык Си и может значительно ускорить программу переписыванием кода на Сях; но не следует сразу записывать его в сумасшедшие — некоторые скрипты довольно объемны для переноса кода и используют различные команды, заставляя код пухнуть от нахальных вставок системных вызовов exec().
    Итак, как бы то ни было, разработчики bash третьей версии наделили нас возможностью пользоваться встроенными регулярными выражениями внутри команды [[ при помощи =~.
Большинство результатов на гугление про такую способность bash выносят один и тот же вердикт — «пользоваться регулярными выражениями внутри bash — моветон».
В данной статье я попытаюсь вынести вердикт, насколько всё плохо (а оно действительно как-то нехорошо).
Данные для обработки

    После некоторых опытов у меня осталась база данных автомобилей, содержащая данные про марки, модели и их модификации в формате CSV. Файл достаточно большой для любителей электронных книг в текстовых форматах, приблизительно 1 Мб, т.е. предоставляет некоторый простор для воображения и придумывания своей выборки, позволяя так же оценить работу regex на файлах, больших, чем коротенькие.
Итак, предположим, что я садовник Френк, решивший купить себе Bugatti (выбор пал на неё из-за того, что в несколько старой базе всего 4 машины данной марки; а, кроме того, какому садовнику не хочется выйти со своими саженцами не из переполненного автобуса, а из знаменитой марки, очаровывая местных красавиц).
В используемой базе данных машины отсортированы по марке (хотя, для достоверности тестов сортировка в последствии произведена по модельному году. Фрагмент БД, используемый в тестах:"Модификация";"Цена от";"Скорость (км/ч)";"Разгон (сек до 100км/ч)";"Объем двигателя (см^3)";"Мощность (л.с./об. мин)";"Расход (л на 100 км)";"Тип кузова";"Длина (мм)";"Ширина (мм)";"Высота (мм)";"Модельный год";"Количество дверей";"Количество мест";"Объём багажника (л)"
...
"Brilliance M3 1.8";"-";"210";"10.1";"1793";"170/5500";"7.7";"Купе";"4488";"1812";"1385";"2008";"3";"4";"400"
"Bugatti Veyron EB 16.4";"43 968 000";"407";"3";"7993";"1001/6000";"24.1";"Купе";"4465";"2000";"1205";"2006";"2";"2";"-"
"Bugatti EB 110 GT";"-";"340";"3.6";"3500";"559/8000";"14.3";"Купе";"4400";"1960";"1125";"1991";"2";"2";"72"
"Bugatti EB 110 S";"-";"350";"3.4";"3500";"620/8000";"13.5";"Купе";"4400";"1960";"1125";"1991";"2";"2";"72"
"Bugatti EB 112 6.0";"-";"300";"4.7";"5995";"461/6300";"18.2";"Седан";"5070";"1960";"1405";"1993";"4";"4";"365"
"Buick Enclave CX";"-";"180";"-";"3564";"279/6600";"-";"Кроссовер";"5126";"2006";"1846";"2007";"5";"8";"535-3259"
...
Поставленная задача эксперимента — оценить скорость выборки строк с маркой Bugatti встроенными в bash регулярными выражениями. Ленивые обратят внимание, что это возможно сделать без regexp одной командой:grep Bugatti auto.csv
Но, ситуация выдуманная для теста, а не для реального применения — действительно, какому садовнику хватит на Bugatti?
Метод тестирования

    Сравнение производительности заключается в сравнении результатов команды time для функции, где используются встроенные регулярные выражения и для функции, использующей потоковый редактор sed. (возможно выбрать любой другой, но мне он симпатичен).
Для упрощения, испытуемые получают данные, уже считанные из файла в первый параметр, а записывают результаты в глобальный массив tmp.
Итак, функция, использующая возможности редактора sed выглядит так:function test_sed()
{
    OLD_IFS=IFS
    IFS=$'n'
    tmp=($(sed -n '/.*(Bugatti[^n]*)/s//1/p' <<< "$1"))
    IFS=OLD_IFS
}
Необходимо отметить, что шаблон регулярного выражения предоставляет простор для воображения, можно использовать символы, обозначающие начало и конец строки, или вовсе придумать совершенно иной шаблон.
Усреднённый результат тестирования на моём оборудовании выглядит следующим образом:real 0m0.805s
user 0m0.719s
sys 0m0.082s
От встроенных в bash регулярных выражений ожидается значительное уменьшение времени затрат на системные вызовы и некоторое снижение общего времени теста.
Функция test_bash_rematch

    Некоторое время потрачено на написание функции, тестирующей regexp в bash, поэтому следует описать встреченные мной препятствия.
Общий вид поиска по шаблону в bash третьей версии выглядит так: [[ $str =~ "$regex" ]]
Результат команды — 0, если выражение, соответствующее шаблону найдено, 1 — когда не найдено и 2 — при неверно написанном шаблоне. Найденное совпадение с шаблоном записывается в массив S{BASH_REMATCH} (с индексом 0 — для той части, что совпадает со всем шаблоном и с индексами групп, в порядке их появления в шаблоне.
Первое встреченное препятствие — начиная с некоторой версии шаблон не нужно заключать в кавычки, чего я проглядел в man bash.
Второй подводный камень — используется POSIX для regex, а жадная и ленивая квантификация у меня не работают.
И, наконец, водоворот, который существенно замедляет продвижение — результатом поиска по шаблону может быть как первое совпадение с шаблоном, так и любое последующее (это вам не потоковый редактор, который ищет в файле строчку за строчкой до первого совпадения).
В результате тестирование велось с использованием следующих двух функций:function test_bash_rematch_single()
{
    [[ "$1" =~ (Bugatti[[:alpha:][:digit:][:punct:][:blank:]]*) ]] && tmp[0]="${BASH_REMATCH[1]}"
}
Ищет одно совпадение с шаблоном, усреднённые результаты тестирования:real 0m0.678s
user 0m0.624s
sys 0m0.030s
Лучше, чем для sed, но оно и понятно — пока только одно совпадение с шаблоном.
И вторая функция, использующая встроенную команду read и цикл:function test_bash_rematch_while()
{
    i=0
    while read line
    do
        [[ "$line" =~ (Bugatti.*) ]] && tmp[i]="${BASH_REMATCH[1]}" && ((i++))
    done <<< $1
}
С результатами:real 0m1.523s
user 0m1.360s
sys 0m0.030s
Вывод

    Как видно из результатов, время, затрачиваемое на обработку системных вызовов при использовании встроенных в bash регулярных выражений действительно снижается. Но, на данный момент bash версии 4.1.5(1) осуществляет поиск по шаблону весьма неторопливо, что исключает использование встроенных bash regexp в критических местах, а там, где время выполнения не имеет значения так же не следует использовать встроенные в bash регулярные выражения, так как это снижает переносимость между оболочками, а плюсов не даёт.
P.S.

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

Поделиться

* - обязательные к заполнению поля