Hacker News Reader

Comment by chrisseaton | Hacker News Reader

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.

View on HN

> But doesn't appending to a string buffer still mean copying a lot of bytes as you build up the final string?

Look at the article and see for yourself. They do the string-builder measurement and show results. It's in figure 5.

The "GEOMETRIC" approach to string building from small fragments is slightly slightly faster than the rope approach. That's where characters are copied to a contiguous buffer, and the buffer is reallocated by doubling in size whenever it is filled.

The slowest by far is the "UNBUFFERED" [cord] version, which creates a new cord node for each append, instead of copying the characters.

"BUFFERED" [cord] is quite good. It's still a bit slower than "GEOMETRIC", but good enough.

In a nutshell, the paper shows that copying bytes when the number of bytes at a time is small is essential to all fast methods of string building.

That's because creating nodes and changing pointers is slower than copying contiguous bytes, up to some number of bytes. That number is probably larger now than it was when the paper was written due to modern memory architecture.

Hm that's interesting, actually the paper is sort of wishy-washy about the contribution? It doesn't claim that ropes are faster.

It claims that they make systems "more robust". I think they basically mean that certain apps that use long strings are less likely to run out of memory.

I guess my response is that I don't think Python or JS really need native ropes, even for string heavy workloads like templating: https://news.ycombinator.com/item?id=24960806

(Also, I would expect penalties of pointer chasing and thus ropes to be much more severe in 2020 vs. 1995, like maybe 10x more?)

We claim that the traditional implementations ofstrings, and often the supported functionality, are not well suited to such general-purpose use.They should be confined to applications with specific, and unusual, performance requirements.We present ‘ropes’ or ‘heavyweight’ strings as an alternative that, in our experience leads to systems that are more robust, both in functionality and in performance.

Conclusion:

It is not clear whether the implementation we suggested above is in any senseoptimal. However, it performs sufficiently well for our purposes, and sufficientlywell that for most purposes it is preferred over traditional ‘flat’ string representations.Our experience has been that it results in software that is noticeably more robust,particularly in that it scales correctly to unexpectedly large inputs.

edit: I guess they are making a computational complexity claim then? But again I would say it's a common idiom in Python and JS to append to a list and join(). At least now it is, maybe in 1995 programmers weren't used to that idiom.

Right, << and StringBuffer is still less efficient, at least in terms of the asymptotic number of bytes copied.

I guess what I'm saying is that if you "properly" write a template engine, there should be no advantage to ropes at all.

Rather than a tree of non-copied fragments in the language runtime (ropes), you can simply create an array of non-copied fragments in the language itself.

Following the template engine I wrote in Python and JS:

- Fragments come from two places: holes and consts. holes come from variables, and consts are figured out at template compile time (e.g. which happens when the web server starts, and shouldn't be benchmarked).

- Fragments are never copied. They are simply appended to a big array of fragments. The template engine is a recursive tree walk interpreter that always appends to an array.

This is even true for a feature like #include. Some template engines may do the "right" thing for local fragments, but the copying may sneak back in for #include. But if you care, it's easy to handle #include in a consistent way.

So if you use that "obvious" architecture, then I claim there should be no advantage to ropes. But I guess that's not what happens in practice!

(Well, seeing some sibling comments about copying being faster, at least the claim is that this architecture should be as fast or as slow as ropes! :) But yeah I think ERB is probably doing something different and even worse, which is not surprising.)

> I guess what I'm saying is that if you "properly" write a template engine, there should be no advantage to ropes at all.

If you're building up your string as an array of strings, and you want to pass that to some existing code that expects a full string (like the web framework you're using) then you're going to need to flatten it to create the final full string.

Ropes don't need to do that. They still have an advantage.

Also... the implementation doing things for you so you don't have to manually optimise your code is kind of the point of an optimisation. We can always say 'but I could do this manually' to any optimisation, couldn't we?

Yeah it's a moot point either way, because ERB is like that... but

- This wasn't an optimization, it was literally the first thing I thought of when I wrote my first and only template engine 10 years ago. And I have seen plenty of others do it; it is "obvious".

The code is the exact same length as the string version, so I don't consider it an optimization.

- Python's WSGI accepts an iterable of strings for the body. From a cursory reading, looks like Ruby's rack does too:

https://en.wikipedia.org/wiki/Rack_(web_server_interface)#Ex...

e.g. it's ["Hello, World"] and not "Hello, World" (I don't know Ruby that well though)

Maybe frameworks mess it up in the middle...

> 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

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.

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.

Also, once your buffer exceeds the virtual memory page size, those copies turn into page table updates that never touch the string data.

Reply on news.ycombinator.com