Overlay tree. Stuck again

Overlay tree. Stuck again

[Joakim Jalap]

Hello Emacs Devs.

As ever, I've been hacking on the overlay tree branch. Now it's turned
sour again though.

For those it may concern this is the problem: The overlays in the tree
are ordered first by their start position, if that is the same we look
at the end position, if that is also equal we order by memory address.

However the nodes can be updated "externally" from the trees point of
view. For example if there is a delete in the buffer those overlays
which were in the deleted portion of the buffer will now be crowded at
the from_char of the delete. But those could have any address, so they
will probably be out of order. The problem is how to get them in order
again.

As far as I've gotten is to gather all the affected nodes (which I think
are only those of length zero which start (and end) at from_char) into
an array and sort that. But I can't figure out how to get them into the
tree again while keeping all the pointers correct.

My feeble attempts can be seen at
https://github.com/jockej/emacs-mirror1, branch arne-without-parent.

I've been wrestling with this for a while now. I'm starting to think
this whole approach is... not so good. But if anyone has a brilliant
idea I'd be glad to hear it :)

Happy hacking!

-- Joakim

Re: Overlay tree. Stuck again

[Eli Zaretskii]

> From: Joakim Jalap <joakim.jalap@fastmail.com>
> Date: Thu, 12 Jan 2017 22:10:44 +0100
> 
> However the nodes can be updated "externally" from the trees point of
> view. For example if there is a delete in the buffer those overlays
> which were in the deleted portion of the buffer will now be crowded at
> the from_char of the delete. But those could have any address, so they
> will probably be out of order. The problem is how to get them in order
> again.
> 
> As far as I've gotten is to gather all the affected nodes (which I think
> are only those of length zero which start (and end) at from_char) into
> an array and sort that. But I can't figure out how to get them into the
> tree again while keeping all the pointers correct.

This might be a silly idea, but did you try removing them from the
tree, and then re-adding them?  (I assume that adding a node will
produce an ordered tree.)

Apologies if I'm missing something obvious.

Re: Overlay tree. Stuck again

[Joakim Jalap]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Joakim Jalap <joakim.jalap@fastmail.com>
>> Date: Thu, 12 Jan 2017 22:10:44 +0100
>> 
>> However the nodes can be updated "externally" from the trees point of
>> view. For example if there is a delete in the buffer those overlays
>> which were in the deleted portion of the buffer will now be crowded at
>> the from_char of the delete. But those could have any address, so they
>> will probably be out of order. The problem is how to get them in order
>> again.
>> 
>> As far as I've gotten is to gather all the affected nodes (which I think
>> are only those of length zero which start (and end) at from_char) into
>> an array and sort that. But I can't figure out how to get them into the
>> tree again while keeping all the pointers correct.
>
> This might be a silly idea, but did you try removing them from the
> tree, and then re-adding them?  (I assume that adding a node will
> produce an ordered tree.)

Yes, that is the "big hammer" approach :) I hae thought about it, but I
think the problem is that it will be too expensive. When I traverse the
tree to adjust the overlays for a delete I traverse the whole tree at
once (and gather the problematic overlays in an array). If I would
remove the problematic overlays instead, I would have to do so with the
first one detected (because that's the only time we know the tree is in
OK shape). But then the tree might change because of rebalancing, so
then I think I would have to restart the adjusting traversal from the
root.

After all of this I would then have to insert each of the problematic
overlays one by one, which is of course also possibly expensive. So I
think this approach will be too slow, unfortunately.

However, I just had another idea about how to do this (about the 43rd I
guess), so I will try that and report back in a few weeks :)

Thanks,

-- Joakim

Re: Overlay tree. Stuck again

[Fabrice Popineau]

[-- Attachment #1: Type: text/plain, Size: 311 bytes --]

2017-01-13 12:56 GMT+01:00 Joakim Jalap <joakim.jalap@fastmail.com>:

> However, I just had another idea about how to do this (about the 43rd I
> guess), so I will try that and report back in a few weeks :)
>
>
And the 42nd wasn't the right answer? Or what was the question?

(Sorry, couldn't resist).

Fabrice

[-- Attachment #2: Type: text/html, Size: 717 bytes --]

Re: Overlay tree. Stuck again

[Joakim Jalap]

Fabrice Popineau <fabrice.popineau@centralesupelec.fr> writes:

> 2017-01-13 12:56 GMT+01:00 Joakim Jalap <joakim.jalap@fastmail.com>:
>
>  However, I just had another idea about how to do this (about the 43rd I
>  guess), so I will try that and report back in a few weeks :)
>
> And the 42nd wasn't the right answer? Or what was the question?

When the 42nd failed I decided to ask emacs-devel ;)

> (Sorry, couldn't resist).

Understandable :)

Re: Overlay tree. Stuck again

[Eli Zaretskii]

> From: Joakim Jalap <joakim.jalap@fastmail.com>
> Cc: emacs-devel@gnu.org
> Date: Fri, 13 Jan 2017 12:56:15 +0100
> 
> > This might be a silly idea, but did you try removing them from the
> > tree, and then re-adding them?  (I assume that adding a node will
> > produce an ordered tree.)
> 
> Yes, that is the "big hammer" approach :) I hae thought about it, but I
> think the problem is that it will be too expensive.

I suggest to implement it and time it.  You might be surprised.  Even
if you are right, and it is indeed too expensive, you will at the very
least have a base-line performance figure against which you could
compare the alternative solutions.

> However, I just had another idea about how to do this (about the 43rd I
> guess), so I will try that and report back in a few weeks :)

Thanks.

Re: Overlay tree. Stuck again

[Joakim Jalap]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Joakim Jalap <joakim.jalap@fastmail.com>
>> Cc: emacs-devel@gnu.org
>> Date: Fri, 13 Jan 2017 12:56:15 +0100
>> 
>> > This might be a silly idea, but did you try removing them from the
>> > tree, and then re-adding them?  (I assume that adding a node will
>> > produce an ordered tree.)
>> 
>> Yes, that is the "big hammer" approach :) I hae thought about it, but I
>> think the problem is that it will be too expensive.
>
> I suggest to implement it and time it.  You might be surprised.  Even
> if you are right, and it is indeed too expensive, you will at the very
> least have a base-line performance figure against which you could
> compare the alternative solutions.
>
If the 43rd fails I will try it :)

Actually I'm afraid it will be too slow anyway. It seems a lot of the
use of overlays is not as "static" as one would like. For example magit
deletes and recreates its overlays every time point moves, even if they
stay in the same place. For such uses I guess a linked list will be a
lot faster than a self balancing tree.

But first I will try to make it work at all :)

Re: Overlay tree. Stuck again

[Andreas Politz]

Joakim Jalap <joakim.jalap@fastmail.com> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>> [...] try removing them from the tree, and then re-adding them [...]
>
> Yes, that is the "big hammer" approach :) I hae thought about it, but I
> think the problem is that it will be too expensive. [...]

Joakim, I think that trying to somehow manually fix the disorder is at
least as expensive as a deletion and reinsertion.  Because if it weren't
you would have essentially discovered a better algorithm for balancing
trees then the one you've got.

The trick is probably to gather the dirty nodes in post-order and delete
them all at once. This way you're only removing a node, if its
corresponding sub-tree is in order.  After that you're free to reinsert
them again.

-ap

Re: Overlay tree. Stuck again

[Andreas Politz]

Joakim Jalap <joakim.jalap@fastmail.com> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>> [...] try removing them from the tree, and then re-adding them [...]
>
> Yes, that is the "big hammer" approach :) I hae thought about it, but I
> think the problem is that it will be too expensive. [...]

Joakim, I think that trying to somehow manually fix the disorder is at
least as expensive as a deletion and reinsertion.  Because if it weren't
you would have essentially discovered a better algorithm for balancing
trees then the one you've got.

The trick is probably to gather the dirty nodes in post-order and delete
them all at once. This way you're only removing a node, if its
corresponding sub-tree is in order.  After that you're free to reinsert
them again.

-ap

Re: Overlay tree. Stuck again

[Joakim Jalap]

Andreas Politz <politza@hochschule-trier.de> writes:

> Joakim Jalap <joakim.jalap@fastmail.com> writes:
>
>> Eli Zaretskii <eliz@gnu.org> writes:
>>> [...] try removing them from the tree, and then re-adding them [...]
>>
>> Yes, that is the "big hammer" approach :) I hae thought about it, but I
>> think the problem is that it will be too expensive. [...]
>
> Joakim, I think that trying to somehow manually fix the disorder is at
> least as expensive as a deletion and reinsertion.  Because if it weren't
> you would have essentially discovered a better algorithm for balancing
> trees then the one you've got.

Well this case isn't really about rebalncing, since the tree was
balanced to begin with, and no nodes are deleted or inserted. The
problem is that a few overlays end up in the wrong place in the tree
since I sort by different criteria (memory address) than before for
those overlays which happened to end up with the same start/end.

> The trick is probably to gather the dirty nodes in post-order and delete
> them all at once. This way you're only removing a node, if its
> corresponding sub-tree is in order.  After that you're free to reinsert
> them again.

Yes, that should do it. But that would be many traversals of the tree,
so I'm afraid it would be too slow.

Anyway, I'm trying a new approach now, where the tree is separate from
the acual struct Lisp_Overlays, but each overlay is linked to a node in
the tree with a pointer (and vice versa). I think this might be easier
(that's my theory at least).

>
> -ap

-- Joakim

Re: Overlay tree. Stuck again

[Andreas Politz]

Joakim Jalap <joakim.jalap@fastmail.com> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>> [...] try removing them from the tree, and then re-adding them [...]
>
> Yes, that is the "big hammer" approach :) I hae thought about it, but I
> think the problem is that it will be too expensive. [...]

Joakim, I think that trying to somehow manually fix the disorder is at
least as expensive as a deletion and reinsertion.  Because if it weren't
you would have essentially discovered a better algorithm for balancing
trees then the one you've got.

The trick is probably to gather the dirty nodes in post-order and delete
them all at once. This way you're only removing a node, if its
corresponding sub-tree is in order.  After that you're free to reinsert
them again.

-ap