Эффективное хранение в памяти и поиск классифицированных строковых литералов в C ++

Question

Примечание: это продолжение до этого вопроса .

У меня есть «устаревшая» программа, которая выполняет сотни совпадений строк с большими кусками HTML. Например, если HTML соответствует 1 из 20+ строк, сделайте что-нибудь. Если это соответствует 1 из 4 других строк, сделайте что-нибудь еще. Существует 50-100 групп этих строк для сопоставления с этими фрагментами HTML (обычно целыми страницами).

Я пытаюсь реорганизовать этот беспорядок кода и пытаюсь найти хороший подход для выполнения всех этих совпадений.

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

С учетом этих требований было бы наиболее эффективно, если бы только одна копия этих строк сохранялась в ОЗУ (см. Мой предыдущий вопрос, связанный выше).

Эта программа в настоящее время работает в Windows с компилятором Microsoft, но я хотел бы сохранить решение как можно более кроссплатформенным, поэтому я не думаю, что хочу использовать файлы ресурсов PE или что-то в этом роде.

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

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

Answer 1

Я не уверен, насколько медленной является текущая реализация.Поэтому трудно рекомендовать оптимизацию, не зная, какой уровень оптимизации необходим.

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

Тогда запуск вашего процесса должен состоятьчтения в основополагающем дереве и сопоставления.Если вы хотите / нуждаетесь в оптимизации хранения памяти в дереве, это можно сделать как отдельный проект, но для меня это звучит так, будто улучшение алгоритма сопоставления будет более эффективным использованием времени.В некотором смысле это идея «развернуть свою собственную систему регулярных выражений».Скорее похоже на предложение использовать генератор синтаксического анализатора.

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

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

Answer 2

Если строки, которые должны быть сопоставлены, могут быть заблокированы во время компиляции, вам следует рассмотреть возможность использования генератора токенизатора, например lex , для сканирования вашего ввода на совпадения. Если вы не знакомы с ним, lex берет исходный файл, который имеет некоторые регулярные выражения (включая самые простые регулярные выражения - строковые литералы) и код действия C, который будет выполняться при обнаружении совпадения. Он часто используется при сборке компиляторов и подобных программ, и есть несколько других подобных программ, которые вы также можете использовать (на ум приходят flex и antlr). lex создает таблицы конечных автоматов, а затем генерирует эффективный код C для сопоставления ввода с регулярными выражениями, которые представляют эти таблицы состояний (по умолчанию ввод является стандартным вводом, но вы можете изменить это). Использование этого метода, вероятно, не приведет к дублированию строк (или других данных) в памяти между различными экземплярами вашей программы, которых вы боитесь. Вероятно, вы могли бы легко сгенерировать регулярные выражения из строковых литералов в вашем существующем коде, но может потребоваться немало усилий, чтобы переработать вашу программу, чтобы использовать код, который lex генерировал.

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

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

"string1"
"string2"
"string3"

и ввод:

"string2"

Частичное совпадение для «строки» будет выполнено только один раз для системы регулярных выражений DFA (детерминированный конечный автомат) (например, lex ), которая, вероятно, ускорит вашу систему. Создание этих вещей требует большой работы от имени lex , но вся тяжелая работа выполняется заранее.

Answer 3

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

Существуют и другие приемы, позволяющие оптимизировать производительность ввода-вывода, например выделение больших страниц, но это зависит от размера файла и привилегий, предоставленных вашей программе.

Суть в том, что вам нужно экспериментировать, чтобы увидеть, что работает лучше всего, и не забывать измерять после каждого изменения:) ...