[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Overlays as an AA-tree
From: |
Andreas Politz |
Subject: |
Re: Overlays as an AA-tree |
Date: |
Fri, 17 Feb 2017 05:58:34 +0100 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux) |
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
- Re: Overlays as an AA-tree, (continued)
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/08
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/08
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/09
- Re: Overlays as an AA-tree, Joakim Jalap, 2017/02/09
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/09
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/12
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/13
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/13
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/13
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/14
- Re: Overlays as an AA-tree,
Andreas Politz <=
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/17
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/19
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/19
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/19
- Re: Overlays as an AA-tree, Eli Zaretskii, 2017/02/20
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21
- Re: Overlays as an AA-tree, Stefan Monnier, 2017/02/21
- Re: Overlays as an AA-tree, Andreas Politz, 2017/02/21