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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
22 messages Options
12
KC
Reply | Threaded
Open this post in threaded view
|

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

KC

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.
Reply | Threaded
Open this post in threaded view
|

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

MigMit
No it's #not.

> On 10 Jul 2016, at 20:44, KC <[hidden email]> 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.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Stefan Monnier
In reply to this post by KC
> 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

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Christopher Allen
In reply to this post by KC
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 <[hidden email]> 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
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Richard A. O'Keefe
In reply to this post by KC


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.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

David Fox-12
In reply to this post by KC
On Sun, Jul 10, 2016 at 11:44 AM, KC <[hidden email]> 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>

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Alex Belanger

That's not just about Haskell, it's C.S. in general.

You're always going to make space and time tradeoffs.

Funny how the same constraints appear in physics; I wonder if it is trying to tell us something...

- nitrix

On Jul 11, 2016 8:54 AM, "David Fox" <[hidden email]> wrote:
On Sun, Jul 10, 2016 at 11:44 AM, KC <[hidden email]> 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>

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Stephen Tetley-2
In reply to this post by David Fox-12
On 11 July 2016 at 13:54, David Fox <[hidden email]> 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...
_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

David Fox-12
On Mon, Jul 11, 2016 at 7:28 AM, Stephen Tetley <[hidden email]> wrote:
On 11 July 2016 at 13:54, David Fox <[hidden email]> 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.​


_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Bardur Arantsson-2
In reply to this post by Stephen Tetley-2
On 07/11/2016 04:28 PM, Stephen Tetley wrote:

> On 11 July 2016 at 13:54, David Fox <[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

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

David Feuer

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" <[hidden email]> wrote:
On 07/11/2016 04:28 PM, Stephen Tetley wrote:
> On 11 July 2016 at 13:54, David Fox <[hidden email]> 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.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Bardur Arantsson-2
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.


_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Bardur Arantsson-2
In reply to this post by David Fox-12
On 07/11/2016 02:54 PM, David Fox wrote:

> On Sun, Jul 10, 2016 at 11:44 AM, KC <[hidden email]
> <mailto:[hidden email]>> 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)?


_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

David Fox-12


On Mon, Jul 11, 2016 at 2:09 PM, Bardur Arantsson <[hidden email]> wrote:
On 07/11/2016 02:54 PM, David Fox wrote:
> On Sun, Jul 10, 2016 at 11:44 AM, KC <[hidden email]
> <mailto:[hidden email]>> 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.​
 

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Bardur Arantsson-2
On 07/12/2016 12:22 AM, David Fox wrote:

>
>
> On Mon, Jul 11, 2016 at 2:09 PM, Bardur Arantsson <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     On 07/11/2016 02:54 PM, David Fox wrote:
>     > On Sun, Jul 10, 2016 at 11:44 AM, KC <[hidden email] <mailto:[hidden email]>
>     > <mailto:[hidden email] <mailto:[hidden email]>>> 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.)

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Richard A. O'Keefe
In reply to this post by David Fox-12
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#.

_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Will Yager
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 <[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

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

Richard A. O'Keefe


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.


_______________________________________________
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.
Reply | Threaded
Open this post in threaded view
|

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

Branimir Maksimovic
In reply to this post by Will Yager

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 <[hidden email]> 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.
Reply | Threaded
Open this post in threaded view
|

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

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

ср, 13 июл. 2016 г. в 16:41, Branimir Maksimovic <[hidden email]>:

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 <[hidden email]> 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.

_______________________________________________
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.
12