Hacker News Reader

Comment by seliopou | Hacker News Reader

The original line was something like this:

  acc = "";
  for (var i = 0; i < strings.length; i++) {
      acc += strings[i]
  }

The new version is something like this:

  strings.join("")

The second version can pre-allocate a string and copy characters into that string under the hood. The first version has to allocate a new string and recopy the characters on every iteration.

View on HN

Even if the buffers were vanilla Strings, and there were no pre-allocation, the patch would still have fixed the quadratic-runtime problem. Consider that, for vanilla Strings, the buffer ops are implemented like so:

    buf_append bufOps = (++)
    buf_concat bufOps = concat

Since (++) has a running time that's linear in the length of its left argument, you want to treat it as a right-associative operator to prevent quadratic runtime when joining a bunch of strings.

But, going back to the patch in question, the original code was effectively this:

    foldr (flip (++)) [] strs

Since flip had been applied to (++), the resulting operator you now want to treat as left associative to avoid quadratic blow-up. The code, however, uses the right-associative fold, foldr, to join the list of strings str.

The patch fixes this problem by replacing the code with the equivalent code

    concat (reverse strs)

And how is concat defined in the libraries? Looking at the source [1], it's

    concat = foldr (++) []

Thus the fix is basically

    foldr (++) [] (reverse strs).

This version reverses strs, at linear-time cost, to be able to apply the normal, unflipped (++) with a right-associative fold and thus avoid the dreaded quadratic blow-up.

[1] http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...

EDITED TO ADD: Also, if you knew the buffers were vanilla Strings, you could even eliminate the reverse overhead since

    foldr op z xs == foldl (flip op) z (reverse xs)

for all finite lists xs. Thus you could flip (++) and use foldl instead of foldr to get an efficient implementation like this:

    foldl (flip (++)) [] strs

Nice explanation. I'm surprised that no one so far mentioned a cool trick for getting around this using a different way to define mappend as function composition, to make sure ++ is applied in the right order, since it's from LYAH (scroll to end of the linked chapter):

http://learnyouahaskell.com/for-a-few-monads-more#writer

I recall when I studied algorithms and data structures, but just swapping to using references/pointers instead of copying memory, I could speed up my algorithms ridiculously. Correct me if I am wrong. "Small" things like these (as we just saw) can be really beneficial!

As an aside, immutability (ie purity) in Haskell allows refercences everywhere, and thus less copying. (They call it `sharing' in Haskell land.)

It's worth noting, though, that immutability doesn't always mean less copying. Immutable arrays, where the entire array must be copied with the change of one element, are an example of that. And by extension, hash tables, etc. Of course there are lots of tricks that can be employed to get around this, to a degree.

Yes. The right data structure for the right job.

If your array only has one future---ie there are no references to the unchanged array around---you can re-use the old array. That means you get to mutate in place but still pretend you have immutability.

>Immutable arrays, where the entire array must be copied with the change of one element, are an example of that

That is not how modern persistent data structures are implemented. Please do not talk about immutability as if it necessarily means having a naive implementation like this.

Like I said there are tricks to get around it. I was referring to a C-style array. I think it's still accurate to say that immutability does not always mean less copying.

"tricks to get around it" if by that you mean non-naive data structures that you're supposed to use in order to make immutability efficient yes.

Egregious mischaracterization.

Said "tricks" are an entire branch of research in CS.

As a fellow Clojurist, I agree with the substance of what you're saying here but wish you could express it in a more friendly manner. Both your comments essentially say "you're wrong" without educating or adding value. I don't feel that reflects well on the Clojure community, and I'd like us to do better.

Your tone suggests that you think I don't understand what you're saying (which perhaps I wouldn't, since you succeeded only in telling me I was wrong and failed to actually explain "how modern persistent data structures are implemented" -- as if they were all implemented the same way). Your last sentence suggests that you don't think I know that efficient immutable data structures are an active area of computer science research. Both assumptions are incorrect.

Now, I realize that in my original post, I might have given the wrong impression. I thought that by my second post I was being clear enough, but perhaps I wasn't. Let's try take three:

Immutable data structures do not necessarily guarantee less copying, or necessarily imply a performance gain. A data structure which does not lend itself well to immutability, such as a C-style array, can lead to very inefficient code when used in an immutable fashion. The C-style array or a variation thereof is also the default in most current languages, including Java, Python, C++, Ruby, and many others, so this is hardly a thing of the past. It's important to be aware of the performance characteristics of the data structures one is using, respective to the way in which they are used.

No, you'd have to resort to tricks in order to have a C-style array and encounter this problem; if you just use the default stuff, you get data structures that work great with immutability.

> Immutable arrays, where the entire array must be copied with the change of one element, are an example of that.

Only in a naive implementation. Clojure, for example, has a persistent vector that only requires O(log32 n) copying, which grows so slowly as to be effectively O(1).

See: http://hypirion.com/musings/understanding-persistent-vector-...

I wonder if there's something different about Haskell that makes "less copying" more attractive?

In the C++ world, libstdc++ strings have copy-on-write semantics, which (as far as I heard) turned out to be terrible because you have to do reference counting instead, and with multithreading it requires atomic operations, which is slower than copying for small strings.

How is the original (the for loop that you mentioned) O(n^2)? Isn't that O(n)? Isn't acc += strings[i] a O(1) operation?

not if you have to reallocate space for storing acc on each iteration

Each time strings[i] is added to acc, it may require reallocating entire acc to new memory location with more memory for the concatenated string.

But strings.length is O(n), and you have to run it n times.

No, it is not.

With the naive representation of a string as a list of characters [Char], it is. The only way to get to the end of the list is to recursively take the tail of the string (see the source at http://hackage.haskell.org/package/base-4.6.0.1/docs/src/GHC...).

There's alternative representations with different trade offs, such as Data.Text

Heh... but I was referring to the example seliopou gave, which appears to be in JavaScript, and strings is [String] rather than [Char]. I think the analogy might cause more confusion than clarification.

`acc` is assumed immutable, so it has to be copied entirely on each concatenation. Copying a string is an O(n) operation.

Reply on news.ycombinator.com