[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: State of the overlay tree branch?
From: |
Stefan Monnier |
Subject: |
Re: State of the overlay tree branch? |
Date: |
Mon, 19 Mar 2018 09:43:12 -0400 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) |
>> The idea is that the above loop (even if called only twice) might be
>> sufficient to make line-number-at-pos take 0.2s.
> I very much doubt that loop could take such a long time.
I also find it unlikely.
> And running a benchmark 1000 times means that the 2nd through 1000th
> iteration find the mapping much faster, probably bypassing the
> loop entirely.
Quite likely.
BTW, when thinking about how to avoid this loop's worst case (regardless
if it's the source of the current problem), I was thinking that we could
probably make that worst case even less likely by replacing the
hardcoded "50" with a limit that grows as the loop progresses.
The patch below should make sure that the total number of iterations
(through markers + through chars) is no more than 2*buffer-size, no matter
how many markers there are.
[ Rather than incrementing by 1 we should ideally increment by
a number that corresponds to how much slower is each iteration through
markers compared to the iteration through chars, but I have no idea
what that number would typically be. ]
WDYT?
Stefan
diff --git a/src/marker.c b/src/marker.c
index f61701f2f6..bfe6de486e 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -141,6 +141,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 = 50;
eassert (BUF_BEG (b) <= charpos && charpos <= BUF_Z (b));
@@ -180,8 +181,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++;
}
/* We get here if we did not exactly hit one of the known places.
@@ -293,6 +296,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 = 50;
eassert (BUF_BEG_BYTE (b) <= bytepos && bytepos <= BUF_Z_BYTE (b));
@@ -323,8 +327,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++;
}
/* We get here if we did not exactly hit one of the known places.
RE: State of the overlay tree branch?, Drew Adams, 2018/03/18
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/18
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/19
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/19
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/19
- Re: State of the overlay tree branch?,
Stefan Monnier <=
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/19
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/19
Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/19
Re: State of the overlay tree branch?, Sebastien Chapuis, 2018/03/21
Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/26