On Mon, Jul 11, 2016 at 7:28 AM, Stephen Tetley wrote:

On 11 July 2016 at 13:54, David Fox wrote:

...

When I mentioned some of this, I was told "different data structures for different purposes", which sort of makes sense, but honestly if Haskell

is a

...

language where you have to sit down and choose a representation every time you want to build some text, I get a bit discouraged.

Don't C# and Java have StringBuilder classes (different to their regular String types) for this as well?

Maybe imperative OO is also antithetical to efficient strings...

​Probably.​

Edward Kmett did some work with things he called "ropes" https://hackage.haskell.org/package/rope that can be efficient for some byte string manipulations. There may be other good choices. On Jul 11, 2016 1:42 PM, "Bardur Arantsson" wrote:

On 07/11/2016 04:28 PM, Stephen Tetley wrote:

...

On 11 July 2016 at 13:54, David Fox wrote:

...

When I mentioned some of this, I was told "different data structures for different purposes", which sort of makes sense, but honestly if Haskell

is a

...

language where you have to sit down and choose a representation every time you want to build some text, I get a bit discouraged.

Don't C# and Java have StringBuilder classes (different to their regular String types) for this as well?

Yes, they do.

If you just naively do

String s = ""; for (int i = 0; i < 1000000; i++) { s = s + "hello"; }

in Java you'll also get terrible performance (O(n^2)) as opposed to the equivalent code using StringBuilder which would be O(n). This does not change if you use e.g. Text/ByteString/Vector in Haskell.

In Haskell, I could certainly imagine List[Char] being more performant than copying huge chunks of memory over and over... even though List traversal *is* generally slow.

(Of course the actual performance depends on lots and lots of specifics.)

...

Maybe imperative OO is also antithetical to efficient strings...

Bad algorithms and data structures are antithetical to efficient strings :).

Regards,

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

On 07/11/2016 02:54 PM, David Fox wrote:

On Sun, Jul 10, 2016 at 11:44 AM, KC mailto:kc1956@gmail.com> wrote:

Is the #functional programming paradigm antithetical to efficient strings? #Haskell

​I can certainly see how it might seem so. Our main string representation​ uses about 10 times more memory than seems necessary, and is relatively fast, though probably not compared to C. Recently I spent some time looking into how to reduce this memory overhead, and I modified the pretty library (https://github.com/ddssff/pretty/tree/textdetails) so it could use any type that was an instance of ListLike and StringLike (https://github.com/JohnLato/listlike https://github..com/JohnLato/listlike). Then I tried the UnitLargeDoc test with several different data types. This just concatenates a list of ten million "Hello" strings. Using String this happens in about 5 seconds. Using strict or lazy Text it immediately blew the stack. When I increased the stack size to over 1GB it took minutes to complete. When I used the Data.Text.Lazy.Builder type instead it took about 30 seconds to complete. Results with utf8 encoded ByteStrings were siimilar.

Did you try similar code on Java/C# (or whatever)?

On 07/12/2016 12:22 AM, David Fox wrote:

On Mon, Jul 11, 2016 at 2:09 PM, Bardur Arantsson mailto:spam@scientician.net> wrote:

On 07/11/2016 02:54 PM, David Fox wrote: > On Sun, Jul 10, 2016 at 11:44 AM, KC mailto:kc1956@gmail.com > mailto:kc1956@gmail.com>> wrote: > > Is the #functional programming paradigm antithetical to efficient > strings? #Haskell > > ​I can certainly see how it might seem so. Our main string > representation​ uses about 10 times more memory than seems necessary, > and is relatively fast, though probably not compared to C. Recently I > spent some time looking into how to reduce this memory overhead, and I > modified the pretty library > (https://github.com/ddssff/pretty/tree/textdetails) so it could use any > type that was an instance of ListLike and StringLike > (https://github.com/JohnLato/listlike > https://github..com/JohnLato/listlike). Then I tried the UnitLargeDoc > test with several different data types. This just concatenates a list > of ten million "Hello" strings. Using String this happens in about 5 > seconds. Using strict or lazy Text it immediately blew the stack.. When > I increased the stack size to over 1GB it took minutes to complete. > When I used the Data.Text.Lazy.Builder type instead it took about 30 > seconds to complete. Results with utf8 encoded ByteStrings were siimilar. >

Did you try similar code on Java/C# (or whatever)?

​I did not.​

Do try it -- it's an educational experience! (Even in C++, Rust or whatever takes your fancy.) (... and at this point I'm left wondering whether KC is just trolling.)

You picked the single slowest way to do it. Please see https://gist.github.com/wyager/df063ad4edd9a9c8b0ab762c91a79894 All times are on my Intel Atom Macbook. Compiled with -O3, no other options. Using Lazy Bytestrings (either through the Builder interface or plain old concatenation) is about 7-7.5 times faster than string concatenation so on your computer it should take about 0.12 seconds. In other words, faster than C. This is my usual experience with lazy bytestrings; due to their optimization for cache size, they are extremely fast with almost no effort. They often out-perform "fast" array operations in C due to fusion and cache coherency. I will note that if you want to do exactly what C does (often with only slightly different assembly output), you can often achieve this with unboxed vectors (mutable or immutable, depending on your application). --Will On Mon, Jul 11, 2016 at 10:24 PM, Richard A. O'Keefe wrote:

Making a list of "Hello world" 10,000,000 times and then concatenating that list to produce a single String took 0.87 seconds (start program to end program) in Haskell.

rust (no need for array but anyway) [bmaxa@manjaro rust]$ time ./append 10000000 took 0.064016791 110000000 took 0.13466229 real 0m0.204s user 0m0.167s sys 0m0.033s haskell (your fastest version) [bmaxa@manjaro rust]$ time ./concat "Done" real 0m0.224s user 0m0.220s sys 0m0.000s c++ (no array) [bmaxa@manjaro rust]$ time ./a.out real 0m0.115s user 0m0.100s sys 0m0.013s rust: use std::time::*; fn main() { let mut arr=Vec::new(); arr.reserve(10_000_000); let start = Instant::now(); for _ in 0 .. 10_000_000 { arr.push("hello world"); } let end = start.elapsed(); let diff = (end.as_secs()*1000000000 + end.subsec_nanos() as u64) as f64/1000000000.; println!("{} took {}",arr.len(),diff); let mut str = String::new(); str.reserve(110_000_000); let start = Instant::now(); for i in arr { str .push_str(i); } let end = start.elapsed(); let diff = (end.as_secs()*1000000000 + end.subsec_nanos() as u64) as f64/1000000000.; println!("{} took {}",str.len(),diff); } c++: #include #include <string> int main() { std::string tmp; tmp.reserve(110000000); for (int i=0;i<10000000;i++) { tmp += "hello world"; } } Model name: Intel(R) Core(TM) i3-5005U CPU @ 2.00GHz On 07/12/2016 05:36 AM, William Yager wrote:

You picked the single slowest way to do it. Please see https://gist.github.com/wyager/df063ad4edd9a9c8b0ab762c91a79894

All times are on my Intel Atom Macbook. Compiled with -O3, no other options.

Using Lazy Bytestrings (either through the Builder interface or plain old concatenation) is about 7-7.5 times faster than string concatenation so on your computer it should take about 0.12 seconds. In other words, faster than C.

This is my usual experience with lazy bytestrings; due to their optimization for cache size, they are extremely fast with almost no effort. They often out-perform "fast" array operations in C due to fusion and cache coherency.

I will note that if you want to do exactly what C does (often with only slightly different assembly output), you can often achieve this with unboxed vectors (mutable or immutable, depending on your application).

--Will

On Mon, Jul 11, 2016 at 10:24 PM, Richard A. O'Keefe mailto:ok@cs.otago.ac.nz> wrote:

Making a list of "Hello world" 10,000,000 times and then concatenating that list to produce a single String took 0.87 seconds (start program to end program) in Haskell.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

Isn't that how suppose to be? 10000000 "hello worlds" ? On 07/14/2016 06:42 AM, Geraldus wrote:

Your rust version pushes only 10'000'000 strings from arr into str, doesn't it?

ср, 13 июл. 2016 г. в 16:41, Branimir Maksimovic mailto:branimir.maksimovic@gmail.com>:

rust (no need for array but anyway)

[bmaxa@manjaro rust]$ time ./append 10000000 took 0.064016791 110000000 took 0.13466229

real 0m0.204s user 0m0.167s sys 0m0.033s

haskell (your fastest version)

[bmaxa@manjaro rust]$ time ./concat "Done"

real 0m0.224s user 0m0.220s sys 0m0.000s

c++ (no array)

[bmaxa@manjaro rust]$ time ./a.out

real 0m0.115s user 0m0.100s sys 0m0.013s

rust:

use std::time::*;

fn main() { let mut arr=Vec::new(); arr.reserve(10_000_000); let start = Instant::now(); for _ in 0 .. 10_000_000 { arr.push("hello world"); } let end = start.elapsed(); let diff = (end.as_secs()*1000000000 + end.subsec_nanos() as u64) as f64/1000000000.; println!("{} took {}",arr.len(),diff); let mut str = String::new(); str.reserve(110_000_000); let start = Instant::now(); for i in arr { str .push_str(i); } let end = start.elapsed(); let diff = (end.as_secs()*1000000000 + end.subsec_nanos() as u64) as f64/1000000000.; println!("{} took {}",str.len(),diff); }

c++:

#include #include <string>

int main() { std::string tmp; tmp.reserve(110000000); for (int i=0;i<10000000;i++) { tmp += "hello world"; } }

Model name: Intel(R) Core(TM) i3-5005U CPU @ 2.00GHz

On 07/12/2016 05:36 AM, William Yager wrote:

...

You picked the single slowest way to do it. Please see https://gist.github.com/wyager/df063ad4edd9a9c8b0ab762c91a79894

All times are on my Intel Atom Macbook. Compiled with -O3, no other options.

Using Lazy Bytestrings (either through the Builder interface or plain old concatenation) is about 7-7.5 times faster than string concatenation so on your computer it should take about 0.12 seconds. In other words, faster than C.

This is my usual experience with lazy bytestrings; due to their optimization for cache size, they are extremely fast with almost no effort. They often out-perform "fast" array operations in C due to fusion and cache coherency.

I will note that if you want to do exactly what C does (often with only slightly different assembly output), you can often achieve this with unboxed vectors (mutable or immutable, depending on your application).

--Will

On Mon, Jul 11, 2016 at 10:24 PM, Richard A. O'Keefe mailto:ok@cs.otago.ac.nz> wrote:

Making a list of "Hello world" 10,000,000 times and then concatenating that list to produce a single String took 0.87 seconds (start program to end program) in Haskell.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.

_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.