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: Performance improvement in k-d tree FindNearest() #7608

Merged
merged 1 commit into from Oct 8, 2019

Conversation

GabdaZM
Copy link
Contributor

@GabdaZM GabdaZM commented May 25, 2019

The improvement is small, around 4-8%.
I have tested it on a few different map by calling the FindNearest() function on every tile of a map, and counting the number of the FindNearestRecursive() calls.
The version of this PR draft contains the old and the new FindNearest() functions, and an additional console command 'count_calls' to test the improvement.

@LordAro LordAro requested a review from nielsmh May 27, 2019 07:02
@LordAro
Copy link
Member

LordAro commented May 27, 2019

Usual commit message stuff applies.

In terms of the review, I'd recommend splitting it up properly - replace the function with the first commit, and add the debug stuff in a separate commit. Makes it much easier to review, especially when the debug stuff changes the contents of the function (removal of const due to call_counter - maybe mutable might be better here?)

@GabdaZM
Copy link
Contributor Author

GabdaZM commented May 28, 2019

Commit message changed.
Split the commit into two according to your suggestion. The commit message of the second one is made to fail the check, just in case.
Changed the counter to be mutable, thanks for the tip!

@GabdaZM
Copy link
Contributor Author

GabdaZM commented Jul 16, 2019

Added TICC-TOCC to measure time as well. It seems like the performance improvement is closer to 8%.

@GabdaZM GabdaZM marked this pull request as ready for review July 16, 2019 14:01
@LordAro
Copy link
Member

LordAro commented Aug 17, 2019

Needs a rebase

Correction: Probably just needs the debug code removing

Copy link
Contributor

@nielsmh nielsmh left a comment

Choose a reason for hiding this comment

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

The test/measurement code needs to be removed.

src/core/kdtree.hpp Outdated Show resolved Hide resolved
@nielsmh nielsmh merged commit 652fb40 into OpenTTD:master Oct 8, 2019
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