Back to Questions
1.2k
views4
comments
Conversion from char array to string takes too long
f#

Why in the following code

1
2
3
4
5
6
7
8
9
10

            

override this.ReadToEnd() = 

            let buffer = Array.create 4096 ' '
            match this.Read(buffer, 0, buffer |> Array.length) with
            | 0 -> ""
            | _ as l -> 
                let s = new System.String(buffer.[..l-1])
                s + this.ReadToEnd()

building the string out of array takes over 20 sec?

the value of l here is 4096

.

Your code is very inefficient, here is something that I think is better (have not compiled it):

1
2
3
4
5
6
7
8
9
10
11
12

override this.ReadToEnd() = 
    let sb = new System.Text.StringBuilder()
    let len = 4096
    let buffer = Array.create len ' '
    let mutable numRead = this.Read(buffer, 0, len)
    while numRead <> 0 do
        if numRead = len then
            sb.Append(new System.String(buffer)) |> ignore
        else
            sb.Append(new System.String(buffer.[..numRead-1])) |> ignore
        numRead <- this.Read(buffer, 0, len)
    sb.ToString()

Specifically

  • don't clone the array with a.[..len-1] when it's the whole thing
  • don't use '+' to accumulate a string in a loop, that's O(N^2) - use a StringBuilder, that's O(N)
  • don't use the call stack, use a loop (or tail recursion)
By on 5/22/2009 2:29 PM ()

Your code is very inefficient, here is something that I think is better (have not compiled it):

  • don't clone the array with a.[..len-1] when it's the whole thing
  • don't use '+' to accumulate a string in a loop, that's O(N^2) - use a StringBuilder, that's O(N)
  • don't use the call stack, use a loop (or tail recursion)

I agree, the code is less than perfect, that's why I am looking at it to begin with, but

1) - I thought the 'slice' op gives you a 'view' over the existing array rather than cloning it - apparently I was wrong

2) - no argument here it shall be changed

3) - isn't the way the this.Read is called a tail recursion? - oh I just realized - it is not.. - or is it?

also even it is cloning the array - why cloning an array of 4000 items takes this long? is there something else happening on top of copying the values?

By on 5/22/2009 2:43 PM ()

Some good learning bits here...

1) the value of a slice expression has type 'a array (which means it must be a clone- all arrays are 'concrete')

3) it's not tail recursion, since after the call you still have the "s+<result>" to execute

I've no idea what is 'actually taking that long' (not sure what/how you measured), but if you were reading a huge stream, all this extra allocation could have made the garbage collector go crazy or started thrashing system memory (just guesses).

By on 5/22/2009 2:54 PM ()

Some good learning bits here...

I've no idea what is 'actually taking that long' (not sure what/how you measured), but if you were reading a huge stream, all this extra allocation could have made the garbage collector go crazy or started thrashing system memory (just guesses).

Wow... I do now - The way I tried to get a feel on what takes what was that I just stepped through the code in the debugger using F10 while looking at the timer. Not a precise way to measure anything, but you can get an idea, and then take a closer look - or so I thought. Cloning of the array of 4k characters does take over 20 sec - while stepping through the code in the debugger. If you just run it nothing of the sort is happening. I had some other problems there and now as I fixed them the entire thing flies through in under a sec. I am still gonna fix it as you suggested, but cloning never was an issue here.

By on 5/26/2009 5:18 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper