Memory leaks with resumes?

[TheDying0fLight]

The following code works fine. But by changing small things I seem to get memory leaks and I dont know why. I would like to know if this is a me issue or Effekt issue does anyone know about this? I provide example memory usage after about 20s of running each code.

Working:

effect Dual(idx: Int): Array[Bool]

def main() = {
  with on[OutOfBounds].panic
  val listsize = 50
  var arr = array(listsize, false)
  try {
    each(0,listsize) { v =>
      arr = do Dual(v)
      println(v)
    }
  } with Dual { idx =>
    arr.set(idx, true)
    resume(arr.copy)
    arr.set(idx, false)
    resume(arr)
  }
}

Problem1:

If I either change it to this (add a counter to the effect):

effect Dual(idx: Int): Array[Bool]

def main() = {
  with on[OutOfBounds].panic
  var countFalse = 0
  val listsize = 50
  var arr = array(listsize, false)
  try {
    each(0,listsize) { v =>
      arr = do Dual(v)
      println(v)
    }
  } with Dual { idx =>
    arr.set(idx, true)
    resume(arr.copy)
    countFalse = countFalse + 1
    arr.set(idx, false)
    resume(arr)
    countFalse = countFalse - 1
  }
}

Problem2:

Or to this (exchange array with list):

effect Dual(idx: Int): List[Bool]

def main() = {
  with on[OutOfBounds].panic
  var countFalse = 0
  val listsize = 50
  var arr = fill(listsize, false)
  try {
    each(0,listsize) { v =>
      arr = do Dual(v)
      println(v)
    }
  } with Dual { idx =>
    resume(arr.updateAt(idx){_ => true})
    resume(arr.updateAt(idx){_ => false})
  }
}

[marvinborner]

Thanks for the issue! We often have issues with memory leaks, so I wouldn't be surprised.

The images aren't loading, so I'm not entirely sure what you're referring to (I couldn't observe abnormal memory usage for Problem1 in LLVM, for example). What backend are you using and how are you measuring the memory leaks?

[TheDying0fLight]

Exchanged the images with new versions hope they work now. I use the JavaScript backend on Windows 10 and use the Task Manager to track the memory (as the images would show)

[b-studios]

In general, we are not the most memory efficient language. However, in your example, you are creating $2^{n + 1} - 2$ many arrays of size $n$ (where n=50).

So, assuming something like 500 bytes per array, this is roughly 1000 Petabytes.

JS is garbage collected, so in general we cannot guarantee that the memory will be freed right-away. However, given that the program terminates on your computer says a lot about it not leaking too much memory ;)

It is also not very surprising that the list version allocates a lot more, since there we allocate roughly 50 linked objects.

The following will not make a lot of sense to you, but what we could investigate is whether the "shadow stack" of regions potentially holds onto the arrays for too long preventing GC to do its work. Again, given that the program terminates at all I'd say we are good here.

(disclaimer: I only thought a few minutes about this, so I might be wrong with my analysis)

[b-studios]

I have to say, I like this as a benchmark though ;)

Here (for N=24) is JS (/usr/bin/time -l):

       11.20 real        10.98 user         0.12 sys
            77856768  maximum resident set size
                   0  average shared memory size
                   0  average unshared data size
                   0  average unshared stack size
                5279  page reclaims
                   1  page faults
                   0  swaps
                   0  block input operations
                   0  block output operations
                   0  messages sent
                   0  messages received
                   0  signals received
                   0  voluntary context switches
               17846  involuntary context switches
        183751342222  instructions retired
         35430678327  cycles elapsed
            60757632  peak memory footprint

and llvm:

        4.95 real         4.43 user         0.51 sys
          7095566336  maximum resident set size
                   0  average shared memory size
                   0  average unshared data size
                   0  average unshared stack size
              433213  page reclaims
                   4  page faults
                   0  swaps
                   0  block input operations
                   0  block output operations
                   0  messages sent
                   0  messages received
                   0  signals received
                   0  voluntary context switches
                  37  involuntary context switches
         70141067796  instructions retired
         15580367548  cycles elapsed
          7098611584  peak memory footprint

Here LLVM uses 5,6 GB peak memory, while JS is around 58 MB! (cc @phischu). Nevertheless, it is still twice as fast.

[TheDying0fLight]

In general, we are not the most memory efficient language. However, in your example, you are creating 2 n + 1 − 2 many arrays of size n (where n=50).

So, assuming something like 500 bytes per array, this is roughly 1000 Petabytes.

JS is garbage collected, so in general we cannot guarantee that the memory will be freed right-away. However, given that the program terminates on your computer says a lot about it not leaking too much memory ;)

It is also not very surprising that the list version allocates a lot more, since there we allocate roughly 50 linked objects.

Sorry I was not clear about this. The programm did not terminate for me, but that is not the important part. What I wanted to demonstrate is that adding a counter or changing an array to a list will cause a memory leak. While the example without them rarely uses more than 50MB of RAM the other ones quickly run out of memory when the println is removed.

I tested a bit with the counting. When running the following code we get an ever increasing memory usage (task manager screenshots after running for 20s or Out of memory, what happens first):

effect Dual(idx: Int): Array[Bool]

def main() = {
  with on[OutOfBounds].panic
  var count = 0
  val listsize = 50
  var arr = array(listsize, false)
  try {
    each(0,listsize) { v =>
      arr = do Dual(v)
    }
  } with Dual { idx =>
    arr.set(idx, true)
    resume(arr.copy)
    arr.set(idx, false)
    resume(arr)
    count = count + 1
  }
}

If the count is moved outside (directly before the effect), which does results in the same count, the memory usage increases slowly or not at all (Only code for try with as the rest stays the same):

try {
each(0,listsize) { v =>
  count = count + 1
  arr = do Dual(v)
 }
} with Dual { idx =>
  arr.set(idx, true)
  resume(arr.copy)
  arr.set(idx, false)
  resume(arr)
}

It seems the counting at the end of the effect has some weird behaviour. When the count is increased before the end of the effect this issue also does not occur:

try {
  each(0,listsize) { v =>
    arr = do Dual(v)
  }
} with Dual { idx =>
  arr.set(idx, true)
  resume(arr.copy)
  arr.set(idx, false)
  count = count + 1
  resume(arr)
}

The following will not make a lot of sense to you, but what we could investigate is whether the "shadow stack" of regions potentially holds onto the arrays for too long preventing GC to do its work.

What you described seems plausible (but for lists and not for arrays since arrays behave as expected). It shouldn't use much more memory than the arrays solution as it creates a similar amount of arrays (also tried copying the array in both resumes with similar results).

[phischu]

Thank you for minifying these examples. The expected result if you would print count at the end is 2^50, right?

  } with Dual { idx =>
    arr.set(idx, true)
    resume(arr.copy)
    arr.set(idx, false)
    resume(arr)
    count = count + 1
  }

In a handler like this, the increments will only be done after the very last resume has finished. Operationally, we remember that we will have to increment the count as a stack frame. This requires a stack of size 2^50.

[TheDying0fLight]

Wouldn't the following code then have the same issue if that is the problem? I reduced the iterations to 26 then code without memory issues finishes on my PC and the other fails due to OOM.

effect Dual(): Unit

def main() = {
  var count = 0
  try {
    each(0,26) { _ =>
      do Dual()
    }
  } with Dual {
    resume(())
    resume(())
    count = count + 1
  }
}

I removed the first set as it does not have an effect on the issue. I think I pinned the issue down to these two lines, when both lines are there the memory issues exist otherwise its fine.

effect Dual(idx: Int): Array[Bool]

def main() = {
  with on[OutOfBounds].panic
  var count = 0
  val listsize = 26
  var arr = array(listsize, false)
  try {
    each(0,listsize) { v =>
      arr = do Dual(v)
    }
  } with Dual { idx =>
    resume(arr.copy)
    arr.set(idx, false) // if this is removed there is no issue
    resume(arr)
    count = count + 1 // same for this (only one has to be removed)
  }
}