Re: Release plans

[Stephen J. Turnbull]

Thomas Lord writes:

 > It says extents are implemented as a pair of gap buffers.

Well, yes and no.  The extent lists used by redisplay are implemented
as a pair of gap buffers; this allows O(log N) -- where N is always
the number of objects (here, extents) -- identification of the
display-order-maximal extent containing a buffer location, and also is
the correct order for redisplay to process extents so that redisplay
of an Emacs window can be O(number of buffer characters visible in
window).

However, extents themselves are full-fledged Lisp objects allocated on
the heap, and that is where position information is kept.  And it
turns out that in many common cases finding a particular extent is
O(N) (consider the case where the desired extent happens to cover the
whole buffer and the location is (point-max), while any extent *could*
have the desired property).

How does your splay tree scheme handle that?

 > It also talks about the concept of cached stacks of events -- e.g.,
 > a cache of the list of extents at a given point from which the
 > extents over a nearby point can be quickly computed.

With the caveat above, this is the current scheme.

 > The splay tree of gap buffers should do considerably better with
 > [the] access patterns [Steve described].  That's the theory,
 > anyway:

OK.

 > The new data structure has an operation equivalent
 > to "move the gap" (so, e.g., insertions just write to
 > a linear piece of memory) however gap motion
 > is O(log N) buffer size in terms of operations and
 > O(1) for the amount of text that has to move.  Marker
 > updates, getting the position of a marker, and

Urk.  Markers are not interesting AFAICS.  What needs to be efficient
is extents (whether text properties or overlays), because they carry
display properties and other things that may be referenced many times
in a pass over the buffer (eg, font-lock or building a parse tree).
What is difficult (for me, anyway) is extents.

 > getting back a list of text properties over a given point are all
 > O(log N) -- O(1) with good locality.

This last I'll want to see.  I suspect it will be expensive in space.

 > If extents are still the double gap buffer + extent stack
 > cache then I can see where you'd have problems like those
 > you describe.   In theory, this new thing does better in
 > those cases.

Well, we'll see.  I've found it quite easy to develop O(log N)
algorithms for markers.  But (except for redisplay, where the
two-sorted-list scheme is great), common operations on extents can
involve O(N) algorithms.