Статьи

Еще более быстрый Java Expression Evaluator

Май 21, 2018

Я читал статью Как написать один из самых быстрых оценщиков выражений в статье на Java (также опубликованной в JCG ) и подумал про себя: есть еще более быстрый способ!

Таким образом, я установил тест Caliper, который вы можете проверить на моей учетной записи GitHub .

Бенчмарк компилирует производительность следующих библиотек:

Прежде чем перейти к результатам, пара общих слов о состоянии библиотек оценщиков выражений (с открытым исходным кодом) в Java (я не смог протестировать библиотеки с закрытым исходным кодом, потому что они налагают ограничения — например, «вычисляется только 15 выражений»), что делает его невозможным чтобы сравнить их):

  • Никто из них не находится в центральном Maven (или даже в Maven в этом отношении — за исключением Janino, но там вам все еще нужно другое репо, чтобы получить последнюю версию)
  • Их развитие в основном остановлено
  • Им не хватает функций и / или они глючат

Ориентир состоит в оценке 2 + (7-5) * 3.14159 * x + sin(0)выражения (аналогично оригинальной статье). К сожалению, часть возведения в степень пришлось исключить, потому что не все библиотеки поддерживают ее. Кроме того, x должен был быть установлен в 0, потому что parsii ошибочно всегда считает его нулевым.

Большинство библиотек (исключение составляют JEPLite и MathEval) разделяют идею «компиляции» и «оценки» выражения. Это может быть очень полезно, если мы хотим вычислить одно и то же выражение для множества значений содержащейся переменной. Таким образом, тест тестирует два случая: компилировать + оценивать и только оценивать (в зависимости от вашего варианта использования тот или иной вариант более уместен). Кроме того, Jeval по умолчанию исключен из теста, поскольку он работает так плохо, что затмевает все остальные результаты. Если вы хотите увидеть, насколько плохо он работает, раскомментируйте соответствующие методы из BenchmarkExpressionEvaluation.

Без лишних слов, вот результаты (чем меньше, тем лучше):

expression_evaluator_results

Как видите, пользовательская реализация превосходит парсию в 10 раз! Итак, как это работает? Вы всегда можете проверить исходный код , но я также объясню: он использует Janino для компиляции класса вида:

import static java.lang.Math.*; // to get sin, cos, etc

public static final class JaninoCompiledFastexpr1234 implements UnaryDoubleFunction {
    public double evaluate(double x) {
        return (/* your expression here */);
    }
}

который вы можете позже вызвать. Преимущества этого подхода:

  • грубая скорость — как вы можете видеть из теста, парсер / компилятор Java очень хорошо оптимизирован и его сложно превзойти, даже когда вы разбираете свой собственный парсер для подмножества случаев
  • сырая скорость во второй раз — JIT очень помогает нам и дает такие оптимизации, как постоянное свертывание или векторизация для «свободного»
  • краткость — все доказательство концепции реализовано в 60 строк, возможно, меньше строк, чем в этой статье
  • «Без мусора» — после начальной компиляции в куче не выделяются никакие ресурсы, а все параметры передаются в стек (так как они являются примитивами)

Разумеется, решение не лишено недостатков:

  • в зависимости от источника выражения мы можем  компилировать и выполнять произвольный код Java, отправленный нам злонамеренным пользователем . Не красивая перспектива. Мы пытаемся смягчить это двумя способами:

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

    • сам компилятор может иметь ошибки (это случалось в прошлом )
    • ни одна из мер безопасности не предотвращает потенциальный отказ в обслуживании (например, создание бесконечных циклов или использование всей памяти)
  • Кроме того, это просто подтверждение концепции — для более полного решения необходимо добавить больше интерфейсов (таких как BinaryDoubleFunction, TernaryDoubleFunction, а также UnaryLongFunction и т. д.), а также некоторые настройки, связанные с именованием параметров.

Тем не менее, это отличный пример силы экосистемы Java и того, чего можно достичь, немного подумав.

Если вы запустите тест для себя, вы можете найти пару интересных вещей:

  • тест «Янино» постоянно предупреждает о перекомпиляции. Это ожидаемо, если вы немного об этом думаете — поскольку при каждом вызове он «компилирует» выражение. То же самое относится и к JaninoFastexpr
  • и Janino, и JaninoPrecompiled жалуются на чрезмерную сборку мусора. Это потому, что они используют автобокс (varargs) для передачи параметров, что не очень эффективно (генерирует много мусора)

Вот и все, наслаждайтесь исходным кодом  и, надеюсь, это вдохновит людей на поиск лучших решений своих проблем!

39
Share: