Specializing Ropes for Ruby [pdf]

chrisseaton.com

68 pointschrisseaton3 comments

I'm marginally surprised nobody's used ropes for Ruby previously; this is something that was done in the first few years for all the JS VMs* given it provides pretty sizeable perf gains (because string concatenation is so common), and this seems to show it's true for much Ruby code too.

*: to be pedantic, Carakan never did use ropes, just lazily concatenating strings for some operations.

(And now I wait for someone who worked on this to tell me why they didn't do it sooner. :))

If you prefer the video format, I also gave a talk based on this content at RubyKaigi 2016:

https://www.youtube.com/watch?v=UQnxukip368

To give some context, rstring rep is like an expanded Pascal rep with more metadata. rstrings allow nearly free substrings if string data is immutable. IIRC this is similar to what Java uses for string-table constants (CONSTANT_Utf8_info).

For historical context, a string rep besides ASCIIZ / charZ (NUL-terminated) was dollar-terminated used by DOS.

Pascal would store a byte length at the head of a string to indicate it's length.

Reply on news.ycombinator.com