|
Yes, OT has a time complexity of O(1) for processing a local change. 1. I think you are confusing the cost of OT with the cost of implementing standard editor operations (i.e, insert/delete characters/strings/object). Editors have existed before collaborative editing came along and folks have figured out how to build it to be performant using ropes, piece table or many other data structures -- optimized for their own set of needs (more discussions here https://news.ycombinator.com/item?id=15381886). OT is orthogonal to the choice of design/implementation of the underlying editor, but interacts with the editor through an abstract-data-type, which in the case of text editing is a character sequence. Lumping the cost of OT with the cost of editor operations is a common mistake I see. 2. Hashtables in RGA are used only for processing remote operations. Comparing local to remote processing cost is like comparing apples and oranges. Elaborations from the article, on page 9:
We should further highlight that the use of position-based operations does not imply the text sequence
must be implemented as an array of characters. The positional reference to the text sequence could
be (and has commonly been) implemented in numerous data structures, such as an array of
characters, the linked-list structures, the buffer-gap structures, and piece tables, etc. [8,69]. .. and on page 11:
In OT-based co-editors, for example, the choice of strategies (e.g. what native data structures or operation models to use) for implementing efficient document editing is completely left to application designers, and the support for real-time collaboration is layered above and interfaced with the editing application’s exposed abstract-data-type, which is, in the case of text editing, a sequence of characters [8, 21] |