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
Bisect all the things! #3300
base: master
Are you sure you want to change the base?
Bisect all the things! #3300
Conversation
This optimisation passes rich testing (obviously) and it also passes the full Textual test suite. Replace explicit binary search with the module 'bisect'. To simplify the code, we replace the list of ranges and widths present in rich/_cell_widths.py with the lists of range starts, range ends, and respective widths. Having a separate list for the starts makes it easier to apply the bisection.
This optimisation passes Textual testing as well. Instead of repeatedly computing the cell length of the current attempted split, we compute the width of each character and use binary search to find the cut point. This is faster because we only compute the length of the full string once (as we compute the width of each character once) instead of recomputing cell lengths.
These benchmarks help us make sure the optimisations are going in the right direction. The benchmark added to time Segment.divide also shows that two proposed changes to 'Segment.divide' using binary search ended up being slower that the current linear search. They're included here because: 1. it _may_ come in handy in the future (unlikely); and 2. I'm sad about throwing this code away. The first implementation replaces the (very clever) linear search with a binary search similar to what we did for `set_cell_size`. My benchmarks showed that this was only 10% faster so I thought maybe I could replace the list slicing with iterator slicing and it would be better, which resulted in my second implementation. They're both equally fast, and the rich benchmarks showed both were actually slower. ```py @classmethod def divide( cls, segments: Iterable["Segment"], cuts: Iterable[int] ) -> Iterable[List["Segment"]]: """Divides an iterable of segments into portions. Args: segments (Iterable[Segment]): The segments to divide. cuts (Iterable[int]): Cell positions where to divide. Yields: Iterable[List[Segment]]: An iterable of Segments in List. """ _cell_len = cached_cell_len segments = list(segments) cuts = list(cuts) widths = [0 if s.control else _cell_len(s.text) for s in segments] lengths = list(accumulate(widths)) offset = 0 for cut in cuts: if cut == offset: yield [] continue segment_idx = bisect.bisect_left(lengths, cut) if segment_idx >= len(lengths): yield segments return if lengths[segment_idx] == cut: yield segments[: segment_idx + 1] segments = segments[segment_idx + 1 :] lengths = lengths[segment_idx + 1 :] else: start_width = lengths[segment_idx - 1] if segment_idx > 0 else offset before, after = segments[segment_idx].split_cells(cut - start_width) yield segments[:segment_idx] + [before] segments = segments[segment_idx:] segments[0] = after lengths = lengths[segment_idx:] offset = cut @classmethod def divide( cls, segments: Iterable["Segment"], cuts: Iterable[int] ) -> Iterable[List["Segment"]]: """Divides an iterable of segments into portions. Args: segments (Iterable[Segment]): The segments to divide. cuts (Iterable[int]): Cell positions where to divide. Yields: Iterable[List[Segment]]: An iterable of Segments in List. """ _cell_len = cached_cell_len segments = list(segments) cuts = list(cuts) widths = [0 if s.control else _cell_len(s.text) for s in segments] lengths = list(accumulate(widths)) segments_iter = iter(segments) idx_offset = 0 offset = 0 for cut in cuts: if cut == offset: yield [] continue length_idx = bisect.bisect_left(lengths, cut) if length_idx >= len(lengths): yield list(segments_iter) return if lengths[length_idx] == cut: segments = list(islice(segments_iter, length_idx - idx_offset + 1)) yield segments idx_offset += len(segments) else: start_width = lengths[length_idx - 1] if length_idx > idx_offset else offset segments = list(islice(segments_iter, length_idx - idx_offset + 1)) before, after = segments[-1].split_cells(cut - start_width) segments_iter = chain([after], segments_iter) segments[-1] = before yield segments idx_offset += len(segments) - 1 offset = cut ```
We replace the linear search with a binary search like the one in cells.py::set_sell_size. This doesn't seem to produce a significant impact in the performance of the method but it does fix bug #3299.
This uses the module 'bisect' to replace two binary searches. This optimisation passes the Textual test suite.
I also tried optimising |
Codecov ReportAttention: Patch coverage is
❗ Your organization needs to install the Codecov GitHub app to enable full functionality. Additional details and impacted files@@ Coverage Diff @@
## master #3300 +/- ##
==========================================
- Coverage 98.30% 98.26% -0.05%
==========================================
Files 74 74
Lines 8038 8020 -18
==========================================
- Hits 7902 7881 -21
- Misses 136 139 +3
Flags with carried forward coverage won't be shown. Click here to find out more. ☔ View full report in Codecov by Sentry. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I gather the _cell_widths.py
change is for bisect. Could we keep the pairs and use key=itemgetter(0)
with bisect?
Just discovered that bisect key was added in 3.10. However, I don't think we will need it. It will work with the tuples--no need to separate them. |
Ideally we'd use the parameter `key` of `bisect_right` with `itemgetter(0)` but that's +3.10 only. So, instead we build the tuple `(cp,)`. This means that the tuple `(2,)` will be placed to the right of the range `(1, 31, -1)`, and we can do the calculations as before. However, this will codepoints at the start of their ranges on the wrong side of the range. E.g., `(1,)` would be placed to the left of `(1, 31, -1)` instead of to the right. To fix this, we add a second element to the tuple that is larger than any second element in the ranges, which ensures that whenever the first element of the tuples (the codepoint and the range start) match, the tuple with the codepoint is always placed on the right. Relevant review comment: #3300 (comment)
It works with tuples directly, yes. See 7a53a9f. |
@willmcgugan do you need anything else from me on this PR? |
No, its good. Just need to find the time to review. |
This PR replaces a couple of searches with the module
bisect
.The screenshot below shows Rich's benchmarks ran, on my machine, on v13.7.1 and on my changes.
There were clear wins at the top from the optimisations in
cells.py
.I boxed a region of things that stayed the same but whose underlying code was changed to fix the bug reported in #3299.
I also cut the code in
Text.divide
in half by usingbisect
.The
Text.divide
benchmarks show no change but that seems to have a positive impact inText.split
. (8% in this screenshot, 5% - 10% from the multiple times I ran the benchmarks while testing changes).I don't know if I'm supposed to commit and upload the benchmark results, so I didn't for now.
I also don't know if “optimised some code” should go on the changelog so I didn't put it there for now.
Fixes #3298
Fixes #3299