News:

Use the "Forum Search"
It may help you to find anything in the forum ;).

Pull request: significant futher private car route memory saving

Started by freddyhayward, January 17, 2021, 01:00:12 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

freddyhayward

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.

jamespetts

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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

Vladki

Is there any description how is the route information implemented? For both private and player vehicles?

freddyhayward

Quote from: Vladki on January 17, 2021, 08:18:26 PMIs 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.

Vladki

Quote from: freddyhayward on January 17, 2021, 08:54:27 PM
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).

freddyhayward

Quote from: Vladki on January 18, 2021, 08:51:22 AMIs 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.

Mariculous

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?

Vladki

Quote from: freddyhayward on January 18, 2021, 09:37:17 AMIt'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.

Mariculous

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.

Vladki

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.

Ranran(retired)

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.
ひめしという日本人が開発者達の助言を無視して自分好みの機能をextendedに"強引に"実装し、
コードをぐちゃぐちゃにしてメンテナンスを困難にし(とりわけ道路と建物関連)、
挙句にバグを大量に埋め込み、それを知らんぷりして放置し(隠居するなどと言って)別のところに逃げ隠れて自分のフォーク(OTRP)は開発を続けている
その事実と彼の無責任さに日本人プレイヤーは目を向けるべき。らんらんはそれでやる気をなくした(´・ω・`)
他人の振り見て我が振り直せ。ひめしのようにならないために、らんらんが生み出したバグや問題は自分で修正しなくちゃね(´・ω・`)

Mariculous

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)

Vladki

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.

freddyhayward

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.

freddyhayward

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:
Quote from: freddyhayward on January 17, 2021, 01:00:12 PM1. 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.

Quote from: freddyhayward on January 17, 2021, 01:00:12 PM2. 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:

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.

Quote from: freddyhayward on January 17, 2021, 01:00:12 PM3. 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.

Quote from: freddyhayward on January 17, 2021, 01:00:12 PM
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.

freddyhayward

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.

Matthew

Quote from: freddyhayward 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.

: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!

QuoteConversion 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?

QuoteAnecdotally, [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?
(Signature being tested) If you enjoy playing Simutrans, then you might also enjoy watching Japan Railway Journal
Available in English and simplified Chinese
如果您喜欢玩Simutrans的话,那么说不定就想看《日本铁路之旅》(英语也有简体中文字幕)。

Vladki

Quote from: Matthew on January 19, 2021, 12:52:30 PMThis 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 ;-)

freddyhayward

Quote from: Matthew on January 19, 2021, 12:52:30 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

Quote from: Matthew on January 19, 2021, 12:52:30 PMI 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).

Quote from: Vladki on January 19, 2021, 05:11:41 PMAnd 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.

jamespetts

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:


              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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.

freddyhayward

Quote from: jamespetts on January 19, 2021, 10:42:00 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?

jamespetts

Quote from: freddyhayward on January 19, 2021, 11:09:28 PM
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.
Download Simutrans-Extended.

Want to help with development? See here for things to do for coding, and here for information on how to make graphics/objects.

Follow Simutrans-Extended on Facebook.