OpenRailAssociation / osrd

An open source web application for railway infrastructure design, capacity analysis, timetabling and simulation
https://osrd.fr
GNU Lesser General Public License v3.0
419 stars 40 forks source link

core: stdcm: improve heuristic by using lookahead data #7844

Closed eckter closed 1 week ago

eckter commented 2 weeks ago

Fix https://github.com/OpenRailAssociation/osrd/issues/7642

Work in progress: the tests fail, and it will conflict hard with https://github.com/OpenRailAssociation/osrd/pull/7830 once merged (this PR won't be merged first)

  1. Small refactor of the heuristic to wrap in in a class
  2. Cache the MRSPs
  3. Use lookahead data to correctly identify which edges are going the wrong way
  4. Improve how we evaluate the number of passed steps (prerequisite for this to work out)

Benchmark results:

image Average -10% time.

But there's a few requests that used to cause an error and have been fixed, which increase the average response time (that's the +55s in the first max). Ignoring all errors, the average time goes from 3.79 to 2.58s (32% less time).

image

codecov-commenter commented 2 weeks ago

:warning: Please install the 'codecov app svg image' to ensure uploads and comments are reliably processed by Codecov.

Codecov Report

Attention: Patch coverage is 96.49123% with 4 lines in your changes missing coverage. Please review.

Project coverage is 28.54%. Comparing base (dd067f8) to head (75d32da). Report is 6 commits behind head on dev.

Files Patch % Lines
...c/main/kotlin/fr/sncf/osrd/stdcm/STDCMHeuristic.kt 96.26% 1 Missing and 3 partials :warning:

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## dev #7844 +/- ## ========================================= Coverage 28.53% 28.54% Complexity 2059 2059 ========================================= Files 1249 1249 Lines 154125 154150 +25 Branches 3036 3042 +6 ========================================= + Hits 43983 44003 +20 - Misses 108332 108337 +5 Partials 1810 1810 ``` | [Flag](https://app.codecov.io/gh/OpenRailAssociation/osrd/pull/7844/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | Coverage Δ | | |---|---|---| | [core](https://app.codecov.io/gh/OpenRailAssociation/osrd/pull/7844/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | `75.00% <96.49%> (+0.04%)` | :arrow_up: | | [editoast](https://app.codecov.io/gh/OpenRailAssociation/osrd/pull/7844/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | `71.66% <ø> (-0.02%)` | :arrow_down: | | [front](https://app.codecov.io/gh/OpenRailAssociation/osrd/pull/7844/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | `10.00% <ø> (ø)` | | | [gateway](https://app.codecov.io/gh/OpenRailAssociation/osrd/pull/7844/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | `2.34% <ø> (ø)` | | | [railjson_generator](https://app.codecov.io/gh/OpenRailAssociation/osrd/pull/7844/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | `87.49% <ø> (ø)` | | | [tests](https://app.codecov.io/gh/OpenRailAssociation/osrd/pull/7844/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | `72.93% <ø> (ø)` | | Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#carryforward-flags-in-the-pull-request-comment) to find out more.

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.