Быстрый анализатор логических выражений

У меня есть приложение, которое включает в себя оценщик логических выражений с тремя операторами (& | !) с переменными и константами. Как правило, выражения не слишком длинные (возможно, максимум 50 терминов, но обычно намного меньше). Выражений может быть очень много — я ожидаю, что верхний предел будет около миллиона. В настоящее время у меня есть написанный от руки синтаксический анализатор с очень простым оценщиком, который просто рекурсивно обходит дерево синтаксического анализа. Одним из ограничений является то, что это должно вызываться из C++. У меня нет разделения между выражениями. Я хотел бы исследовать ускорение этого.

Я вижу два направления исследований.

  1. Добавьте совместное использование и сохраните состояние, указывающее, был ли оценен узел выражения или нет.
  2. Извлечь общие подвыражения.

Также я ожидаю, что подход с генерацией кода будет быстрее, чем подход с интерпретацией, работающий с деревьями синтаксического анализа или подобными структурами. Вероятно, было бы довольно просто сгенерировать некоторый код C++, но, учитывая длину функций, я не знаю, сможет ли такой компилятор, как GCC, оптимизировать CSE.

Я видел, что есть несколько библиотек, доступных для оценки выражений, но в моей рабочей среде добавление сторонних библиотек не так просто, и все они кажутся очень сложными по сравнению с моими потребностями.

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

Любые предложения, по какому пути идти?


antlr4 llvm expression-evaluation
person Paul Floyd    schedule 25.05.2017    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

Таким образом, чтобы ускорить ваши оценки, вы можете рассмотреть JIT-выполнение ваших формул с использованием LLVM. То есть, учитывая вашу формулу F, вы можете (относительно) легко сгенерировать соответствующий LLVM IR и напрямую оценить его. Этот решатель SMT делает именно это. Генерация кода IR реализована в одном классе C++ здесь. Обратите внимание, что упомянутые вами логические выражения являются подмножеством языка SMT, поддерживаемого этим решателем. Кроме того, вы можете легко настроить, насколько агрессивным должен быть оптимизатор LLVM.

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

person Codoka    schedule 26.05.2017

arrow_upward
1
arrow_downward

Как бы я ни хотел предложить ANTLR4, я боюсь, что он не удовлетворит ваши потребности в производительности. Под капотом его адаптивных алгоритмов LL(*) происходит много всего, и хотя есть некоторые общие приемы для повышения его производительности, простое отслеживание интерпретатора ANTLR4 во время выполнения предполагает, что если ваш текущий оценщик выражений не очень неэффективен, он, вероятно, быстрее, чем ANTLR4, промышленный движок, предназначенный для поддержки грамматик, намного более сложных, чем ваша. Я использую ANTLR, когда движок LALR(1) DFA с уменьшением сдвига не поддерживает мою грамматику, и получаю снижение производительности в обмен на дополнительную мощность синтаксического анализа ANTLR4.

person TomServo    schedule 25.05.2017
comment
Время выполнения parse и lex не должно быть проблемой. Это отдельная фаза от оценки, которая выполняется неоднократно, потенциально с продолжительностью выполнения в несколько дней. Таким образом, фаза parse lex даже в несколько часов не будет проблемой. Скорость оценки является ключевым моментом. - person Paul Floyd; 26.05.2017
comment
Ах я вижу. Тогда неправильно понял ваш вопрос. Оценка в ANTLR может быть весьма эффективной. Существует грамматика под названием Mu, которую я использовал в качестве основы для интерпретатора выражений во время выполнения. ссылка. - person TomServo; 27.05.2017