3 ms·

I’ve done a few implementations of this data structure recently. It’s an essential part of making a high performance CRDT for collaborative text editing. I hav

I’ve done a few implementations of this data structure recently. It’s an essential part of making a high performance CRDT for collaborative text editing. I haven’t found any decent 3rd party order statistic tree online that I can use for CRDTs for 2 reasons: 1. I want my tree to be internally run-length encoded. Ie, each item in my tree represent an adjacent runs of inserted characters in the document. In my tests, this seems to make the data structure about 20x smaller. But it adds complexity - we also need to be able to later split those runs if we discover an insert in the middle of any run. 2. I also need random access. Items have a unique ID, and I need to be able to find any item by looking up its ID. The IDs are just auto incremented integers to make the run length encoding work. You end up with a pretty custom set of data structures, but the result is a system which performs fabulously well in practice. The fastest implementation I know of of this stuff is the Cola crdt library, which is written in 100% safe rust.

yencabulator 2y ago
FYI "run-length encoded" means compressing repetitions. "123 repeats of the character 'x'" would be RLE. You seem to be talking about keeping a tree-of-strings instead of tree-of-characters, to decrease the overhead. https://en.wikipedia.org/wiki/Run-length_encoding https://en.wikipedia.org/wiki/Run-length_encoding
- o11c 2y ago
  It's almost like a RangeMap, of which there are at least 3 notable variations: * The basic RangeMap, where a range of adjacent keys all map to the same value * The computed RangeMap, where a range of adjacent keys all map to adjacent values (common for e.g. case-conversion of Unicode, can also come up for IP addresses) * The DenseMap, where a range of adjacent keys map to arbitrary values, but use an array for memory optimization. The first two actually can be made to work for string-like keys. The last is only possible for integer-like keys; use a carefully chosen trie design for string-like keys.
- josephg 2y ago
  It’s not “123 repeats of the character x”, and it’s not a tree of characters either. The sibling comment is right. The data is crdt metadata. If you type a series of characters, each character has some fields. In my case, this is an id (autoincrementing integer), and origin-left and origin-right (the id of the items immediately to the left and right when the character was typed). If a user types a continuous run of 100 characters, we don’t need to actually store all 100 IDs - since they’re just, say, the numbers 1000-1100 in order. The origin-right for all items will be the same. And we don’t need to store the origin-left for each one. The first item in the run has an unguessable left origin (say, 600). But the rest will have an origin-left equal to the id of the previous item. Ie, 1000, 1001, 1002, and so on up to 1099. Naively you’d need 300 integers to store the metadata for 100 contiguous items. But if you’re clever, a run of 100 items only needs to store a start id, length (or end id), the origin-left of the first item in the run and the common origin-right for all the items in the run. That’s just 4 integers, which I store in a single fixed sized entry in the btree. Because of how humans actually type, this compression makes a big difference in practice. In code, I have a pair of rust traits for Splitable and Mergable which define functions like len(), can_append(), append(), truncate(), split() and so on. Then I have a generic order statistic tree implementation which stores Splitable & Mergable items. Run-length encoding is the best term I’ve seen for this kind of packing. It’s definitely not a tree of strings - the document text itself is stored in a completely separate data structure. (In my case, a skip list). (Credit for the run length encoding goes to Kevin Jahns, author of Yjs.)
  - yencabulator 2y ago
    I would recommend not using a well-established term for something that doesn't actually match the well-established term..
    - josephg 2y ago
      I’m encoding a set of runs. Each run has a value component and a length. The only difference from traditional RLE is that, when expanded, the values are computed from the base+offset rather than repeated. Eg the IDs expand to 1000,1001,1002,… instead of just repeating; 1000,1000,1000,… What would you call that?

yencabulator 2y ago

FYI "run-length encoded" means compressing repetitions. "123 repeats of the character 'x'" would be RLE. You seem to be talking about keeping a tree-of-strings instead of tree-of-characters, to decrease the overhead. https://en.wikipedia.org/wiki/Run-length_encoding https://en.wikipedia.org/wiki/Run-length_encoding

o11c 2y ago
It's almost like a RangeMap, of which there are at least 3 notable variations: * The basic RangeMap, where a range of adjacent keys all map to the same value * The computed RangeMap, where a range of adjacent keys all map to adjacent values (common for e.g. case-conversion of Unicode, can also come up for IP addresses) * The DenseMap, where a range of adjacent keys map to arbitrary values, but use an array for memory optimization. The first two actually can be made to work for string-like keys. The last is only possible for integer-like keys; use a carefully chosen trie design for string-like keys.
josephg 2y ago
It’s not “123 repeats of the character x”, and it’s not a tree of characters either. The sibling comment is right. The data is crdt metadata. If you type a series of characters, each character has some fields. In my case, this is an id (autoincrementing integer), and origin-left and origin-right (the id of the items immediately to the left and right when the character was typed). If a user types a continuous run of 100 characters, we don’t need to actually store all 100 IDs - since they’re just, say, the numbers 1000-1100 in order. The origin-right for all items will be the same. And we don’t need to store the origin-left for each one. The first item in the run has an unguessable left origin (say, 600). But the rest will have an origin-left equal to the id of the previous item. Ie, 1000, 1001, 1002, and so on up to 1099. Naively you’d need 300 integers to store the metadata for 100 contiguous items. But if you’re clever, a run of 100 items only needs to store a start id, length (or end id), the origin-left of the first item in the run and the common origin-right for all the items in the run. That’s just 4 integers, which I store in a single fixed sized entry in the btree. Because of how humans actually type, this compression makes a big difference in practice. In code, I have a pair of rust traits for Splitable and Mergable which define functions like len(), can_append(), append(), truncate(), split() and so on. Then I have a generic order statistic tree implementation which stores Splitable & Mergable items. Run-length encoding is the best term I’ve seen for this kind of packing. It’s definitely not a tree of strings - the document text itself is stored in a completely separate data structure. (In my case, a skip list). (Credit for the run length encoding goes to Kevin Jahns, author of Yjs.)
- yencabulator 2y ago
  I would recommend not using a well-established term for something that doesn't actually match the well-established term..
  - josephg 2y ago
    I’m encoding a set of runs. Each run has a value component and a length. The only difference from traditional RLE is that, when expanded, the values are computed from the base+offset rather than repeated. Eg the IDs expand to 1000,1001,1002,… instead of just repeating; 1000,1000,1000,… What would you call that?