all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: Andreas Politz <politza@hochschule-trier.de>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: emacs-devel@gnu.org
Subject: Re: Overlays as an AA-tree
Date: Fri, 24 Feb 2017 09:43:16 +0100	[thread overview]
Message-ID: <87vas07zdn.fsf@luca> (raw)
In-Reply-To: <jwvefyrml0q.fsf-monnier+gmane.emacs.devel@gnu.org> (Stefan Monnier's message of "Tue, 21 Feb 2017 14:18:44 -0500")

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Is there a reason why "struct Lisp_Overlay" and "struct interval_node"
> are separate?

The main reason is that it can't be used for anything else, once the
nodes are all Lisp_Overlay's .  There are at least two other balanced
trees in Emacs and maybe, at some time, there should be only one. (Also,
initially I didn't need to worry about the Emacs side.)

> [...] That means an overlay takes up about twice the size of a marker.
>
> Should we then (re)implement markers as degenerate overlays?  [it's not
> as simple as it sounds: contrary to overlays markers can be GC'd if not
> referenced, so we'd need to add support for "weakly referenced
> overlays".  Furthermore markers are used to speed up byte<->char
> conversions, so we'd need to replace that code accordingly.  ]

Could we use the end attribute as byte value ?  Also, does Emacs create
extra markers for this lookup or can this be called a "opportunistic
optimization" ?

I did some comparisons between marker and empty overlays regarding
insertions and deletions.  *-before and *-after insert/delete at
point-min resp. -max, scatter means randomly.  In each case 4096
single character were inserted/deleted.

===============================================
                     32K               64K
                 ------------     -------------
4096 edits        ma    ov         ma     ov
-----------------------------------------------
insert-before    4.20  0.22       16.66  0.44

insert-after     3.28  0.12       12.96  0.20

insert-scatter   4.84  0.21       18.74  0.37

delete-before    4.09  60.32      16.16  277.75

delete-after     3.75  35.49      14.74  160.91

delete-scatter   4.02  0.36       15.64  0.86
===============================================

As you can see the delete-before/after cases are still somewhat
problematic.  Maybe we should think about using a single node per
position combined with a list.  What do you think ?

-ap



  parent reply	other threads:[~2017-02-24  8:43 UTC|newest]

Thread overview: 110+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-09-20 10:32 Overlays as an AA-tree Joakim Jalap
2016-09-20 12:14 ` Clément Pit--Claudel
2016-09-20 12:43 ` Lars Ingebrigtsen
2016-09-20 16:19   ` Joakim Jalap
2016-09-20 23:19   ` Richard Stallman
2016-09-20 14:40 ` Eli Zaretskii
2016-09-20 17:13   ` Joakim Jalap
2016-09-21 16:14     ` Eli Zaretskii
2016-09-22 10:35       ` Joakim Jalap
2016-09-22 12:24         ` Stefan Monnier
2016-09-21 14:52 ` Stefan Monnier
2016-09-21 15:58   ` Eli Zaretskii
2016-09-21 16:24     ` Stefan Monnier
2016-09-21 16:43       ` Eli Zaretskii
2016-09-21 18:41         ` Stefan Monnier
2016-09-21 19:28           ` Eli Zaretskii
2016-09-22 10:35   ` Joakim Jalap
2016-09-22 12:17     ` Stefan Monnier
2016-09-22 20:11       ` Joakim Jalap
2016-09-23  1:29         ` Stefan Monnier
2016-09-27  6:26           ` Joakim Jalap
2016-09-27 11:50             ` Stefan Monnier
2016-09-27 14:38             ` Eli Zaretskii
2016-09-27 16:07               ` Joakim Jalap
2016-11-21 17:32                 ` Clément Pit--Claudel
2016-11-22  8:09                   ` Joakim Jalap
2016-11-22 13:44                     ` Stefan Monnier
2016-11-23  6:58                       ` Joakim Jalap
2016-11-22 13:44                     ` Clément Pit--Claudel
2016-11-22 13:55                       ` Evgeny Roubinchtein
2016-11-23  7:16                         ` Joakim Jalap
2016-11-23 15:42                           ` Eli Zaretskii
2016-11-23 16:06                             ` Stefan Monnier
2016-11-24 18:33                               ` Evgeny Roubinchtein
2016-11-23  7:13                       ` Joakim Jalap
2017-02-03  8:49 ` Andreas Politz
2017-02-03  9:13   ` Eli Zaretskii
2017-02-03 10:24     ` Andreas Politz
2017-02-03 11:33   ` Joakim Jalap
2017-02-03 12:44     ` Andreas Politz
2017-02-03 14:11       ` Joakim Jalap
2017-02-03 15:02         ` Andreas Politz
2017-02-03 15:23           ` Joakim Jalap
2017-02-03 15:54             ` Andreas Politz
2017-02-04 21:22       ` Stefan Monnier
2017-02-04 23:10         ` Andreas Politz
2017-02-06  9:56           ` Joakim Jalap
2017-02-06 11:33             ` Andreas Politz
2017-02-06 15:33               ` Joakim Jalap
2017-02-06 15:46                 ` Stefan Monnier
2017-02-06 16:52                   ` Joakim Jalap
2017-02-06 17:34                     ` Stefan Monnier
2017-02-06 17:32                 ` Andreas Politz
2017-02-07 12:35               ` Andreas Politz
2017-02-07 14:46                 ` Joakim Jalap
2017-02-07 22:00                 ` Andreas Politz
2017-02-08  0:36                   ` Andreas Politz
2017-02-08  6:53                     ` Joakim Jalap
2017-02-08  7:34                       ` Andreas Politz
2017-02-08  8:18                         ` Joakim Jalap
2017-02-08  8:44                           ` Andreas Politz
2017-02-08 16:34                           ` Andreas Politz
2017-02-08 17:38                         ` Eli Zaretskii
2017-02-08 13:04                   ` Stefan Monnier
2017-02-08 22:27                     ` Andreas Politz
2017-02-08 22:34                       ` Stefan Monnier
2017-02-09  9:34                         ` Andreas Politz
2017-02-09 10:05                           ` Joakim Jalap
2017-02-09 10:19                             ` Andreas Politz
2017-02-13  3:44                             ` Andreas Politz
2017-02-13  6:11                               ` Eli Zaretskii
2017-02-13  9:04                                 ` Andreas Politz
2017-02-13 14:36                                   ` Eli Zaretskii
2017-02-14 10:07                                     ` Andreas Politz
2017-02-17  4:58                                 ` Andreas Politz
2017-02-17  7:12                                   ` Eli Zaretskii
2017-02-19 22:39                                     ` Andreas Politz
2017-02-19 23:10                                       ` Stefan Monnier
2017-02-19 23:44                                         ` Andreas Politz
2017-02-20 15:34                                       ` Eli Zaretskii
2017-02-21  6:56                                         ` Andreas Politz
2017-02-21 15:11                                           ` Stefan Monnier
2017-02-21 18:26                                             ` Andreas Politz
2017-02-21 19:18                                               ` Stefan Monnier
2017-02-21 23:36                                                 ` Andreas Politz
2017-02-24  8:43                                                 ` Andreas Politz [this message]
2017-04-08 13:28                                                   ` Clément Pit-Claudel
2017-05-03 19:20                                                     ` Andreas Politz
2017-05-03 19:40                                                       ` Stefan Monnier
2017-05-05 20:39                                                         ` Andreas Politz
2017-05-04  0:54                                                       ` Clément Pit-Claudel
2017-05-05 20:10                                                         ` Andreas Politz
2017-05-05 22:22                                                           ` Clément Pit-Claudel
2017-05-06  8:05                                                             ` Andreas Politz
2017-05-04 14:21                                                       ` Eli Zaretskii
2017-05-05 20:08                                                         ` Andreas Politz
2017-05-05 21:41                                                           ` Eli Zaretskii
2017-09-24 13:09                                                         ` Clément Pit-Claudel
2017-10-04  8:17                                                           ` Andreas Politz
2017-10-04  9:22                                                             ` Eli Zaretskii
2017-10-04 20:36                                                               ` Andreas Politz
2017-02-14  0:45                               ` Richard Stallman
2017-02-14  8:32                                 ` Andreas Politz
2017-02-06 13:51             ` Stefan Monnier
2017-02-06 14:26               ` Andreas Politz
2017-02-06 15:06                 ` Stefan Monnier
2017-02-06 15:40               ` Joakim Jalap
2017-02-06 16:24                 ` Clément Pit-Claudel
2017-02-03 13:55   ` Stefan Monnier
2017-02-03 15:14     ` Andreas Politz

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=87vas07zdn.fsf@luca \
    --to=politza@hochschule-trier.de \
    --cc=emacs-devel@gnu.org \
    --cc=monnier@iro.umontreal.ca \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this external index

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

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.