search

opentripplanner / OpenTripPlanner

An open source multi-modal trip planner
http://www.opentripplanner.org
Other
2.19k stars 1.03k forks source link

Improve ParetoSet performance #4077

Closed slvlirnoff closed 2 years ago

slvlirnoff commented 2 years ago

I've been thinking on this topic a bit, this is a dump of all approaches that I've identified to improve the performance of the ParetoSet.

The ParetoSet are used in many places and are used very often (heuristic check, stop arrivals, destination arrivals) and there are a few improvements that could be made in general.

This seems to be a bottle neck of particularly long searches (and/or with large search window), the small improvement I've proposed (https://github.com/opentripplanner/OpenTripPlanner/pull/4072) already reduce the longest search duration in the perf-test by 1s, or 25%.

Looking at state or the art for Skyline filter, Pareto Front, there is maybe a library that could be used out of the box to back that feature?

In a tailored made solution, it seems that we reject a lot of solutions using the pareto sets. Which is good, since the call is to reduce the exploration space, maybe this could be improved by having some "bounding boxes" to reject solutions faster?

Another direction could be a "addAll" to commit/test all arrivals in one step, allowing us to divide & conquer to optimise the check. One arrival that would be dominated in a subset doesn't have to be checked against all solutions from the other subset.

Another direction could be to use the new Vector API from Java to try to benefits from SIMD CPU capabilities. I guess that there's some benefits in doing so to compare several solutions, or several criteria (they are all integer so far), with one instruction.

Also most of the criteria are kinda correlated, i.e., duration, cost and number of transfers, while some aren't or less correlated (iteration/arrival time). Knowing this, some optimisation are definitely possible. Some reading of research on this could help. I guess that by using this information we can reject solutions faster or select solutions to test again more efficiently.

Another point, that I've found doing that PR is that the solution have some relations in the order by which they are generated. This point can also be used as shown in the PR to more efficiently test and reject solutions.

As a result of the points above, maybe a different implementation should be used depending on the search context or the context in which the ParetoSet is used.

github-actions[bot] commented 2 years ago

This issue is stale because it has been open 90 days with no activity. Remove stale label or comment or this will be closed in 30 days