From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: Question collaborative editing. Date: Thu, 01 Oct 2020 16:40:59 +0300 Message-ID: <83pn62gj2s.fsf@gnu.org> References: <20200929215849.zg4wzytbrwx2b7ih@Ergus> <84B86B7C-81F0-42DF-894C-BF577E4B3D6E@mit.edu> <83a6x7js6y.fsf@gnu.org> <83eemji6e8.fsf@gnu.org> <83blhni3kr.fsf@gnu.org> <0B69D727-B2C1-44FC-8382-FDAB6C7CBDAD@mit.edu> <83a6x7i1d0.fsf@gnu.org> <20200930231159.q6h6etboucwkjcfe@Ergus> Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="39653"; mail-complaints-to="usenet@ciao.gmane.io" Cc: qhong@mit.edu, fmfs@posteo.net, bugs@gnu.support, npostavs@gmail.com, emacs-devel@gnu.org, kfogel@red-bean.com, monnier@iro.umontreal.ca To: Ergus Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Oct 01 15:42:35 2020 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1kNyqw-000ACg-KG for ged-emacs-devel@m.gmane-mx.org; Thu, 01 Oct 2020 15:42:34 +0200 Original-Received: from localhost ([::1]:60224 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kNyqv-0000KO-Li for ged-emacs-devel@m.gmane-mx.org; Thu, 01 Oct 2020 09:42:33 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:52420) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kNypZ-0007zQ-At for emacs-devel@gnu.org; Thu, 01 Oct 2020 09:41:11 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]:54752) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kNypX-0001zp-TN; Thu, 01 Oct 2020 09:41:08 -0400 Original-Received: from [176.228.60.248] (port=2127 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1kNypV-0008W8-IY; Thu, 01 Oct 2020 09:41:06 -0400 In-Reply-To: <20200930231159.q6h6etboucwkjcfe@Ergus> (message from Ergus on Thu, 1 Oct 2020 01:11:59 +0200) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 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-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:256841 Archived-At: > Date: Thu, 1 Oct 2020 01:11:59 +0200 > From: Ergus > Cc: Qiantan Hong , fmfs@posteo.net, bugs@gnu.support, > npostavs@gmail.com, emacs-devel@gnu.org, kfogel@red-bean.com, > monnier@iro.umontreal.ca > > If I understood the Qiantan idea; his approach is to add such ID as a > text property within the emacs buffer. To modify the buffer it is only > needed to search (go to) the property ID of text chars/words whatever in > the emacs buffer and perform the action. So the error probability is > smaller because the IDs ARE in the text itself. IMO, that is not a good idea, to put it mildly. Since these properties can potentially span very few characters, or even change the value at each buffer position in extreme cases, they will most probably slow down redisplay, perhaps even significantly so. The problem here is that the display engine always knows where's the next buffer position, called "stop position" at which text properties change values. Between the stop positions, the display engine runs at full throttle, using the information about properties (notably, faces) and overlays it computed at the last stop position. But when it comes to the next stop position, it stops and reconsiders all the stuff that can affect display: text properties (faces, invisibility), overlays, composed characters, etc., something that requires non-trivial processing. Having text properties change too often will cause slowdown, even though these properties don't affect redisplay. You can measure this slowdown by putting some text property on each character in a buffer (the property should have a different value for each character), then timing redisplay in a large enough buffer with such properties. For example, lean on the DOWN arrow and see how long it takes to scroll through a large file; or run one of the scroll-down benchmarks that were posted here in the past. Maybe I'm being overly pessimistic, but I expect slower redisplay with so many text property changes. So I definitely wouldn't recommend going that way. > This will reduce undetected errors inserting in the wrong positions when > translating form the CRDT ID to the real "global" buffer position to do > an "insert". Which could happen in some corner cases... (lets say > basically synchronization errors between local modifications (which > modify local absolute positions) and processing remote ones using > outdated information (translating to global indices)... I'm not sure we need to implement this in Emacs. For example, Tandem doesn't require this from its plugins; presumably, it builds the character IDs internally? You could look at its implementation of CRDT and take the ideas from there; AFAIU, it requires only a couple of very simple operations to be implemented by plugins. I also am not sure we should disregard the OT-based designs. It is true that they scale worse than CRDTs, but do we really envision groups of tens, let alone hundreds or thousands of users working at the same time in Emacs on the same document? For smaller groups, OT-based design might be good enough, and if it is simpler to implement and requires less from Emacs core, maybe this possibility should also be considered? > My previous concerns about the internal storage and performance was > because the linear search of text properties in a long linear buffer may > be very expensive as described in the refereed paper; Text property search in Emacs is not linear, it uses interval trees. The problem is not in the search, the problem is in how often we will need to do this when we traverse the buffer text, as redisplay does.