Re: Release plans

[Stefan Monnier <monnier@iro.umontreal.ca>]

>>> I don't think we would want to implement undo by making a snapshot,
>>> even if the data makes snapshots possible, because this would take up
>>> a lot more space than the current undo data.
>> I don't think it would necessarily take up significantly more memory.
>> In some cases it'll use up less memory.  OTOH it might make it difficult
>> to implement undo-elt-in-region.
> Neat problem.  No, I hadn't thought about that case.
> Is it the case that undo-elt-in-region exists for little or
> nothing more than undo-in-region?

AFAIK yes.

> Markers are currently still stored in a list, right?

Yes.

> My plan is to keep markers in a tree in such a way that
> inserts and deletes are log N in the number of markers,
> and accessing a marker's position is log N in the number
> of markers, but because this will be a self-adjusting tree
> all those operations will be O(1) in the expected case where
> changes display pretty good locality.

Not sure how you intend to do that (I considered exactly this kind of
change in the past, but could never come up with a solution that was
satisfactorily elegant).  The O(1) is not necessary, actually.
Anything close to O(log N) will be a welcome improvement.
IIUC XEmacs uses a gap-buffer kind of solution (i.e. not a list of
markers but an array of markers with a moving gap in the middle).

(I've tried splay-trees for text-properties, and the performance was not
noticeably different from the current mostly-balanced binary tree.
In particular it seems that either we don't get to see the O(1) behavior
because the locality is not as good as it seems, or the constant factor
makes up for the difference).

> It *should* (in theory) be just fine for each undo-elt
> to contain both string snapshot(s) and markers that
> track the region effected.   That's easy to code and in
> turn it makes undo-elt-in-region very easy to code.

But that would significantly increase the size of the undo log, I expect
(maybe not algorithmically, but by a non-negligible factor).

It's too bad, because of we ignore the undo-in-region, we don't need
undo info for each modification, we could just grab a snapshot in
undo-boundary.  That would be elegant (tho it's not like it matters:
changing the implementation of the undo data is trying to solve
a non-problem, really).


        Stefan