Topic: Lower than expected private car traffic

[freddyhayward]

I am currently investigating a possible bug shown on the Bridgewater-Brunel server in which there appears to be much, much less inter-city private car traffic than expected even in cases where cities are linked with good roads and have had enough time to refresh their routes. I am not able to reproduce this in a minimal test case, so will need to work on the server saved game for testing, which is likely to be a long and difficult task.

I have been collecting data on the number of stored private car routes. The left hand side indicates the reading set while the right is the writing set. This particular change occurred at a force-sync, where it seems the reading set was swapped for the writing set which had far fewer routes, presumably because the private car route finder had not finished checking routes for its current city and had not yet replaced those routes deleted at the start of the check. I'm not sure whether or not this contributes to the problem.

[prissi]

I am just curious: Does this mean there are 14 million route generated each time a connection is changed? Because I wonder, if there were ever 14 million city cars on that map at any point. Otherwise treating citycars as convois and let them calculate their own route would be much more efficient.

[jamespetts]

Freddy - that is very helpful, thank you. Further investigation shows that what was happening was that the list of cities awaiting a private car check was being reset every time that the game was saved/loaded because I had not written code to save the contents of this list (I presumably had not thought it necessary at the time).

I have now added the code for loading/saving of this list, which prevents the reading/writing set from being swapped on loading and saving. What I infer may well have been happening was that the cities would always populate the list in the same order, so cities near the top of the list would be checked but those near the bottom may well never be reached.

I shall look forward to seeing the effect of this with to-morrow's nightly build.

Prissi - I had considered this some time ago, but it is not just the private car graphics that need this information: it is also used for very large numbers of attempted private car trips that turn out to take too long and are skipped in favour of an alternative destination.

[freddyhayward]

I have tested this for a long time and found that private car routes will almost never be updated at all, since the swap only occurs after all cities have been checked. I gave up after the total number of routes in the writing set reached 100 million, whereas the reading set had not increased from 14 million.

[jamespetts]

Thank you for your testing. Can I check precisely how you are computing the number of stored routes? It is difficult to see why there should be 14 million, let alone 100 million such routes. There are 307 cities and 2758 industries in the Bridgewater-Brunel game at present. The number of attractions is not stated. The private car route finder will find a route starting at all cities and ending in any city, industry or attraction.

Thus, the number of routes should be calculated in accordance with the below formula:

R = C * (C + A + I)

where:

R: Routes
C: Cities
A: Attractions
I: Industries

We do not know the number of attractions, so if we assume it to be the same number as industries, we get:

R = 307 * (307 + 2758 + 2758)

which equates to 1,787,661.

I cannot immediately remember whether a reverse route is created from out of city attractions back to cities; if it is, the formula would be:

R = C * (C + 2A + 2I),

which in our case would give

R = 307 * (307 + (2 * 2758) + (2 * 2758))

which equates to

3,481,073

Either the way in which these routes is being counted is wrong, or there are for some reason that is unclear an excessive number of routes being generated.

There may be some merit in giving information in the display dialogue about the private car route finder in the same way as information is given about the path explorer.

[freddyhayward]

Thank you for your testing. Can I check precisely how you are computing the number of stored routes? It is difficult to see why there should be 14 million, let alone 100 million such routes. There are 307 cities and 2758 industries in the Bridgewater-Brunel game at present. The number of attractions is not stated. The private car route finder will find a route starting at all cities and ending in any city, industry or attraction.

Thus, the number of routes should be calculated in accordance with the below formula:

R = C * (C + A + I)

where:

R: Routes
C: Cities
A: Attractions
I: Industries

We do not know the number of attractions, so if we assume it to be the same number as industries, we get:

R = 307 * (307 + 2758 + 2758)

which equates to 1,787,661.

I cannot immediately remember whether a reverse route is created from out of city attractions back to cities; if it is, the formula would be:

R = C * (C + 2A + 2I),

which in our case would give

R = 307 * (307 + (2 * 2758) + (2 * 2758))

which equates to

3,481,073

Either the way in which these routes is being counted is wrong, or there are for some reason that is unclear an excessive number of routes being generated.

There may be some merit in giving information in the display dialogue about the private car route finder in the same way as information is given about the path explorer.

By stored routes, I mean the total amount of routes stored in road tiles. If there are 10 roads, and each stores information about 10 routes, then I count this as 100 routes. Perhaps there is a more accurate term to describe this than 'routes', but it is a highly relevant definition because it directly corresponds to memory usage.

[jamespetts]

Perhaps "route tiles" would be a better definition?

Either way, we will need data, I think, to understand how long that it takes to process each city and what, if anything, further needs to be done about this. Note that private car routing will now run in the background when the server is paused because no clients are connected, will run with all 6 threads instead of 1 (because there is no client that can lose synchronisation) and will process 4x as many route tiles per step as when clients are connected and/or the game is unpaused.

[freddyhayward]

Either way, we will need data, I think, to understand how long that it takes to process each city and what, if anything, further needs to be done about this. Note that private car routing will now run in the background when the server is paused because no clients are connected, will run with all 6 threads instead of 1 (because there is no client that can lose synchronisation) and will process 4x as many route tiles per step as when clients are connected and/or the game is unpaused.

I ran some tests on my laptop. Without any limits to route tiles per step, it takes 10-25 seconds to find private car routes for each city on bridgewater-brunel. With a limit of 8192, each city takes roughly 3-4 minutes. With a limit of 32768 (4x8192), each city took 45-75 seconds (this is not really applicable to the time it takes while paused). I didn't conduct any tests with the server paused as I couldn't get this to work.

[jamespetts]

Thank you. The Bridgewater-Brunel server is set to 16,384 tiles per step, so each city should be taking 1.5-2 minutes when players are connected, thus taking between 460.5 and 614 minutes (7.6 - 10.2 hours) to complete the route search for all 307 cities.

With the rate multiplied by 4 and multiplied again by 6 (for multi-threading) when there are no clients connected, this should take between 19.18 and 25.5 minutes.

Having logged onto the server a little earlier, I see that the routes have, in fact, refreshed, presumably whilst nobody was connected. Memory usage seems fairly high, however, at ~8Gb, presumably because there are now far more private car routes in the world.

This suggests that performance is workable provided that there are significant periods (i.e. at least half an hour) during which players are offline each day, which does indeed seem to be the case.

One possible way of significantly reducing the computational load of this system if necessary would be not to calculate separate routes to industries and attractions inside cities, although this would not be ideal in gameplay terms, as doing this is specifically intended to allow for load balancing of different road routes through cities. For this reason, I do not want to do this unless necessary, and it appears as though it is probably not necessary, although I am minded to start the next game with fewer towns. I should note that the number of towns in this game has increased considerably as a result of player built towns, which has thus increased significantly both the computational load and memory requirement of this system. Consideration will need to be given as to what, if anything, to do about this in future server games.

[freddyhayward]

I tested a modification to the code that excludes all routes to industries and attractions. This saw a dramatic increase in performance, with each city checking all of its routes in roughly 0.3 seconds without limits, and roughly 3 seconds with the limit of 16384 tiles per step. This is obviously not a desirable solution since large volumes of traffic are destined for some attractions and industries. I will soon test a system that excludes destinations based on a threshold of combined visitor and employment demand.

[jamespetts]

Thank you for this: this is helpful. What we need is to maintain private car routes to individual attraction and industry buildings not in towns, but allow such buildings inside towns to be omitted in some cases. This is because the private car route checking system will allow private car travel to destinations inside towns even if there is not an individual route to them if the town itself is connected, using the town as a destination. This is not possible with industries and attractions out of towns. A large proportion of industries and attractions are, in fact, in towns.

Ideally, one would have a system in which whether in-town attractions and industries were checked depended on the size of the map (in the more technical sense of "map" rather than the tile size of the in-game map), perhaps measured by the number of route tiles as you measure in some of the above posts, and, even better, it would be possible to set this threshold in simuconf.tab.

Edit: Incidentally, do I infer that the motivation for this is to make the computation of private car routes more responsive to congestion and congestion alleviation measures such as bypasses?

[freddyhayward]

Thank you for this: this is helpful. What we need is to maintain private car routes to individual attraction and industry buildings not in towns, but allow such buildings inside towns to be omitted in some cases. This is because the private car route checking system will allow private car travel to destinations inside towns even if there is not an individual route to them if the town itself is connected, using the town as a destination. This is not possible with industries and attractions out of towns. A large proportion of industries and attractions are, in fact, in towns.

I don't think there would be much benefit in pursuing savings for in-town industries and attractions - the bulk of small, non-town destinations that I had aimed to exclude were sheep farms.

[jamespetts]

I don't think there would be much benefit in pursuing savings for in-town industries and attractions - the bulk of small, non-town destinations that I had aimed to exclude were sheep farms.

That would prevent any private car travel to these destinations at all, which would not be good; but it may be sensible to have the degree of route finding truncating to be customisable in simuconf.tab.

One possibility is to have only the nearest town(s) having routes to these industries and having other origins having to go through those towns, but this would require a much more substantial amount of coding work.

[jamespetts]

I have been working on something similar to what Freddy discussed above: my work so far can be found in the private-car-route-memory-saving branch on Github. This introduces a number of new settings to simuconf.tab. Four new settings are introduced, but, of those, three are usable, the other is experimental, mostly untested and what I have tested of it does not work: it would in any event increase rather than reduce memory consumption, so is only suitable for smaller maps.

The three useful new settings are documented in simuconf.tab and I quote the relevant parts:

# The following settings adjust the recording of private car routes.
# These are the routes encoded on the in-game roads that private cars
# follow when going from place to place. Without private car routes
# written into the world, private cars will move on the basis of
# a heuristic algorithm estimating which is the best way of getting
# to their destination, but this will often lead to wrong turns.
#
# However, properly writing these data can take a large amount of
# memory on a large map (and memory consumption of this increases
# exponentially with the number of cities). Thus, these settings
# are intended to allow fine tuning of how much in the way of
# route data are stored.
#
# The first two settings relate to whether private car route
# finding should not make individual routes to town industries
# and attractions. If these are enabled (a non-zero value),
# private cars headed to industries and attractions will instead
# use the route to the town in which the industry/attraction is
# located and move heuristically on entering the town.
# The number represents the minimum visitor demand (adjusted
# for scale - i.e., the numbers shown in game, rather than in
# the .dat files for the pakset) for an in-town industry/attraction
# before it is allowed to have its own route. This allows load
# balancing for high demand town buildings with different access
# routes without consuming large amounts of memory with routes to
# large numbers of lower demand buildings.

private_car_route_to_attraction_visitor_demand_threshold = 0
private_car_route_to_industry_visitor_demand_threshold = 0

# The next setting deals with private car routes to industries out
# of town. Cars will not be able to route to these by using the route
# to the town, so not having a private car route for these is more
# of a problem. However, if this is set to any non-zero value,
# no private car route to a non-consumer industry too far away
# to be within the maximum journey time tolerance of the fastest
# private car journey possible will be recorded. This may be
# a problem if private vans (industry owned goods transport)
# should ever be introduced, but that is not an issue at present.

do_not_record_private_car_routes_to_distant_non_consumer_industr ies = 0

With all three settings at zero, the current behaviour is continued. The routes to in-town industries/attractions and distant out of town non-consumer industries can be limited using the settings. For in-town buildings, where no route is recorded, private cars will simply use the route to the city itself. For out of town industries, private cars will not be able to use a route at all, but the system is such that it will only not add industries that are definitely too far away to be reached within the maximum commuting time tolerance and are not consumer industries, so it would be extremely rare that there would be any private car trips to these in any event.

Testing shows that, with the Bridgewater-Brunel game from May 1981, letting the private car route finder run twice (one for the reading set, one for the writing set), the peak memory consumption is approximately 9.6Gb. This is smaller than the October 1984 save, which is circa 11Gb. I am currently in the process of running a control test to check the memory usage in May 1981 with the above settings zeroed, but this testing takes a very long time because of the amount of time necessary to process all the private car routes on the Bridgewater-Brunel saved game.

I have also implemented some other fixes/features, including a display of the private car routing data next to the path explorer routing data in the display dialogue (I wonder whether these should be in their own tab rather than "GUI settings"?), have fixed an issue whereby buildings which could have multiple target tiles stored their routes multiple times (this did not increase memory consumption, as the earlier routes were overwritten, but may well have impacted on route refresh speed) and also fixed a bug which meant that the system of running the path explorer in the background on a network server was not multi-threaded as had been intended.

Unfortunately, I am experiencing intermittent crashes which are so rare that there is no reliable reproduction case, but common enough to be likely to cause problems on the server, seeming to occur most often when a client disconnects. I suspect that the last mentioned of the changes is responsible, since the crashes take the form of memory corruption inside the route hashtables being read/written multi-threadedly. The problem may well be that the mutex only protects against two threads writing at the same time rather than one thread reading and another writing, but I do not know of a way of a mutex being able to do this without also preventing multiple threads all from reading at the same time, which is safe and important to allow to ensure performance. An attempt to put the mutex around a wider section of code (the #if 0ed out code can be seen in the branch) results in entirely inexplicable thread related memory corruption crashes in freelist which are much more frequent than those which this code attempts to solve.

Unfortunately, this last problem may well delay significantly any attempt to deploy this improved code. Any suggestions as to how to deal with this problem would be much appreciated.

Edit: The threading problem/crash is not after all related to the fix for multi-threading in the background on the server, as the problem also occurs in single player mode. Also, my attempt at a controlled test was thwarted precisely by one of these hashtable memory corruption crashes.

[TurfIt]

Sounds like you want a rwlock instead of a plain mutex...

[jamespetts]

Sounds like you want a rwlock instead of a plain mutex...

That is extremely helpful, thank you: I have now managed to implement an rwlock and this does indeed solve the problem.

Now having been able to run the test, I am able to get a proper control for the 9.6Gb peak memory usage recorded above. With the new code with the default settings, rather than the adjusted settings with the thresholds set to 120 each, peak memory usage is circa 11.5Gb, giving a 1.9Gb saving with the new code. This is sufficient for this to have been worthwhile, I think, although it is not clear whether this will be enough to improve server performance on Bridgewater-Brunel.

[Matthew]

That is extremely helpful, thank you: I have now managed to implement an rwlock and this does indeed solve the problem.

Learning how to implement a new threading feature must have been a big effort. Thank you for doing this James, and to TurfIt for the suggestion!

Now having been able to run the test, I am able to get a proper control for the 9.6Gb peak memory usage recorded above. With the new code with the default settings, rather than the adjusted settings with the thresholds set to 120 each, peak memory usage is circa 11.5Gb, giving a 1.9Gb saving with the new code. This is sufficient for this to have been worthwhile, I think, although it is not clear whether this will be enough to improve server performance on Bridgewater-Brunel.

Bridgewater-Brunel has 8GB of RAM, right? Ubuntu Server is advertized as needing 512MB, so only 7.5GB is available for Sim-Ex. If the provisional adjusted settings use 9.6GB, performance will certainly be poor, and Freddy's solution would be preferable if its difficulties are overcome, though a bird in the hand is worth two in the bush. Maybe the settings could be adjusted more conservatively?

[jamespetts]

Bridgewater-Brunel has 8GB of RAM, right? Ubuntu Server is advertized as needing 512MB, so only 7.5GB is available for Sim-Ex. If the provisional adjusted settings use 9.6GB, performance will certainly be poor, and Freddy's solution would be preferable if its difficulties are overcome, though a bird in the hand is worth two in the bush. Maybe the settings could be adjusted more conservatively?

It is not that straightforward, as the command line server uses considerably less memory than the graphical clients because it does not load any of the graphics or sounds; thus, the relative memory figures represent the savings on the server, but the actual peak memory usage will be higher than on the server.

[jamespetts]

I have now implemented the private car memory saving branch changes into the master branch. The server will adopt the hard-coded default threshold values of 120 for the minimum visitor demand for linking in-city attractions and industries, so a memory saving should be apparent after two full refresh cycles of the private car route finder (one for the reading set and one for the writing set).

This branch also fixes some bugs with the private car route finder, including one in which some routes would be deleted inappropriately, as well as allowing the multi-threading to work in a network game that is paused with no clients connected (the previous attempt to do this had not worked).

I shall be interested in any feedback on this from to-morrow's nightly build onwards.

[Matthew]

Thank you for this, James!

Initial impressions are that performance is a bit better than yesterday, but the game still slows slower than real time at points. Joining seems to be a bit faster, but I have not timed it yet.

There is no difference in the speed of private car routing yet, but maybe it needs some time without people playing.