Ropes: A High-Performance Alternative to Strings
| (require rope) | package: rope |
Based on the paper by Boehm, Atkinson, and Plass.
1 Miscellaneous Notes
A rope is a balanced binary tree where each leaf contains a raw chunk of individual elements. A chunk can be any sequential data structure, such as a string or a vector.
Although ropes are typically used as a drop-in replacement for strings or byte strings, where the elements are likely to have a fixed size, this is not a hard requirement. For example, it is possible to create ropes whose elements are lexical tokens that carry the text of the words they represent. This extra precision allows parsers to determine not only the offset of a token, but also the offset of an individual character in its underlying text.
2 Appendix
contracted vs uncontracted
generic calls are macros (for performance)
clean and precise error messages
for overlap=?, default looping algorithem is generally faster on strings or collections of Racket-level (i.e., boxed) values, but can be astonishingly slower (e.g., than slicing) for special types (e.g., bytes - contiguous, unboxed C arrays).
there will be no "gen:" generics API because run-time dispatch is too slow. We will need good docs on how to use the included macro-based generic APIs instead.