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 (un)zoom performance #6911

Merged
merged 1 commit into from Oct 26, 2018
Merged

Conversation

jmakovicka
Copy link
Contributor

When zooming out with a high res display, there can be about 150k sprites
to be sorted before displaying. With the O(n^2) complexity of the sprite
sorter, this can take several seconds.

This patch works around this by sorting the sprites by the xmin coordinate
first using QSort, which later allows an early bailout out of the inner
loop. This is enough to cut down the full unzoom time on a 4k display to a
fraction of second.

@michicc
Copy link
Member

michicc commented Sep 17, 2018

Side note: You can update your PR's by using git push -f to force an update to your github branch.

@jmakovicka
Copy link
Contributor Author

Side note: You can update your PR's by using git push -f to force an update to your github branch.

Sorry about that, I closed the previous PR after realizing it's a wrong solution and could not reopen it later after pushing the reworked version.

@LordAro
Copy link
Member

LordAro commented Sep 19, 2018

Only thing I can see codestyle-wise - opening brace of a function should be on a newline

@jmakovicka
Copy link
Contributor Author

Only thing I can see codestyle-wise - opening brace of a function should be on a newline

Fixed.

When zooming out with a high res display, there can be about 150k sprites
to be sorted before displaying. With the O(n^2) complexity of the sprite
sorter, this can take several seconds.

This patch works around this by sorting the sprites by the xmin coordinate
first using QSort, which later allows an early bailout out of the inner
loop. This is enough to cut down the full unzoom time on a 4k display to a
fraction of second.
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.

Seems to at least not break anything. Some quick testing shows not much improvement, but that was with a debug build where something else might drown out the difference sorting makes. My test scenario got 360 ms going to smallest zoom unpatched, versus 325 ms with this patch.

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

4 participants