Re: Overlays as an AA-tree

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

So,

 I've been working on this thing and below are my preliminary
findings, so to speak.  The code can be found here [1].  There is a
file etc/noverlay.org in there, containing some notes and pointing to
some other files.

I developed some performance tests, which for the most part are very
bare-bones and test single functions only in a constrained environment.
Following are some numbers, a description of the test-functions and an
attempt to make sense of the results.

====================================================================================
                                        list                          tree
n=1000                          n        8n      64n           n       8n     64n
                               ----------------------        ----------------------
perf-make-overlay              0.00	0.01	0.10         0.00     0.01    0.08
perf-make-overlay-continuous   0.00	0.01	0.10         0.00     0.01    0.08
perf-make-overlay-scatter      0.00	0.22	50.76        0.00     0.01    0.16
perf-delete-overlay            0.01	0.69	74.54        0.00     0.00    0.01
perf-delete-overlay-continuous 0.01	0.52	54.10        0.00     0.00    0.01
perf-delete-overlay-scatter    0.00	0.31	37.43        0.00     0.00    0.01
perf-overlays-at               0.00	0.44	88.08        0.00     0.02    0.32
perf-overlays-in               0.00	0.46	90.91        0.00     0.05    0.76
perf-insert-before             0.01	0.11	1.49         0.00     0.00    0.00
perf-insert-after              0.01	0.09	1.12         0.00     0.00    0.00
perf-insert-scatter            0.02	1.25	186.64       0.00     0.02    0.31
perf-delete-before             0.02	1.80	298.44       0.04     3.02    468.16
perf-delete-after              0.02	1.77	299.54       0.03     2.24    309.39
perf-delete-scatter            0.02	1.64	277.82       0.00     0.05    1.09
                               -----------------------       -----------------------

perf-flycheck                        5.01* / 23.83                    4.88
perf-flycheck-display                  15.03*                         7.64

====================================================================================
                                                             * with overlay-recenter

* perf-(make|delete)-overlay
  (Make|delete) N overlays in an empty buffer.
* perf-(make|delete)-overlay-continuous
  (Make|delete) N consecutive overlays of length 1 in a buffer of size
  N.
* perf-(make|delete)-overlay-scatter
  (Make|delete) N randomly chosen overlays of length 24 in a buffer of
  size N.
* perf-overlays-(at|in)
  Extract overlays (at|in) every buffer (position|range of length 24) from
  1 to point-max.
* perf-insert-(before|after|scatter)
  Insert N overlays randomly in a N sized buffer and insert N
  character at (point-min|point-max|randomly).
* perf-delete-(before|after|scatter)
  Same as above, but delete characters.
* perf-flycheck
  Perform a flycheck on a notorious file[2] with about 15000 errors.
  The second lower number for the master branch results from an
  inserted overlay-recenter into the flycheck code.  These numbers
  vary greatly for the list implementation.
* perf-flycheck-display
  Same as above, then scroll the buffer once completely down and up
  again, while redisplaying after every scroll step.


Since the current overlay implementation is very sensitive to its
center position, I chose the most favorable of either point-min or
-max in every non-random test.  Furthermore, I measured only the
function itself, e.g. perf-delete-overlay does not include the time to
create the overlays.  Also I garbage-collected before every test.  All
overlays were created with default advance.

I think we see what one should expect: The list implementation
performs decent, if the number of overlays stays reasonable or it is
allowed to insert/delete from the list start.  Only when the numbers
get close to 100.000 and it needs to perform random-access operations,
are we seeing a serious performance degradation.

On the other hand, the tree stays solid even with large numbers,
except for two notable cases: Continuously deleting at the beginning
or end of the buffer.  In this case the overlays sooner or later all
linger at the same position and the tree slowly turns into a black
soup -- effectively a unordered, awkward to traverse list.

Recentering the list's center in the flycheck test shows the
difference between the optimal linear and the worst case quadratic
complexity of this implementation (when adding n elements).  But I
this "magic trick" (using overlay-recenter) only works, if the buffer
does not contain a significant amount of overlays to begin with.

The final test seems to indicate that redisplay has an effect on this,
probably due to the fact that it in some cases recenters the lists.

-ap

[1] https://github.com/politza/emacs-noverlay
[2] https://github.com/flycheck/flycheck/issues/635