Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Change: Non-rectangular sparse station catchment area #7235

Merged
merged 4 commits into from Mar 9, 2019

Conversation

PeterN
Copy link
Member

@PeterN PeterN commented Feb 16, 2019

This patch changes station catchment from a single rectangle covering the largest catchment radius of the station, to individual tiles based on the catchment radius of the station tiles near them.

The non-saved calculated set of catchment tiles is stored off-map within the station class. This set is then tested against when cargo is delivered to and from industries and towns.

Adds a third station catchment area option:

Original fixed-size catchment area:
catchment0

Modified variable-size catchment area:
catchment1

New non-rectangular sparse catchment area:
catchment2

@PeterN
Copy link
Member Author

PeterN commented Feb 16, 2019

This sparse catchment area is how many players believe it already works, e.g. #7198.

@PeterN
Copy link
Member Author

PeterN commented Feb 16, 2019

So the big issue with this is performance due to the FOR_ALL_STATIONS loop within FindStationsAroundTiles().

I tested with the same savegame as with the above screenshots, using variable/modified catchment (not sparse) and world ticks jumped from 0.62ms to 1.47ms

src/station_cmd.cpp Outdated Show resolved Hide resolved
@Eddi-z
Copy link
Contributor

Eddi-z commented Feb 16, 2019

this is again one of those cases where we should ask "why do we even bother keeping the original version around"?

also, nobody is going to understand what is meant by "sparse catchment area".

@planetmaker
Copy link
Contributor

I have to agree with Eddi: making this an option does not sound like a good idea - even when it somewhat breaks ancient savegames.

Making a change for catchment area towards what is actually expected by players (and maybe making the catchment area for gathering resources the same as distributing cargo) is a desirable change.

@PeterN
Copy link
Member Author

PeterN commented Feb 16, 2019

The option is already there, this just adds another variant. Yeah, sparse was the best word I could think of this morning :p

@J0anJosep
Copy link
Contributor

J0anJosep commented Feb 16, 2019

I think it is a significant improvement to make catchment areas more intuitive, so keep on with this PR.

I also wrote some patches for this concept of precise catchment area long ago. My code can be much better written, of course. I wrote it when I had little experience with coding.

Let me explain how I got to my current implementation of precise catchment areas. The first approach I used was saving the tiles caught by a station, as I understand PeterN has done. But in the code I wrote, that lead to performance issues. In a second approach I used a bool array, and later I used a bitmap, as more experienced developers pointed out.

TESTING: I have a big savegame where world ticks need 3.25 ms on original algorithm, 10ms on the PR proposed by PeterN and 3.5 ms on my branch. Anyway, my proposal may be slightly faster than those 3.5 ms, because the "bitmap" struct I use probably isn't a good one. Moreover, I think my proposal differs with PeterN's one, as it is much more restrictive trying to make catchment and delivery areas equal (see that in TriggerWatchedCargoCallbacks on houses is dealt with in my branch).

So... glad someone has brought something like this to a PR. I will review it when I can.

@PeterN
Copy link
Member Author

PeterN commented Feb 17, 2019

Urgh, turns out in improving it I ended up changing quite a few existing algorithms, so I need to figure out how to chop it up.

src/station.cpp Outdated Show resolved Hide resolved
@PeterN PeterN changed the title New non-rectangular sparse station catchment area Change: Non-rectangular sparse station catchment area Feb 18, 2019
@PeterN
Copy link
Member Author

PeterN commented Feb 18, 2019

Using the Wentbourne save, the original commit suffers badly. World ticks jumped from around 2ms to 40ms, which is clearly unacceptable.

The second commit adds nearby stations caching to industries and towns. This involves quite a bit of extra code, as the cache needs to be maintained, however the performance benefit over the first iteration is vast, as world ticks is around the same as in this save.

@citymania-org
Copy link

citymania-org commented Feb 18, 2019

Following our discussion in IRC I thought a bit about your station patch, but can't really suggest any good structure or algorithm here as I don't know how frequent each operation is. Have some random thoughts though:

  1. bitmap instead of tile set for each station is indeed a good idea. That alone should offset any performance drop of non-rectangular zones.
  2. 20x20(or so) tile search is a very fast operation so stations_near caches may not even be worth maintaining. Especially town one as towns grow very often and rebuilding cache each time is costly. In fact, with my recent patches they can grow mind-boggingly fast (up to 1 house/tick). Though there isn't currently a public method to achieve such speed (only savegame or command editing) and even when/if such method will be added it won't be used that often it's still something to keep in mind. But anyway just a lookup with town->stations_near->catchment_tiles loop doesn't look faster to me than 20x20 search.
  3. For each station you have a list of stations that have intersecting catchment area. Then for each tile cache any covering station and

@ldpl
Copy link
Contributor

ldpl commented Feb 18, 2019

On second thought, I probably shouldn't use citymania account for commenting. Even if my personal one sucks xD

@PeterN
Copy link
Member Author

PeterN commented Feb 18, 2019

  1. If checking a particular tileindex inside a bitset is more performant than the same of an unordered set, yes.

  2. The catchment_tiles loops are only used when recalculating the caches, otherwise for industries we only care about the stations_near list itself (because we already checked its catchment when adding it), and for houses we only need to additional test if a house tile is inside the catchment of the listed stations. Without the caches, indeed you'd have to do a tile loop, and in many cases you can't abort early as you want to collect all nearby station tiles.

  3. Not sure where this is heading.

@ldpl
Copy link
Contributor

ldpl commented Feb 18, 2019

@PeterN

  1. unordered_set seems to be hash set and while is has same theoretical performance of O(1) per lookup bitmaps should be much faster on practice. And it gets better with rectangular area lookups. Also you can reduce memory consumption as you only need 1 bit / tile.
  2. It's not just for recalculatiing caches, it's for any cargo production which happens very often: MoveGoodsToStation->StationFinder::GetStations()->FindStationsAroundTiles. So a loop of (catchment + area)**2 tiles (easily CPU cached) turns into area**2*#stations_near tile lookups with questionable performance.
  3. Oops :) For each station you have a list of stations that have intersecting catchment area. Then for each tile cache any covering station and when you want to find all nearby stations check that first one an all it intersecs. It's just a random idea though, not sure if it's of any actual use. Nice part about it is that you can easily see if there are no covering stations. But when there are, again, tile search is probably better.

@PeterN
Copy link
Member Author

PeterN commented Feb 18, 2019

  1. Is std::bitset worth using or some other complex construct?

  2. FindStationsAroundTiles doesn't iterate catchment_tiles, For house tiles it just checks a single tile is in the catchment. Yeah, I should remove the w & h parameters are they are always 1! For industries again it never iterated catchment_tiles, however this catchment lookup is going to be removed because that's already handled by the stations_near list.

  3. I'll have to think about what this is trying to be.

@J0anJosep
Copy link
Contributor

I think a bitset would make things easier.

I have checked your PR and my branch. For big savegames, memory usage drops from 228 MB to 214 MB or from 323 MB to 311 MB. Comparing times with those savegames, PeterN PR/JJ Branch, 3.02/3.08 and 1.60/1.80. My branch although is far from efficient, as I kept the original catchment algorithms and modified catchments, and I didn't optimize it as much as PeterN current PR.

So, I think a generic bitmap/bitset could be used. This is the one I used, but for sure it can be improved.

@J0anJosep
Copy link
Contributor

I don't know whether this is out of scope, but I will ask anyway. On this function:
TriggerWatchedCargoCallbacks (on station_cmd.cpp)
Does the full TileArea of the station get the trigger callback, or it should only trigger for tiles under catchment?
If it should trigger for tiles under catchment, I think it will speed up your PR even more.

@PeterN
Copy link
Member Author

PeterN commented Feb 18, 2019

Probably should be under the catchment tiles only. Same with the subsidy tests.

@PeterN
Copy link
Member Author

PeterN commented Feb 18, 2019

Performance improvement on the Wentbourne savegame:

Unmodified master: World tick is 1.9ms per game tick.
std::unordered_set: World tick is 1.75ms per tick.
BitmapTileArea: World tick is 1.45ms per tick.

@PeterN
Copy link
Member Author

PeterN commented Feb 18, 2019

Okay, there's an issue with station catchment somewhere, got some spurious tiles :-)

@PeterN
Copy link
Member Author

PeterN commented Feb 19, 2019

I think a new building finding a new nearby station is rare enough that that the Town::stations_near.Sort() on addition will not be a performance issue.

@Eddi-z
Copy link
Contributor

Eddi-z commented Feb 19, 2019

I haven't checked which sorting algorithm is used here (probably qsort?), but some sorting algorithms handle "nearly-sorted" lists more gracefully than others

@PeterN
Copy link
Member Author

PeterN commented Feb 19, 2019

It's just a simple QSort. The list is already sorted before the addition. We do have Gnome sort available if that would be better. The list is generally in the order of low tens of entries, not hundreds.

@ldpl
Copy link
Contributor

ldpl commented Feb 19, 2019

I'm actually surprised how well this patch handles a stress-test. Memory consumption is only about 2% more than master. Though it's mostly due to master itself gobbling a ridiculous amount of memory xD
CPU load seems to be doing pretty well too. But I managed to crash it so that's something I guess :p
Happens a few secs after unpausing the game. Though I'm not sure it's a perfectly correct save but it runs in 1.9.0-beta2 without any issues.
gr0_50k_stations63.zip

UPD: crash log: https://paste.openttdcoop.org/pwbjmocxr

@PeterN
Copy link
Member Author

PeterN commented Feb 25, 2019

Ok, so FindStationsAroundTiles has reverted back to doing a map-scan rather than a station-scan, albeit using iterators instead of nested for-loops. It is significantly faster on games with lots of stations, and is pretty much constant speed, unless there are overlapping stations. In that case, station-scan doesn't win anything anyway.

Big reason not to use station scan is we limited the area by max station spread, however this can be reduced in game after the fact, and thus we'll end up with incorrect information.

@PeterN
Copy link
Member Author

PeterN commented Mar 4, 2019

I think it's time to squash most of this together, except for the first 3 commits. Yay/nay?

@nielsmh
Copy link
Contributor

nielsmh commented Mar 4, 2019

Yep probably time to squash and final review.

@PeterN
Copy link
Member Author

PeterN commented Mar 6, 2019

4k x 4k map, high towns 100% 10x cities, very fast town growth, but no vehicles:

Master world ticks: 16.91ms/t
non-rect-catchment world ticks: 12.71ms/t

This suggests the the performance benefit of generating cargo not having to do a tile search seems to outweigh the extra cost of expanding towns doing it instead.

@PeterN
Copy link
Member Author

PeterN commented Mar 9, 2019

Awkwardly, this rebase effectively reimplements the neutral station handling changes in a different way.

@PeterN PeterN merged commit 8b1b3fd into OpenTTD:master Mar 9, 2019
@PeterN PeterN deleted the non-rect-catchment branch March 9, 2019 16:50
PeterN added a commit to PeterN/OpenTTD that referenced this pull request Apr 16, 2019
douiwby pushed a commit to douiwby/OpenTTD that referenced this pull request Apr 16, 2020
@nielsmh
Copy link
Contributor

nielsmh commented Feb 22, 2021

This also actually fixed #5661

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

9 participants