Re: [Haskell-cafe] The question of ByteString

Tim Chevalier wrote:

On 11/2/07, Andrew Coppin wrote:

...

Somewhat related to the discussions about Haskell's performance...

String. ByteString. Do we really need both? Can one replace the other?

You can't get rid of "String" because a String is just a [Char]. Requiring the element type of a list to be "anything except Char" would be silly. In addition, it's useful to have a String that you can apply arbitrary list operations to when performance isn't a concern (i.e., most of the time). Finally, removing String would break existing code.

...

Why is one faster? Can't we make *all* lists this fast? [insert further variations here]

ByteString takes advantage of the fact that the elements are, well, bytes. The operations are optimized for reading large amounts of text, but not necessarily for other applications. Lists are a parameterized type, so the elements of a list are pointers to arbitrary data. So that's why the same tricks as ByteString don't apply to general lists. That isn't to say that there aren't possible optimizations which haven't yet been dreamed of.

Well OK, maybe I was a little vague. Let me be a bit more specific... If you do text processing using ByteString rather than String, you get dramatically better performance in time and space. For me, this raises a number of questions: 1. Why do I have to type "ByteString" in my code? Why isn't the compiler automatically performing this optimisation for me? (I.e., is there some observable property that is changed? Currently the answer is yes: the ByteString interface only provides "trancated" Unicode characters. But, in principle, that could be changed.) 2. ByteString makes text strings faster. But what about other kinds of collections? Can't we do something similar to them that makes them go faster? As I understand it, ByteString is faster due to several factors. First of all, it's stricter. Secondly, it's an "unboxed" structure (so you eliminate layers of indirection and there's less GC load). Third, it's implemented as an array that looks like a linked list. Given how ubiquitous lists are in Haskell, "array that looks like a linked list" sounds like one seriously useful data type! Yet ByteString seems to be the only implementation of this concept - and only for lists on unboxed bytes. (Not even unboxed Word16 or anything else, *only* Word8.) If I understand this correctly, a ByteString is actually a linked list of large array chunks. (This presumably yields fastER random access than a plain linked list?) Also, it seems to be possible to create a new array which is merely a subrange of an existing one, without any copying; the standard array API doesn't seem to provide this, yet it sounds damn useful. These are the things I'm thinking about. Is there some deep theoretical reason why things are the way they are? Or is it merely that nobody has yet had time to make something better? ByteString solves the problem of text strings (and raw binary data) very nicely, it's just a pitty we can't apply some of that know-how more widely...