From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Ergus Newsgroups: gmane.emacs.devel Subject: Re: Question collaborative editing. Date: Thu, 1 Oct 2020 17:55:50 +0200 Message-ID: <20201001155550.qkg3jresu7zopwbs@Ergus> References: <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> <83pn62gj2s.fsf@gnu.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="14865"; 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: Eli Zaretskii Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Thu Oct 01 18:22:05 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 1kO1LI-0003jo-Q4 for ged-emacs-devel@m.gmane-mx.org; Thu, 01 Oct 2020 18:22:04 +0200 Original-Received: from localhost ([::1]:53244 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kO1LH-0007S1-Py for ged-emacs-devel@m.gmane-mx.org; Thu, 01 Oct 2020 12:22:03 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:34250) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kO0wG-0003Ns-19 for emacs-devel@gnu.org; Thu, 01 Oct 2020 11:56:12 -0400 Original-Received: from sonic301-2.consmr.mail.bf2.yahoo.com ([74.6.129.41]:38845) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kO0w8-00069n-RH for emacs-devel@gnu.org; Thu, 01 Oct 2020 11:56:11 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aol.com; s=a2048; t=1601567762; bh=IU5RCgAJ4y7n8QkcyPbnvZryyCJCQq/JFQFHCd9Zass=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From:Subject; b=kopbdJOv1rTzo6MzW43ntwslGe1cMIe+GnXKRx/WWMjd5itUFxcqCeohQ8vT4OnLsdGFnP5DNNLVoOlCqc50+qRE/lt4ruqHayMTgXbH6Ol7d1GynqbcsK7qjyfZt3+3Seoed2LR9qR2QGz9xBNIhhf3X6CB3/ASBvjqk+4SodQCEnwNmERpC2J3Qj0F+KNOaYn+G2h95Si+6e9zq/IVZWF8nqsPRuMOmXqXQj3B5HeRHBoPOSeQ3Fqs08WIejXdUUTgB3ZWC3VQdOq7PMQNEksc97mtzbjvQDbY/ouSpOQ35g/o5ET9u9g3fQh5HWXNHiUMsLP+GbqcrhtgpWuVjg== X-YMail-OSG: .biguMUVM1nYDmw.ll_PWb2dVAyJpoR1t8SXcBvuxwVMVejpBa.wylQuAR_qIaT FiM9_5bYZrMzqimsFsxesBBQG3pDvzXwZfrCTPd3_X9.LJnVw8w8N6arH2eN6.iLPnh3J3YXK6Rw jFtsavn9Zo5wuF4x_4cL52O07zv0hc9WafjLDJpAzgkyUgtIl2BHkvazrWbIbANmiCdLL_Gc8NUD ZvOKp9aoRVG2bl082Fi9gH133Pn6ExDewYikBE.eGFe1IyMlZnEG.UB8f60XZ9eCS5EQN.Yzh.Y1 b...rxH8La.xNKqN_Uu0iiSh15mAOvHmZ1a8m4YaCUwN45nQKsO6FOkGuN7VL01.bZx8S4KMNeLR khEHzHvhTDu8O_YPWUAqRvlynuqligL4Aw2b9pS_Nz21Rvq58vzDGl6v7Kzpvoy7foqP754lKy8X iyFHW8vhl3f5q.UI2uUIaZEyXf1jwQKNdKkr3PFib.WxSvK52up1kAOnUP4ShbMXFHYCCHED9PrF IMl3aadTQbSsnudDJ5rMpXojQ8SYytTbMsukryJeal.eaLqP.xVmi5QStJNx6Qxtq1Fj3lPeU.Z9 T0ieJMCFYGFGKUuHPpTClH_8Fd0KwkB08OwkXryLKNnRniQhuDA3hcVP4nEy2S1jbMW2h7RL06hR CXFtfCLZ6kybPrRaAojzZlUZVAJKmflHwFPZCtELPmjEhLEPdFUpIa383mOXg.86nBTenpTCXWmX 6y7x8bCyY4DzAvwi9dOoqNtOhV9kAZn4iGwU9QTWIaiYnLIVm5agJnYjxMYLwNgLbn45WHEJi0nH yrCx692VTZoxk.1MA.Od2cUs5QdmGrFvst3N1fyAYd Original-Received: from sonic.gate.mail.ne1.yahoo.com by sonic301.consmr.mail.bf2.yahoo.com with HTTP; Thu, 1 Oct 2020 15:56:02 +0000 Original-Received: by smtp402.mail.ir2.yahoo.com (VZM Hermes SMTP Server) with ESMTPA ID d84e08cae95bd11b555061ebcd519eb7; Thu, 01 Oct 2020 15:55:59 +0000 (UTC) Content-Disposition: inline In-Reply-To: <83pn62gj2s.fsf@gnu.org> X-Mailer: WebService/1.1.16718 mail.backend.jedi.jws.acl:role.jedi.acl.token.atz.jws.hermes.aol Apache-HttpAsyncClient/4.1.4 (Java/11.0.7) Received-SPF: pass client-ip=74.6.129.41; envelope-from=spacibba@aol.com; helo=sonic301-2.consmr.mail.bf2.yahoo.com X-detected-operating-system: by eggs.gnu.org: First seen = 2020/10/01 11:55:50 X-ACL-Warn: Detected OS = Linux 3.11 and newer [fuzzy] X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=unavailable autolearn_force=no X-Spam_action: no action 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:256875 Archived-At: On Thu, Oct 01, 2020 at 04:40:59PM +0300, Eli Zaretskii wrote: >> 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. > Oh; you are right. Now that I remember some of that code in the display engine you are totally right. >> 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. > Indeed; that's why I was considering the external library in C. In general it is actually feasible. Sadly the translation from Tandem to C will require some time because it is split with many code mixtures and non of them in C... but if you think is better we could do that (with SOME time). Any way we could wait for the Qiantan implementation and consider some optimizations if you think it worth the effort. >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? > Indeed; If we use an external library; one of the advantages is that we could have both because for the emacs side will be exactly the same. It only received a "list" of changes to implement then a set of external ones. And the network implementation and so on will be more or less the same. IMO the hardest part of this is all the network managing, server and so on... not CRDT is OT implementations. >> 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.