unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Overlay tree. Stuck again
@ 2017-01-12 21:10 Joakim Jalap
  2017-01-13  8:12 ` Eli Zaretskii
  0 siblings, 1 reply; 11+ messages in thread
From: Joakim Jalap @ 2017-01-12 21:10 UTC (permalink / raw)
  To: emacs-devel

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



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-12 21:10 Overlay tree. Stuck again Joakim Jalap
@ 2017-01-13  8:12 ` Eli Zaretskii
  2017-01-13 11:56   ` Joakim Jalap
  0 siblings, 1 reply; 11+ messages in thread
From: Eli Zaretskii @ 2017-01-13  8:12 UTC (permalink / raw)
  To: Joakim Jalap; +Cc: emacs-devel

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



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13  8:12 ` Eli Zaretskii
@ 2017-01-13 11:56   ` Joakim Jalap
  2017-01-13 13:22     ` Fabrice Popineau
                       ` (4 more replies)
  0 siblings, 5 replies; 11+ messages in thread
From: Joakim Jalap @ 2017-01-13 11:56 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: emacs-devel

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




^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13 11:56   ` Joakim Jalap
@ 2017-01-13 13:22     ` Fabrice Popineau
  2017-01-13 14:20       ` Joakim Jalap
  2017-01-13 13:54     ` Eli Zaretskii
                       ` (3 subsequent siblings)
  4 siblings, 1 reply; 11+ messages in thread
From: Fabrice Popineau @ 2017-01-13 13:22 UTC (permalink / raw)
  To: Joakim Jalap; +Cc: Eli Zaretskii, Emacs developers

[-- 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 --]

^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13 11:56   ` Joakim Jalap
  2017-01-13 13:22     ` Fabrice Popineau
@ 2017-01-13 13:54     ` Eli Zaretskii
  2017-01-13 14:26       ` Joakim Jalap
  2017-02-03  8:27     ` Andreas Politz
                       ` (2 subsequent siblings)
  4 siblings, 1 reply; 11+ messages in thread
From: Eli Zaretskii @ 2017-01-13 13:54 UTC (permalink / raw)
  To: Joakim Jalap; +Cc: emacs-devel

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



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13 13:22     ` Fabrice Popineau
@ 2017-01-13 14:20       ` Joakim Jalap
  0 siblings, 0 replies; 11+ messages in thread
From: Joakim Jalap @ 2017-01-13 14:20 UTC (permalink / raw)
  To: Fabrice Popineau; +Cc: Emacs developers

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 :)



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13 13:54     ` Eli Zaretskii
@ 2017-01-13 14:26       ` Joakim Jalap
  0 siblings, 0 replies; 11+ messages in thread
From: Joakim Jalap @ 2017-01-13 14:26 UTC (permalink / raw)
  To: Eli Zaretskii; +Cc: emacs-devel

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 :)




^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13 11:56   ` Joakim Jalap
  2017-01-13 13:22     ` Fabrice Popineau
  2017-01-13 13:54     ` Eli Zaretskii
@ 2017-02-03  8:27     ` Andreas Politz
  2017-02-03  8:28     ` Andreas Politz
  2017-02-03  8:28     ` Andreas Politz
  4 siblings, 0 replies; 11+ messages in thread
From: Andreas Politz @ 2017-02-03  8:27 UTC (permalink / raw)
  To: Joakim Jalap; +Cc: Eli Zaretskii, emacs-devel

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



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13 11:56   ` Joakim Jalap
                       ` (2 preceding siblings ...)
  2017-02-03  8:27     ` Andreas Politz
@ 2017-02-03  8:28     ` Andreas Politz
  2017-02-03 12:35       ` Joakim Jalap
  2017-02-03  8:28     ` Andreas Politz
  4 siblings, 1 reply; 11+ messages in thread
From: Andreas Politz @ 2017-02-03  8:28 UTC (permalink / raw)
  To: Joakim Jalap; +Cc: Eli Zaretskii, emacs-devel

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



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-01-13 11:56   ` Joakim Jalap
                       ` (3 preceding siblings ...)
  2017-02-03  8:28     ` Andreas Politz
@ 2017-02-03  8:28     ` Andreas Politz
  4 siblings, 0 replies; 11+ messages in thread
From: Andreas Politz @ 2017-02-03  8:28 UTC (permalink / raw)
  To: Joakim Jalap; +Cc: Eli Zaretskii, emacs-devel

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



^ permalink raw reply	[flat|nested] 11+ messages in thread

* Re: Overlay tree. Stuck again
  2017-02-03  8:28     ` Andreas Politz
@ 2017-02-03 12:35       ` Joakim Jalap
  0 siblings, 0 replies; 11+ messages in thread
From: Joakim Jalap @ 2017-02-03 12:35 UTC (permalink / raw)
  To: Andreas Politz; +Cc: emacs-devel

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



^ permalink raw reply	[flat|nested] 11+ messages in thread

end of thread, other threads:[~2017-02-03 12:35 UTC | newest]

Thread overview: 11+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2017-01-12 21:10 Overlay tree. Stuck again Joakim Jalap
2017-01-13  8:12 ` Eli Zaretskii
2017-01-13 11:56   ` Joakim Jalap
2017-01-13 13:22     ` Fabrice Popineau
2017-01-13 14:20       ` Joakim Jalap
2017-01-13 13:54     ` Eli Zaretskii
2017-01-13 14:26       ` Joakim Jalap
2017-02-03  8:27     ` Andreas Politz
2017-02-03  8:28     ` Andreas Politz
2017-02-03 12:35       ` Joakim Jalap
2017-02-03  8:28     ` Andreas Politz

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).