From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: Markers/intervals/overlays + trees Date: Thu, 09 Aug 2012 19:15:38 +0300 Message-ID: <83pq70dot1.fsf@gnu.org> References: <5022934F.3050702@yandex.ru> <83wr19dzbj.fsf@gnu.org> <83vcgtdsg9.fsf@gnu.org> <5023344C.6020603@yandex.ru> Reply-To: Eli Zaretskii NNTP-Posting-Host: plane.gmane.org X-Trace: dough.gmane.org 1344529345 10600 80.91.229.3 (9 Aug 2012 16:22:25 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Thu, 9 Aug 2012 16:22:25 +0000 (UTC) Cc: monnier@IRO.UMontreal.CA, emacs-devel@gnu.org To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Aug 09 18:22:25 2012 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1SzVV7-0001Dj-2R for ged-emacs-devel@m.gmane.org; Thu, 09 Aug 2012 18:22:21 +0200 Original-Received: from localhost ([::1]:44458 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SzVV6-0000hx-4C for ged-emacs-devel@m.gmane.org; Thu, 09 Aug 2012 12:22:20 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:39074) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SzVV3-0000hc-I7 for emacs-devel@gnu.org; Thu, 09 Aug 2012 12:22:18 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SzVUx-0000el-JJ for emacs-devel@gnu.org; Thu, 09 Aug 2012 12:22:17 -0400 Original-Received: from mtaout22.012.net.il ([80.179.55.172]:53116) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SzVUx-0000ec-Ay for emacs-devel@gnu.org; Thu, 09 Aug 2012 12:22:11 -0400 Original-Received: from conversion-daemon.a-mtaout22.012.net.il by a-mtaout22.012.net.il (HyperSendmail v2007.08) id <0M8H00300X11RZ00@a-mtaout22.012.net.il> for emacs-devel@gnu.org; Thu, 09 Aug 2012 19:15:34 +0300 (IDT) Original-Received: from HOME-C4E4A596F7 ([87.69.4.28]) by a-mtaout22.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0M8H003F6X5YJB60@a-mtaout22.012.net.il>; Thu, 09 Aug 2012 19:15:34 +0300 (IDT) In-reply-to: <5023344C.6020603@yandex.ru> X-012-Sender: halo1@inter.net.il X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-Received-From: 80.179.55.172 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:152367 Archived-At: > Date: Thu, 09 Aug 2012 07:53:48 +0400 > From: Dmitry Antipov > CC: Eli Zaretskii , > Stefan Monnier > > The more I do different things around buffers and markers/intervals/overlays, > the more I think that the last three ones represents nearly the same thing, > i.e. "buffer range with properties" (marker is the range of length 0 (or 1, > that's may be the question), and without properties). They are not necessarily as similar as you make them sound. I don't know if the dissimilarities contradict your idea, but they should be kept in mind: . Intervals are basis for text properties, and text properties cannot overlap, in the sense that 2 text properties with same property but different values cannot span overlapping regions of text. By contrast, overlays with the same property but different values _can_ overlap. . Text properties can be attached to strings, not just buffers. The other two kinds cannot. > Is it reasonable/ possible/feasible to generalize them into the only > type and use it everywhere? What would be the gains from such a generalization? > If not, shouldn't markers and overlays be chained into double-linked lists > instead of single-linked, for the sake of fast unchain/re-chain and in-place sort? My gut feeling is that the most important operation is to find an overlay covering the some buffer position, or the next/previous overlay from a given position. Optimization efforts should be directed to these operations first and foremost. > Finally, what about an idea to generalize red-black tree from alloc.c and > use it everywhere when O(log(n)) data structure is needed? Aren't insertion and deletion more expensive in red-black trees than in "regular" binary trees? If they are, this will hurt text properties performance. Buffers with an enormous amount of text properties are quite frequent. As another data point, the XEmacs "extents", which are (AFAIK) a kind of text properties and overlays in the same feature, are not implemented on top of trees. I dare to assume that this is not because the designers didn't know about trees. IOW, I think little more analysis and initial design is needed before we can assess the alternatives.