Look in to using bisect module to replace home grown binary searches.

Textualize / rich

Rich is a Python library for rich text and beautiful formatting in the terminal.

https://rich.readthedocs.io/en/latest/

MIT License

48.13k stars 1.69k forks source link

Look in to using bisect module to replace home grown binary searches. #3298

Open willmcgugan opened 4 months ago

willmcgugan commented 4 months ago

I implemented a few binary searches in Rich, such as getting the cell length of a character. I wonder if we can replace those binary searches with the bisect module. If that is implemented in C, which I imagine it is, then it could be a speed win.

Suggest we try it, and if it works profile the improvement (if any).

github-actions[bot] commented 4 months ago

Thank you for your issue. Give us a little time to review it.

PS. You might want to check the FAQ if you haven't done so already.

This is an automated reply, generated by FAQtory

rodrigogiraoserrao commented 4 months ago

These are the binary searches I found:

rich/cells.py::_get_codepoint_cell_size
rich/cells.py::set_cell_size
rich/text.py::Text.divide
tools/make_terminal_widths.py (irrelevant)

rodrigogiraoserrao commented 4 months ago

Segment.divide and Segment._split_cells use a linear search that could potentially benefit from binary search.