Accelerating Searches in Display Code

In the time critical display stuff at serveral places the search for start of logical line, search for next logical line, and search for start/end of elided range is required. All these searches are quite slow, the worst case complexity is in general O(n), if n is the number of lines. In revised version all the searches will be done with the B-Tree, now the worst case complexity is O(log n).

Additional Caching of Display Line Heights

The current behavior with caching only the line metric of physical lines has one drawback: scrolling, especially scrolling upward, can be very slow (this means the behavior is jumpy, and sometimes it feels as if the widget is hanging), if very long lines, producing many display lines, are involved. In revised version the line metric of all display lines will be cached, in this way the repeated computation of the display lines, which are currently not visible, but required for line scroll, is eliminated. The mouse hovering was infected in the same way (repeated computation of display lines), this problem is also gone.

Enhanced Update of Line Metrics

The widget is computing asynchronously the line metrics, this is required for the scrollbar, and for the acceleration of some operations. The old algorithm is quite slow in some egde cases. Instead of iterating over all lines now a range list will be used, in this way these edge cases are not critical anymore.

Enhanced Algorithms

Some of the display functions, especially TkTextIndexYPixels(), TkTextMeasureDown(), YScrollByLines(), GetYPixelCount(), and MeasureUp(), are iterating over lines while computing the line metric (again). The revised version don't need iteration, it works with B-Tree lookups, and the line metric will be computed only once. In revised version now any call of LayoutDLine() will update the line metric cache, so no more reduntant line metric computation like in the old code.

Reduced Display Line Computation

The old algorithms are a bit stupid. One example: some text will be inserted into the widget, and afterwards the text view will be positioned to the end of the text. Because the line metric computation is not yet done – we assume that no update has been triggered in the meanwhile – all display lines will be computed until the last display line metric is known, and then all visible display lines will be computed again for displaying. The revised implementation is using the result of the line metric computation for displaying – no repeated computation –, and only after displaying has been done the superfluous display lines will be deleted. The decrease of display line computation is expecially important for the Mac, because here the line metric computation is quite expensive due to required sub-pixel accuracy.

Another example: when scrolling the widget content it happens with old algorithm that some display lines at start will be deleted, and immediately afterwards some of the deleted display lines will be re-computed for filling empty space at top of widget. The revised algorithm avoids the re-computation.

Scrolling is not Flickering Anymore

Scrolling the widget is flickering (wish8.6). When scrolling with mouse wheel tagged text content may flicker, because the tagged region may receive a mouse-over event for a short time, and this might change temporarily some tag options. This is especially very nasty when the line metric is changing while the mouse is hovering, the effect is a volatile screen.

In revised version (per default; see option -responsiveness) the repick (sending event/leave/motion events) will be done after the successive scroll operations have been finished, not between the successive scroll operations as in old widget.

Mouse Hovering

The mouse hovering requires an x,y position lookup inside the display lines. In revised version the last hovered display chunk will be cached, in this way a new search over the display lines will only happen if the mouse cursor is leaving the cached chunk. This is reducing the number of computations significantly. Moreover the display line now contains chunk sections, this provides a fast mapping between x-coordinates and byte indices, the increase in speed is at least factor 10.