Back to Questions
1.0k
views2
comments
Trying to work with memoziation and async jobs..
f#async

Hi all,

I'm an F# newbie, so please be gentle.

I have an application that calculates pricing for various combinations of products. Currently the application launches up to seven process asynchonously and waits for them to finish before proceeding.

All seven processes need to use some of the same calculations, and the various combination of parameters for these calculations is somewhat limited, so I feel memoization is a good way to optimize the application.

My problem comes with this bit of code:

1
2
3
4
5

match rateDict.TryGetValue(key) with
| true, result -> result
| false, _      -> let actualResult = rates.GetRate(rq)
                       rateDict.Add(key, actualResult)
                       actualResult

Basically what I'm doing is putting the parameters into a tuple and using that as a key to a dictionary where I store the result of the calculation. I have a non-async test version of this which works fine. My problem is that with the async version, I tend to get a lot of "An item with the same key has already been added." errors.

I understand why I'm getting this error. It's not really a big deal, but the application stops when it happens.

So, I kinda of have two questions I guess:

  • What is the best way to deal with this. I initally thought locking the dictionary would stop it, but it seems to negate the benefit of going async in the first place. Besides, it didn't seem to work anyway.
  • My second idea, and this is where I'm not sure I'm making the right descision, is to simply catch and ignore the error. Since I know why I'm getting it, it doesn't seem to have much downside. Again, being an F# newbie I'm don't know if there is a better way, or if this idea is solid. Also, I haven't been able to find an example of a "try..catch" structure that simply ignores the excpetion and moves on, and all attemtps to figure it out myself have failed.

Any advice I get on this issues would be VERY appreciated!

Thanks!

.

Below is a sample Memoize that never calls 'f x' more than once for the same 'x'. It does put a lot of contention around the lock if the computation-other-than-memoized-lookup is small. I show it only to demonstrate a working 'lock' example; I'm sure one could author faster code.

If you're allowed to call 'f' more than once one the same input (it will give same result, you may be wasting some CPU but perhaps can reduce lock contention) then you could choose not to lock on read and allow for failure on write (add duplicate key). The F# syntax

1
2

            try d.Add(k,v)
            with e -> ()

will ignore an exception thrown by "Add".

Anyway, take this all as some advice for 'learning F# constructs', as for 'the best way to attack this specific problem', I have to imagine it's a problem that comes up a lot and some experts have created great data structures for exactly this kind of thing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

 

let TryGet (d : System.Collections.Generic.Dictionary<_,_>) key =
    let mutable v = Unchecked.defaultof<_>
    if d.TryGetValue(key, &v) then Some(v) else None

let Memoize f =
    let d = new System.Collections.Generic.Dictionary<_,_>()
    let o = new obj()
    (fun x ->
        let r = lock o (fun () -> 
            match TryGet d x with
            | None -> let r = lazy(f x) in d.Add(x, r); r
            | Some(r) -> r)
        r.Force())

let GetRate x =
    printfn "Calling GetRate(%d)..." x
    System.Threading.Thread.Sleep(2000) // expensive to compute
    printfn "Done with GetRate(%d)..." x
    100 * x

let MGetRate = Memoize GetRate    

let asyncs = Array.init 100 (fun x -> async { return MGetRate(x%9) })
let sw = System.Diagnostics.Stopwatch.StartNew()
let r = asyncs |> Async.Parallel |> Async.RunSynchronously 
printfn "Took %dms" sw.ElapsedMilliseconds 
printfn "Results: %A" r
By on 9/2/2009 10:03 AM ()

Hi James,

It seems that shared mutable state is at the heart of your async computations, which goes against the grain of functional programming. Without knowing more about the application I'd recommend trying the new concurrent collections in the Parallel Extensions library. The ConcurrentDictionary seems like a good fit.

Let us know how you get on.

Danny

By on 9/2/2009 9:39 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