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 town name refresh on viewports #7242

Closed
wants to merge 1 commit into from

Conversation

GabdaZM
Copy link
Contributor

@GabdaZM GabdaZM commented Feb 17, 2019

Instead of checking all town name signs, filter by the Y coordinate of the signs, and check only filtered town names.
A town gets into the filtered town if the Y coordinate of its sign is between the lines marked by the redraw box top and bottom. There is no filtering by the X coordinates, as the width of the town names can change in a wide range.
Time complexities:

  • original: O(#towns)
  • this one: O(log(#towns)) + O(#filtered_towns)

Performance improvement can be observed only in maps with high town count. On a 4096x4096 map with 30k towns (scenario editor) when scrolling on the map the time of viewport drawing went form 90 ms to 5 ms with this improvement (according to the framerate window).

src/town.h Outdated
uint size;

public:
TownList(){
Copy link
Member

@PeterN PeterN Feb 18, 2019

Choose a reason for hiding this comment

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

Space between ) and {
Also the constructor can be written as TownList() : needs_resort(true), initialized(false), size(0) { }

src/town.h Outdated
@@ -295,4 +297,72 @@ static inline uint16 TownTicksToGameTicks(uint16 ticks) {

extern CargoTypes _town_cargoes_accepted;

/** Data structure with cached data of towns. */
/* ToDo: documentation */
/* ToDo: move function definitions to town_cmd.cpp */
Copy link
Member

Choose a reason for hiding this comment

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

Yes please!

@PeterN
Copy link
Member

PeterN commented Feb 18, 2019

Cache is never invalidated so does not handle creation of new towns. I'm not sure if towns ever get removed though.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 18, 2019

Cache is never invalidated so does not handle creation of new towns. I'm not sure if towns ever get removed though.

Yes, I forgot to add this to the ToDo. You can delete towns in scenario editor (and on random town generation can delete towns as well).

@citymania-org
Copy link

citymania-org commented Feb 18, 2019

Again instead of using a proper spatial structure you're making some knock-off that's not even any faster in the worst case :P. Same kd-tree/r-tree/... would easily solve both highlight problem and this range query. Also you probably can find some library to use so it would be even simpler to implement.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 18, 2019

I think sorting along the Y axis is a proper spatial structure. Sorting by the X axis would bring in lots of problems. Also kd-tree and r-tree are hard to balance, and in the scenario editor, you can add and remove towns.
I use built in functions/structures for storing, sorting and searching, the other function only decides when to sort, build or search, not the performance critical parts.
I would like you to give an example when this change is not faster in a game.

@PeterN: does/can this project use 3rd party open source libraries?

@PeterN
Copy link
Member

PeterN commented Feb 18, 2019

Yes it can but we tend not to as it complicates cross-platform support.

I don't think you need to worry about performance of removing or adding towns too much, it's not a hugely common occurrence and a few ms here and there for that is fine.

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Feb 19, 2019

With ~37k towns, instead of checking all signs, this approach can filter it down to about 300 (on the middle of the map, where most of the town can be found on a row). The sign redraw time can decrease from 2000 us to 50 us. As a single redraw of the whole screen (e.g. when zooming) can consist of more than 500 redraw calls even on small resolution, this could add up to a visible improvement.
On small maps the improvement is not much, 10 us -> 1 us per redraw call.

From the 50 us (with ~37k towns) 2-3 us is spent with finding the first town, the remaining time is needed to check the ~300 towns one by one. If the k-d tree in #7250 can be extended to include signs as well, it could speed it up even more, as the one by one check seems to be the most expensive part.

Instead of checking all town name signs, filter by the Y coordinate
of the signs, and check only filtered town names.
@GabdaZM
Copy link
Contributor Author

GabdaZM commented Mar 11, 2019

Closing in favor of #7250.

@GabdaZM GabdaZM closed this Mar 11, 2019
@GabdaZM GabdaZM deleted the town_sign_sort branch March 11, 2019 13:04
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

3 participants