From: Sebastian Sturm <s.sturm@arkona-technologies.de>
To: emacs-devel@gnu.org
Subject: Re: State of the overlay tree branch?
Date: Fri, 23 Mar 2018 13:25:19 +0100 [thread overview]
Message-ID: <1ea4248a-11ce-00a9-0644-df7b2e5a3a58@arkona-technologies.de> (raw)
In-Reply-To: <jwvbmffjwyq.fsf-monnier+gmane.emacs.devel@gnu.org>
I haven't tested this very extensively yet, but artificial benchmark
results are now comparable to the noverlay branch and editing seems
similarly fluid. Many thanks for that!
On a tangential note, removing the bottleneck now brought up another
hotspot in my performance profile (less severe than the one previously
reported) that seems to be due to cc-mode itself. Since I don't want to
derail this thread, I'll try to implement some of the suggestions made
in the "Latency profiling?" thread and come up with some reproducible
data on that other issue.
On 03/23/2018 06:03 AM, Stefan Monnier wrote:
>> since noverlay performs so well, I guess the technical issue here is already
>> solved and I'll just have to wait for it to make it into the master
>> branch.
>
> Yes and no: there can still be many markers (even without having any
> overlays) and that poses the same problem (and the noverlays branch
> doesn't change that).
>
> I've made some further tests and found that the patch I sent indeed
> doesn't help tremendously with "distance += 10" but that when we reach
> "+= 50" the effect is more significant.
>
> Could you try the patch below (ideally not just with artificial tests
> but also in actual use) to see if it helps?
>
>
> Stefan
>
>
> diff --git a/src/marker.c b/src/marker.c
> index 7773c4fce0..6ab0d3d61e 100644
> --- a/src/marker.c
> +++ b/src/marker.c
> @@ -133,6 +133,28 @@ CHECK_MARKER (Lisp_Object x)
> CHECK_TYPE (MARKERP (x), Qmarkerp, x);
> }
>
> +/* When converting bytes from/to chars, we look through the list of
> + markers to try and find a good starting point (since markers keep
> + track of both bytepos and charpos at the same time).
> + But if there are many markers, it can take too much time to find a "good"
> + marker from which to start. Worse yet: if it takes a long time and we end
> + up finding a nearby markers, we won't add a new marker to cache this
> + result, so next time around we'll have to go through this same long list
> + to (re)find this best marker. So the further down the list of
> + markers we go, the less demanding we are w.r.t what is a good marker.
> +
> + The previous code used INITIAL=50 and INCREMENT=0 and this lead to
> + really poor performance when there are many markers.
> + I haven't tried to tweak INITIAL, but my experiments on my trusty Thinkpad
> + T61 using various artificial test cases seem to suggest that INCREMENT=50
> + might be "the best compromise": it significantly improved the
> + worst case and it was rarely slower and never by much.
> +
> + The asymptotic behavior is still poor, tho, so in largish buffers with many
> + overlays (e.g. 300KB and 30K overlays), it can still be a bottlneck. */
> +#define BYTECHAR_DISTANCE_INITIAL 50
> +#define BYTECHAR_DISTANCE_INCREMENT 50
> +
> /* Return the byte position corresponding to CHARPOS in B. */
>
> ptrdiff_t
> @@ -141,6 +163,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
> struct Lisp_Marker *tail;
> ptrdiff_t best_above, best_above_byte;
> ptrdiff_t best_below, best_below_byte;
> + ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
>
> eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
>
> @@ -180,8 +203,10 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
> /* If we are down to a range of 50 chars,
> don't bother checking any other markers;
> scan the intervening chars directly now. */
> - if (best_above - best_below < 50)
> + if (best_above - best_below < distance)
> break;
> + else
> + distance += BYTECHAR_DISTANCE_INCREMENT;
> }
>
> /* We get here if we did not exactly hit one of the known places.
> @@ -293,6 +318,7 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
> struct Lisp_Marker *tail;
> ptrdiff_t best_above, best_above_byte;
> ptrdiff_t best_below, best_below_byte;
> + ptrdiff_t distance = BYTECHAR_DISTANCE_INITIAL;
>
> eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
>
> @@ -323,8 +349,10 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
> /* If we are down to a range of 50 chars,
> don't bother checking any other markers;
> scan the intervening chars directly now. */
> - if (best_above - best_below < 50)
> + if (best_above - best_below < distance)
> break;
> + else
> + distance += BYTECHAR_DISTANCE_INCREMENT;
> }
>
> /* We get here if we did not exactly hit one of the known places.
>
>
--
Sebastian Sturm
Research & Development
Phone: +49 (0) 6155 7808977
Fax: +49 (0) 6155 7802880
Email: s.sturm@arkona-technologies.de
Web: www.arkona-technologies.de
arkona technologies GmbH
Im Leuschnerpark 4
64347 Griesheim
Germany
Amtsgericht / Commercial Register of Darmstadt, HRB 90080
USt-ID: DE273794666
Steuernummer / Tax-ID: 007 / 228 / 19331
Geschäftsführung / Managing Director: Rainer Sturm
This e-mail may contain confidential and/or privileged information. If
you are not the intended recipient (or have received this e-mail in
error) please notify the sender immediately and delete this message and
any attachments from your system. Any unauthorised copying, disclosure
or distribution of the material in this e-mail is strictly forbidden.
We cannot accept any responsibility for the accuracy or completeness of
this message as it has been transmitted over a public network. If,
despite our use of anti-virus software, a virus enters your systems in
connection with the sending of the e-mail, you may not hold us liable
for any damages that may possibly arise in that connection. We will
accept liability which by law we cannot exclude.
next prev parent reply other threads:[~2018-03-23 12:25 UTC|newest]
Thread overview: 54+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-03-18 20:14 State of the overlay tree branch? Sebastian Sturm
2018-03-18 20:39 ` Eli Zaretskii
2018-03-18 21:04 ` Sebastian Sturm
2018-03-18 23:03 ` Sebastian Sturm
2018-03-18 23:20 ` Sebastian Sturm
2018-03-19 6:43 ` Eli Zaretskii
2018-03-19 9:53 ` Sebastian Sturm
2018-03-19 12:57 ` Eli Zaretskii
2018-03-19 14:56 ` Stefan Monnier
2018-03-19 15:07 ` Sebastian Sturm
2018-03-19 15:13 ` Stefan Monnier
2018-03-20 1:23 ` Sebastian Sturm
2018-03-20 6:30 ` Eli Zaretskii
2018-03-21 0:36 ` Sebastian Sturm
2018-03-21 6:47 ` Eli Zaretskii
2018-03-22 13:16 ` Stefan Monnier
2018-03-22 19:54 ` Sebastian Sturm
2018-03-22 20:04 ` Sebastian Sturm
2018-03-22 20:52 ` Stefan Monnier
2018-03-22 23:11 ` Sebastian Sturm
2018-03-23 5:03 ` Stefan Monnier
2018-03-23 12:25 ` Sebastian Sturm [this message]
2018-03-23 12:47 ` Eli Zaretskii
2018-03-23 13:19 ` Stefan Monnier
2018-03-23 13:37 ` Noam Postavsky
2018-03-23 13:55 ` Stefan Monnier
2018-03-23 14:22 ` Eli Zaretskii
2018-03-23 14:39 ` Stefan Monnier
2018-03-23 19:39 ` Stefan Monnier
2018-03-25 15:11 ` Stefan Monnier
2018-03-25 16:39 ` Eli Zaretskii
2018-03-25 17:35 ` Stefan Monnier
2018-03-23 8:07 ` Eli Zaretskii
2018-03-23 9:08 ` Eli Zaretskii
2018-03-23 10:15 ` Sebastian Sturm
2018-03-23 12:39 ` Eli Zaretskii
2018-03-23 12:12 ` Stefan Monnier
2018-03-23 12:40 ` Eli Zaretskii
2018-03-23 12:55 ` Stefan Monnier
2018-03-19 6:36 ` Eli Zaretskii
2018-03-19 6:28 ` Eli Zaretskii
2018-03-21 14:14 ` Sebastien Chapuis
2018-03-21 15:35 ` Eli Zaretskii
2018-03-26 13:06 ` Stefan Monnier
2018-03-27 20:59 ` Sebastian Sturm
[not found] <<c24f8534-5245-026e-da18-f6be7b9702bf@arkona-technologies.de>
[not found] ` <<834lldp18f.fsf@gnu.org>
2018-03-18 21:37 ` Drew Adams
2018-03-19 1:33 ` Stefan Monnier
2018-03-19 6:50 ` Eli Zaretskii
2018-03-19 12:29 ` Stefan Monnier
2018-03-19 13:02 ` Eli Zaretskii
2018-03-19 13:43 ` Stefan Monnier
2018-03-19 14:28 ` Eli Zaretskii
2018-03-19 14:39 ` Stefan Monnier
2018-03-19 6:33 ` Eli Zaretskii
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=1ea4248a-11ce-00a9-0644-df7b2e5a3a58@arkona-technologies.de \
--to=s.sturm@arkona-technologies.de \
--cc=emacs-devel@gnu.org \
/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.