[0.17.37] Train update taking very long

[BattleFluffy]

I recently overhauled my main rail network to improve traffic flow.

After my changes, I've noticed the UPS drop considerably. Looking at the time usage, it seems like trains are taking an excessively long time to update.

times.png (166.69 KiB) Viewed 4537 times

Prior to making this change to the rails, I had these times:

update times.png (70.91 KiB) Viewed 4537 times

The number of trains did not change. The main changes are that there are fewer merges/exits on the main highway than before, there are some extra circuits connected to rail signals in some places, while hundreds of other "decorative" circuits were removed, and the overall density of rail signals increased.

I thought perhaps I had just put too many rail signals in, but Stevetrov, a very experienced player, advised me in the Discord group that he has never seen such update times for trains, and that something weird was going on. I thought I would post it here just in case it points the way to some bugfix or optimization..

Here is a save file after the rail changes, where the train update time takes ages:
https://drive.google.com/file/d/1R7JF-f ... cNaWnRRpz0


Here's another save file just before I made all the rail network changes, for comparison. Train updates don't take nearly as long in this one.
https://drive.google.com/open?id=1V3z5c ... Ul-9xTKse9


Thanks for being awesome ! :>

[Rseding91]

From looking at the save(s) through the zoomed to world view and in the profiler it's very simple:

You've more than doubled the number of rail signals being used which has more than doubled the number of individual segments on the rail network. That results in a lot more work for the path finder as it has more smaller segments to go over.

Simply put: you built too many signals. Remove about 2/3rds of what you have and it will fix your problem.

[BattleFluffy]

Great, thanks ! :>

[BattleFluffy]

I removed a ton of signals... thousands.. And now things are a lot faster. :> I did not realize that an excessive number of signals could cause the pathfinder update time to explode like that.
Also, the trains didn't really seem to behave much differently with fewer signals on the track. I think on high speed rails it doesn't make much difference to throughput whether you have them every train length or every 2 tiles.

Thanks again for looking at this for me! I can continue building my city now :>

[sparr]

Why would doubling the number of signals, without changing the number of forks, cause the pathfinder time to more than double?

[nuhll]

he said it already, because its more segments the train logic have to go thru.

The computer doesnt know that 10 segments or 1 segments on the same track make no difference. It has to look at each segment indipediply.

[robot256]

I mean, it "knows" they are connected, but when you put down a signal every 2 tiles you are telling the game to look at each square separately. If you don't want it to spend time doing that, don't put so many signals down

[sparr]

Neither of you have actually addressed the question I asked.

[BattleFluffy]

Why would doubling the number of signals, without changing the number of forks, cause the pathfinder time to more than double?

Because of the way the pathfinder algorithm works. I'll try to explain using my limited understanding - if I get anything wrong I'm sure someone will jump in and correct me. :>

When a train is about to start a journey to a station, it uses a pathfinder algorithm to figure out the best path to take. In programming terms this is basically a loop.

Each iteration of the pathfinder loop, it explores outwards from its current position by 1 block. Depending on the things it finds in that block (trains, other stations, etc), and the length of the block, it adds a "path cost" to this route.
Eventually one of the routes that is branching out from its current position will contain a station that is the destination. The train then sets off in this direction.


Because it does this loop, if we drastically increase the number of rail signals, then it has a corresponding increase in the number of blocks - and the number of iterations of the pathfinder loop that will be required to find a destination station.
Trains also revalidate and recalculate their paths frequently during journeys, especially in a busy train network, so the pathfinder algorithm is running a lot. So that is why adding an excessive number of rail signals slows things down. :>

Further reading: https://wiki.factorio.com/Railway/Train_path_finding

[boran_blok]

well crap, in my current city block layout I use 1-1 trains with corresponding signal blocks being 2 wagons long.

I should probably change this design then to use longer signal blocks, but I alwasy heard that for good train throughput you need to space the signals "train length" apart.

[BattleFluffy]

I had heard that too!

I guess small trains might benefit more from tightly spaced signals, because they have a shorter stopping distance since they're less heavy.
Big trains naturally drive really far apart from each other because they have so much mass/momentum. So spacing the signals close together for big trains probably isn't very useful.

I think also that the speed of the rail needs to be taken into account. If it's a highway where everything is travelling fast, I imagine it's fine to have sparse signals. But in waiting areas, single track entry ways and other places where trains might travel slower, tighter signalling is probably justified.

[sparr]

if we drastically increase the number of rail signals, then it has a corresponding increase in the number of blocks - and the number of iterations of the pathfinder loop that will be required to find a destination station.

Why would doubling the number of signals, without changing the number of forks, cause the pathfinder time to more than double?

[Rseding91]

if we drastically increase the number of rail signals, then it has a corresponding increase in the number of blocks - and the number of iterations of the pathfinder loop that will be required to find a destination station.

Why would doubling the number of signals, without changing the number of forks, cause the pathfinder time to more than double?

It was not a pure doubling. Look at the before and after saves - it's > double but I didn't count the exact amount.

[ratchetfreak]

The more technical answer is that pathfinding work like

Code: Select all

while(set not empty){
     take a block b out of set

     mark b visited

     if destination is in block return b

     for each possible next block nb directly reachable from b {
          if nb is not visited {
              add nb to set with b as it's predecessor
          }
     }
}

The operations "take a block b out of set" and "add nb to set" are not constant but scale with at least O(log n).

It is possible to change the adding step to merge long non-branching section first (perhaps to a point) and avoid the extra overhead. Though limiting how much gets merged will be needed to avoid pathological behaviors on super-long rail sections.

[BattleFluffy]

Interesting. It reminds me I have some unanswered questions about train pathfinding, this seems like a good place to ask..

First question, does the pathfinder iterate through blocks, or through "segments"?
A block is defined by rail signals which demarcate the edges of the block, but a segment is defined as "an uninterrupted plain sequence of rails, with no intersections, stops, or signals" according to the wiki page on Train Pathfinding.
It sounds like the pathfinder probably iterates over segments?

Second question, the wiki page also seems to distinguish between "blocks" and "paths". What is a path? How do paths, blocks and segments relate to each other?
I can probably guess these, but it would be better if somebody knows the exact answers :>

[nuhll]

Neither of you have actually addressed the question I asked.

Just bc you dont understand the answer, or dont have the correct question, it doesnt mean that the answeres were wrong.