Memory leak when using nested Seq.unfold to generate first 1000000 primes

[chav-n]

For the purpose of learing F# I tried solving a typical programming exercise: write a program that prints all primes. To make it more challenging, I wrote an implementation where recursions/loops were replaced with two nested Seq.unfold usages.Then I modified it to print the nth prime. Here is a function that will print the nth prime after generating the first n primes:

let printAllPrimesSeq() =
  let tryFindPrimeDivisor primesL i =
    (primesL |> List.takeWhile(fun x -> x*x <= i) |> List.tryFind(fun x -> i % x = 0))
  let nextPrime primesL =
     let tryFindPrimeDivisor1 = tryFindPrimeDivisor (List.fold (fun acc elem -> elem::acc) [] primesL)
     fst(
       Seq.unfold
         (fun (i: int) -> Some(
           (i, tryFindPrimeDivisor1 i),
           (i + 2)))
         (primesL.Head + 2)
       |> Seq.find(fun x -> snd x = None))
  let allPrimes =
    Seq.unfold
      (fun (primes: int list) ->
        let i' = (nextPrime primes)
        Some(i', i'::primes))
      ([3])

  (*
  printf "2, 3, "
  for i in allPrimes do
    printf "%i, " i
   *)
  printf "Please give a number: "
  let n = int (System.Console.ReadLine())
  let prime =
    if n = 1 then 2
    elif n = 2 then 3
    else (allPrimes |> Seq.take(n - 2) |> Seq.last)
  printf "%i" prime

Requesting the 1000000th prime will send memory usage above 5GB in Windows 11 (only the *.exe file), half an hour later, running on 10th gen Core i5. The dotnet generated project is set to net7.0. Other programs running in the background: Chrome, Notepad++

[mciccottidmg]

I think the issue you're running into is that you're creating a lot of large, ephemeral memory allocations.

I ran your code in FSI with #time on and here are a few illustrative results:

10,000:

Real: 00:00:00.431, CPU: 00:00:00.546, GC gen0: 193, gen1: 1, gen2: 0

80,000:

Real: 00:00:39.248, CPU: 00:00:39.359, GC gen0: 12254, gen1: 83, gen2: 0

100,000:

Real: 00:01:09.639, CPU: 00:01:09.703, GC gen0: 19144, gen1: 14116, gen2: 1

As you can see, as your number of primes go up, the number of higher generational garbage collections increases, which means the lists allocated in previous iterations of your sequence become less and less likely to have been collected as later iterations are executed.

The allocations are happening here:

let tryFindPrimeDivisor1 = tryFindPrimeDivisor (List.fold (fun acc elem -> elem::acc) [] primesL)

Each time you find a new prime, you're re-allocating the list of primes already found.

If you change your code like this to eliminate the majority of the allocations (showing only lines that changed):

  let tryFindPrimeDivisor primesL i =
    primesL |> List.tryFind(fun x -> i % x = 0)
  let nextPrime primesL =
     let tryFindPrimeDivisor1 = tryFindPrimeDivisor primesL

You can see that while this is slower, the # of garbage collections fall off by several orders of magnitude.

100,000

Real: 00:02:03.111, CPU: 00:02:03.125, GC gen0: 13, gen1: 2, gen2: 0

I haven't tried it, but I'm guessing this would be able to successfully generate 1,000,000 primes without running out of memory.

A few general comments:

• Be careful of performance problems when reversing lists. Generally, it's better to find a different approach if you find yourself needing to reverse a list in a tight loop (or an unfold in this case)
• Functional is good, but sometimes you need to fall back to imperative for certain performance-intensive situations
• Minor improvement to your code: (List.fold (fun acc elem -> elem::acc) [] primesL) is equivalent to List.rev
• You'd probably get an answer a lot faster if you ask this type of question in an F# community group like https://discord.me/fsharp

[chav-n]

My first impementation was with rec loops, purely functional and with no "memory leaks". However, it is better style to avoid them when possible. Maybe the GC can be improved and handle runnaway allocations with stop-the-world cleanups.

[Xyncgas]

:/ functional should be the obvious choice for anyone who wants to achieve performance intensive goals, it can avoid heap allocations completely by using stack based list, the overhead of calling a function generally doesn't exist because functions get inlined as if you didn't write functions but 'imperative' codes (in f# the inline keyword works like c++ macro)

[vzarytovskii]

@mciccottidmg thanks for taking time and responding with explaination!