perf(YouTube): Filter litho components using prefix tree #447
Conversation
This file contains 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
…ilter strings are very short and the paths are large.
oSumAtrIX
changed the title
oSumAtrIX
changed the title
|
Since no protobuffer filters exist just yet, I tried merging #416 and this all works correctly as expected. When the flyout menu is opened: |
|
Cheers, in this case we can merge #416. It was put on hold due to performance issues |
|
I was able to speed up the flyout menu filtering even more by checking the protobuffer only if the flyout is present (since currently the flyout filter is the only filter that uses protobuffer filtering) If #446 is merged first, then I'll add this change to this PR: |
…t object. This lets the calling class know which filter in the group matched.
…s if the Setting is null or it's enabled.
oSumAtrIX
changed the title
oSumAtrIX
approved these changes
Aug 1, 2023
revanced-bot
pushed a commit
that referenced
this pull request
Aug 1, 2023
# [0.115.0-dev.5](v0.115.0-dev.4...v0.115.0-dev.5) (2023-08-01) ### Performance Improvements * **YouTube:** Filter litho components using prefix tree ([#447](#447)) ([18f2900](18f2900))
revanced-bot
pushed a commit
that referenced
this pull request
Aug 2, 2023
# [0.115.0](v0.114.0...v0.115.0) (2023-08-02) ### Bug Fixes * **YouTube - SponsorBlock:** Fix skip highlight button showing when set to 'show in seekbar' ([ea7bc57](ea7bc57)) * **YouTube - Spoof App Version:** Remove 17.30.35 target ([e906c6d](e906c6d)) * **YouTube:** fix potential litho filter thread race ([d3f523f](d3f523f)) ### Features * **Tiktok - Feed filter:** Add more filters ([#445](#445)) ([c16c038](c16c038)) * **YouTube - Hide layout components:** Hide `chips shelf` ([#448](#448)) ([c7d2a9b](c7d2a9b)) * **YouTube:** add `Player Flyout Menu` patch ([#416](#416)) ([b2085ae](b2085ae)) ### Performance Improvements * **YouTube:** Filter litho components using prefix tree ([#447](#447)) ([18f2900](18f2900))
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.
Since all litho filters are all searching against the same target path and protobuffer, a prefix tree (trie) can be used to speed this up quite a bit.
This PR adds a prefix tree search class (
TrieSearch), which works for both strings and byte arrays.This default ReVanced patch installation uses 79+ filter strings, and a trie effectively searches for all of them in 1 pass. This implementation does not prune away any non-enabled filters, so the runtime is basically a constant time regardless of how many filters are added or enabled.
Performance using default patches, default settings.
Average method runtime of each call to
LithoFilterPatch#filterto run all enabled filters:Before this PR, average method call runtime of 235,139 ns
With this PR, average method call runtime of 55,437 ns
Which gives a 425% speed up. Of note, that if more 'hide' features are enabled beyond the default settings then the speedup would be even greater (as the old linear searching would be adding more work, while the trie would continue to take the same time). During development a 10x speedup of the worse case (slowest use cases) was seen.
The litho filter has one fundamental change, instead of each filter always being called with "Check if you match this path/protobuffer, then confirm if you want to hide the litho element". With this PR the litho patch searches the trie once for matches, and then any matched filters are then confirmed with "I found a match of one of your filters, should I hide the litho component?"
Of note, the existing filter group classes still work the same as before, where they do a linear search for each pattern. These existing filter groups can still be used to fine tune the filtering, just as ShortsFilter and a few other filters do.