From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Thomas Lord Newsgroups: gmane.emacs.devel Subject: Re: Release plans Date: Mon, 01 Sep 2008 13:17:52 -0700 Message-ID: <48BC4DF0.3090908@emf.net> References: <878wusz0v9.fsf@uwakimon.sk.tsukuba.ac.jp> <87vdxp27z6.fsf@uwakimon.sk.tsukuba.ac.jp> <87prnxe5hc.fsf@rattlesnake.com> <873aktck5d.fsf@uwakimon.sk.tsukuba.ac.jp> <87k5e5dsvq.fsf@rattlesnake.com> <48B44802.1080302@emf.net> <48B5D5EF.2030501@emf.net> <20080827220906.GB5374@muc.de> <48B5FB11.6090708@emf.net> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="------------060406090807020405020507" X-Trace: ger.gmane.org 1220297229 28421 80.91.229.12 (1 Sep 2008 19:27:09 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2008 19:27:09 +0000 (UTC) Cc: acm@muc.de, bob@rattlesnake.com, rms@gnu.org, emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Sep 01 21:28:02 2008 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1KaF4D-000776-G2 for ged-emacs-devel@m.gmane.org; Mon, 01 Sep 2008 21:28:01 +0200 Original-Received: from localhost ([127.0.0.1]:36489 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaF3E-0000sc-Fy for ged-emacs-devel@m.gmane.org; Mon, 01 Sep 2008 15:27:00 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KaF39-0000qd-DZ for emacs-devel@gnu.org; Mon, 01 Sep 2008 15:26:55 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KaF37-0000p8-QJ for emacs-devel@gnu.org; Mon, 01 Sep 2008 15:26:54 -0400 Original-Received: from [199.232.76.173] (port=57348 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaF37-0000op-9Z for emacs-devel@gnu.org; Mon, 01 Sep 2008 15:26:53 -0400 Original-Received: from mail.42inc.com ([205.149.0.25]:33711) by monty-python.gnu.org with esmtps (SSL 3.0:RSA_3DES_EDE_CBC_SHA1:24) (Exim 4.60) (envelope-from ) id 1KaF32-0006UX-3p; Mon, 01 Sep 2008 15:26:48 -0400 X-TFF-CGPSA-Version: 1.5 X-TFF-CGPSA-Filter-42inc: Scanned X-42-Virus-Scanned: by 42 Antivirus -- Found to be clean. Original-Received: from [69.236.75.128] (account lord@emf.net HELO [192.168.1.64]) by mail.42inc.com (CommuniGate Pro SMTP 5.0.13) with ESMTPA id 38074992; Mon, 01 Sep 2008 12:26:34 -0700 User-Agent: Thunderbird 1.5.0.5 (X11/20060808) In-Reply-To: X-detected-kernel: by monty-python.gnu.org: Linux 2.6, seldom 2.4 (older, 4) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:103387 Archived-At: This is a multi-part message in MIME format. --------------060406090807020405020507 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Stefan Monnier wrote: >> 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? Because: Markers are currently still stored in a list, right? So inserts and deletes are linear in the number of markers in a buffer, right? (I thought I remembered that changing long ago but looking at 22.1 source I guess not.) 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. In other words: markers get a lot cheaper. 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. That's an example of why I (so far) like this data structure better than the current ones. If markers get significantly cheaper than they currently are, and functional string edit operations get faster -- a lot of code can be simpler. -t > > Stefan > > > > > --------------060406090807020405020507 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Stefan Monnier wrote: 
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?    Because:

Markers are currently still stored in a list, right?
So inserts and deletes are linear in the number of
markers in a buffer, right?   (I thought I remembered
that changing long ago but looking at 22.1 source
I guess not.)

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.

In other words: markers get a lot cheaper.

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.

That's an example of why I (so far) like this data
structure better than the current ones.   If markers get
significantly cheaper than they currently are, and
functional string edit operations get faster -- a lot of
code can be simpler.

-t






        Stefan

--------------060406090807020405020507--