Incrementally generate raptor transfers from constrained transfers for new pattern #6191
Conversation
Codecov ReportAttention: Patch coverage is
Additional details and impacted files@@ Coverage Diff @@
## dev-2.x #6191 +/- ##
=============================================
- Coverage 69.90% 69.90% -0.01%
- Complexity 17723 17725 +2
=============================================
Files 1998 1998
Lines 75443 75468 +25
Branches 7718 7727 +9
=============================================
+ Hits 52740 52754 +14
- Misses 20025 20031 +6
- Partials 2678 2683 +5 ☔ View full report in Codecov by Sentry. |
|
In our deployment (40k pattern, 60k constrained transfer) updating the transit layer goes from systematically ~6s to ~10-20ms in average and a up to a few hundreds ms when new pattern are created. |
slvlirnoff
changed the title
|
@t2gran I've investigated further where the performance issue comes from for switzerland's setup. Out of the 50k constrained transfers, the majority of them are trip to trip and aren't causing an issue but there is around 8'000 stations to stations transfers (for minimum transfer time) that are creating 40'000'000 |
I am not sure if you are allowed to do it or not, but to me a sensible thing would be to specify a Is there a time witch we can discuss this? |
|
My experience is that often legacy systems required explicit transfers to be defined for them to work at all. When these data sets are being converted to GTFS they are mapped to minimum_transfer_times when in fact it just means that a transfer is possible. In GTFS and OTP it's not necessary to explicitly say that the transfer is possible and the better option is to micromap your stations so that you get good, flexible walking instructions with detailed paths. I often completely drop the minimum_transfer_times from my German data sets. I suspect the source of @slvlirnoff's data is a German software vendor. |
|
Yep, unfortunately we currently have a need to use this information. In many cases it is difficult to micromap the station level for several reasons, the main one is that we aren't always in contact with the producer/owner of the specific station data. They also use these constraints to sometimes prevent/discourage short transfer between specific stops, for instance there are nearby bus stops up the mountains were you could theoretically switch bus in under a minute, however if your bus is late or the other bus is running early you'll be stuck in the middle of nowhere for an hour and it'd be safer to consider only transfers with 10mn slack. In other cases the train platforms are very long and you could reach them from multiple connecting bus stops relatively quickly, to the front, the middle or respectively the back of the platform. This is harder to map and historically done with these transfer time. Would you map these with pathways? In any case, there are two issues:
|
This is supported in NeTEx/OTP by setting stop priority.
No, this should be done with a new feature "minimumTransferTime for stop with an optional submode". Submode, if you want to distinguage between local and long distance trains. There is a report in the report API witch can be used to look at the number of generated constrained transfers: /otp/report/transfers.csv |
I also want this. So, I will review the PR, sorry for the delay. We planned to fix this after the refactoring of the transit model, but I think that will take time. |
| @@ -42,6 +42,10 @@ public class TransferIndexGenerator { | |||
| private final Map<Route, Set<RoutingTripPattern>> patternsByRoute = new HashMap<>(); | |||
| private final Map<Trip, Set<RoutingTripPattern>> patternsByTrip = new HashMap<>(); | |||
|
|
|||
| private int lastPatternIndex = 0; | |||
There was a problem hiding this comment.
Rename to prevProcessedNumberOfPatterns, and make it equals to the size of the collection.
| private TransferForPatternByStopPos[] prevForwardTransfers = {}; | ||
| private TransferForPatternByStopPos[] prevReverseTransfers = {}; |
There was a problem hiding this comment.
The above code keep a reference to the list(array) of transfers kept elsewhere. This may lead to inconsistency problems, but I guess this is also the case for the other cashed data in this class. So I think we can ignore it for know. There is no performance gain of keeping these as arrays, so they can be ArrayLists. I will comment on the needed changes bellow to use ArrayList instead, the coping is also unnecessary, so:
// We need to use ArrayList to be able to enforce the capacity
private ArrayList<TransferForPatternByStopPos> forwardTransfers = new ArrayList<>();
private ArrayList<TransferForPatternByStopPos> reverseTransfers = new ArrayList<>();
| return new ConstrainedTransfersForPatterns( | ||
| Arrays.asList(prevForwardTransfers), | ||
| Arrays.asList(prevReverseTransfers) | ||
| ); |
There was a problem hiding this comment.
This is not dry, make a private factory method, if using ArrayList it will be something like:
/**
* TODO - Doc on:
* - Why we set prevProcessedNumberOfPatterns here
* - Why we make a defensive copy of the list or push into ConstrainedTransfersForPatterns
*/
private ConstrainedTransfersForPatterns createConstrainedTransfersForPatterns() {
this.prevProcessedNumberOfPatterns = prevForwardTransfers.size();
return new ConstrainedTransfersForPatterns(
// TODO: Push the copy into the construct instead of doing it here
List.copyOf(forwardTransfers),
List.copyOf(reverseTransfers)
);
}
Note! No matter how you do this the arrays will be copied at this point, see Arrays.asList(), List.copyOf().
| // Copy previously generated transfers | ||
| System.arraycopy(prevForwardTransfers, 0, forwardTransfers, 0, prevForwardTransfers.length); | ||
| System.arraycopy(prevReverseTransfers, 0, reverseTransfers, 0, prevReverseTransfers.length); | ||
|
|
There was a problem hiding this comment.
With ArrayList this can be replaced with (line 68-73):
// Ensure we increment the capacity once and not incremental when we add new transfers
forwardTransfers.ensureCapacity(nPatterns);
reverseTransfers.ensureCapacity(nPatterns);
Unsure if this is needed, but at least it can hurt much (except readability).
| // Update the last pattern handled index and store the generated transfers | ||
| lastPatternIndex = nPatterns - 1; | ||
| prevForwardTransfers = forwardTransfers; | ||
| prevReverseTransfers = reverseTransfers; | ||
|
|
There was a problem hiding this comment.
| // Update the last pattern handled index and store the generated transfers | |
| lastPatternIndex = nPatterns - 1; | |
| prevForwardTransfers = forwardTransfers; | |
| prevReverseTransfers = reverseTransfers; |
And replace the new Co... with the factory method.
| boolean alightFromPreviouslySeenPattern = | ||
| fromPoint.pattern.patternIndex() <= lastPatternIndex; |
There was a problem hiding this comment.
The pattern.patternIndex() <= lastPatternIndex is a leaked abstraction, but it is difficult to fix here - I looked into it, but at least you should make sure it is dry - implemented in just one place with a private method:
private boolean `isNewPattern(RoutingTripPattern pattern) { return pattern.patternIndex() >= prevProcessedNumberOfPatterns; }`
and
boolean alightFromPreviouslySeenPattern = !isNewPattern(fromPoint.pattern);
| @@ -158,6 +186,9 @@ private List<TPoint> findTPoints(StationTransferPoint point) { | |||
| var result = new ArrayList<TPoint>(); | |||
|
|
|||
| for (RoutingTripPattern pattern : patterns) { | |||
| if (onlyNewPatterns && pattern.patternIndex() <= lastPatternIndex) { | |||
There was a problem hiding this comment.
| if (onlyNewPatterns && pattern.patternIndex() <= lastPatternIndex) { | |
| if (onlyNewPatterns && !isNewPattern(pattern)) { |
| @@ -180,6 +211,9 @@ private List<TPoint> findTPoints(StopTransferPoint point) { | |||
| var result = new ArrayList<TPoint>(); | |||
|
|
|||
| for (RoutingTripPattern pattern : patterns) { | |||
| if (onlyNewPatterns && pattern.patternIndex() <= lastPatternIndex) { | |||
There was a problem hiding this comment.
| if (onlyNewPatterns && pattern.patternIndex() <= lastPatternIndex) { | |
| if (onlyNewPatterns && isNewPattern(pattern)) { |
|
Thanks for the review @t2gran I'll try to address your comments shortly. |
Summary
This aims at incrementally updating the generated raptor transfers for the transit layer from the constrained transfers. It keeps track of the last RoutingPattern index and only generate transfers that are alighting or boarding newly created patterns.
Issue
Closes #6190