On Sun, 2010-04-11 at 16:11 +0400, Mukhamed Karanashev wrote:

Hi, James. Because "String" is represented by the "[Char]", each element of String is allocated individually. ByteString represents a string in a single array and hasn't overhead for allocating each char.

Hmm. I read somewhere that GHC optimizes it to handle it more as char * if possible. Could anyone clarify it? Regards

Am Sonntag 11 April 2010 15:29:38 schrieb Stephen Tetley:

Hi James

There's a paper describing the implementation of ByteStrings here:

http://www.cse.unsw.edu.au/~dons/papers/CSL06.html http://www.cse.unsw.edu.au/~dons/papers/fusion.pdf

For my own work, I generally need short immutable strings and haven't found ByteStrings compelling,

ByteStrings shine for long strings. When you're using long strings, ByteStrings almost certainly are *much* faster (utf8-ByteStrings are probably significantly slower, but should still beat [Char] comfortably). I've found ByteStrings better than [Char] when dealing with short strings only for a few things (e.g. as keys of Maps, ByteStrings tend to be better [at least if using ByteStrings there doesn't introduce too much packing and unpacking], things like edit-distance are faster on ByteStrings; UArray Int Char is slower than ByteString [in my measurements] for these tasks, but it can also be used for characters > toEnum 255 and isn't too much slower). Other things [see below] were faster for short [Char] than for short ByteStrings. When dealing with short strings, in my experience there are rarely compelling reasons to choose one over the other.

though the results presented in the above suggest [Char] is better at nothing

[Char] is (far) better at sorting short Strings; it often is better for map and filter.

and worse at many things.

[Char]-IO is abysmally slow in comparison, [Char] uses much more memory, random access is horrible for lists.

[Hmm - insert emoticon here]

Best wishes

Stephen

Am Sonntag 11 April 2010 17:15:22 schrieb Stephen Tetley:

On 11 April 2010 15:42, Daniel Fischer wrote: [SNIP]

...

When dealing with short strings, in my experience there are rarely compelling reasons to choose one over the other.

Hi Daniel

Thanks - I was slightly surprised at the results in the paper because the 'cons' test for was equal, I thought bytestrings have to do a bit more work for a 'cons' - looking at the code lazy bytestring uses one constructor and a bit of C memory poking, which is the C memory poking more than I'd expect the [Char] version to do.

Well, I guess it depends on what actually happens with fusion (a single cons doesn't take significant time for either). If repeated conses lead to a chain of one-element chunks, I'd expect that to be significantly slower than [Char], but if it's rewritten to - allocate a new chunk, - write from end and decrement offset counter, it shouldn't be slower.

The only 'determinant' I've found for choosing which type for short strings is if I'm using a library that forces one or the other on me,

Sure, that's pretty compelling - as long as you don't need two libraries with different choices :)

otherwise I'm swayed by the simplicity of [Char].

Best wishes

Stephen

Am Sonntag 11 April 2010 15:31:52 schrieb Maciej Piechotka:

On Sun, 2010-04-11 at 12:07 +0100, James Fisher wrote:

...

Hi,

After working through a few Haskell tutorials, I've come across numerous recommendations to use the Data.ByteString library rather than standard [Char], for reasons of "performance". I'm having trouble swallowing this -- presumably the standard String is default for good reasons.

But performance is none of those reasons. The choice to make String a synonym for [Char] instead of a specialised datatype allows you to easily manipulate strings with the plethora of list- processing functions from the standard libraries. However, that means some things can't be fast and there's a significant space overhead for string handling.

...

Nothing has answered this question: in what case is it better to use [Char]?

In most cases you need an actuall String and it is not time-critical I believe. ByteString is... well string of bytes not char - you have no idea whether they are encoded as utf-8, ucs-2, ascii, iso-8859-1 (or as jpeg ;) ). If you want the next char you don't know how many bytes you need to read (1? 2? 3? depends on contents?).

And - sorting short strings - for using map or filter, [Char] is often superior

String ([Char]) have defined representation - while read/write function might incorrect encode/decode it (up to GHC 6.12 System.IO had assumes ascii encoding IIRC on read) it is their error.

...

Could anyone point me to a good resource showing the differences between how [Char] and ByteString are implemented, and giving good a heuristic for me to decide which is better in any one case?

ByteString is pointer with offset and length. Lazy ByteString is a linked list of ByteStrings (with additional condition that none of inner ByteStrings are empty).

And it's a head-strict list, not the usual lazy Haskell list.

In theory String is [Char] i.e. [a] i.e.

data [a] = [] | a:[a]

In other words it is linked list of characters. That, for long strings, may be inefficient (because of cache, O(n) on random access and necessity of checking for errors while evaluating further[1]).

I heard somewhere that actual implementations optimizes it to arrays when it is possible (i.e. can be detected and does not messes with non-strict semantics). However I don't know if it is true.

I've never heard of that before, so I'm skeptical.

I *guess* that in most cases the overhead on I/O will be sufficiently great to make the difference insignificant. However:

? which difference? Try reading large files. Count the lines or something else, as long as it's simple. The speed difference between ByteString-IO and [Char]-IO is enormous. When you do something more complicated the difference in IO-speed may become insignificant. On the other hand, when you're appending a lot of short lines to a file one by one, there's a good chance that [Char]-IO is actually faster.

- If you need exact byte representation - for example for compression, digital signatures etc. you need ByteString - If you need to operate on text rather then bytes use String or specialized data structures as Data.Text & co. - If you don't care about performance and need easy of use (pattern matching etc.) use String. - If you have no special requirements than you can ByteString

While some languages (for example C, Python, Ruby) mixes the text and it's representation I guess it is not always the best way. String in such separation is an text while ByteString is a binary representation of something (can be text, picture, compresses data etc.).

...

Best,

James Fisher

Regards

[1] However the O(n) access time and checking of errors are still introduced by decoding string. So if you need UTF-8 you will still get the O(n) access time ;)

It might then be a good idea to use a UArray Int Char if you need repeated random access.

Am Sonntag 11 April 2010 18:04:14 schrieb Maciej Piechotka:

On Sun, 2010-04-11 at 17:17 +0200, Daniel Fischer wrote:

...

...

I *guess* that in most cases the overhead on I/O will be

sufficiently

...

great to make the difference insignificant. However:

? which difference?

I meant: difference between ByteString-IO and [Char]-IO or which difference?

...

Try reading large files.

Well - while large files are not not-important IIRC most files are small (< 4 KiB) - at least on *nix file systems (at least that's the core 'idea' of reiserfs/reiser4 filesystems).

Well, sometimes one has to process large files even though most are small. If the processing itself is simple, IO-speed is important then.

I guess that for large strings something like text (I think I mentioned it) is better

Unless you know you only have to deal with one-byte characters, when plain ByteStrings are the simplest and fastest method. But those are special cases, in general I agree.

...

Count the lines or something else, as long as it's simple. The speed difference between ByteString-IO and [Char]-IO is enormous. When you do something more complicated the difference in IO-speed may become insignificant.

Hmm. As newline is a single-byte character in most encodings it is believable.

You can measure it yourself :) cat-ing together a few copies of /usr/share/dict/words should give a large enough file.

However what is the difference in counting chars (not bytes - chars)? I wouldn't be surprise is difference was smaller.

Nor would I. In fact I'd be surprised if it wasn't smaller. [see below] This example was meant to illustrate the difference in IO-speed, so an extremely simple processing was appropriate. The combination of doing IO and processing is something different. If you're doing complicated things, IO time has a good chance to become negligible.

Of course: - I haven't done any tests. I guessed (which I written)

I just have done a test. Input file: "big.txt" from Norvig's spelling checker (6488666 bytes, no characters outside latin1 range) and the same with ('\n':map toEnum [256 .. 10000] ++ "\n") appended. Code: main = A.readFile "big.txt" >>= print . B.length where (A,B) is a suitable combination of - Data.ByteString[.Lazy][.Char8][.UTF8] - Data.Text[.IO] - Prelude Times: Data.ByteString[.Lazy]: 0.00s Data.ByteString.UTF8: 0.14s Prelude: 0.21s Data.ByteString.Lazy.UTF8: 0.56s Data.Text: 0.66s Of course Data.ByteString didn't count characters but bytes, so for the modified file, those printed larger numbers than the others (well, it's BYTEString, isn't it?). It's a little unfair, though, as the ByteString[.Lazy] variants don't need to look at each individual byte, so I also let them and Prelude.String count newlines to see how fast they can inspect each character/byte, BS[.Lazy]: 0.02s Prelude: 0.23s both take 0.02s to inspect each item. To summarise: * ByteString-IO is blazingly fast, since all it has to do is get a sequence of bytes from disk into memory. * [Char]-IO is much slower because it has to transform the sequence of bytes to individual characters as they come. * counting utf-8 encoded characters in a ByteString is - unsurprisingly - slow. I'm a bit surprised *how* slow it is for lazy ByteStrings. (Caveat: I've no idea whether Data.ByteString.UTF8 would suffer from more multi-byte characters to the point where String becomes faster. My guess is no, not for single traversal. For multiple traversal, String has to identify each individual character only once, while BS.UTF8 must do it each time, so then String may be faster.) * Data.Text isn't very fast for that one.

- It wasn't written what is the typical case

Aren't there several quite different typical cases? One fairly typical case is big ASCII or latin1 files (e.g. fasta files, numerical data). For those, usually ByteString is by far the best choice. Another fairly typical case is *text* processing, possibly with text in different scripts (latin, hebrew, kanji, ...). Depending on what you want to do (and the encoding), any of Prelude.String, Data.Text and Data.ByteString[.Lazy].UTF8 may be a good choice, vanilla ByteStrings probably aren't. String and Text also have the advantage that you aren't tied to utf-8. Choose your datatype according to your problem, not one size fits all.

- What is 'significant' difference

Depends of course. For a task performed once, who cares whether it takes one second or three? One hour or three, however, is a significant difference (assuming approximately equal times to write the code). Sometimes 10% difference in performance is important, sometimes a factor of 10 isn't. The point is that you should be aware of the performance differences when making your choice.

Regards

Cheers, Daniel

Am Montag 12 April 2010 01:01:36 schrieb Maciej Piechotka:

On Sun, 2010-04-11 at 22:07 +0200, Daniel Fischer wrote:

...

Am Sonntag 11 April 2010 18:04:14 schrieb Maciej Piechotka:

...

Of course: - I haven't done any tests. I guessed (which I written)

I just have done a test. Input file: "big.txt" from Norvig's spelling checker (6488666 bytes, no characters outside latin1 range) and the same with ('\n':map toEnum [256 .. 10000] ++ "\n") appended.

Converted myspell polish dictonary (a few % of non-ascii chars) added twice (6531616 bytes).

Optimized:

Length - ByteString: 0.01223 s Length - Lazy ByteString: 0.00328 s Length - String: 0.15474 s Length - UTF8 ByteString: 0.19945 s Length - UTF8 Lazy ByteString: 0.30123 s Length - Text: 0.70438 s Length - Lazy Text: 0.62137 s

String seems to be fastest correct

For me, strict UTF8 ByteString was faster than String, but as for you, both played in the same league.

Searching - ByteString: 0.04604 s Searching - ByteString: 0.04424 s Searching - String: 0.18178 s Searching - UTF8 ByteString: 0.32606 s Searching - UTF8 Lazy ByteString: 0.42984 s Searching - Text: 0.26599 s Searching - Lazy Text: 0.37320 s

While ByteString is clear winner String is actually good compared to others.

The ByteStrings should be faster if you use count instead of foldl' find 0. Anyway, where applicable, ByteStrings are much faster for certain tasks - I suspect they wouldn't do so well if one had a (map function . filter predicate) on the input. I'm surprised here that a) searching takes so much longer than calculating the length for BS.UTF8 b) searching is *much faster* than calculating the length for Text c) both, UTF8 BS and Text, are slower than String

Searching ą - String: 0.18557 s Searching ą - UTF8 ByteString: 0.32752 s Searching ą - UTF8 Lazy ByteString: 0.43811 s Searching ą - Text: 0.28401 s Searching ą - Lazy Text: 0.37612

String is fastest? Hmmm.

Not much difference to the previous.

Compiled:

Compiled means no optimisations? That's a *bad* idea for ByteStrings and Text. You only get the fusion magic with optimisations turned on, without, well...

Length - ByteString: 0.00861 s Length - Lazy ByteString: 0.00409 s Length - String: 0.16059 s Length - UTF8 ByteString: 0.20165 s Length - UTF8 Lazy ByteString: 0.31885 s Length - Text: 0.70891 s Length - Lazy Text: 0.65553 s

ByteString is also clear winner but String once again wins in 'correct' section.

Searching - ByteString: 1.27414 s Searching - ByteString: 1.27303 s Searching - String: 0.56831 s Searching - UTF8 ByteString: 0.68742 s Searching - UTF8 Lazy ByteString: 0.75883 s Searching - Text: 1.16121 s Searching - Lazy Text: 1.76678 s

I mean... what? I may be doing something wrong

Yes, using ByteString and Text without optimisations :)

PS. Tests were repeated a few times and each gave similar results.

...

...

- It wasn't written what is the typical case

Aren't there several quite different typical cases? One fairly typical case is big ASCII or latin1 files (e.g. fasta files, numerical data). For those, usually ByteString is by far the best choice.

On the other hand - if you load the numerical data it is likely that: - It will have some labels. The labels can happen to need non-ascii or non-latin elements

Possible. But label-free formats of n columns of numbers are fairly common (and easier to handle).

- Biggest time will be spent on operating on numbers then strings.

In that case, it is of course less important which type you use for IO.

...

Another fairly typical case is *text* processing, possibly with text in different scripts (latin, hebrew, kanji, ...). Depending on what you want to do (and the encoding), any of Prelude.String, Data.Text and Data.ByteString[.Lazy].UTF8 may be a good choice, vanilla ByteStrings probably aren't. String and Text also have the advantage that you aren't tied to utf-8.

Choose your datatype according to your problem, not one size fits all.

My measurements seems to prefer String but they are probably wrong.

Yes, measurements always are wrong ;) More seriously, you measured a couple of tasks on one system. For different tasks and other systems, different results should be expected. The best choice depends on the task. For SPOJ problems, ByteStrings are what you'll want. For text processing, probably not. If you want to find a pattern in a long ASCII string, however, they likely are.

Regards

Cheers