From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: Release plans Date: Mon, 01 Sep 2008 15:53:26 -0400 Message-ID: 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> <48BC4DF0.3090908@emf.net> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1220298836 983 80.91.229.12 (1 Sep 2008 19:53:56 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 1 Sep 2008 19:53:56 +0000 (UTC) Cc: acm@muc.de, bob@rattlesnake.com, rms@gnu.org, emacs-devel@gnu.org To: Thomas Lord Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Mon Sep 01 21:54:50 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 1KaFU9-0005OJ-GF for ged-emacs-devel@m.gmane.org; Mon, 01 Sep 2008 21:54:50 +0200 Original-Received: from localhost ([127.0.0.1]:37540 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaFT9-0002UU-3h for ged-emacs-devel@m.gmane.org; Mon, 01 Sep 2008 15:53:47 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KaFT4-0002UF-Ui for emacs-devel@gnu.org; Mon, 01 Sep 2008 15:53:42 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KaFT1-0002Tq-QM for emacs-devel@gnu.org; Mon, 01 Sep 2008 15:53:42 -0400 Original-Received: from [199.232.76.173] (port=37694 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KaFT1-0002Tn-KD for emacs-devel@gnu.org; Mon, 01 Sep 2008 15:53:39 -0400 Original-Received: from ironport2-out.pppoe.ca ([206.248.154.182]:19975 helo=ironport2-out.teksavvy.com) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1KaFSt-00025B-N2; Mon, 01 Sep 2008 15:53:32 -0400 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApMFAHTlu0hFxJrH/2dsb2JhbACBZbFfgWmBBw X-IronPort-AV: E=Sophos;i="4.32,309,1217822400"; d="scan'208";a="26194754" Original-Received: from 69-196-154-199.dsl.teksavvy.com (HELO ceviche.home) ([69.196.154.199]) by ironport2-out.teksavvy.com with ESMTP; 01 Sep 2008 15:53:26 -0400 Original-Received: by ceviche.home (Postfix, from userid 20848) id C280CB41E9; Mon, 1 Sep 2008 15:53:26 -0400 (EDT) In-Reply-To: <48BC4DF0.3090908@emf.net> (Thomas Lord's message of "Mon, 01 Sep 2008 13:17:52 -0700") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.60 (gnu/linux) X-detected-kernel: by monty-python.gnu.org: Genre and OS details not recognized. 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:103389 Archived-At: >>> 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