Is the #functional programming paradigm antithetical to efficient strings? #Haskell
Is the #functional programming paradigm antithetical to efficient strings? #Haskell -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey
No it's #not.
On 10 Jul 2016, at 20:44, KC <kc1956@gmail.com> wrote:
Is the #functional programming paradigm antithetical to efficient strings? #Haskell
-- --
Sent from an expensive device which will be obsolete in a few months! :D
Casey
_______________________________________________ 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.
Is the #functional programming paradigm antithetical to efficient strings?
Why would it be? Most string operations in non-low-level languages are naturally functional (e.g. my local Emacs build makes strings immutable and 99% of Elisp packages don't even notice the difference). Stefan
Even if it was, you could use a mutable container of runes if there was something that didn't really gel with the algorithm you wanted. IME, the slicing based API of ByteString and Vector has been great when I've needed efficient string code. http://hackage.haskell.org/package/bytestring-trie is a great library if you're doing stuff like dictionaries of strings. There's not really any limitations in Haskell as to what you can do, it just doesn't let you lie about what it is you're up to. On Sun, Jul 10, 2016 at 1:44 PM, KC <kc1956@gmail.com> wrote:
Is the #functional programming paradigm antithetical to efficient strings? #Haskell
-- --
Sent from an expensive device which will be obsolete in a few months! :D
Casey
_______________________________________________ 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.
-- Chris Allen Currently working on http://haskellbook.com
On 11/07/16 6:44 AM, KC wrote:
Is the #functional programming paradigm antithetical to efficient strings? #Haskell
What on earth does "efficient strings" mean? To the extent that I can extract any meaning from that, the answer is "no, obviously not". The functional programming paradigm includes languages like ML, which has always had packed-array-of-byte strings and corresponding contiguous-slice-of-shared-packed-array-of-byte substrings, and languages where the default implementation is a singly-linked list with one cell per code. What is "efficient" is a matter of what you are *doing* with the strings. An important consideration these days is that the old idea of a mutable array with one element per character (which was never the only way to implement strings) is a very poor fit for Unicode.
On Sun, Jul 10, 2016 at 11:44 AM, KC <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). 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. 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. So is functional programming antithetical to efficient strings? In theory maybe not, but I would love to see some hard evidence. </rant>
On 11 July 2016 at 13:54, David Fox <dsf@seereason.com> 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...
On Mon, Jul 11, 2016 at 7:28 AM, Stephen Tetley <stephen.tetley@gmail.com> wrote:
On 11 July 2016 at 13:54, David Fox <dsf@seereason.com> 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.
On 07/11/2016 04:28 PM, Stephen Tetley wrote:
On 11 July 2016 at 13:54, David Fox <dsf@seereason.com> 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,
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" <spam@scientician.net> wrote:
On 07/11/2016 04:28 PM, Stephen Tetley wrote:
On 11 July 2016 at 13:54, David Fox <dsf@seereason.com> 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 10:07 PM, David Feuer wrote:
Edward Kmett did some work with things he called "ropes" https://hackage..haskell.org/package/rope <https://hackage.haskell.org/package/rope> that can be efficient for some byte string manipulations. There may be other good choices.
Yup, sometimes you want ropes (e.g. editors may benefit), other times you want VLists, etc. etc.
On 07/11/2016 02:54 PM, David Fox wrote:
On Sun, Jul 10, 2016 at 11:44 AM, KC <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)?
On Mon, Jul 11, 2016 at 2:09 PM, Bardur Arantsson <spam@scientician.net> wrote:
On 07/11/2016 02:54 PM, David Fox wrote:
On Sun, Jul 10, 2016 at 11:44 AM, KC <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.
On 07/12/2016 12:22 AM, David Fox wrote:
On Mon, Jul 11, 2016 at 2:09 PM, Bardur Arantsson <spam@scientician.net <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 <kc1956@gmail.com <mailto:kc1956@gmail.com> > <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.)
Please do NOT confuse "the functional programming paradigm" with Haskell. "The imperative programming paradigm" is not identical to C, is it? The following measurements were made on a 3.2 GHz core i5 Mac running OSX 10.11 with clang (Apple LLVM version 7.3.0). Making an array with 10,000,000 pointers to "Hello world" in optimised C took 32 milliseconds and concatenating them to make a new 110,000,000 character string took 134 milliseconds. Using the built-in 'string' type in C++, no array, just hr += hw, took 260 milliseconds optimised, 460 milliseconds unoptimised. The maximum String size in SML/NJ is 2^24 characters, which is unfortunately too small for this problem. Taking 1,000,000 strings and concatenating them took 61.4 milliseconds, so presumably if String.maxSize were large enough the ML version would take 614 milliseconds. 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. Having made an array of 10,000,000 'Hello world' strings, concatenating the strings into a single String (a *mutable* packed array of character codes) took 0.50 seconds in Smalltalk (an object-oriented programming language). Concatenating the ten million strings in Java 1.8 using a StringBuilder took 0.84 seconds, very close to the Haskell time. Concatenating 10,000,000 copies of 'Hello world' in Python3 (using StringIO) took 1.312 seconds. Frankly, the Haskell time just doesn't stand out here. In a real program, I'd be trying to avoid string concatenation in *any* language. By the way, one toy microbenchmark by itself tells us NOTHING worth knowing about string efficiency, because there are many many other things we want to do to strings. A colleague of mine who uses C++ for text-heavy applications wouldn't be caught dead using C++ strings. I note that Clean, which in many ways resembles Haskell, has always had packed byte strings. Then of course there are languages like OCaml and F#, where F# uses the same string processing as C#, so F# strings should have the *same* efficiency (whatever that means) as C#.
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 <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.
On 12/07/16 3:36 PM, William Yager wrote:
You picked the single slowest way to do it. No, the way I did it was linear time, making it NOT the slowest way to do it. The point I was making is that the simplest not-totally-stupid way to do it in Haskell isn't actually all that bad compared with other languages.
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 <stdio.h> #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 <ok@cs.otago.ac.nz <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.
Your rust version pushes only 10'000'000 strings from arr into str, doesn't it? ср, 13 июл. 2016 г. в 16:41, Branimir Maksimovic < 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 <stdio.h> #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 <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.
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 <branimir.maksimovic@gmail.com <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 <stdio.h> #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 <ok@cs.otago.ac.nz <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.
Oh, sorry, yes it. чт, 14 июл. 2016 г. в 9:56, Branimir Maksimovic < branimir.maksimovic@gmail.com>:
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 < 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 <stdio.h> #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 <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.
participants (12)
-
Bardur Arantsson -
Branimir Maksimovic -
Christopher Allen -
David Feuer -
David Fox -
Geraldus -
KC -
MigMit -
Richard A. O'Keefe -
Stefan Monnier -
Stephen Tetley -
William Yager