[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Emacs-diffs] feature/gnus-select 29d2a98 214/218: * src/marker.c: Try a
From: |
Andrew G Cohen |
Subject: |
[Emacs-diffs] feature/gnus-select 29d2a98 214/218: * src/marker.c: Try and speed up byte<->char conversion with many markers. |
Date: |
Fri, 14 Dec 2018 03:35:46 -0500 (EST) |
branch: feature/gnus-select
commit 29d2a98366f075ffcc891992e6f2e2fa9d79d085
Author: Stefan Monnier <address@hidden>
Commit: Andrew G Cohen <address@hidden>
* src/marker.c: Try and speed up byte<->char conversion with many markers.
When considering markers (to find a starting point for the conversion),
typically one of the two bounds is nearby (coming from
cached_(byte|char)pos) but the other is far (point-min or point-max),
so change the exit condition so we stop as soon as *one* of the bounds
is near.
(BYTECHAR_DISTANCE_INITIAL, BYTECHAR_DISTANCE_INCREMENT): New constants.
(buf_charpos_to_bytepos, buf_bytepos_to_charpos): Use them to try and
reduce the number of markers we consider.
---
src/marker.c | 50 ++++++++++++++++++++++++++++++++++++++++----------
1 file changed, 40 insertions(+), 10 deletions(-)
diff --git a/src/marker.c b/src/marker.c
index 7773c4f..9933d95 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -90,7 +90,7 @@ clear_charpos_cache (struct buffer *b)
#define CONSIDER(CHARPOS, BYTEPOS) \
{ \
ptrdiff_t this_charpos = (CHARPOS); \
- bool changed = 0; \
+ bool changed = false;
\
\
if (this_charpos == charpos) \
{ \
@@ -105,14 +105,14 @@ clear_charpos_cache (struct buffer *b)
{ \
best_above = this_charpos; \
best_above_byte = (BYTEPOS); \
- changed = 1; \
+ changed = true; \
} \
} \
else if (this_charpos > best_below) \
{ \
best_below = this_charpos; \
best_below_byte = (BYTEPOS); \
- changed = 1; \
+ changed = true; \
} \
\
if (changed) \
@@ -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 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,11 @@ 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 - charpos < distance
+ || charpos - best_below < distance)
break;
+ else
+ distance += BYTECHAR_DISTANCE_INCREMENT;
}
/* We get here if we did not exactly hit one of the known places.
@@ -248,7 +274,7 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t charpos)
#define CONSIDER(BYTEPOS, CHARPOS) \
{ \
ptrdiff_t this_bytepos = (BYTEPOS); \
- int changed = 0; \
+ int changed = false; \
\
if (this_bytepos == bytepos) \
{ \
@@ -263,14 +289,14 @@ buf_charpos_to_bytepos (struct buffer *b, ptrdiff_t
charpos)
{ \
best_above = (CHARPOS); \
best_above_byte = this_bytepos; \
- changed = 1; \
+ changed = true; \
} \
} \
else if (this_bytepos > best_below_byte) \
{ \
best_below = (CHARPOS); \
best_below_byte = this_bytepos; \
- changed = 1; \
+ changed = true; \
} \
\
if (changed) \
@@ -293,6 +319,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 +350,11 @@ 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 - bytepos < distance
+ || bytepos - best_below < distance)
break;
+ else
+ distance += BYTECHAR_DISTANCE_INCREMENT;
}
/* We get here if we did not exactly hit one of the known places.
@@ -744,8 +774,8 @@ count_markers (struct buffer *buf)
ptrdiff_t
verify_bytepos (ptrdiff_t charpos)
{
- ptrdiff_t below = 1;
- ptrdiff_t below_byte = 1;
+ ptrdiff_t below = BEG;
+ ptrdiff_t below_byte = BYTE_BEG;
while (below != charpos)
{
- [Emacs-diffs] feature/gnus-select fe87972 186/218: * doc/emacs/trouble.texi: Fix location of `emacs-version' index., (continued)
- [Emacs-diffs] feature/gnus-select fe87972 186/218: * doc/emacs/trouble.texi: Fix location of `emacs-version' index., Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 21aa752 184/218: Make update_autogen work in git worktrees, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 7985c87 188/218: * src/alloc.c: Avoid O(N²) complexity when unchaining markers (bug#24548)., Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 1a1bb0c 185/218: Explain more about (defvar foo) form (Bug#18059), Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select d46646d 195/218: Replace cl in some obsolete files, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select e70347a 202/218: Limit build load, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select f06346b 198/218: Clarify syntax of radixed integers, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 7bb9822 203/218: Remove variables labeled as obsolete that do nothing, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 6d35e8a 183/218: Quieten cl-lib related compiler warnings, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select fdbaac5 213/218: Fix problem with trailing slash in Tramp, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 29d2a98 214/218: * src/marker.c: Try and speed up byte<->char conversion with many markers.,
Andrew G Cohen <=
- [Emacs-diffs] feature/gnus-select 5a33078 217/218: Trivial fixes for last changes to package.el and marker.c, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 491c4c3 201/218: Ensure configure is running if necessary, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 3cd3c00 210/218: Allow `&rest' or `&optional' without following variable (Bug#29165), Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select fe90b22 215/218: * lisp/emacs-lisp/package.el: New quickstart feature, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select fe4af1c 126/218: Normalize and fix some mistakes in NS-related commentary, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select bdea39b 190/218: Instrument tramp-test39-utf8, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 5a4b225 199/218: Quieten lisp/obsolete compilation, Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select 49b7f74 205/218: * lisp/vc/vc.el (vc-initial-comment): Remove var unused since 23.2., Andrew G Cohen, 2018/12/14
- [Emacs-diffs] feature/gnus-select cf14b56 207/218: Reduce build load, Andrew G Cohen, 2018/12/14