Back to Questions
1.7k
views9
comments
Optimizing for speed
f#

Hello,

I'm porting some c++ code I wrote for the Netflix competition a while back in order to try and learn F#.

let lr = 0.001

let k = 0.02

let f = 9

// c & m are always of length f + 1

let update(c: float[], m: float[], err: float) =

for i = 0 to f do

let ci = c.[i]

let mi = m.[i]

c.[i] <- ci + (lr * (err * mi - k * ci))

m.[i] <- mi + (lr * (err * ci - k * mi))

The update function gets called from inside another loop in a different function ~100million times, which takes about 18s when f=9. About 80% of the processing time is spent in the "update" function.

Anyone see a way of improving the performance of this function in F#?

.

Doing large scale SVD in F# is not efficient, not efficient in C# either. You can consider

1. Use P/Invoke, build your C++ SVD as native dll and use P/Invoke in F#. A tutorial here:
[link:fdatamining.blogspot.com]

2. Use stochastic gradient decedent for SVD. You can refer to Yehuda Koren's winning papers.

3. SGD could also be paralleled.

I am interested how slow is your F# version compared to C++'s.

By on 5/4/2010 10:27 PM ()

I apologize for answering a question with a question but why are there lightbulbs in your sample code? :-) Must be some combination of characters that gives you that--but which combo?

By on 5/4/2010 4:27 PM ()

One super simple thing to try is to change your loop limits to 

1

for i = 0 to c.Length-1

. As I understand it, the CLR JIT compilation has some special case logic for array updates so that this should avoid the bounds checks on reading and writing c.[ i]. Unfortunately, I believe that there will still be a bounds check on each access to m.[ i].

By on 5/1/2010 7:35 AM ()

I think you are correct. Changing to c.Length-1 does give me a slight improvement, but only noticeable at much larger values for f, ie at 60 it saves about 2 seconds.

By on 5/1/2010 8:29 AM ()

Would working with pointers improve performance?

Can someone remind me how to go from float[] to float* (or equivalent)?

By on 5/3/2010 9:54 AM ()

Although it's possible that pinning the array and performing direct access without bounds checks could potentially speed things up, it's possible that the overhead from pinning will overwhelm any gains, especially if the array is small. See [link:cs.hubfs.net] for some possibly out of date information along these lines.

By on 5/3/2010 11:28 AM ()

kvb is absolutely right : I considered using the pointer approach while building a matrix algebra library and abandonned the idea after some benchmarking on operations such as dot product and matrix multiply. What you get is a modest performance improvement for large matrices or vectors (at most like 30%) and a disastrous performance for small ones. I don't seem to find the original benchmarks but just running a little non-scientific experiment in fsi on array dot products gives me a break even at 1000 elements, a 30% improvement at 100000 but a 500% slowdown at 100 !

By on 5/3/2010 1:23 PM ()

The CLR supports very efficient pinning on the IL level. Basically the only necessary overhead is copying the array reference onto the stack once before you start using it, which should be completely negligible. Unfortunately, the F# compiler doesn't support native pinning and the code the .NET C# compiler generates for the fixed-statement is rather inefficient. One issue is that the C# compiler emits null and 0-length checks even though the C# standard leaves the respective behaviour undefined and one hence can't rely on them. Another, more severe issue is that the C# compiler puts the whole code inside the scope of the fixed statement into a try-finally block, even if the whole function body has no exception handlers and only consists of that one fixed statement. The try-finally block in turn inhibits certain optimizations by the JIT.

By on 5/4/2010 5:48 AM ()

@mau,

you have to pin the array and then get a pointer (nativeptr<float>) on the now fixed memory bloc.

The NativePtr module defines helper functions to perform pointer arithmetic and read/writes.

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

#r "FSharp.Powerpack.dll"
#nowarn "9"
open Microsoft.FSharp.NativeInterop

let pointerOps() =
    let a = [| 0.0; 1.0 ; 2.0 |]
    use pinA = PinnedArray.of_array a
    let ptrA = pinA.Ptr
    for k = 0 to a.Length - 1 do
        NativePtr.set ptrA k (NativePtr.get ptrA k - 1.0)
    a
By on 5/3/2010 11:18 AM ()

    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