The overlay branch (yet again)

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

The overlay branch (yet again)

Vladimir Kazanov
Hi all,

a few years ago I tried replacing the underlying overlay data
structure with a tree-based one. Back then I ran out of spare time and
had to delay the project.

I'll have time on my hands this winter and would like to get back to
the project again. This time it seems that most of the work was done
by Andreas Politz in the feature/noverlay branch:

https://lists.gnu.org/archive/html/emacs-devel/2018-03/msg00565.html
https://lists.gnu.org/archive/html/emacs-devel/2019-09/msg00543.html

It seems reasonable to pick up the branch and try to finish it, unless
somebody is already working on it. So my questions are:

is anybody working on the branch? why was it abandoned? Are there any
known problems with it?

Thank you

--
Yours sincerely,


Vladimir Kazanov

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Vladimir Kazanov
Hi all again,

I went through the code written by Andreas Politz (in the
feature/noverlay branch) and all of the related discussions. He
completed an astonishing amount of work! Apart from changes to the
working code the branch includes 1300 LOC of manually written
overlay-related tests, 5700 LOC of automatically generated unit tests
and C-level interval tree tests. Check test/src/buffer-tests.el in the
feature/noverlay branch for reference.

It would be a waste to just throw all of that away. As a first step I
really want to put those tests to work.

Given that nobody replied to my original email I assume everybody is
busy with the new release. In the meantime I'd really like to try to
pick up the work already done on overlays. I have a following plan:

1. A separate patch containing all those tests.
2. A second patch, making overlay code independent from the underlying
implementation.
3. A third patch, providing a tree-based data structure using either
what Andreas built, or smth else.

The first patch should be fairy trivial: I'll extract overlay-specific
tests into a overlay-test.el (while attributing all of the changes to
Andreas, of course), clean up a bit and drop C-level tests. I believe
those tests are really useful the way they are right now and can be
merged separately.

Having those tests merged it will be much easier to go on with further
overlay-related changes (i.e. tweaking internal APIs, or underlying
data structures).

Is anybody interested in me doing this work?

On Tue, Nov 26, 2019 at 2:44 PM Vladimir Kazanov <[hidden email]> wrote:

>
> Hi all,
>
> a few years ago I tried replacing the underlying overlay data
> structure with a tree-based one. Back then I ran out of spare time and
> had to delay the project.
>
> I'll have time on my hands this winter and would like to get back to
> the project again. This time it seems that most of the work was done
> by Andreas Politz in the feature/noverlay branch:
>
> https://lists.gnu.org/archive/html/emacs-devel/2018-03/msg00565.html
> https://lists.gnu.org/archive/html/emacs-devel/2019-09/msg00543.html
>
> It seems reasonable to pick up the branch and try to finish it, unless
> somebody is already working on it. So my questions are:
>
> is anybody working on the branch? why was it abandoned? Are there any
> known problems with it?
>
> Thank you
>
> --
> Yours sincerely,
>
>
> Vladimir Kazanov



--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Eli Zaretskii
> From: Vladimir Kazanov <[hidden email]>
> Date: Tue, 3 Dec 2019 15:35:17 +0000
>
> Is anybody interested in me doing this work?

Yes, of course.  Thanks for volunteering.

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

martin rudalics
In reply to this post by Vladimir Kazanov
 > Given that nobody replied to my original email I assume everybody is
 > busy with the new release.

I didn't reply becaue I'm not enough familiar with the subject, in
particular with the work that Andreas did.

 > Is anybody interested in me doing this work?

I definitely am interested.

Thanks, martin

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Vladimir Kazanov
Thanks, Eli and Martin! Will do.

Martin,

in short, Andreas replaced the current (relatively) inefficient linked
list overlay implementation with a tree-based one. This might sound as
something relatively simple but in practice it turns out that there
are lots of subtle issues in both the tree implementation and
resulting Emacs integration. I know because I tried - and failed. At
least twice :-)

But Andreas almost made it! So I want to reuse some of that massive
effort: merge tests at the very least, untangle overlay code a bit and
- hopefully - replace those linked lists.

On Tue, Dec 3, 2019 at 4:06 PM martin rudalics <[hidden email]> wrote:

>
>  > Given that nobody replied to my original email I assume everybody is
>  > busy with the new release.
>
> I didn't reply becaue I'm not enough familiar with the subject, in
> particular with the work that Andreas did.
>
>  > Is anybody interested in me doing this work?
>
> I definitely am interested.
>
> Thanks, martin



--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Stefan Monnier
>>  > Given that nobody replied to my original email I assume everybody is
>>  > busy with the new release.

Not exactly with the new release, but yes your message fell into the
"todo" black hole, sorry :-(

>>  > Is anybody interested in me doing this work?
>> I definitely am interested.

Me too.

> But Andreas almost made it! So I want to reuse some of that massive
> effort: merge tests at the very least, untangle overlay code a bit and
> - hopefully - replace those linked lists.

Yes, please!

Also, I hope the new code can capture some of the insights learned along
the way, and the design choices, e.g. in the form of comments describing the
various performance aspects that were considered (complexity of
`make-overlay`, `delete-overlay`, `overlay-start`, `overlays-at/in`,
`previous-char-property-change`, of updating overlays in response to
buffer text modifications, ...).

Also, some performance tests would be great.  IIRC a few months ago
someone here posted some simple tests showing some percentage
improvement in some cases, but there has to be situations where the new
code is massively faster (after all, the new code uses a different data
structure specifically to change the algorithmic complexity of some
operations).  It's quite possible that those situations don't "occur
naturally" in current code, but it should be possible to trigger them in
artificial but realistic situations (maybe changing font-lock to use
overlays instead of text-properties, or forcing nhexl-mode to nhexlify
eagerly the whole buffer, I don't know).

But merging the tests into `master` would be a great first step.


        Stefan


Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Vladimir Kazanov
> Also, I hope the new code can capture some of the insights learned along
> the way, and the design choices, e.g. in the form of comments describing the
> various performance aspects that were considered (complexity of
> `make-overlay`, `delete-overlay`, `overlay-start`, `overlays-at/in`,
> `previous-char-property-change`, of updating overlays in response to
> buffer text modifications, ...).

Do mean something like inline comments for functions accessible from
Emacs Lisp? I'll try to do my best. But it'll take some time before I
will fell comfortable with the new implementation. This time around I
want to proceed in small steps: merge tests -> untangle/clarify
internal overlay apis -> replace the lists (with the code Andreas
built, hopefully).

> Also, some performance tests would be great.  IIRC a few months ago
> someone here posted some simple tests showing some percentage
> improvement in some cases, but there has to be situations where the new
> code is massively faster (after all, the new code uses a different data
> structure specifically to change the algorithmic complexity of some
> operations).  It's quite possible that those situations don't "occur
> naturally" in current code, but it should be possible to trigger them in
> artificial but realistic situations (maybe changing font-lock to use
> overlays instead of text-properties, or forcing nhexl-mode to nhexlify
> eagerly the whole buffer, I don't know).

I found at least three performance comparisons Andreas provided when
discussing his implementation:

https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00488.html
https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00598.html
https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00736.html

Notice how in the second message he provides a couple of nice
realistic examples.

But I don't think I saw (I'll have to recheck as I wasn't looking) any
benchmarking code in the branch. Anyways, It'll take some time for me
to reach that point.

> But merging the tests into `master` would be a great first step.

Indeed.

On Tue, Dec 3, 2019 at 5:58 PM Stefan Monnier <[hidden email]> wrote:

>
> >>  > Given that nobody replied to my original email I assume everybody is
> >>  > busy with the new release.
>
> Not exactly with the new release, but yes your message fell into the
> "todo" black hole, sorry :-(
>
> >>  > Is anybody interested in me doing this work?
> >> I definitely am interested.
>
> Me too.
>
> > But Andreas almost made it! So I want to reuse some of that massive
> > effort: merge tests at the very least, untangle overlay code a bit and
> > - hopefully - replace those linked lists.
>
> Yes, please!
>
> Also, I hope the new code can capture some of the insights learned along
> the way, and the design choices, e.g. in the form of comments describing the
> various performance aspects that were considered (complexity of
> `make-overlay`, `delete-overlay`, `overlay-start`, `overlays-at/in`,
> `previous-char-property-change`, of updating overlays in response to
> buffer text modifications, ...).
>
> Also, some performance tests would be great.  IIRC a few months ago
> someone here posted some simple tests showing some percentage
> improvement in some cases, but there has to be situations where the new
> code is massively faster (after all, the new code uses a different data
> structure specifically to change the algorithmic complexity of some
> operations).  It's quite possible that those situations don't "occur
> naturally" in current code, but it should be possible to trigger them in
> artificial but realistic situations (maybe changing font-lock to use
> overlays instead of text-properties, or forcing nhexl-mode to nhexlify
> eagerly the whole buffer, I don't know).
>
> But merging the tests into `master` would be a great first step.
>
>
>         Stefan
>


--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Stefan Monnier
Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Vladimir Kazanov
So here's the first patch containing a few hundred (!!!)
implementation-agnostic overlay tests.

I took all Lisp-level overlay related tests in the feature-noverlay
branch, removed automatically generated ones and a single test that
was aware of the tree-based implementation. This should be a good
basis for any further work related to overlays (and buffers in
general).

I did not add a single line of code, all credit goes to Andreas.

Feel free to request tweaks and additions. Note that I am still in the
process of pushing the papers through corporate bureaucracy. No
problems, I got all the approvals needed but it'll take a week or two
more.

Thanks

On Tue, Dec 3, 2019 at 10:43 PM Stefan Monnier <[hidden email]> wrote:
--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

0001-Include-overlay-tests.patch (71K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Vladimir Kazanov
a gentle reminder :-)

On Wed, Dec 4, 2019 at 11:41 AM Vladimir Kazanov <[hidden email]> wrote:

>
> So here's the first patch containing a few hundred (!!!)
> implementation-agnostic overlay tests.
>
> I took all Lisp-level overlay related tests in the feature-noverlay
> branch, removed automatically generated ones and a single test that
> was aware of the tree-based implementation. This should be a good
> basis for any further work related to overlays (and buffers in
> general).
>
> I did not add a single line of code, all credit goes to Andreas.
>
> Feel free to request tweaks and additions. Note that I am still in the
> process of pushing the papers through corporate bureaucracy. No
> problems, I got all the approvals needed but it'll take a week or two
> more.
>
> Thanks
>
> On Tue, Dec 3, 2019 at 10:43 PM Stefan Monnier <[hidden email]> wrote:
> >
> > > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00488.html
> > > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00598.html
> > > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00736.html
> >
> > At least those links should be in comments somewhere in the code.
> >
> >
> >         Stefan
> >
>
>
> --
> Yours sincerely,
>
>
> Vladimir Kazanov
>
>
> --
> С уважением,
>
> Владимир Казанов



--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Eli Zaretskii
> From: Vladimir Kazanov <[hidden email]>
> Date: Thu, 5 Dec 2019 14:13:30 +0000
> Cc: martin rudalics <[hidden email]>, [hidden email]
>
> a gentle reminder :-)

Please wait for a while longer.  It takes time here to process
patches, and at least I personally like to leave them for a few days
before pushing, so that others could have an opportunity to read and
comment.

Also, do I understand that this is all work by Andreas?  The patches
have no log message (something that we normally ask for providing), so
the authorship is unclear.

Thanks.

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Vladimir Kazanov
Eli,

oops, sorry.

> Also, do I understand that this is all work by Andreas?

Yes, the code is by Andreas. I only removed some of the
irrelevant/temporary tests. He dumped most of it into the
features/noverlay branch in a single commit containing both tests and
main code. So I had to extract things manually.

> (something that we normally ask for providing)

Would something like using the default "git format-patch" format work..?

Thanks


On Thu, Dec 5, 2019 at 3:14 PM Eli Zaretskii <[hidden email]> wrote:

>
> > From: Vladimir Kazanov <[hidden email]>
> > Date: Thu, 5 Dec 2019 14:13:30 +0000
> > Cc: martin rudalics <[hidden email]>, [hidden email]
> >
> > a gentle reminder :-)
>
> Please wait for a while longer.  It takes time here to process
> patches, and at least I personally like to leave them for a few days
> before pushing, so that others could have an opportunity to read and
> comment.
>
> Also, do I understand that this is all work by Andreas?  The patches
> have no log message (something that we normally ask for providing), so
> the authorship is unclear.
>
> Thanks.



--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Eli Zaretskii
> From: Vladimir Kazanov <[hidden email]>
> Date: Thu, 5 Dec 2019 15:31:12 +0000
> Cc: Stefan Monnier <[hidden email]>, martin rudalics <[hidden email]>, [hidden email]
>
> Would something like using the default "git format-patch" format work..?

It would, but how would you produce such a patch if there's a single
commit on the branch, which mixes these changes with others?

Reply | Threaded
Open this post in threaded view
|

Re: The overlay branch (yet again)

Vladimir Kazanov
On Thu, Dec 5, 2019 at 4:38 PM Eli Zaretskii <[hidden email]> wrote:
> It would, but how would you produce such a patch if there's a single
> commit on the branch, which mixes these changes with others?

I wouldn't, at least not this time. But I already have a second patch
in the works, and I really want it to be usable the way I send it..

Stefan already merged the patch, by the way. Nice!


--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов