Re: Overlays as an AA-tree

[Andreas Politz <politza@hochschule-trier.de>]

So, I did as you ask and developed a couple of performance tests
based on 3 variables.  Let N = #overlays.

1. How the overlays are created
   + Either sequentially, one overlay per every other line or
   randomly, with random start and random length from 0 to 70.

2. What property to use
   + One of face, display (with a string) or invisible.

3. How the overlays are accessed
   + Either start at the top scroll down and up again, or jump to
     N/25 random positions and re-display there.

This gives 2*3*2=12 different tests.  In all of them I

+ ran all tests once with N=12.500 and 37500 overlays.
+ used a buffer with 2*N lines and 70 columns,
+ measured display time only, i.e. not make-overlay etc. .
+ ran each test thrice and took the average.

*--------------------------------------------------------------*

                            +----------------------------------+
                            |     12.5K      |      37.5K      |
 creation/property/action   |  list   tree   |   list    tree  |
================================================================
|sequential/display/scroll  |  6.32   5.24   |  37.59   16.47  |
|                           |                |                 |
|sequential/display/random  |  4.47   4.60   |  30.41   13.03  |
+---------------------------+----------------+-----------------+
|sequential/face/scroll     |  7.07   5.75   |  38.18   18.64  |
|                           |                |                 |
|sequential/face/random     |  4.25   4.13   |  30.50   13.23  |
+---------------------------+----------------+-----------------+
|sequential/invisible/scroll|  6.63   5.02   |  36.62   16.02  |
|                           |                |                 |
|sequential/invisible/random|  3.98   3.64   |  29.93   11.10  |
+---------------------------+----------------+-----------------+
|random/display/scroll      | 20.39   18.6   |  88.84   58.18  |
|                           |                |                 |
|random/display/random      |  7.57   7.22   |  77.65   21.14  |
+---------------------------+----------------+-----------------+
|random/face/scroll         | 11.16   8.75   |  88.31   27.72  |
|                           |                |                 |
|random/face/random         |  6.19   5.59   |  105.0   17.05  |
+---------------------------+----------------+-----------------+
|random/invisible/scroll    |  9.91   7.99   |  87.01   25.97  |
|                           |                |                 |
|random/invisible/random    |  6.58   5.75   |  86.73   17.01  |
+---------------------------+----------------+-----------------+
|                           |      list      |      tree       |
+---------------------------+----------------------------------+
|make-lines-invisible       |     812.67     |       1.43      |
|                           |                |                 |
|line-numbering             |      >15m *    |     112.79      |
================================================================

As you can see they stick pretty close together in the cases with
12500 overlays, while the tree performs at least twice times better
with 37500 overlays.

After that I took 2 real-world cases.  The first one stems from this
[1] thread, where a user complains about the performance of his
function make-lines-invisible.  The function puts overlays with an
invisible property on all lines matching a given regexp.  The function
also messages the number of hidden lines after every found match,
which may be the reason for its bad performance with the current
implementation, speak re-display.  This test measures the creation of
these overlays, no scrolling.

For the other case, I wrote a very simple linum.el clone.  This
function creates an overlay with a margin property containing the
line-number for every line in the buffer.  Here I measured creation of
the overlays as well as a full scroll up and down.

Both of the final tests were run on a ~300000 lines file with one
english word per line (/usr/share/dict/words).

* I gave up and quit the test after nothing seemed to happen on the
screen for more than 15 minutes.

So, I think this looks pretty decent.

Finally, let me note, that the tree implementation is not
completely free of quadratic worst-case performance.  There are
certain patterns of overlay layout, which trigger this kind of
thing.  Though, it can be argued how likely these are to occur in
a real-world scenario.  Maybe I'll write a bit more about that
later.

-ap


[1] https://lists.gnu.org/archive/html/emacs-devel/2009-04/msg00242.html