4 ms·
TruffleRuby is an implementation of Ruby that uses ropes instead of character arrays for strings, if you want to see a modern implementation in practice. It wo
by chrisseaton 6y ago
TruffleRuby is an implementation of Ruby that uses ropes instead of character arrays for strings, if you want to see a modern implementation in practice.
It works brilliantly for mostly string concatenation workloads, like rendering web page templates.
Gets tricky when you decide to flatten it if people are repeatedly mutating single characters or indexing.
Cool thing is that it can provide a char* interface to a rope data structure, in order to support C extensions not expecting ropes.
https://rubybib.org/#menard2018 https://rubybib.org/#menard2018
- chubot 6y agoThis was an interesting paper, and I read over it while thinking about implementing ropes for https://www.oilshell.org/ https://www.oilshell.org/ (which would be a huge change, affecting the entire interpreter, since all shell scripts mostly deal with strings) What surprised me is that Ruby template engines make heavy use of string concatenation? Like 'a' + 'b' ? The generated Ruby fragment from ERB makes heavy use ofstring concatenation, which is generally favorable to ropes. Theright-most graph of Figure 5 shows that TruffleRuby ropes are 9.4× faster than MRI, rendering around 870 000 templates per second. I would have thought the idiom for writing a template engine is to use something like Java's StringBuffer, or the Python pattern of appending immutable strings to a list, and joining them at the end. So you avoid a ton of intermediate strings that way. (And I have written a template engine myself in both Python and JS, and that is the technique I used, and it's plenty fast) Would that technique speed up ERB, or is there something I'm missing? Not to say it's not worthwhile to still do ropes, but it seems like low hanging fruit. ----- Though what turned me off of ropes is that for many workloads, most strings are small. And small strings are often smaller than records of pointers (and they have more locality). If I have a pointer to a string, a start offset, and an end offset, on machines that's 8 + 4 + 4 = 16 bytes, which is already approaching the size of an HTML tag or two. And a GC has to chase that pointer (in my situation), whereas a GC can stop if it's a blob of bytes. Not to say it's not a useful technique of course ... I think it does make sense as an optimization when you have existing workloads to measure, but I was hesistant to do it starting from scratch. ----- somewhat related: Elixir RAM and the Template of Doom https://www.evanmiller.org/elixir-ram-and-the-template-of-doom.html https://www.evanmiller.org/elixir-ram-and-the-template-of-do... (a syscall optimization that goes well with ropes)
- chrisseaton 6y agoI don't think ERB literally does +, I think it does <<, which is exactly the same as the string buffer thing you're suggesting. But doesn't appending to a string buffer still mean copying a lot of bytes as you build up the final string? In ropes you don't need to copy anything, you just create a little node of a couple of words to remember that two strings were joined. Yeah there's non-locality and things like that, but most people are building up strings not reading them. Then you write out the final string - and we have system calls like writev that work with ropes. Finally, remember that if your string is created and used within a single compilation unit remember that rope nodes with disappear with escape-analysis and scalar-replacement-of-aggregates. Helps operations on strings fold and become constant.
- bonzini 6y agoAppending to a string buffer that grows exponentially will copy roughly twice as many bytes as building the result in a buffer that has the exact size. If you have to copy out of the resizable buffer into an exact-size area of memory, that becomes three times.
- kd5bjo 6y agoAlso, once your buffer exceeds the virtual memory page size, those copies turn into page table updates that never touch the string data.
- mpweiher 6y ago> copying a lot of bytes Depends on what you mean by "a lot", doesn't it? Yes, you are going to copy all the bytes in the final result once (at least). But it's hard to see how to avoid that, and no, delegating that task to the kernel doesn't magically/consistently make it faster. > you just create a little node of a couple of words Hmm..."just" creating a "little" node can often be quite expensive on today's machines. And "words" are pretty big, typically 8 bytes per word. > Yeah there's non-locality and things like that Well, non-locality and "things like that" are kind of a biggie, these days. The biggie, actually, most of the time. "...computation is essentially free, because it happens “in the cracks” between data fetch and data store; on a clocked processor, there is little difference in energy consumption between performing an arithmetic operation and performing a no-op." -- Andrew Black in Object-oriented programming: some history, and challenges for the next fifty years
- pmoriarty 6y agoChicken Scheme has a rope egg: http://wiki.call-cc.org/eggref/5/rope http://wiki.call-cc.org/eggref/5/rope
- ibraheemdev 6y agoHey Chris. Completely unrelated question. I've been following your work on truffleruby (it looks pretty awesome btw), and I was wondering what the ultimate goal was? Do you believe truffleruby can eventually become the goto Ruby for Rails developers? Is Shopify going to completely move to truffle and the graalvm?
- deleted 6y ago[deleted]