feat: construct srr connection map on-demand

[sebhoerl]

This PR introduces an option to SwissRailRaptor that constructs the stop-route-connection graph on-demand instead of upfront when initializing the simulation. The reason is that we work with a large GTFS schedule for Île-de-France that takes about 20GB in memory by default, which has two implications:

• If we increase the connection distance from 100m even further, the memory consumption gets even larger. The present PR may reduce slightly this consumption in case there are some lines/routes that are never explored.
• If we only perform small test simulations of 1% or even 0.1% to simply test a new software feature, we still need to construct the whole graph which takes a lot of upfront time, while the simulation itself only takes several seconds (or gives an error when we are debugging a feature).

So in this PR, a new switch is introduced which either keeps the existing behavior, or it constructs the stop graph on-demand while exploring the routes. We used a benchmark where we load the GTFS schedule and then perform a routing of 10,000 random stop connections. We also vary the connection distance that is explored. In the next figure, we show the benchmark results for the IDF schedule and for the Berlin schedule in comparison. The solid line shows memory consumption during loading/preparation of SRR, while the dotted line shows the memory during routing. First, one can see that the maximum required memory for IDF goes up with the connection distance. Furthermore, we can see how memory increases quickly when using the standard implementation, while the routing part starts almost instantly in the Cached implementation, and then memory increases gradually. In total, less memory is used (especially when looking at D=800). We see similar effects for Berlin, but everything is on a much shorter time scale and much less memory is needed in general as the schedule is quite a bit smaller.

Of course, using the cache has a certain impact on the overall runtime (loading + routing) and the upfront loading time becomes less relevant if we talk about very long simulations. So this is really a feature that only makes sense if we have a large GTFS schedule, but want to run rather small simulation samples. The next figure shows the runtime impact. The Cached implementation is a bit slower for the Berlin case, but there is quite a significant difference for IDF (although admittedly, this only one series of test runs). But despite the increase in runtime, this seems to be an interesting feature to us to avoid upfront computation time and quickly run a few iterations, or even just one where a schedule, but no routing is required at all.

Closes #3226.

[sebhoerl]

The benchmark code if you're interested: https://github.com/sebhoerl/srr-test

[sebhoerl]

@mrieser @jfbischoff Anything against this PR ? :)

[sebhoerl]

Ok, just waiting for @mrieser to unblock the merge ;)

[mrieser]

Sorry, my mailbox with Github-Notifications is overflowing, so I missed this one. I just found it when working on SRR myself and wondering about the new stuff... Feel free to write me directly next time, sorry.

Some thoughts/remarks:

• MinimalTransferTimes.getCandidates() is very poorly named in my opinion. It is "candidates" in your use case, but from the view of the class, that currently just stores some data, the term "candidates" does not make sense. getConnectedStops() or getDefinedTransfers() might be more suitable
• MinimalTransferTimes.getCandidates() does not have any Javadoc explaining what an implementation should do or what the method is intended to do.
• SwissRailRaptorData.calculateTransfers() is quite a long method which is now called lots of times within SwissRailRaptorCore.handleTransfers(). Due to the large amount of code in calculateTransfers(), the method will likely not be inlined, resulting in reduced performance to before due to the additional method invocation. Did you make performance tests before/after the change?
• SwissRailRaptorData.calculateTransfers() has an if-statement at the beginning. Probably, the if-statement could be moved to SwissRailRaptorCore.handleTransfers() in order to prevent the (comparatively expensive) method call in cases where it is not needed.
• Formatting does not show much love, with sometimes spaces and tabs used for indentation on the same line.
• What is the use of SwissRailRaptorData.staticTransferTimes? To me it looks as if it is just a copy of the exactly same data that is also stored in MinimalTransferTimesImpl, also as nested Maps... What benefit does it bring instead of just querying the minimal transfer times?
• The transfers are now likely calculated in multiple threads (because routing uses multiple threads), leading to the observed speed improvement. A parallel calculation of transfers could likely also be implemented for the "initial" mode, leading to improvements also there.
• The logic to calculate (potential) transfers is now duplicated...

[sebhoerl]

Hi @mrieser, thanks for the comments!

MinimalTransferTimes.getCandidates() is very poorly named in my opinion. It is "candidates" in your use case, but from the view of the class, that currently just stores some data, the term "candidates" does not make sense. getConnectedStops() or getDefinedTransfers() might be more suitable

MinimalTransferTimes.getCandidates() does not have any Javadoc explaining what an implementation should do or what the method is intended to do.

Okay, will update those two points.

SwissRailRaptorData.calculateTransfers() is quite a long method which is now called lots of times within SwissRailRaptorCore.handleTransfers(). Due to the large amount of code in calculateTransfers(), the method will likely not be inlined, resulting in reduced performance to before due to the additional method invocation. Did you make performance tests before/after the change?

SwissRailRaptorData.calculateTransfers() has an if-statement at the beginning. Probably, the if-statement could be moved to SwissRailRaptorCore.handleTransfers() in order to prevent the (comparatively expensive) method call in cases where it is not needed.

Yes, this is what makes the on-demand version slower, but there is no impact on the standard pre-comuted version. Yes, I can move the if outside of the function to avoid calling the method altogether.

Formatting does not show much love, with sometimes spaces and tabs used for indentation on the same line.

Do you use a specific formatting file for the SRR code?

What is the use of SwissRailRaptorData.staticTransferTimes? To me it looks as if it is just a copy of the exactly same data that is also stored in MinimalTransferTimesImpl, also as nested Maps... What benefit does it bring instead of just querying the minimal transfer times?

• First I had the impression that you want MinimalTransferTimes to be a data object that is used for preparation, not later on in the simulation.
• Second, MTT is a Map<Id, Map<Id, Double>>, so completely based on IDs. The staticTransferTimes uses an IdMap which should be quicker for lookup (not just iteration like MTT is used mostly before).
• Third, the staticTransferTiles is a Map<Id, Map<TransitStopFacility, Double>>, which makes it easy to look up an (transfer origin) stop by ID, and then directly iterate over stop objects + their transfer time. This is useful because I need the TransitStopFacility object to get the coordinates for the Euclidean distance calculation. Otherwise, I would need to do another lookup in the schedule to get the object for a stop ID.

The transfers are now likely calculated in multiple threads (because routing uses multiple threads), leading to the observed speed improvement. A parallel calculation of transfers could likely also be implemented for the "initial" mode, leading to improvements also there.

Yes, indeed. Our concern was more memory and that there is an avoidable calculation offset at all at the beginning of the simulation, when we just run simple debugging tests but with a large schedule.

The logic to calculate (potential) transfers is now duplicated...

Yes indeed, the point was to be minimally invasive on the default implementation, but probably we could merge things in a way or another. We could hide all of this behind a TransferLookup interface or something similar. In a way this corresponds to what I meant before: The MTT seems to be a data object, not necessarily aimed at looking up things on-the-fly in the simulation, but we could hide this logic behind another interface now that there are two options already.

[sebhoerl]

Actually, I had a second look. Probably for the staticTransferTimes it is more the Second point that is valid, not the Third.