From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Qiantan Hong Newsgroups: gmane.emacs.devel Subject: Re: Question collaborative editing. Date: Wed, 30 Sep 2020 00:47:59 +0000 Message-ID: <185C953C-EB4B-4078-9D42-8700E72A0B67@mit.edu> References: <20200925002239.fgg3vw2nylltcoyp@Ergus> <219042AC-556D-48CC-8920-82D9BF2BD3AA@aol.com> <3A81FB67-A558-4281-8285-CDD9B01033E3@posteo.net> <1C949FC9-6023-467E-99EC-75D57B08AFB0@gnu.support> <20200929124513.fd745r2txowwbiir@Ergus> <87blho7af9.fsf@red-bean.com> <20200929215849.zg4wzytbrwx2b7ih@Ergus> <84B86B7C-81F0-42DF-894C-BF577E4B3D6E@mit.edu> <20200930001333.g6b3mqa4mdsoxiue@Ergus> Mime-Version: 1.0 Content-Type: multipart/signed; boundary="Apple-Mail=_2A7EE18D-A046-468F-9B05-197EDBA71364"; protocol="application/pkcs7-signature"; micalg=sha-256 Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="30018"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Fermin , Jean Louis , Noam Postavsky , Emacs developers , Karl Fogel , Stefan Monnier To: Ergus Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Wed Sep 30 02:49:02 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 1kNQIo-0007gq-7a for ged-emacs-devel@m.gmane-mx.org; Wed, 30 Sep 2020 02:49:02 +0200 Original-Received: from localhost ([::1]:33060 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kNQIn-0006Qn-Ay for ged-emacs-devel@m.gmane-mx.org; Tue, 29 Sep 2020 20:49:01 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:53600) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kNQHv-0005hv-DD for emacs-devel@gnu.org; Tue, 29 Sep 2020 20:48:07 -0400 Original-Received: from outgoing-exchange-5.mit.edu ([18.9.28.59]:34144) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kNQHt-0001WY-2T for emacs-devel@gnu.org; Tue, 29 Sep 2020 20:48:06 -0400 Original-Received: from w92exedge3.exchange.mit.edu (W92EXEDGE3.EXCHANGE.MIT.EDU [18.7.73.15]) by outgoing-exchange-5.mit.edu (8.14.7/8.12.4) with ESMTP id 08U0lxCi028155; Tue, 29 Sep 2020 20:48:00 -0400 Original-Received: from w92expo16.exchange.mit.edu (18.7.74.70) by w92exedge3.exchange.mit.edu (18.7.73.15) with Microsoft SMTP Server (TLS) id 15.0.1293.2; Tue, 29 Sep 2020 20:47:22 -0400 Original-Received: from oc11expo16.exchange.mit.edu (18.9.4.47) by w92expo16.exchange.mit.edu (18.7.74.70) with Microsoft SMTP Server (TLS) id 15.0.1365.1; Tue, 29 Sep 2020 20:47:59 -0400 Original-Received: from oc11expo16.exchange.mit.edu ([18.9.4.47]) by oc11expo16.exchange.mit.edu ([18.9.4.47]) with mapi id 15.00.1365.000; Tue, 29 Sep 2020 20:47:59 -0400 Thread-Topic: Question collaborative editing. Thread-Index: AQHWkA+RtV3K1wr9B0aFczVHqkD+n6lzGC2+gAByx1WAA75ZgIABUIuAgAAtCoCAAKrvgIAEEd+AgAGGOACAABFAAIAAe9OAgABIs4CAAA5xVYAAjDuAgAAchYCAAAkggIAACZ+A In-Reply-To: <20200930001333.g6b3mqa4mdsoxiue@Ergus> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: yes x-ms-exchange-messagesentrepresentingtype: 1 x-ms-exchange-transport-fromentityheader: Hosted x-originating-ip: [18.18.245.17] Received-SPF: pass client-ip=18.9.28.59; envelope-from=qhong@mit.edu; helo=outgoing-exchange-5.mit.edu X-detected-operating-system: by eggs.gnu.org: First seen = 2020/09/29 19:41:06 X-ACL-Warn: Detected OS = Windows 7 (Websense crawler) X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham 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:256738 Archived-At: --Apple-Mail=_2A7EE18D-A046-468F-9B05-197EDBA71364 Content-Type: multipart/alternative; boundary="Apple-Mail=_1D949709-8A88-46C6-9AF9-B0F354E5BD77" --Apple-Mail=_1D949709-8A88-46C6-9AF9-B0F354E5BD77 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 > I would be concerned about the performance (but I am paranoid about > Emacs performance anyway so don't worry for that). AFAIR emacs buffers > are stored in a contiguous way (I may be wrong) and in that case the > search with CRDT may be expensive. At least as it was explained here = (in > the optimization section): >=20 > https://conclave-team.github.io/conclave-site/ >=20 > Unless some extra optimizations are implemented of course. Yes, I=E2=80=99m also concerning that, but nobody knows without trying = it out. At least in principle, text-property-search-* and *-property-change are C primitives and should be really fast. Also, there=E2=80=99s = caching trick used in Yjs described here=20 https://github.com/yjs/yjs/blob/main/INTERNALS.md#item-storage = On the other hand the text-property/gap-array data structure in emacs seems to save us from using double linked list, since the total order is just reflected in the continuous buffer. In any case I=E2=80=99m afraid its possible to do it for normal size = buffer but it won=E2=80=99t scale for really large buffers =E2=80=94 I imagine = when buffer is large enough, the cost of even roaming around the buffer (possibly using the position cache) to look for place to insert will be unacceptable, because moving in gap array takes copying cost proportional to moving distance (I might be wrong)=E2=80=A6 But I guess let=E2=80=99s assume people are not going to collaborative = edit some 10MB log file.= --Apple-Mail=_1D949709-8A88-46C6-9AF9-B0F354E5BD77 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8
I would be concerned about the performance (but I am paranoid = about
Emacs performance anyway so don't worry for that). = AFAIR emacs buffers
are stored in a contiguous way (I may = be wrong) and in that case the
search with CRDT may be = expensive. At least as it was explained here (in
the = optimization section):

https://conclave-team.github.io/conclave-site/

Unless some extra optimizations are = implemented of course.
Yes, I=E2=80=99m also = concerning that, but nobody knows without trying it
out. = At least in principle, text-property-search-* and *-property-change
are C primitives and should be really fast. Also, there=E2=80=99= s caching trick
used in Yjs described here 
https://github.com/yjs/yjs/blob/main/INTERNALS.md#item-storage<= /a>

On the other = hand the text-property/gap-array data structure in
emacs seems to save us from using double linked list, = since
the total order is just reflected in the = continuous buffer.

In any case I=E2=80=99m afraid its possible to do it for = normal size buffer
but it won=E2=80=99t scale for = really large buffers =E2=80=94 I imagine when buffer
is large enough, the cost of even roaming around the = buffer
(possibly using the position cache) to look = for place to insert
will be unacceptable, because = moving in gap array takes copying
cost proportional = to moving distance (I might be wrong)=E2=80=A6
But = I guess let=E2=80=99s assume people are not going to collaborative = edit
some 10MB log file.
= --Apple-Mail=_1D949709-8A88-46C6-9AF9-B0F354E5BD77-- --Apple-Mail=_2A7EE18D-A046-468F-9B05-197EDBA71364 Content-Disposition: attachment; filename="smime.p7s" Content-Type: application/pkcs7-signature; name="smime.p7s" Content-Transfer-Encoding: base64 MIAGCSqGSIb3DQEHAqCAMIACAQExDzANBglghkgBZQMEAgEFADCABgkqhkiG9w0BBwEAAKCCA70w ggO5MIIDIqADAgECAhAaql39NsO1qLVjkS2hl517MA0GCSqGSIb3DQEBCwUAMGwxCzAJBgNVBAYT AlVTMRYwFAYDVQQIEw1NYXNzYWNodXNldHRzMS4wLAYDVQQKEyVNYXNzYWNodXNldHRzIEluc3Rp dHV0ZSBvZiBUZWNobm9sb2d5MRUwEwYDVQQLEwxDbGllbnQgQ0EgdjEwHhcNMjAwODAzMDEyNDIz WhcNMjEwODAxMDEyNDIzWjCBoTELMAkGA1UEBhMCVVMxFjAUBgNVBAgTDU1hc3NhY2h1c2V0dHMx LjAsBgNVBAoTJU1hc3NhY2h1c2V0dHMgSW5zdGl0dXRlIG9mIFRlY2hub2xvZ3kxFTATBgNVBAsT DENsaWVudCBDQSB2MTEVMBMGA1UEAxMMUWlhbnRhbiBIb25nMRwwGgYJKoZIhvcNAQkBFg1xaG9u Z0BNSVQuRURVMIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAylUlEQdK4BSXKzoGh6As CKN/TpLmC0kjhPdxUKMj1/86Xl6GDCla4h95uISDOWVAKdu3cIlA8m9zRLT2jNEIkt1DVpXP6c9h y8RRyfJm0qlrvr6tsHi5AmO4Li6s2dEGaTxbakPL6vEn7ZYr86t5orq56nubki77Z8ZvRv9/fWdF bF/YBNGDayLNk0NbXIEQdCHiz1l+bxfw+GHHRmdOge3MKWSg463+GGMdxtLQ61AbtR2vm47FIJBt c0X6ptcInWUg4Nf/9vSNGl6KvREvfbEWKCT6TfL5ncIFlitf6ZWKue2PZ4ULFfIQ3/7EsEk03xxr S7sTOy7e2dbPboe/WwIDAQABo4GhMIGeMAkGA1UdEwQCMAAwEQYJYIZIAYb4QgEBBAQDAgWgMB0G A1UdJQQWMBQGCCsGAQUFBwMEBggrBgEFBQcDAjALBgNVHQ8EBAMCBeAwHQYDVR0OBBYEFDeb9Jlj XSm+y0CD872IhzRDIGv1MDMGA1UdHwQsMCowKKAmoCSGImh0dHA6Ly9jYS5taXQuZWR1L2NhL21p dGNsaWVudC5jcmwwDQYJKoZIhvcNAQELBQADgYEApBTx4tBbD5rQ+bNGd/Z3OBV07qFsm5QHNg0+ 6lxJ3j7q5zMMq35o6y5cBIhcFG6t+MFqJIdERZ3EprDturyqozQsIBMHFnqh+iZcMg0uQyssEqKZ hrzIdw8GuY4Z6jNewdGy5mwwG9yjpEbzWWgdofSM5rnezZz7EvCQu9ilt1sxggNDMIIDPwIBATCB gDBsMQswCQYDVQQGEwJVUzEWMBQGA1UECBMNTWFzc2FjaHVzZXR0czEuMCwGA1UEChMlTWFzc2Fj aHVzZXR0cyBJbnN0aXR1dGUgb2YgVGVjaG5vbG9neTEVMBMGA1UECxMMQ2xpZW50IENBIHYxAhAa ql39NsO1qLVjkS2hl517MA0GCWCGSAFlAwQCAQUAoIIBkzAYBgkqhkiG9w0BCQMxCwYJKoZIhvcN AQcBMBwGCSqGSIb3DQEJBTEPFw0yMDA5MzAwMDQ3NTlaMC8GCSqGSIb3DQEJBDEiBCDSFqDMy0eB HvD1WjAn89jffcJ8vC6NGlNB9zma835uSjCBkQYJKwYBBAGCNxAEMYGDMIGAMGwxCzAJBgNVBAYT AlVTMRYwFAYDVQQIEw1NYXNzYWNodXNldHRzMS4wLAYDVQQKEyVNYXNzYWNodXNldHRzIEluc3Rp dHV0ZSBvZiBUZWNobm9sb2d5MRUwEwYDVQQLEwxDbGllbnQgQ0EgdjECEBqqXf02w7WotWORLaGX nXswgZMGCyqGSIb3DQEJEAILMYGDoIGAMGwxCzAJBgNVBAYTAlVTMRYwFAYDVQQIEw1NYXNzYWNo dXNldHRzMS4wLAYDVQQKEyVNYXNzYWNodXNldHRzIEluc3RpdHV0ZSBvZiBUZWNobm9sb2d5MRUw EwYDVQQLEwxDbGllbnQgQ0EgdjECEBqqXf02w7WotWORLaGXnXswDQYJKoZIhvcNAQEBBQAEggEA wmsiBhFib0lLczHy3A6CoUjo/tFWLdthflkvJF1MaXZWIiw7Fp5vYzA691tLLz+8/0NIs6eMlDRF NXoKF011TqHDhAJBBEgdWw9m684K0WA0ve1xpcVpDYG02B81gJWXn8k+3oo6u1q8qMEfNNqQ6Je9 fOoXqDE3m2hdLIRgT24GPrJE9anTKm4wYHbfrJStq8tmW2cge5FLHXqOZz4jNuOHO/pQWh3VgvSL QDpSjG8EtJ1ft7/AmD0IEuyq3Fz/8rvLRZs/NLVm43YcJeEDUH/UhqoZHHIEfo3h2s0fhoz4KkF7 vFVhFSKMlX6DsUJF1wrvV+mOfR/nj1Qm/c48OAAAAAAAAA== --Apple-Mail=_2A7EE18D-A046-468F-9B05-197EDBA71364--