Bavet - How much faster does it make OptaPlanner for you?

[Geoffrey De Smet]

Hi all,

We developed a faster score calculation engine for OptaPlanner called Bavet.
It is feature complete in OptaPlanner 8.27.0.Final, which is available on Maven Central now.

We need your help to make OptaPlanner better.

According to our benchmarks, Bavet makes OptaPlanner 2.3x faster on average,
but we'd love to know that turns out for you.
Let us know your score calculation speed before and after Bavet.

Specifically, here's how you can help us:

1. Upgrade to OptaPlanner 8.27.0.Final
2. Solve your use case for a minute.
  Get the "score calculation speed" of Drools from the log:
    INFO  Solving ended: time spent (...), best score (...), score calculation speed (10000/sec), ...
3. Switch the ConstraintStreamImplType to BAVET. This is a one-line change. See below.
  Solve it again for the same time.
  Get the "score calculation speed" of Bavet from the log.
    INFO  Solving ended: time spent (...), best score (...), score calculation speed (23000/sec), ...

Then let us know both score calculation speed numbers.
Hopefully you see the same speedup as us!

Switching to Bavet is a one-line change:

Plain java: Switch to Bavet in either your *.java file:

SolverFactory<TimeTable> solverFactory = SolverFactory.create(new SolverConfig()
        ...
        .withConstraintStreamImplType(ConstraintStreamImplType.BAVET)
        ...);

or in your solverConfig.xml:

  <scoreDirectorFactory>
    ...
    <constraintStreamImplType>BAVET</constraintStreamImplType>
  </scoreDirectorFactory>

Quarkus: Switch to Bavet in src/main/resources/application.properties:

quarkus.optaplanner.solver.constraintStreamImplType=BAVET

Spring: Switch to Bavet in src/main/resources/application.properties:

optaplanner.solver.constraintStreamImplType=BAVET

Note: A Red Hat support subscription will not offer support for Bavet. Drools intends to catch up performance wise.

--

With kind regards,
Geoffrey De Smet
OptaPlanner lead

[Mathe Groß]

I ran two short benchmarks with my real world course-curriculum project (it has many complex constraints).

Unfortunately, DROOLS was roughly twice as fast as BAVET (2.126/s vs. 1.201/s and 2.274/s vs 740/s).

Would be interesting to understand why. Do you have any insights in which situations DROOLS tends to be faster than BAVET?

[Geoffrey De Smet]

Mathe, this is good to know.
Thank you for reporting!

1) What's the size of your dataset?
2) Is this with 8.27.0.Final?
3) Do you have a constraint with 3+ joins?

We have 2 out of 20 use case benchmarks where we see Drools being faster than Bavet.
We have a working theory why that is, which may or may not relate to your usage.
I'd love to see your constraints.

For curriculumCourse in optaplanner-examples,
we're seeing pretty much the same speed numbers between Drools and Bavet.

There will be a blog post tomorrow with more details on Bavet:
  https://www.optaplanner.org/blog/

With kind regards,
Geoffrey De Smet

--
You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/optaplanner-dev/ed9a7bc5-5625-4ea6-a333-510c924984b0n%40googlegroups.com.

[Mathe Groß]

It's with 8.27 final. The dataset has 533 lessons (called lectures in optaplanner example terminology) with planning variables room and timeslot.

I use ca. 15 constraints, where 3 constraints have for 3 times join or ifExist or ifNotExists (but not 3 joiners in a row). Those three are quite ugly and slow the calculation down but in my use case I have grades divided into arbitrary subgroups where I have to guarantee, that no student has windows between two lessons. And I have some lessons with duration 2. So I didn't find anything more performant until now. Here they are:

1) GradeWindowConstraint:

factory.forEach(Lesson.class)
                .join(Lesson.class, Joiners.equal(Lesson::getDay),
                        Joiners.filtering((first, second) -> second.getHour() > first.getHourAfter()
                                && !ScheduleEvaluator.getSingleton(schedule).surroundingMiddayBreak(first, second)
                                && ScheduleEvaluator.getSingleton(schedule).haveSameGrade(first, second)))
                .ifNotExists(Lesson.class,
                        Joiners.filtering((first, second, middle) -> first.getDay().equals(middle.getDay())
                                && first.getHour() < middle.getHour() && middle.getHour() < second.getHour()
                                && ScheduleEvaluator.getSingleton(schedule).haveSameGrade(first, middle)
                                && ScheduleEvaluator.getSingleton(schedule).haveSameGrade(second, middle)))
                .penalize(this.getId(), this.getScore(), (first, second) -> getQuadraticDistance(first, second));

2) GroupWindowConstraint:

factory.forEach(Lesson.class).filter(ScheduleEvaluator.getSingleton(schedule)::notWholeGrade)
                .filter(t -> t.getHour() < firstMiddayHour)
                .ifExists(Lesson.class,
                        Joiners.filtering((first, second) -> first.getDay().equals(second.getDay())
                                && first.getHour() < second.getHour()
                                && ScheduleEvaluator.getSingleton(schedule).haveSameGrade(first, second)
                                && !(first.getGroups().containsAll(second.getGroups())
                                        && second.getGroups().containsAll(first.getGroups()))))
                .ifNotExistsOther(Lesson.class, Joiners.filtering(
                        (first, second) -> ScheduleEvaluator.getSingleton(schedule).areGegenteiler(first, second)
                                && first.contains(second)))
                .penalize(this.getId(), this.getScore());

3) GroupWindowConstraint for second part of lessons with duration 2:

    return factory.forEach(Lesson.class).filter(t -> t.getDuration() == 2)
                .filter(ScheduleEvaluator.getSingleton(schedule)::notWholeGrade)
                .ifExists(Lesson.class,
                        Joiners.filtering((first, second) -> first.getDay().equals(second.getDay())
                                && first.getHourAfter() <= second.getHour()
                                && ScheduleEvaluator.getSingleton(schedule).haveSameGrade(first, second)))
                .ifNotExistsOther(Lesson.class, Joiners.filtering(
                        (first, second) -> ScheduleEvaluator.getSingleton(schedule).areGegenteiler(first, second)
                                && second.getHour().equals(first.getHour() + 1)))
                .penalize(this.getId(), this.getScore());

[Geoffrey De Smet]

Thank you, Mathe.

Until proven otherwise, I believe this is the same performance loss as
  https://issues.redhat.com/browse/PLANNER-2787
Stay tuned for 8.28.0 in a few weeks.

With kind regards,
Geoffrey De Smet

To view this discussion on the web visit https://groups.google.com/d/msgid/optaplanner-dev/289ba319-aef5-4aa2-a26c-d8cc39e09885n%40googlegroups.com.

[Geoffrey De Smet]

Here's the related blog post:
  https://www.optaplanner.org/blog/2022/09/01/Bavet-a-faster-score-engine-for-OptaPlanner.html

With kind regards,
Geoffrey De Smet

[Geoffrey De Smet]

We've merged a performance improvement for 8.29.0.Final (not 8.28).
It would be good to know if that helps.

With kind regards,
Geoffrey De Smet

[Geoffrey De Smet]

I've identified a 2nd performance opportunity for Bavet:
  https://issues.redhat.com/browse/PLANNER-2818

Your code matches the pattern for which this could make a big difference:

join(Lesson.class, Joiners.equal(Lesson::getDay),
                        Joiners.filtering((first, second) -> second.getHour() > first.getHourAfter()
                                && !ScheduleEvaluator.getSingleton(schedule).surroundingMiddayBreak(first, second)
                                && ScheduleEvaluator.getSingleton(schedule).haveSameGrade(first, second)))

So I suspect that PLANNER-2818 is the real fix.

With kind regards,
Geoffrey De Smet

[Fan Zeng]

The performance is much worse for my test case in 8.27.0.Final. My baseline is 8.22.1.Final. Here are the numbers.

8.27.0.Final/Bavet on : INFO Solving ended: time spent (626036), best score (0hard/0medium/0soft), score calculation speed (8031/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (4).

8.27.0.Final/Bavet off: INFO Solving ended: time spent (613239), best score (0hard/0medium/0soft), score calculation speed (8210/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (4).

8.22.1.Final                  : INFO Solving ended: time spent (229055), best score (0hard/0medium/0soft), score calculation speed (18239/sec), phase total (2), environment mode (REPRODUCIBLE), move thread count (4).

The performance degradation is always in 8.27.0.Final, regardless of the choice of score engine. 

The test case is a timetabling problem with about 1900 lessons. Here are few sample constraints.

return constraintFactory
.forEachUniquePair(Lesson.class,
equal(Lesson::getClazz),
equal(Lesson::getDayOfWeek),
filtering((la, lb) -> la.isConsecutiveLeaderOf(lb) || lb.isConsecutiveLeaderOf(la)))
.join(NonConsecutiveLesson.class,
equal((la, lb) -> la.getClazz(), NonConsecutiveLesson::getClazz),
equal((la, lb) -> la.getCourse(), NonConsecutiveLesson::getACourse),
equal((la, lb) -> lb.getCourse(), NonConsecutiveLesson::getBCourse),
filtering((la, lb, c) -> c.periodDayCluster.contains(la.getPeriodDay())))
.penalize( "constraint a"   HardMediumSoftScore.ofMedium(5), (la, lb, c) -> c.userDefined ? 2 : 1);

constraintFactory
.forEachUniquePair(Lesson.class,
equal(Lesson::getTeacher),
equal(Lesson::getPeriodDay),
filtering((la, lb) -> !la.getEvenOddWrapper().isEvenOddPair(lb.getEvenOddWrapper())))

.ifNotExists(CombinedLesson.class,
equal((la, lb) -> la.getCourse(), CombinedLesson::getCourse),
equal((la, lb) -> lb.getCourse(), CombinedLesson::getCourse),
filtering((la, lb, minMax) -> minMax.getClasses().contains(la.getClazz()) && minMax.getClasses().contains(lb.getClazz())))

.ifNotExists(MinMaxLesson.class,
equal((la, lb) -> lb.getClazz(), MinMaxLesson::getClazz),
equal((la, lb) -> lb.getCourse(), MinMaxLesson::getCourse),
filtering((la, lb, minMax) -> isMustAssign(minMax, lb)))
.penalize("constraint x", HardMediumSoftScore.ofHard(10));

[Marko Bilic]

Hey Geoffrey,

Thought I'd share some good news with you in regards to Bavet and the score calculations on our project

so our project initially was on version 8.17.0.Final and we had the following score calculation speed

5387/sec

after switching to 8.29.0.Final we had the following speed without Bavet

5447/sec

and with Bavet we have

13809/sec

just to note we are doing a Multi day vehicle routing solution with constraints that match drivers to specific times for clients needs and also required skills for the clients.

Great Job on this new engine it looks like its been great so far 

[Geoffrey De Smet]

Hi Marko,

Thank you for sharing :) Great numbers!

With kind regards,
Geoffrey De Smet

---

The information and attachments in this email are confidential and intended only for use by the individual indicated above or those authorized to receive or view them. If you received this communication in error please notify the sender immediately and permanently delete the original message and any attachments without making a copy. Unauthorized use or copying of information received in error is prohibited and unlawful. --

You received this message because you are subscribed to the Google Groups "OptaPlanner development" group.
To unsubscribe from this group and stop receiving emails from it, send an email to optaplanner-d...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/optaplanner-dev/5a526728-3fb6-4abd-994a-992addc76748n%40googlegroups.com.

[Edwin Yaqub]

Hi Geoffrey,

Thanks for sharing about Bavet. Here are a few points as feedback:

1- Using 8.29.0.Final, on a problem similar to Cloud Balancing (bin packing), with Bavet I get score calculation speed = 134530/sec, while without it (with Drools via ConstraintStreams API), score calculation speed = 79616/sec.

2- However in above setup, a known earlier bug is seen in Multi-threaded mode (moveThreadCount enabled with AUTO) in that search terminates earlier than allocated time or reaching mentioned bestScoreLimit (0/0). 

The error received is: "No doable selected move at step index (xxx), time spent (xxxx). Terminating phase early"

There is a stackoverflow page that mentions this bug (reported in a different context) will be fixed in 8.30.Final release.

3- Finally, on 8.11.1.Final, using Bavet in a real-time planning scenario (implemented using OptaPlanner GUI Framework), an IllegalStateException is thrown when the ProblemFactChange.doChange() method is triggered. 

Have you tested it in real-time planning? 

I paste the main part of trace for your reference:

INFO Scheduling addition of Entity (com.xx.yy.zz.domain.MyEntity) AND update of all effected Entities.

Exception in thread "AWT-EventQueue-0" java.lang.IllegalStateException: The tuple (From(com.xx.yy.zz.domain.MyEntity) with 0 children) already has a dirty state (CREATING) so it cannot transition to newState (UPDATING).

at org.optaplanner.core.impl.score.stream.bavet.BavetConstraintSession.transitionTuple(BavetConstraintSession.java:148)

at org.optaplanner.core.impl.score.stream.bavet.BavetConstraintSession.update(BavetConstraintSession.java:125)

at org.optaplanner.core.impl.score.director.stream.BavetConstraintStreamScoreDirector.afterProblemPropertyChanged(BavetConstraintStreamScoreDirector.java:161)

at com.xx.yy.zz.gui.realtime.AddMyEntityProblemFactChange.doChange(AddMyEntityProblemFactChange.java:50)

at org.optaplanner.examples.common.business.SolutionBusiness.doProblemFactChange(SolutionBusiness.java:338)

at org.optaplanner.examples.common.swingui.SolutionPanel.doProblemFactChange(SolutionPanel.java:212)

at org.optaplanner.examples.common.swingui.SolutionPanel.doProblemFactChange(SolutionPanel.java:208)

at com.xx.yy.zz.gui.MyOptimizationPanel.someLogic(MyOptimizationPanel.java:903)

at com.xx.yy.zz.gui.MyOptimizationPanel.addMyEntityButtonActionPerformed(MyOptimizationPanel.java:809)

...

Thanks for continuing the innovation on making OptaPlanner even faster!

Best Wishes,

Ed

[Lukáš Petrovický]

Edwin,

On Wed, Nov 16, 2022 at 5:21 PM Edwin Yaqub <edwin...@gmail.com> wrote:

1- Using 8.29.0.Final, on a problem similar to Cloud Balancing (bin packing), with Bavet I get score calculation speed = 134530/sec, while without it (with Drools via ConstraintStreams API), score calculation speed = 79616/sec.

Looks good. Thanks for letting us know!

 

2- However in above setup, a known earlier bug is seen in Multi-threaded mode (moveThreadCount enabled with AUTO) in that search terminates earlier than allocated time or reaching mentioned bestScoreLimit (0/0). 

The error received is: "No doable selected move at step index (xxx), time spent (xxxx). Terminating phase early"

There is a stackoverflow page that mentions this bug (reported in a different context) will be fixed in 8.30.Final release.

Indeed. Do let us know if you still see this bug in 8.30.0.Final.

 

3- Finally, on 8.11.1.Final, using Bavet in a real-time planning scenario (implemented using OptaPlanner GUI Framework), an IllegalStateException is thrown when the ProblemFactChange.doChange() method is triggered. 

Until 8.29.0.Final, Bavet was experimental, many features not even implemented, bugs likely. If you can reproduce any bugs on 8.29.0.Final and later, we'll take a look. In earlier versions, anything to do with Bavet is possible and we will leave it like that.

 

Regards!

--

Lukáš Petrovický

OptaPlanner Project Lead

lukas.pe...@redhat.com

My work week is Monday to Thursday.
No need to respond outside of your working hours.