Speed up the comparison time lookups#338
Merged
CryZe merged 2 commits intoLiveSplit:masterfrom Jun 11, 2020
Merged
Conversation
We use a Vec here now because a HashMap would require hashing the comparison and then comparing the comparison with the string at the index calculated from the hash. This means at least two full iterations over the string are necessary, with one of them being somewhat expensive due to the hashing. Most of the time it is faster to just iterate the few comparisons we have and compare them directly. Most will be rejected right away as the first byte doesn't even match, so in the end you'll end up with less than two full iterations over the string. In fact most of the time Personal Best will be the first in the list and that's the one we most often want to look up anyway. One additional reason for doing this is that the ahash that was calculated for the HashMap uses 128-bit multiplications which regressed a lot in Rust 1.44 for targets where the `compiler-builtins` helpers were used. rust-lang/rust#73135 We could potentially look into interning our comparisons in the future which could yield even better performance.
e1dbd59 to
710f53c
Compare
wooferzfg
approved these changes
Jun 11, 2020
Member
wooferzfg
left a comment
There was a problem hiding this comment.
These changes and the explanation make sense to me.
Also, for what it's worth, I'm not noticing meaningful differences in performance when running my benchmark branch with these changes vs. master (and I don't see a difference when using Rust 1.43 either), so I'm questioning whether those results are actually valuable.
Co-authored-by: wooferzfg <spapushin@gmail.com>
Collaborator
Author
|
I'll merge this regardless for now. Though I would like to understand why you are not seeing any improvements. We should look into this again. |
CryZe
added a commit
to CryZe/LiveSplitOne
that referenced
this pull request
Jun 14, 2020
This updates livesplit-core which brings a variety of performance improvements: - The Layout State is now being reused and thus most frames don't require any heap allocations anymore. However we still serialize everything over into a JSON string for now, which puts a lot of garbage on the JS heap. LiveSplit/livesplit-core#334 - The frequent performance.now() calls we do, first lookup up the window and performance object every time. This tripled the amount of calls we do over into JavaScript, with each call into JavaScript being quite expensive in Chrome. LiveSplit/livesplit-core#335 - By introducing a timer snapshot mechanism we further reduce the calls to performance.now() to a single time. LiveSplit/livesplit-core#339 - Rust 1.44 regressed the performance of 128-bit integer multiplications by accident. Those are used for hashing the comparisons when looking up the times for a comparison, which is something we do very frequently. We however don't have many comparisons, so a simple Vec that we loop through is a bit faster, even in native code, and quite a bit faster in the web, because of the Rust 1.44 regression. LiveSplit/livesplit-core#338 - We delay registering the Gamepad Hook Interval until the first gamepad button is registered. Most people won't use a gamepad, so the interval just waits cpu time for no reason. LiveSplit/livesplit-core#340
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
We use a Vec here now because a HashMap would require hashing the comparison and then comparing the comparison with the string at the index calculated from the hash. This means at least two full iterations over the string are necessary, with one of them being somewhat expensive due to the hashing. Most of the time it is faster to just iterate the few comparisons we have and compare them directly. Most will be rejected right away as the first byte doesn't even match, so in the end you'll end up with less than two full iterations over the string. In fact most of the time Personal Best will be the first in the list and that's the one we most often want to look up anyway.
One additional reason for doing this is that the ahash that was calculated for the HashMap uses 128-bit multiplications which regressed a lot in Rust 1.44 for targets where the
compiler-builtinshelpers were used.rust-lang/rust#73135
We could potentially look into interning our comparisons in the future which could yield even better performance.