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

Codechange: Improve performance of closest town lookups with cache #7120

Closed
wants to merge 3 commits into from

Conversation

GabdaZM
Copy link
Contributor

@GabdaZM GabdaZM commented Jan 27, 2019

Work in progress.
Works only with the first map loaded, have to restart the whole game for a new map.
To see what it does, you have to select land info, or a construction function (station, tree, ...).
I only put part into the viewport to see how it works. It is by no means a good place to initialize. (I might need help with where to put initializations and destructions).
I plan to move the whole thing into a class. Question: should I out the map array part into the class as well?
No function to add or remove a town, it will be added later.

@TrueBrain TrueBrain added the wip Work in progress. Feature branch that will require feedback during the development process label Jan 27, 2019
@nielsmh
Copy link
Contributor

nielsmh commented Jan 27, 2019

Remember to run the projects/generate script when modifying source.list as well, your current commit doesn't have the updated Visual Studio project files, so the build fails on Windows with VS.

@nielsmh
Copy link
Contributor

nielsmh commented Jan 27, 2019

Demo

@Eddi-z
Copy link
Contributor

Eddi-z commented Jan 27, 2019

This should really use euclidean distance, not manhattan.

@nielsmh
Copy link
Contributor

nielsmh commented Jan 27, 2019

As someone also mentioned on IRC, the map overlay of every tile within the town boundary highlighting might be a bit excessive. I think it'd be better to only highlight the borders of the "town zone", and then draw that highlight over the top of station catchment area, so both are visible.

Perhaps also add a line to the station build window showing the name of the town the station will be named after, below the accepts/supplies lines.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Jan 28, 2019

This should really use euclidean distance, not manhattan.

What do you mean? To change the distance measurements in the whole game to euclidean?

the map overlay of every tile within the town boundary highlighting might be a bit excessive

The visualization won't be a part of this PR. However there are other options, like using smaller highlights so both the catchment and the town zone can be seen, or using a full-tile, homogeneous, mostly transparent fill for all the tiles in the town zone.

@Eddi-z
Copy link
Contributor

Eddi-z commented Jan 29, 2019

This should really use euclidean distance, not manhattan.

What do you mean? To change the distance measurements in the whole game to euclidean?

all fibres in my mathematical knowledge scream at me "voronoi makes no sense with distances other than euclidean", so i would start to make the voronoi with that, and then consider each place that uses "distance to town" whether to switch it to euclidean by using this voronoi diagram.

@Eddi-z
Copy link
Contributor

Eddi-z commented Jan 29, 2019

like using smaller highlights so both the catchment and the town zone can be seen

there used to be a tile highlighting patch that enabled showing two layers of data simultaneously

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Jan 29, 2019

all fibres in my mathematical knowledge scream at me "voronoi makes no sense with distances other than euclidean

I think you got is backwards. I wanted to make a map cache array for the CalcClosestTown for each tile, and named it voronoi, so your suggestion should be that I should rename the function and file.
On the other hand I think it perfectly make sense to use L1 distances (Manhattan) instead of L2 distance (Euclidean) for a Voronoi diagram, it works well with its definition.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 1, 2019

I put most of the code into a class, and now I feel it was a bad idea.
Is it possible that more that one instance of this closest town map is needed?
If there is a need for only one instance, storing the functions in a class might be unreasonable.
My main motivation was to make some functions private. If I don't declare a function in a corresponding header file, it will behave like a private function from the aspect of the other files of the codebase, right?

@GabdaZM GabdaZM force-pushed the voronoi branch 2 times, most recently from ac32056 to 8c3c884 Compare February 2, 2019 18:57
@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 2, 2019

I've dropped the idea to put the diagram in a class.
Town add/remove function is now working.
It is no more necessary to reload the whole game to use the voronoi map in different maps.
ToDo:

  • Initialize it in the appropriate places.
  • change the CalcClosestTownFromTile function to get the result from this diagram.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 3, 2019

Demo function added: checks whether new industry can be built for the town.
lrv3zy6nh1

@glx22
Copy link
Contributor

glx22 commented Feb 3, 2019

Don't use fprintf for debug stuff, that breaks regression tests. We have a DEBUG macro for that and you can probably add a debug category if needed

@PeterN
Copy link
Member

PeterN commented Feb 4, 2019

For the functions only used within town_voronoi.cpp, can you mark them with static?

src/map_func.h Outdated Show resolved Hide resolved
@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 5, 2019

Don't use fprintf for debug stuff, that breaks regression tests. We have a DEBUG macro for that and you can probably add a debug category if needed

I deleted all the debug messages, they were there only for the development phase of the commit.

For the functions only used within town_voronoi.cpp, can you mark them with static?

Done.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 5, 2019

The industry founding related part is now deleted, only the closest town visualization part remained for the duration of the review (it will/should be deleted before merge).

@nielsmh nielsmh removed the wip Work in progress. Feature branch that will require feedback during the development process label Feb 8, 2019
@PeterN
Copy link
Member

PeterN commented Feb 9, 2019

When the town visualization part is removed, what do these changes do actually do?

I think "Feature: " should be reserved for user-visible changes, which I don't think this counts as by itself.

@nielsmh
Copy link
Contributor

nielsmh commented Feb 9, 2019

Agree with @PeterN, the title should rather be "Add: Nearest town cache" or "Change: Improve performance of nearest town lookups with cache"

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 9, 2019

Both of you are right, I am renaming the commits. I am using "Codehange" instead of "Change", as there is no visible change for users.

When the town visualization part is removed, what do these changes do actually do?

It will help the implementation of new features which were held back by the performance of the closest town search. One of these is the industry founding pre-check (see previous gif), though I have to implement a viewport refresh improvement first for this check.
According to @SamuXarick, some AIs use closest town lookup a lot, so this change might help their performance as well.

bool _hold_next_add;
TownID _town_on_hold;

typedef GUIList<const Town*> TownList;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could this not be a std::vector? I think the plan is to scrap our custom implementations and use std classes where we can.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done. (I'll just have to remove the shortlist include part.)

@ldpl
Copy link
Contributor

ldpl commented Feb 11, 2019

It seems you're adding an extra uint16 map array for your cache which basically means increasing OpenTTD memory usage by 20%. That's quite a significant number especially for servers that run multiple OpenTTD processes. And so far I don't see any evidence of nearest town calculation being an actual performance issue. It may be needed for a potential town zone patch but it's own necessity is questionable (especially for servers) and there are lots of ways of doing it much more efficiently in regard to memory consumption.

@Moth-Tolias
Copy link

please consider leaving the town visualisation in, it would be really useful.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 12, 2019

@ldpl: You are right in case of the dedicated servers, but I think this increase in memory usage should not be a problem for clients and non dedicated servers. As the town visualization is useless in dedicated servers, this problem can be solved with a check, and in case of a dedicated server, the current CalcClosestTownFromTile can remain. In case of a new feature that would use closest town calls heavily even in dedicated servers, this problem can be discussed again.
It is true, that this method is optimized for CPU usage rather than memory, but the goal was to make it possible to spam the closest town calls.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 12, 2019

@Moth-Tolias: the town visualization is a separate feature, but the main goal is to have that, and this PR is a preparation work for that. The current visualization is really crude so there is quite some work with this :)
By the way, where/when would you use this visualization? One of my problem is to define when to show this highlight.

@ldpl
Copy link
Contributor

ldpl commented Feb 12, 2019

@Gabda87 IMO even in a client case you're trading too much memory for a too little performance gain. It's such a heavy memory usage that in some cases like random requests you can even lose in performance to some memory-effecient structure due to CPU cache misses. Not that random requests are of any use in openttd anyway but just for town visualization there are ways of doing it more memory-efficient. Since you only need to query in a rectangular area even something as simple as presorting tows by distance and using heuristics to update when moving to the next tile should be fast enough with almost zero memory cost.

Also keep in mind there are some players requesting larger maps like 16k. And if that ever makes it into the game cache usage will be even more of a concern.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 12, 2019

@ldpl The bigger the map, the more performance gain can be achieved with this modification. Of course if we only look at the number of calls in the current version, this mem usage - performance trade does not worth it. 20 % mem increase seems like a lot, but in case of a 4k x 4k map, it is 32 MB, and it shouldn't be an issue with not dedicated servers (as a map of this size requires quite a CPU, and the mem next a CPU of this kind can handle the 32 MB increase).
If you can recommend a more memory efficient method to store this information with still constant time complexity for lookups, I will look into it to see if I can implement it.

@PeterN
Copy link
Member

PeterN commented Feb 12, 2019

If it could be improved, please do. We shouldn't be too concerned about map sizes that are not implemented though.

@ldpl
Copy link
Contributor

ldpl commented Feb 12, 2019

Check this: https://bitbucket.org/citymania/cmclient/commits/70195ad6d3252c569ed234ccc9d3c4ba1e3b8c23

It's a very crude implementation of an even simpler idea but it's already enough to use manhattan-based zones without any lags.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 12, 2019

I really like the idea where you stop the search in the sorted list after p.first > best + ref_dist. One of the downsides is that in CLOSEST_CACHE_THRESHOLD you have to include the clients with 4k display resolution in max zoomed out cases, so all the tiles on the screen must be within the threshold to avoid rebuilding the cache all the time when faraway tiles in the screen gets dirty, so ref_dist can be large as well (although it still stops the search much faster compared to going through all the towns, but it still can be a few 100). I don't know what could be the max distance between tiles on the maximum possible resolution when max zoomed out.
My other concern is the case with additional viewports, as tiles shown in different viewports can be really far. It can be solved with separate cache for each viewport, but it makes the implementation quite complex. If we even want to avoid cases when more viewport want to rebuild their caches, it becomes quite the headache.

@nielsmh
Copy link
Contributor

nielsmh commented Feb 12, 2019

I tried making two optimized builds of OpenTTD, one with just the ai-framerate patch (#7178), and one with this patch + ai-framerate, both builds rebased onto origin/master.

I then created a new game on a 2048x1024 map with 5 AI players all starting immediately, saved this game on January 1st, and loaded the same save both both builds. Then opened the Framerate window, placed the two games side by side, and unpaused both.

The build with this patch runs upwards 25% faster in this test case, and in fast-forward mode quickly pulls ahead in simulation date.

@nielsmh
Copy link
Contributor

nielsmh commented Feb 12, 2019

On a note, the terrain highlight still happens when you use the land area information tool (? button on main toolbar), is that intended?

@ldpl
Copy link
Contributor

ldpl commented Feb 12, 2019

@Gabda87 I know it's far from a perfect solution. I just made it to show that even a simplest check can take advantage of a fact that there isn't much difference between neighboring tiles. If you properly adjust it to tile rendering order and mb use some clever structures it can perform even better. Also I didn't want to change zoning patch too much and it works with every tile individually. If you know the whole rendering zone beforehand you can find all the relevant towns in even more efficient way as you basically need to find intersections of rendering rectangle with Voronoi diagram edges.

As for viewports I don't think it's an issue as long as they render separately (not sure if that's true). Sorting towns isn't that slow, it's ok to do that for each viewport.

Also even if you don't take advantage of neighboring tiles there are plenty of 2d structures that can solve NNS effeciently: https://core.ac.uk/download/pdf/82472164.pdf

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 12, 2019

@nielsmh Thank you for the performance measurement!
The tile highlight is intended for every rectangle selection tool, as every modification I make might break something, so taking out this visualization should be the last modification I make on this PR.

Caching closest town information for all tiles.
The cache is a map sized Voronoi diagram with Manhattan distances.
@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 13, 2019

It seems like most of the data structures that uses O(#towns) space needs O(log(#towns)) time, which is better the the current linear time, but not the constant time like in this PR. I still like the idea of being able to spam the closest town calls, so I think a settings option to enable/disable this function would be better than to use another structure.
For dedicated servers, the default behavior might be to use the original closest town calculation, with the ability to set to use this one, and for every other cases (where the memory increase should not be a problem) the default should be this method (with maybe the ability to use to original).

@PeterN
Copy link
Member

PeterN commented Feb 13, 2019

I'm wondering what dedicated server is going to have issues with an additional 2MB (for a large 1024x1024 map) per instance?

@PeterN
Copy link
Member

PeterN commented Feb 13, 2019

Had a quick play around, the nearest town shapes are quite surprising!

@PeterN
Copy link
Member

PeterN commented Feb 13, 2019

Wondering if this can be made more generic, as some interesting landscape generation could be done with voronoi...

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 13, 2019

You mean dropping random points to the map (independently from the towns), make the Voronoi diagram, and have some fun with map generation? I can think of an island map (or if we invert that, some lake), or rivers on the domain borders.

@Moth-Tolias
Copy link

By the way, where/when would you use this visualization? One of my problem is to define when to show this highlight.

@GabdaZM mostly when placing stations and other infrastructure, so as to avoid the wrath of towns i've previously gotten into poor standing with =] i'm very glad to know this visualisation is in the works!

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 17, 2019

@Moth-Tolias Hmm, the tile highlight color could even correlate with the company rating in the town.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 17, 2019

I'm wondering what dedicated server is going to have issues with an additional 2MB (for a large 1024x1024 map) per instance?

No option to turn this caching on and off then :)
Is there anything you think I should add/change?

@stale
Copy link

stale bot commented Mar 19, 2019

This pull request has been automatically marked as stale because it has not had any activity in the last month.
Please feel free to give a status update now, ping for review, or re-open when it's ready.
It will be closed if no further activity occurs within 7 days.
Thank you for your contributions.

@stale stale bot added the stale Stale issues label Mar 19, 2019
@stale stale bot closed this Mar 26, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
stale Stale issues
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

8 participants