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

Question

Примечание: Это продолжение до this question.

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

"string1" 
"string2" 
"string3" 

и вход:

"string2" 

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