The International Simutrans Forum

 

Author Topic: Pull request: significant futher private car route memory saving  (Read 1076 times)

0 Members and 1 Guest are viewing this topic.

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
This is not yet fully developed, but I do have a working proof-of-concept. I am able to run the bridgewater-brunel save with over 450 million total stored private car route tiles using just 6.4GB of memory. This is achieved by storing a total of ten ordered_vector_tpl, one for each cardinal direction (plus end-of-route) for the reading and writing sets. For those unfamiliar, an ordered_vector_tpl is a sorted container of unique elements. It saves memory over the current hashtable implementation because it does not need to store values (these are implicit based on membership of their container) and does not need to store node structures which require expensive pointers. There are a few areas that need to be addressed before this can even be considered being merged:
1. loading and saving must be implemented.
2. the changes must be tested for any adverse performance impacts - although I believe the overall performance impact will be positive, and route searching seems roughly twice as fast as previously.
3. the changes must be tested to behave identically to the current implementation.
4. the code must be reviewed and optimised.
There is not yet a github branch - this will be pushed in the coming days before making a pull request.
« Last Edit: January 19, 2021, 12:17:01 AM by freddyhayward »

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20776
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
This is very interesting, thank you. I do suggest that you base the version on which you issue a pull request on the master branch after merging private-car-route-memory-saving, since this latter branch fixes a number of important bugs which fixes will need to continue to be active after the incorporation of this new system.

I imagine that this must have been a significant effort - thank you for your work on this.

Offline Vladki

  • Devotee
  • *
  • Posts: 3718
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Is there any description how is the route information implemented? For both private and player vehicles?

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
Is there any description how is the route information implemented? For both private and player vehicles?
Route information is only stored for private vehicles. It is stored in a hashtable on every road tile that uses the final destination as keys and the next tile along that route as values.

Offline Vladki

  • Devotee
  • *
  • Posts: 3718
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Route information is only stored for private vehicles. It is stored in a hashtable on every road tile that uses the final destination as keys and the next tile along that route as values.
Is that in every road tile, or just junctions/crossings (i.e. more than 2 exits?) I'd like to compare if the number of stored routes in road tiles is not higher that the number of private vehicles. Because that it would be more efficient to do the routing in the same way as player vehicles/convoys? I assume they have the route stored in the convoy object somewhere? Is that a list of all tiles to visit or something else?

For travel time tolerance estimates, a list of distances between towns and countryside destinations would be enough. (And refreshed periodically, if any roads were modified).

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
Is that in every road tile, or just junctions/crossings (i.e. more than 2 exits?) I'd like to compare if the number of stored routes in road tiles is not higher that the number of private vehicles. Because that it would be more efficient to do the routing in the same way as player vehicles/convoys? I assume they have the route stored in the convoy object somewhere? Is that a list of all tiles to visit or something else?
It's every road tile. The number of stored routes is certainly higher than the number of private vehicles. You would effectively need to rewrite private cars to make them store their own routes. Journey times are the responsibilities of cities - they have nothing to do with how the actual routes are stored.

Offline Freahk

  • Devotee
  • *
  • Posts: 1505
  • Languages: DE, EN
As James pointed out, we will need to calculate private car routes in between towns and other destinations anyways to determine if it's faster to go by public transport or car.
Surely, we don't have to store that data in the world. If it's faster to calculate and use routes for each single car, that might be an option.
I suspect it might be better in terms of memory to store routes per car, but route calculation performance might then become an issue.
Do we know the performance impact of player vehicle routing?

Offline Vladki

  • Devotee
  • *
  • Posts: 3718
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
It's every road tile.
Could this be limited to junctions/crossings? There is no reason to have all routes stored on a straight piece of road, the car just has to continue further on. And if it hits a dead end, recalculation of the followed route should be triggered immediately to avoid loops as reported in another recent thread.

Offline Freahk

  • Devotee
  • *
  • Posts: 1505
  • Languages: DE, EN
That's an old idea. I guess it was just rejected for simplicity, so no additional logics is needed when a new intersection along a route is created.
Anyways, it could potentially cut the memory footprint quite much.

Offline Vladki

  • Devotee
  • *
  • Posts: 3718
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Another brainstorming idea:

- how long does it take to recalculate a route?
- could we do this on-demand?
- do it only on crossings, plain road is just followed to the other end.
- if vehicle enters a crossing without stored route to its destination, it will do the route search and store it in the crossing (i.e. stop, look at the map, and put up a sign for others to follow). Crossings ahead could be marked at the same time as well.
- if vehicle enters a crossing with stored route for its destination, it will follow it (i.e. look at the road signs and follow it)
- if the vehicle is told to turn back where it came from, recalculate the route. (maybe if we have timestamp for the route we could limit this to happen only on older routes).
- very old routes could expire or be recalculated anyway.

This way routes would be stored only on crossings, and only those that are really needed by cars passing there.

Offline Ranran

  • Devotee
  • *
  • Posts: 1513
  • Languages: ja
Re: Potential pull request: significant futher private car route memory saving
« Reply #10 on: January 18, 2021, 01:10:43 PM »
It should be noted that there is no guarantee that a car can pass through even if the road is straight.
If you impose a one-way street or put a no-entry sign in the middle, it is the same as a divided road.
Therefore checking only the intersections may not evaluate the route correctly.

Offline Freahk

  • Devotee
  • *
  • Posts: 1505
  • Languages: DE, EN
Re: Potential pull request: significant futher private car route memory saving
« Reply #11 on: January 18, 2021, 01:18:04 PM »
Surely, we have to talk about (masked) RIBIS, not straightness of a road.
Any road with at least three masked RIBIS set needs to store route data. (tile can be left in more than two directions)
Any road with two masked RIBIS and at least three "usual" ribis set will also need to store route data. (tile can be left in two directions, but entered from further ones)

Offline Vladki

  • Devotee
  • *
  • Posts: 3718
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Re: Potential pull request: significant futher private car route memory saving
« Reply #12 on: January 18, 2021, 01:27:03 PM »
OK, so lets say it a bit differently.
- Crossing (for the above purpose) is a tile that can be exited in more than one direction, but ignoring the direction of arrival.
- Dead end is a tile that can be exited only in the direction of arrival.

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
Re: Potential pull request: significant futher private car route memory saving
« Reply #13 on: January 18, 2021, 11:29:24 PM »
Sorry all, this is a productive discussion but could it please be moved to another thread? This thread is about a specific change I am working on. Thanks.

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
Re: Potential pull request: significant futher private car route memory saving
« Reply #14 on: January 18, 2021, 11:58:26 PM »
I have now opened the pull request for this change here: https://github.com/jamespetts/simutrans-extended/pull/343
On a recent bridgewater-brunel save from 1986, the server uses 5.1GB of memory in the new implementation, compared to 7.9GB in the old implementation.
I have done some work on addressing the points I brought up earlier:
1. loading and saving must be implemented.
This is now implemented. Conversion from the previous version is quite slow because the lists have to be populated gradually, which requires many memory allocations. This is sped up significantly, even compared to the current (to be old) in loading from the new (to be current) version as the lists can be allocated according to their size.

2. the changes must be tested for any adverse performance impacts - although I believe the overall performance impact will be positive, and route searching seems roughly twice as fast as previously.
I haven't yet tested route searching itself, but I did conduct these tests:
Code: [Select]
save implementation method: times (ms)
ss old hopcheck: 561,741,741
ss new hopcheck: 574,786,794
bb old hopcheck: 3668,3589,3617
bb new hopcheck: 3402,3372,3381

ss old add: 507,616,623
ss new add: 273,362,361
bb old add: 2225,2229,2183
bb new add: 2085,2106,2073

ss old remove: 35,44,42
ss new remove: 67,55,51
bb old remove: 111,112,108
bb new remove: 383,374,375
These tests were conducted over 256 steps on recent saves from bridgewater-brunel and stephenson-siemens, using the current and proposed implementation. They show very modest improvements in accessing the routes by private cars (hop_check) and in adding new routes. However, there was a significant decrease in performance when deleting routes. Unfortunately, this is an inherent issue in using ordered_vector_tpl, because all subsequent data has to be moved when an element is removed. Anecdotally, this can cause very rare lag spikes of ~3 seconds on bridgewater-brunel when refreshing a city's routes. I don't know whether changes to route refreshing can or should address this. In any case, I still believe that this issue is vastly outweighed by memory consumption savings.

3. the changes must be tested to behave identically to the current implementation.
This has proven difficult to test because the way private car routes are interpreted has changed in the new implementation. It uses the existing get_neighbour() method which checks whether the road is connected to another road in a given direction. The original implementation does not check for this - and therefore private cars are often incorrectly sent to tiles that they should not be able to reach. This is a bug that was probably not worth fixing in the original implementation, but it is inherently fixed by the new implementation. Apart from this, all other behaviour appears identical.

4. the code must be reviewed and optimised.
I have done this where possible - if anyone else can suggest improvements to the code, that would be helpful.

In conclusion, I now support merging this pull request. It has a few issues but will provide an overall benefit to performance, especially on bridgewater-brunel.

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
Re: Pull request: significant futher private car route memory saving
« Reply #15 on: January 19, 2021, 09:21:17 AM »
I have now tested the time it takes to find routes for cities under the new implementation, and found the results far better than I expected. It now finds all routes within 1-2 seconds (without limits) for each city - at least an order of magnitude faster than the old implementation.

Offline Matthew

  • Devotee
  • *
  • Posts: 560
    • Japan Railway Journal
  • Languages: EN, some ZH, DE & SQ
Re: Potential pull request: significant futher private car route memory saving
« Reply #16 on: January 19, 2021, 12:52:30 PM »
I have now opened the pull request for this change here: https://github.com/jamespetts/simutrans-extended/pull/343
On a recent bridgewater-brunel save from 1986, the server uses 5.1GB of memory in the new implementation, compared to 7.9GB in the old implementation.

 :award: :award: :award: :award: :award: :award: :award: :award:

This is a great improvement! That would mean you have (more than?) halved B-B memory usage in about a month!

Quote
Conversion from the previous version is quite slow because the lists have to be populated gradually, which requires many memory allocations.

Would it be worth converting the save on a different computer to B-B then, if there will be a temporary increase in memory usage?

Quote
Anecdotally, [deleting routes] can cause very rare lag spikes of ~3 seconds on bridgewater-brunel when refreshing a city's routes. I don't know whether changes to route refreshing can or should address this. In any case, I still believe that this issue is vastly outweighed by memory consumption savings.

I agree. Also, I don't know what build you are using as your control, but on #70a5430 we already get sporadic freezes of ~3 seconds when deleting busy road tiles. So maybe it could be an existing issue?

Offline Vladki

  • Devotee
  • *
  • Posts: 3718
    • My addons, mostly roadsigns, pak128.cs
  • Languages: EN, CS
Re: Pull request: significant futher private car route memory saving
« Reply #17 on: January 19, 2021, 05:11:41 PM »
This is a great improvement! That would mean you have (more than?) halved B-B memory usage in about a month!
And I have bought extra 8 GB for my computer to be able to connect to B-B. What a waste of money ;-)

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
Re: Pull request: significant futher private car route memory saving
« Reply #18 on: January 19, 2021, 07:41:25 PM »
Would it be worth converting the save on a different computer to B-B then, if there will be a temporary increase in memory usage?
There won't be a temporary increase - the amount of memory will be the same, it will just be allocated in many small chunks instead of all at once. However, I believe I have partly addressed this in my change to ordered_vector_tpl

I agree. Also, I don't know what build you are using as your control, but on #70a5430 we already get sporadic freezes of ~3 seconds when deleting busy road tiles. So maybe it could be an existing issue?
I have also averted this issue entirely by deleting all routes in the writing sets at once at the beginning of each refresh (i.e. before cycling through all cities).

And I have bought extra 8 GB for my computer to be able to connect to B-B. What a waste of money ;-)
Also note that memory usage does increase - to about 7GB in my testing (I did not test the old implementation up to that point, so I have no idea what the savings are there) - so our memory woes are not entirely over.

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20776
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Pull request: significant futher private car route memory saving
« Reply #19 on: January 19, 2021, 10:42:00 PM »
Thank you to Freddy for the excellent work on this. I have spent some time testing this, and the results are positive. I can load old and newer saved games, clients can stay in syncronisation with the server the traffic behaviour appears to be correct, the routes refresh at a sensible rate (and take less computational load to refresh than before, allowing for setting a higher number of route tiles per step), and the clearing of all routes in the writing set causes only a very slight pause of what I would estimate is less than a second.

Running performance for the privte cars' hop check appears to take slightly more CPU time than before, although I did not conduct an exact test so the comparison may not be valid for the relatively small difference that I saw, but performance is not degraded significantly enough to be a concern even on a game with a large number of private cars.

Memory consumption is significantly lower, with a version of the Bridgewater-Brunel saved game from yesterday having peak memory consumption in a graphical client of <8Gb (the new system means wider variations in memory consumption between just after refreshing the routes, when it is at its lowest, and just before refreshing the routes, when it is at its highest, than the previous system).

I have also been monitoring the data to test the changes that I made to the code to reduce the number of private car routes stored. The amount of memory used to-day is less than it was ~2 days ago, before this feature was introduced, but it is still higher than the amount of available RAM, meaning that the server is making extensive use of swap space, which is likely to affect performance adversely.

Because the amount of memory used is as follows:

Code: [Select]
              total        used        free      shared  buff/cache   available
Mem:           7961        7741         125           1          94          40
Swap:         18047        2004       16043

which appears to be at the higher end of the range reported so far.

Memory usage on a graphical client will be higher than memory usage on a command line only client, so there is a good chance that Freddy's changes in addition to my earlier changes will allow the server to run entirely in RAM after its next two refreshes of private car routes. This may take some time to propagate, so please be patient.

In the meantime, I will be incorporating these changes. I am very grateful to Freddy for the excellent work on this, which empirical testing shows to be very helpful indeed.

Offline freddyhayward

  • Devotee
  • *
  • Posts: 661
  • Languages: EN
Re: Pull request: significant futher private car route memory saving
« Reply #20 on: January 19, 2021, 11:09:28 PM »

Code: [Select]

              total        used        free      shared  buff/cache   available
Mem:           7961        7741         125           1          94          40
Swap:         18047        2004       16043
To clarify, is this statistic from the recent (now earlier) changes reducing the number of routes stored, or is it from my new changes?

Offline jamespetts

  • Simutrans-Extended project coordinator
  • Administrator
  • *
  • Posts: 20776
  • Cake baker
    • Bridgewater-Brunel
  • Languages: EN
Re: Pull request: significant futher private car route memory saving
« Reply #21 on: January 20, 2021, 12:47:16 AM »
To clarify, is this statistic from the recent (now earlier) changes reducing the number of routes stored, or is it from my new changes?

My changes only.