Понимание производительности алгоритма Phreak - PullRequest
0 голосов
/ 23 марта 2020

Я пытаюсь понять, что заставляет Drools работать плохо в нашем случае. Я прочитал документацию по Phreak здесь: https://access.redhat.com/documentation/en-us/red_hat_decision_manager/7.4/html/decision_engine_in_red_hat_decision_manager/phreak-algorithm-con_decision-engine

Кажется, ничего не говорится о том, как выполняются переходы между узлами. Вот пример, чтобы объяснить, что я имею в виду под этим:

Допустим, у меня есть объект Person с тремя полями: name, lastName, SSN

Таким образом, я определяю большое количество правил: когда lastName = 'Smith' и SSN = 'XXXXXXXXXX', затем name = "Jane". Предполагая, что у меня есть большое количество людей с фамилией «Смит», скажем, 10000, какова сложность получения одного имени с фамилией и SSN? Это займет 10 000 сравнений, или узел «Смит» сохранит некоторую форму карты ha sh со всеми базовыми SSN?

Что если вместо SSN с оператором равенства я использовал диапазон, например например, диапазон дат, определяющий правила, подобные этому: «when lastName = 'Smith' и StartShool> = 2005 и FinnSchool <= 2010". Сохраняют ли узлы некоторую причудливую структуру данных для ускорения запросов с операторами диапазона? </p>

РЕДАКТИРОВАТЬ: По запросу я добавляю пример, чтобы объяснить, как устанавливаются правила

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

Это пример двух правил с возрастающей значимостью. Мы определяем ~ 10K из них.

Можно представить своего рода древовидную структуру, в которой на каждом уровне увеличивается значимость и условия становятся более строгими. Класс Evidence функционирует как своего рода пара ключ-значение, поэтому у многих из них будет один и тот же общий узел (например, name = location).

Чтобы выполнить правила, мы бы добавили два доказательства (например, [ name = location, stringValue = 'BBB'] и [name = code, stringValue = theCode]) и запускают правила.

rule "RULE 1::product"
    salience 0
    activation-group "product"
when
    $outputs : EvidenceSet.Builder(  )  

    Evidence( name == "location" && stringValue == "BBB" )   
then
    $outputs.addEvidences(Evidence.newBuilder().setName("Product").setStringValue("999"));


end

rule "RULE 2::product"
    salience 1
    activation-group "product"
when
    $outputs : EvidenceSet.Builder(  )  

    Evidence( name == "location" && stringValue == "BBB" )   

    Evidence( name == "code" && stringValue == "thecode" )   
then
    $outputs.addEvidences(Evidence.newBuilder().setName("Product").setStringValue("777"));


end

1 Ответ

0 голосов
/ 29 марта 2020

Вот шаблон правил

rule "RULE %s::product"
when
    $outputs : EvidenceSet.Builder(  )  
    Evidence( name == "location" && stringValue == "BBB" ) 
    Evidence( name == "code" && stringValue matches ".*code.*" )
then
    $outputs.addEvidences(Evidence.newBuilder().setName("Product").setStringValue("777"));
end

Вот код, который построил 10000 правил drl из шаблона

public static void main(String[] args) throws IOException {
    String template = Resources.toString(Resources.getResource("template.drl"), Charset.defaultCharset());

    try (PrintStream file = new PrintStream(new File("test.drl"))) {
        for (int i = 0; i < 10_000; i++)
            file.println(String.format(template, i));
    }
}

Вот классы доменов, основанные на вашем синтаксисе drl, исключая equals, hashCode и toString, выглядит странно для меня ...

public class Evidence {
    public String name;
    public String stringValue;

    public Evidence() {
    }

    public Evidence(String name, String stringValue) {
        this.name = name;
        this.stringValue = stringValue;
    }

    public static Builder newBuilder() {
        return new Builder();
    }
}

public class EvidenceSet {
    public static Set<Evidence> evidenceSet = new HashSet<>();

    public static class Builder {
        public Evidence evidence = new Evidence();

        public Builder setName(String name) {
            evidence.name = name;
            return this;
        }

        public Builder setStringValue(String stringValue) {
            evidence.stringValue = stringValue;
            return this;
        }

        public void addEvidences(Builder builder) {
            evidenceSet.add(builder.evidence);
        }
    }
}

Вот тест, который выполняет файл правил 10k

@DroolsSession("classpath:/test.drl")
public class PlaygroundTest {

    private PerfStat firstStat = new PerfStat("first");
    private PerfStat othersStat = new PerfStat("others");
    @Rule
    public DroolsAssert drools = new DroolsAssert();

    @Test
    public void testIt() {
        firstStat.start();
        drools.insertAndFire(new EvidenceSet.Builder(), new Evidence("location", "BBB"), new Evidence("code", "thecode"));
        firstStat.stop();

        for (int i = 0; i < 500; i++) {
            othersStat.start();
            drools.insertAndFire(new Evidence("code", "code" + i));
            othersStat.stop();
        }

        System.out.printf("first, ms: %s%n", firstStat.getStat().getAvgTimeMs());
        System.out.printf("others, ms: %s%n", othersStat.getStat().getAvgTimeMs());
        System.out.println(EvidenceSet.evidenceSet);
    }
}

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

Тест без раздела «for» дает следующий результат профилирования profile1.png

«Победитель» - org.drools.core.rule.JavaDialectRuntimeData.PackageClassLoader.internalDefineClass который создает и регистрирует автоматически сгенерированный java класс для drools затем block, что является тяжелой операцией.

Тест с разделом 'for' дает совершенно другую картину profile2.png

Примечание internalDefineClass остается прежним, и выполнение тестового кода становится заметным. Потому что классы по 10 тысяч правил были загружены, и это заняло 12,5 секунд на моей машине с 12 процессорами. После этого все остальные вставки были выполнены в avg. 700 мс Давайте проанализируем это время.

Затем блок правил выполняется в среднем 0,01 мс.

RULE 9::product - min: 0.00 avg: 0.01 max: 1.98 activations: 501

10000 RHS * 0,01 мс = 100 мс - это время, которое требуется по правилам 10k для выполнения следующих

$outputs.addEvidences(Evidence.newBuilder().setName("Product").setStringValue("777"));

Создание фиктивного объекта и манипулирование им становится заметным, поскольку вы умножаете его на 10k. По результатам второго профилирования производительности большую часть времени он выводил вывод консоли тестера на консоль. И всего 100 мс. Выполнение RHS довольно быстро, принимая во внимание грубое создание объектов, чтобы служить парадигме «строителя».

Чтобы ответить на ваш вопрос, я бы предположил и предложил следующие вопросы:

  1. Вы не можете повторно использовать сессию скомпилированных правил.

  2. Это может быть недооценено, тогда блокируйте время выполнения, если у вас есть фиктивный String.format где-то в RHS, это будет заметно для общего времени выполнения только потому, что формат сравнительно медленный и вы имеете дело с 10k выполнений.

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

  4. Если вы используете сеанс statefull (Я почему-то догадываюсь, что вы этого не делаете, и это root причина проблемы). Я не вижу очистки памяти и удаления объектов. Что может вызвать проблемы с производительностью до OOME. Вот след памяти выполнения ...

profile3

Если предыдущая проблема не решила, я все же прошу вас предоставить рабочий пример теста, который воспроизводит проблему. Работа означает, что можно скопировать и запустить it.


day2 ... декартовы спички

Я удалил фреймворк и проверил декартовы совпадения

@Test
public void testIt() {
    firstStat.start();
    drools.insertAndFire(new EvidenceSet.Builder(), new Evidence("location", "BBB"), new Evidence("code", "thecode"));
    firstStat.stop();

    for (int i = 0; i < 40; i++) {
        othersStat.start();
        drools.insertAndFire(new Evidence("location", "BBB"), new Evidence("code", "code" + i));
        othersStat.stop();
    }

    drools.printPerformanceStatistic();
    System.out.printf("first, ms: %s%n", firstStat.getStat().getAvgTimeMs());
    System.out.printf("others, ms: %s%n", othersStat.getStat().getAvgTimeMs());
    System.out.println(EvidenceSet.evidenceSet);
}

Обратите внимание, что мы вставляем new Evidence("location", "BBB") каждую итерацию. Я смог выполнить тест с 40 итерациями только в противном случае я в конечном итоге с OOME (что-то новое для меня). Вот потребление ЦП и памяти для 40 итераций:

prifile4

Каждое правило было запущено 1681 раз! RHS в среднем время не заметно (оптимизировано и удалено из выполнения?), но когда блок был выполнен ...

RULE 999::product - min: 0.00 avg: 0.00 max: 1.07 activations: 1681
RULE 99::product - min: 0.00 avg: 0.00 max: 1.65 activations: 1681
RULE 9::product - min: 0.00 avg: 0.00 max: 1.50 activations: 1681
first, ms: 10271.322
others, ms: 1614.294

После удаления декартового соответствия тот же тест выполняется намного быстрее и без памяти и G C проблема

RULE 999::product - min: 0.00 avg: 0.04 max: 1.27 activations: 41
RULE 99::product - min: 0.00 avg: 0.04 max: 1.28 activations: 41
RULE 9::product - min: 0.00 avg: 0.04 max: 1.52 activations: 41
first, ms: 10847.358
others, ms: 102.015

profile5

Теперь я могу увеличить количество итераций до 1000, а среднее время выполнения итерации еще меньше

RULE 999::product - min: 0.00 avg: 0.00 max: 1.06 activations: 1001
RULE 99::product - min: 0.00 avg: 0.00 max: 1.20 activations: 1001
RULE 9::product - min: 0.00 avg: 0.01 max: 1.79 activations: 1001
first, ms: 10986.619
others, ms: 71.748

Вставка фактов без отвода будет иметь ограничения, хотя

profile5

Резюме: вам нужно убедиться, что вы не получите декартовы спички.


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

Добавление метода в Evidence class

public boolean isDuplicate(Evidence evidence) {
    return this != evidence && hashCode() == evidence.hashCode() && equals(evidence);
}

Добавьте правило с наибольшим значением

rule "unique known evidence"
salience 10000
when
    e: Evidence() 
    Evidence(this.isDuplicate(e))
then
    retract(e);
end

Это было проверено и, как оказалось, работало в предыдущем тесте junit, который воспроизводил декартову проблему. Интересно, что для самого теста (1000 итераций, 1000 правил) метод isDuplicate вызывался 2008004 раза, а общее время, затраченное на все вызовы, составило 172,543 мс. на моей машине. RHS правила (отвод событий) занимал как минимум в 3 раза больше времени, чем другие правила (сбор доказательств).

RULE 999::product - min: 0.00 avg: 0.00 max: 1.07 activations: 1001
RULE 99::product - min: 0.00 avg: 0.01 max: 1.81 activations: 1001
RULE 9::product - min: 0.00 avg: 0.00 max: 1.25 activations: 1001
unique known evidence - min: 0.01 avg: 0.03 max: 1.88 activations: 1000
first, ms: 8974.7
others, ms: 69.197
...