Revised Implementation of Tk Text Widget

Introduction

The current implementation of tk::text has severe performance problems. My basis for testing are the Chess Database applications – Scid vs. PC (a powerful and widely used multi-platform chess toolkit) and, my own application, Scidb. With the standard tk::text, it can take upto a few minutes just to display a chess game with a 100 lines. Based on profiling the following functions are the top performance killer:

  1. TkBTreeGetTags
  2. CleanupLine
  3. TkTextIsElided
  4. TkBTreeCharTagged
  5. TkBTreeTag
  6. TkTextIndexToSeg
  7. TkTextMarkSegToIndex
  8. MeasureUp
  9. MeasureDown
  10. TkTextPixelIndex

So it's clear what has to be done:

The original implementation is already quite complex, especially in time. It's clear that in general complexity cannot be eliminated. So I shifted the complexity in time to a more complex implementation, especially more complex data structures. The new implementation is very efficient in time. The increase in memory usage is not very high (but a bit high), and despite this, in many cases, especially if many tags are used, and/or undo is enabled, the revised version is even decreasing the memory usage.

Of special interest is the difference in speed, and the effect on user handling (smooth scrolling, fast response time), in some cases the difference is enormous, see Comparison of Old vs. Revised Implementation. With the revised implementation the problem with long lines (polynomial time in old code) is completely solved (in general only O(n × log n) in revised version). So the following performance issues can be removed:

Very long text lines can be expensive, especially if they have many marks and tags within them.
One performance problem can arise if you have hundreds or thousands of different tags …

While examining the code I found some more weak stuff. Furthermore I used this opportunity to add a few features, some for performance reasons, and some for additional functionality. It was the right time for these additions, because the acceleration of the text widget caused a rewrite/redesign of the code anyway. Also some bugs have been eliminated.

Comparison in Performance

Performance Improvements

Bugs/Issues in Original Implementation

Additional Functionality

Index of Commands

Index of Functions

Index of Widget Options

Index of Tag Options

Index of Options for Embedded Window

Index of Chapters

Test Cases

The revised version is passing all test cases under Linux. The special test cases under Windoze and Mac are still open.

In revised version some test cases have been adjusted, because:

  1. The revised version is optimizing the computation of display lines, so some traces have changed.

  2. The revised version has fixed some bugs, and some commands/options have changed.

I've added a few test cases, but for the most new features test cases are not yet written.

Issues in Revised Implementation

Currently only these issues are known:

Some General Suggestions

Credits

Many thanks to Steven Atkinson (Scid vs. PC) for testing, and compiling the Mac version (with backport to tk8.5). He has found so many bugs in revised version, and this was very helpful.

Applications

The revised implementation is already used in applications Scid vs. PC and Scidb. Both applications are displaying normal text and chess data, and especially application Scidb has a very sophisticated text layout, using many features of the text widget.

Reporting Bugs/Issues/Questions/Suggestions

Use the bug tracker of project Scidb for the report of bugs. You need a Sourceforge account. It's important to attach a script file for replication of the bug. And note that currently I cannot fix problems with Windoze or Mac, here a volunteer is needed who is testing and fixing the revised version under Windoze/Mac. But Windoze and Mac is pre-tested, many thanks to Steven Atkinson.

Use the discussion forum of project Scidb for questions, suggestions, and issues. Here also you need a Sourceforge account.

Source Code

Visit Download and Installation for download of the whole package of implementation files. Below you may inspect single implementation files.