Эффективное хранение в памяти и поиск классифицированных строковых литералов в C++
Примечание: это продолжение этого вопроса.
У меня есть "устаревшая" программа, которая выполняет сотни совпадений строк с большими кусками HTML. Например, если HTML соответствует 1 из 20+ строк, сделайте что-нибудь. Если это соответствует 1 из 4 других строк, сделайте что-нибудь еще. Существует 50-100 групп этих строк для сопоставления с этими кусками HTML (обычно целыми страницами).
Я стараюсь реорганизовать этот беспорядок кода и пытаюсь найти хороший подход для выполнения всех этих совпадений.
Требования к производительности этого кода довольно строгие. При выполнении этих совпадений не нужно ждать ввода-вывода, поэтому они должны находиться в памяти. Также может быть запущено более 100 копий этого процесса, поэтому большой ввод-вывод при запуске может вызвать медленный ввод-вывод для других копий.
Учитывая эти требования, было бы наиболее эффективно, если бы только одна копия этих строк была сохранена в ОЗУ (см. Мой предыдущий вопрос, связанный выше).
Эта программа в настоящее время работает на Windows с компилятором Microsoft, но я хотел бы сохранить решение как можно более кросс-платформенным, поэтому я не думаю, что хочу использовать файлы ресурсов PE или что-то подобное.
Преобразование внешнего файла может работать, но тогда у меня возникает проблема синхронизации версии программы и версии данных, одна из которых обычно не меняется без другой. Также для этого требуется некоторый "формат" файла, который добавляет уровень сложности, который я бы предпочел не иметь.
Так что после всего этого преамбулы кажется, что лучшим решением будет иметь множество массивов строк, которые я затем смогу перебрать. Это выглядит немного грязно, так как я сильно смешиваю код и данные, но с учетом вышеуказанных требований есть ли лучший способ справиться с такой ситуацией?
3 ответа
Я не уверен, насколько медленной является текущая реализация. Поэтому трудно рекомендовать оптимизацию, не зная, какой уровень оптимизации необходим.
Однако, учитывая это, я мог бы предложить двухэтапный подход. Возьмите ваш список строк и скомпилируйте его в основополагающее дерево, а затем сохраните это дерево в каком-то произвольном формате (XML может быть достаточно для ваших целей).
Тогда запуск вашего процесса должен состоять из чтения в основном дереве и сопоставления. Если вы хотите / нуждаетесь в оптимизации хранения памяти в дереве, это можно сделать как отдельный проект, но для меня это звучит так, будто улучшение алгоритма сопоставления будет более эффективным использованием времени. В некотором смысле это идея "брось свою собственную систему регулярных выражений". Скорее похоже на предложение использовать генератор парсера.
Изменить: я использовал что-то похожее на это, где, в качестве шага перед компиляцией, пользовательский сценарий генерирует несколько оптимизированную структуру и сохраняет его в большой массив char*. (очевидно, он не может быть слишком большим, но это еще один вариант)
Идея состоит в том, чтобы сохранить этот список (что делает обслуживание достаточно простым), но шаг предварительной компиляции ускоряет доступ во время выполнения.
Если строки, которые должны быть сопоставлены, могут быть заблокированы во время компиляции, вам следует рассмотреть возможность использования генератора токенизатора, такого как lex, для сканирования вашего ввода на совпадения. Если вы не знакомы с ним, lex берет исходный файл, в котором есть некоторые регулярные выражения (включая самые простые регулярные выражения - строковые литералы) и код действия C, который будет выполняться при обнаружении совпадения. Он часто используется при сборке компиляторов и подобных программ, и есть несколько других подобных программ, которые вы также можете использовать (на ум приходят flex и antlr). lex создает таблицы конечных автоматов, а затем генерирует эффективный код C для сопоставления ввода с регулярными выражениями, которые представляют эти таблицы состояний (по умолчанию ввод является стандартным вводом, но вы можете изменить это). Использование этого метода, вероятно, не приведет к дублированию строк (или других данных) в памяти между различными экземплярами вашей программы, которых вы боитесь. Вероятно, вы могли бы легко сгенерировать регулярные выражения из строковых литералов в вашем существующем коде, но может потребоваться немало усилий, чтобы переработать вашу программу, чтобы использовать код, сгенерированный lex.
Если строки, которым вы должны соответствовать, меняются со временем, есть некоторые библиотеки регулярных выражений, которые могут компилировать регулярные выражения во время выполнения, но они действительно используют много оперативной памяти, и в зависимости от архитектуры вашей программы они могут дублироваться в разных экземплярах программы.
Хорошая вещь об использовании подхода регулярных выражений, а не много strcmp звонки в том, что если у вас были шаблоны:
"string1"
"string2"
"string3"
и вход:
"string2"
Частичное совпадение для "строки" будет выполнено только один раз для системы регулярных выражений DFA (детерминированный конечный автомат) (например, lex), которая, вероятно, ускорит вашу систему. Создание таких вещей требует большой работы от имени lex, но вся тяжелая работа выполняется заранее.
Эти литеральные строки хранятся в файле? Если это так, как вы предложили, лучшим вариантом может быть использование файлов с отображенной памятью для совместного использования копий файла в сотнях экземпляров программы. Кроме того, вы можете попытаться настроить размер рабочего набора, чтобы попытаться уменьшить количество сбоев страниц, но, учитывая, что у вас так много экземпляров, это может оказаться контрпродуктивным (и, кроме того, ваша программа должна иметь квота привилегий для настройки размера рабочего набора).
Есть и другие приемы, которые вы можете попытаться оптимизировать производительность ввода-вывода, такие как выделение больших страниц, но это зависит от размера вашего файла и привилегий, предоставленных вашей программе.
Суть в том, что вам нужно экспериментировать, чтобы увидеть, что работает лучше всего, и не забывать измерять после каждого изменения:)...