4 ms·

This 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 b

by chubot 6y ago

This 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 ago
I 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 ago
  Appending 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 ago
    Also, 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
  - chrisseaton 6y ago
    Yes lots of caveats... but it works for Ruby in practice, often getting 10x on template rendering workloads. Particularly, you 'actually...' me about how fetch and store dominates... but we're not storing anything into existing memory! To concatenate strings we only create new nodes and refer to the old nodes. You don't even need to read what's in the existing nodes! The essential fast-path of building up a template is write-only with bump-allocation into the extremely well-managed TLAB. No reading required. That's why it works so well. Yes traversing the tree means writing it out is a little slower, but that's one small part at the end, with good pre-fetching opportunities.

by chubot 6y ago

chrisseaton 6y ago

I 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 ago
Appending 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 ago
  Also, 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
- chrisseaton 6y ago
  Yes lots of caveats... but it works for Ruby in practice, often getting 10x on template rendering workloads. Particularly, you 'actually...' me about how fetch and store dominates... but we're not storing anything into existing memory! To concatenate strings we only create new nodes and refer to the old nodes. You don't even need to read what's in the existing nodes! The essential fast-path of building up a template is write-only with bump-allocation into the extremely well-managed TLAB. No reading required. That's why it works so well. Yes traversing the tree means writing it out is a little slower, but that's one small part at the end, with good pre-fetching opportunities.