Re: State of the overlay tree branch?

[Stefan Monnier <monnier@IRO.UMontreal.CA>]

> OK, I think I'm tired of these experiments.

Taking a break finally let me get rid of my blinders so I could see
more clearly what's going on:

All this time is really spent in find_newline (rather than in things
like goto-char).  The problem goes as follows:

A - (line-number-at-pos POS) will call find_newline, making it scan all
    positions between point-min and POS.
B1- if find_newline uses the newline cache, at each newline encountered it
    will call buf_charpos_to_bytepos.
B2- if find_newline does not use the newline cache, at each newline
    encountered it will call buf_bytepos_to_charpos.
  - Each time buf_charpos_to_bytepos/buf_bytepos_to_charpos is called
    it will "CONSIDER" the known positions at point-min, point-max, and at
    the position of the last-call (i.e. at the previous newline).
    Then it will loop through all the markers until the distance between
    the nearest position before POS and the nearest position after POS
    are within 50 of each other.
C - since one of the known positions is the one of the last newline, the
    distance between the nearest position and POS (before considering any
    marker) is usually pretty small: the length of the current line.
    It's even often smaller than 50.  But that doesn't let us stop because
    the marker loop doesn't pay attention to the distance to POS in order
    to decide to stop: it only consider the distance between the current upper
    and lower bound and since we're scanning in one direction, all the
    recently seen positions (added as markers) are on the same side of
    POS as the last seen newline so they don't help.

So there are various ways to solve this problem.  So far, I tried to
make the markers-loop give up earlier, which helps (C) to some extent but
without attacking the core of its problem which is to pay attention to
the case where one of the bounds is already very close to POS even tho
the other is still way off.

The patch below tweaks my previous patch to take this into account.
The result is now that my test cases stay fast (mostly unaffected by the
number of markers) even for large buffers with a large number of markers.

Note that the above shows that there are other optimisations which would
also solve this problem (and would be worthwhile independently).
A - change line-number-at-pos so it doesn't always rescan all the way
    from point-min.  This would really circumvent the whole problem
    (contrarily to what I thought before with my blinders on, thanks Eli
    for insisting on that).
B - change find_newline so it doesn't call
    buf_charpos_to_bytepos/buf_bytepos_to_charpos at each newline.
    E.g. in the no-newline-cache case it'd probably be faster to
    loop through each char using INC/DEC_BOTH and checking if we're at
    \n, than the current code which uses mem(r)chr to look for the
    bytepos of the next \n and then calls buf_bytepos_to_charpos to get
    the corresponding charpos.  Alternatively, we could just delay the
    computation of the charpos until the end (currently we update it
    at each newline, for the purpose of filling the newline-cache).


-- Stefan


diff --git a/src/marker.c b/src/marker.c
index 7773c4fce0..f869b3f948 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,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.
@@ -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.