On 1 September 2010 15:14, John Millikin wrote:

[aside] does anybody know how to get a list of what packages somebody's uploaded to Hackage? I think I've updated all mine for the new "text" version dependency, but I'm worried I forgot some.

Unfortunately, no; I've often wished the same thing (not for my packages, but because I could have sworn someone uploaded a package that did something, I remembered the maintainer but not the name of the package...). -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

2010/9/1 Tako Schotanus :

As a Haskell noob I'm curious about this statement, is there something intrinsically wrong with String?

String is just a linked list of Char which are unicode code points; which is probably not the optimal way to store text. For intensive use of text it takes too much memory, and/or it's not fast enough. Sometimes I'd love if I could program using String and the compiler would automatically convert that to Text, or Bytestrings, but of course it's wishful thinking. David.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 09/01/2010 02:44 AM, Ivan Lazar Miljenovic wrote:

On 1 September 2010 16:27, David Virebayre wrote:

...

Sometimes I'd love if I could program using String and the compiler would automatically convert that to Text, or Bytestrings, but of course it's wishful thinking. Well, there's OverloadedStrings for String literals...

But the problem with automagic conversion would be one of encoding for Bytestrings at least.

This reminds me: it would be nice if Text, ByteString, etc. exported their own definitions of "type String". As most users have to import them qualified to avoid collisions with Data.List (and the Prelude?) anyway, this would enable someone to import their desired module as, say, S, then use type S.String and string ops S.foo. Anyone who *did* use them unqualified would have to add (hiding (String)) to their imports, of course. The flip side of this would be a module which contained the definition for String and re-exported Data.List, so that the above S.mumble could work for String as well. (The obvious choice would be Data.String, but that's taken for IsString and of course that would be required to pull this off so it can't just have the list implementation stuffed into it.) -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAkx/FsQACgkQIn7hlCsL25Vk8ACeKco9/IFwGi+8gc+BxSyT3QwY oP8An3oabG1lbXHChShbenEWj9HWEq6Q =PQsO -----END PGP SIGNATURE-----

Hi Kevin, thanks for the pointer, although I was aware of the thread and had followed it quite closely, it was quite interesting. But it never explained if and why String should be avoided, all I read is "test and decide depending on the circumstances", which in itself is good advise, but I'd like to have an idea of the reasons so I can form in idea before actually having to code any benchmarks :) Knowing that String literally is a linked list of Char makes it a lot clearer. I figured that maybe Haskell could be using some more efficient mechanism for Strings internally, only treating it outwardly as a [Char]. But I guess that in a lot of circumstances where you're just working with small pieces of text in non-performance critical code it's perfectly okay to use String. Cheers, -Tako On Wed, Sep 1, 2010 at 08:31, Kevin Jardine wrote:

Hi Tako,

The issues involved with String, ByteString, Text and a few related libraries were discussed at great length recently in this thread:

http://groups.google.com/group/haskell-cafe/browse_thread/thread/52a21cf61ff...

Basically, Chars are 32 bit integers and Strings are represented as a list of Chars.

This is very convenient for small computations but often very inefficient for anything large scale.

The String API is also missing various encoding related features.

Because of the limitations of String, various alternative libraries have been proposed. Text is one important option.

You'll find much more detail on the above referenced thread.

Kevin

...

On Wed, Sep 1, 2010 at 07:14, John Millikin wrote:

...

...

Don't forget, you can always improve the text library yourself. I love to receive patches, requests for improvement, and bug reports.

...

Are there any areas in particular you'd like help with, for either library? I'm happy to assist any effort which will help reduce use of String.

As a Haskell noob I'm curious about this statement, is there something intrinsically wrong with String? Or is it more a performance/resource problem when dealing with large amounts of text for example? (Like having to use StringBuilder in Java if you want to avoid the

On Sep 1, 8:13 am, Tako Schotanus wrote: penalty

...

of repeated String allocations when simply concatenating for example)

Cheers, -Tako

_______________________________________________ Haskell-Cafe mailing list Haskell-C...@haskell.orghttp:// www.haskell.org/mailman/listinfo/haskell-cafe

---

Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Wednesday 01 September 2010 18:15:19, Bryan O'Sullivan wrote:

Hi, Daniel -

Thanks for taking the new code for a test drive!

...

The interesting part is the comparison between text and vanilla String I/O, the difference is smaller than I expected for text-0.8.0.0.

Yes. Much of this is due to the new encoding stuff on Handles in GHC 6.12, which is slow. Its performance wasn't so noticeable when it was only shipping String around, but it's much more visible with Text. It's far slower on a Mac than on Linux, in case that's relevant.

I'm on Linux. I guess that's another point in favour of it:) Do you happen to know why it's slower on a Mac?

...

The performance of text-0.8.0.0 has improved significantly over that of text-0.7.2.1 (for the tested features), the improvement of the replacing algorithm is however not as impressive as that of I/O.

I'd bet you that's mostly because the program is I/O bound, in the sense that it's spending time going through the layers of buffering and translation that now make up a Handle. Any improvement in other code is going to be hard to see because of that.

Maybe. As a rough measure, I took (total time - time for just reading and outputting) for an approximation of the processing (replacing) time. For the first example (Lazy), that yields 0.7.2.1: 0.92s - 0.68s = 0.24s 0.8.0.0: 0.44s - 0.26s = 0.18s, for the fourth 0.7.2.1: 1.23s - 0.68s = 0.55s 0.8.0.0: 0.65s - 0.26s = 0.39s Yes, I know it's very crude, but TIO.readFile file >>= TIO.putStrLn does no less translation than with a replacing in between, or does it? So I tentatively believe most of the difference is spent doing the replacements.

The other major consideration, both for this case and the first one you note, is that the inliner in 6.12 chokes on code that uses stream fusion: it boxes and unboxes vast quantities of state. That kills performance due to both the boxing and unboxing overhead and the increased number of nursery GCs.

I haven't looked at the core, so I take your word for it. I know the behaviour from other situations.

The marvelous new 6.13 inliner does a *much* better job here - that's where I see those 3x performance improvements for free.

That's nice. Maybe I should go get the HEAD before 6.14.1 will be released.

What's *really* bad is the space behaviour.

What are you using to measure that?

+RTS -s and top. The figures I gave were the "total memory in use" of +RTS -s, maximum residency was 20MB (vs. 39 total) for 0.7 and 12MB (vs. 17 total) for 0.8 in the bad tests.

Also, please don't forget to post your benchmark code when you make observations like this,

It's not very interesting, {-# LANGUAGE BangPatterns #-} module Main (main) where import System.Environment (getArgs) import qualified Data.Text.Lazy as T import qualified Data.Text.Lazy.IO as TIO main :: IO () main = do (file : pat : sub : _) <- getArgs let !spat = T.pack pat !ssub = T.pack sub work = T.replace spat ssub TIO.readFile file >>= TIO.putStrLn . work with the obvious changes of imports for the strict Text and the almost obvious changes for the ByteString code.

as that way I can reproduce your measurements and fix problems. I appreciate your help!

I can now say more. Looking at Data.Text.Lazy.replace, replace s d = intercalate d . split s , I also got a space leak with that for BS.Lazy's intercalate and stringsearch's split. Looking at intercalate, intercalate t = concat . (Data.List.intersperse t) , that's where you definitely get a space leak, because intersperse :: a -> [a] -> [a] intersperse _ [] = [] intersperse _ [x] = [x] intersperse sep (x:xs) = x : sep : intersperse sep xs isn't lazy enough. Given the context, it's not hard to see what's wrong here. Before intersperse produces any output, it checks whether the list contains at least two elements (if any). If a is a list-like type, like String, lazy ByteStrings or lazy Text, where the elements of the list are lazily produced one after the other, as is the case for split, each element must be complete before it can be delivered and then consumed. So indeed, replace needs O(index pat) space :( I don't think that fixing Data.List.intersperse will fix your space leak, though. split pat src | null pat = emptyError "split" | isSingleton pat = splitBy (== head pat) src | otherwise = go 0 (indices pat src) src where go _ [] cs = [cs] go !i (x:xs) cs = let h :*: t = splitAtWord (x-i) cs in h : go (x+l) xs (dropWords l t) l = foldlChunks (\a (T.Text _ _ b) -> a + fromIntegral b) 0 pat Using the list of indices of the pattern, split can't deliver anything before the first (next) occurrence of the pattern has been located (or the end of the string reached). Again, that forces O(index pat) space consumption. I don't see how to avoid that without duplicating a large part of indices' logic in a dedicated breaking/splitting function. On a related note, break :: Text -> Text -> (Text, Text) break pat src | null pat = emptyError "break" | otherwise = case indices pat src of [] -> (src, empty) (x:_) -> let h :*: t = splitAtWord x src in (h, t) has the same problem. Cheers, Daniel

On Wed, Sep 1, 2010 at 1:00 PM, Daniel Fischer wrote:

I'm not keen on subscribing to libraries@ to follow the official proposal process, any takers?

I'll take it up.

On Wednesday 08 September 2010 06:44:32, Bryan O'Sullivan wrote:

I have a Replace.hs benchmark in the main text repo, just to be sure we're talking about the same thing.

Grabbed the darcs repo, compiled with the darcs version and also with the installed text package, both exhibit the same behaviour - what I reported before.

Factoring out the time spent on I/O, with GHC HEAD, my replace code takes twice the space and time of that in the stringsearch package.

That's very good. Twice the space is a given for mostly ASCII text, twice the time is okay, I think. My timings are quite different, but that's probably because 6.12.3's inliner doesn't give the full fusion benefit, so it'll improve automatically with the next GHC release.

Given that the space involved is just 121KB maximum residency while processing a 124MB file, I'm not concerned about it.

I wouldn't either.

And the time required isn't a bad place to start from, I think.

By the way, as this implies, I can't reproduce your space behaviour at all.

That's surprising. Have you made sure to replace a pattern which does not occur in the text? Can you reproduce the behaviour with a) Data.List.intersperse instead of the lazier version now used, b) ghc-6.12.* instead of HEAD? Anyway, I would've thought that with split pat src | null pat = emptyError "split" | isSingleton pat = splitBy (== head pat) src | otherwise = go 0 (indices pat src) src where go _ [] cs = [cs] go !i (x:xs) cs = let h :*: t = splitAtWord (x-i) cs in h : go (x+l) xs (dropWords l t) l = foldlChunks (\a (T.Text _ _ b) -> a + fromIntegral b) 0 pat you can't start returning chunks before it's known whether the list of indices is empty, so split would have O(index of pattern) space behaviour. If HEAD manages to make the chunks available before they are complete (before it's known how long they will be), it's even awesomer than I'd have dared to hope. Okay, so I'll have to try HEAD.

...

I can now say more. Looking at Data.Text.Lazy.replace,

replace s d = intercalate d . split s

, I also got a space leak with that for BS.Lazy's intercalate and

stringsearch's split.

How did you observe the space leak? Looking at -hT charted with hp2ps shows me nothing, and the program executes in constant space regardless of input size.

top and +RTS -s. I've attached the -hT graph of a run on a 74.3MB file with a pattern that does not occur. It shows exactly the behaviour I expected from the code of split, pretty constant growth of the heap until about twice the file size is reached, then fast and pretty constant shrinking as the text is output. The graphs are much more interesting if you do replacements of patterns without large gaps between occurrences.