Back to Questions
2.1k
views3
comments
Increasing memory consumption
f#parallel.net

Hi,

I'm working on an implementation of a genetic algorithm in F#. Everything is working fine except it consums a lot of memory until it eventually crash.
In my code I create many temporary lists, arrays and objects at each iteration so I know where this problem comes from but it's temporary object so I thought the GC would eventually clean everything. Apparently it's not the case...Do you have any idea how I can avoid this problem or do know any .net trick ?

One of my idea is to try to recycle some objects or array but since it's a parallel algorithm it's not easy to do

Thanks :)

.

First of all, if your algorithm is recursive, you must ensure it is tail recursive. In case you get StackOverflowException, it is obviously the only reason of crashes. But this also can be a reason of OutOfMemoryException, because every time you call a function recursively without tail call, current function values remain in the stack and may continue reference your temporary objects on heap. The latter problem may also be eliminated by turning optimizations on (e.g. building a release version instead of debug).

Second, I'd advice you to use an object per thread using [<ThreadStatic>], but this may complicate your algorithm.

At last, you may post your code here unless it is private: community may help you clean it.

By on 1/11/2011 4:56 AM ()

GA's tend to be written interatively, so using tailcalls or loops should be easy enough. But are you sure you're not really running out of memory? How many individuals in a generation, how many generations, and how much memory per individual? (Then multiply what you think it is by 2x to 5x :)) Or are you doing a hierarchical or hybrid GA - that could be even worse. Are you using generic collections of value types for the individuals, or references types? Anyway, let us know what your domain is and what how the convergence and perf is once things are working...

By on 1/11/2011 11:04 AM ()

Thank you for your answers :)

My algorithm is not really a secret. In fact I wrote it in a way it is generic and it can be reused:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

    open System
    open System.Collections.Generic

        let StartGenAlgo (iPop: list<array<'G>>) 
                         (maxPop: int) 
                         (fEvaluation: array<'G> -> float) 
                         (fMutation: array<'G> -> array<'G>) 
                         (fCrossOver: array<'G> -> array<'G> -> array<'G>) 
                         (fStop: int -> list<array<'G> * float> -> bool) 
                         (comparer: IComparer<array<'G> * float>)
                         (feedbackFunction: Action<int, list<array<'G> * float>>)=

            if iPop.Length > maxPop then failwith "Initial population is higher than the maximum population authorized"

            let rGen = new Random()

            let fSort l = l |> List.sortWith (fun x y -> -comparer.Compare(x,y))

            let fSelectFittest l = 
                let rec loop r l i p =
                    if i = 0 then
                        r
                    else
                        match l with
                        |[] -> r
                        |h::t -> 
                            let eq = comparer.Compare(h, p) = 0
                            let nextr, nexti =
                                if eq then
                                    r, i
                                else
                                    h::r, i - 1
                            loop nextr t nexti h
                loop [] l maxPop (null, 0.0) |> List.rev

            let inline fProbSelect i = rGen.NextDouble() > (i / maxPop |> float)

            let inline fAssignScore item = (item, fEvaluation item)

            let lPop = ref (iPop |> List.map fAssignScore |> fSort)
            let lSelectedPop = ref []
            let aSelectedPop = Array.zeroCreate maxPop
            let totalSelectedPop = ref 0

            let asyncGenerateCrossOver =
                async {
                        let lastIndex = !totalSelectedPop - 1
                        !lSelectedPop |> List.iteri (fun i (item, _) -> aSelectedPop.[i] <- item)                    
                        return !lSelectedPop |> List.map (fun (item, score) -> fCrossOver item aSelectedPop.[rGen.Next(0, lastIndex)] |> fAssignScore)
                }

            let asyncGenerateMutation =
                async {
                        return !lSelectedPop |> List.map (fun (item, score) -> fMutation item |> fAssignScore)
                }

            let asyncGenerateNewPop = [|asyncGenerateCrossOver; asyncGenerateMutation|] |> Async.Parallel

            let mutable generation = 0
            while not (fStop generation !lPop) do
                lSelectedPop := []
                totalSelectedPop := 0

                !lPop |> List.iteri (fun i item -> 
                                            if fProbSelect i then 
                                                lSelectedPop := item::!lSelectedPop
                                                totalSelectedPop := !totalSelectedPop + 1)

                match asyncGenerateNewPop |> Async.RunSynchronously with
                |[|lCrossOver; lMutation|] -> lPop := lCrossOver |> List.append lMutation |> List.append !lSelectedPop |> fSort |> fSelectFittest
                |_ -> failwith "Unknown error"

                feedbackFunction.Invoke(generation, !lPop)
                generation <- generation + 1
                GC.Collect(); // Slow down the increase of memory used

            !lPop

So this the core of the algorithm but you have to provide function to mutate, do cross over, ...
As you can see I'm using a lot of lists, but I don't think it's the problem because I read somewhere that F# reuse items from previous lists. It works very well and most of the time good solutions are found before I run out of memory. But with a population of 20000 and after 500 generation it will crash. I'm just surprised that the app keeps allocating memory.

In the evaluation function (not shown here) I use 2 temporary array. And because this function is called thousands of time I guess it's part of the problem.
As far as I know all of my recursive functions are tail recursive.

I implemented this algorithm for an academy project. We have to schedule the production of 4 products but we must to observe several constraints like producing on time, sharing resources, minimizing cost, ...
It was also the opportunity to learn the MVVM design pattern, View = XAML,View Model = C# and Model = F# :)

By on 1/11/2011 11:38 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