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
@LordAro
Copy link
Member

@LordAro 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 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 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 Jul 16, 2019
@LordAro
Copy link
Member

@LordAro LordAro commented Aug 17, 2019

Needs a rebase

Correction: Probably just needs the debug code removing

nielsmh
nielsmh previously requested changes Aug 18, 2019
Copy link
Contributor

@nielsmh nielsmh left a comment

The test/measurement code needs to be removed.

src/core/kdtree.hpp Outdated Show resolved Hide resolved
LordAro
LordAro approved these changes Oct 7, 2019
@LordAro LordAro dismissed nielsmh’s stale review Oct 7, 2019

out of date

@nielsmh nielsmh merged commit 652fb40 into OpenTTD:master Oct 8, 2019
8 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Linked issues

Successfully merging this pull request may close these issues.

None yet

3 participants