Re: Overlays as an AA-tree

[Eli Zaretskii]

> From: Andreas Politz <address@hidden>
> Cc: address@hidden
> Date: Fri, 17 Feb 2017 05:58:34 +0100
> 
> So, I did as you ask and developed a couple of performance tests
> based on 3 variables.  Let N = #overlays.

Thanks.

>                             +----------------------------------+
>                             |     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      |
> ================================================================

This looks very good indeed, thanks.

> So, I think this looks pretty decent.

I agree.

> 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.

Please do when you have time.