18
$\begingroup$

1. How does Internal`Bag handle memory inside a compiled function? (examples below)

2. Is there a way to explicitly free up memory used by Internal`Bag without exiting the function?

Preface: The strange properties of Internal`Bag's memory handling have been raised in a few (now aging) posts (such as here and here), but hasn't, as far as I know, recieved a definitive answer. This question is, in a sense, a follow up to one of @halirutan's questions, but I have tried to make it more specific and provide some background that might shed some light on a potential answer.

Internal`Bag is an undocumented function, and as such, I am using it at my own peril. If it isn't working as I expect, it's because my expectations need refining... hence this question.

Background: I've been trying to implement a compiled function that uses a disk neighbourhood of entries in an array to build up a new array. Because ragged arrays can't be compiled I've tried a few ways to efficiently get at the neighbourhood, one of which involved Internal`Bag. In the process it turned out that the memory used by Bag (inside a compiled function) doesn't get freed up until the function exits, even if it is reset at the start of the inner module. For a function that fills up a bag, does its thing, and then exits, this isn't an issue. But in my case I'm trying to build up an array within the function, with each cell requiring a new bag, and it quickly becomes unfeasible (ie, crashes the kernel due to lack of memory).

Example: Here are two functions that build up a new array, cell by cell, by looking at a disk neighbourhood of radius $r$ around the corresponding cell in an array passed as an argument. The first Stuffs each row of the neighbourhood into an Internal`Bag. The second puts them into a straightforward rank 1 array. I naively expected them to behave in exactly the same way, memory-wise, since the second approach is really just a way of simulating Bag.

nbdind[s_] := Table[{IntegerPart[-Sqrt[(s + 0.5)^2 - k^2]], IntegerPart[Sqrt[(s + 0.5)^2 - k^2]]}, {k, -s, s}];
flatnbdind[s_] := Partition[Flatten[{#, # + 1} & /@ FoldList[Plus, 0, 1 + #[[2]] - #[[1]] & /@ nbdind[s]]][[2 ;; -2]], 2]

fbag = Compile[{{array, _Real, 2}, {radius, _Integer, 0}, {nbdindices, _Integer, 2}},
  With[{dims = Dimensions[array]},
    Table[
      Module[{nbdbag = Internal`Bag[Most[{0.}]]},
        Do[
          Internal`StuffBag[nbdbag, array[[i + k - radius - 1, j + nbdindices[[k, 1]] ;; j + nbdindices[[k, 2]]]], 1],
        {k, 2 radius + 1}];
        Max[Internal`BagPart[nbdbag, All]]
      ], 
    {i, radius + 1, dims[[1]] - radius}, {j, radius + 1, dims[[2]] - radius}]
  ],
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
];

fsimbag = Compile[{{array, _Real, 2}, {radius, _Integer, 0}, {nbdindices, _Integer, 2}, {flatindices, _Integer, 2}},
  With[{dims = Dimensions[array], nbdlen = flatindices[[-1, 2]]},
    Table[
      Module[{flatnbd = Table[0., nbdlen]},
        Do[
          flatnbd[[flatindices[[k, 1]] ;; flatindices[[k, 2]]]] = array[[i + k - radius - 1, j + nbdindices[[k, 1]] ;; j + nbdindices[[k, 2]]]],
        {k, 2 radius + 1}];
        Max[flatnbd]
      ], 
    {i, radius + 1, dims[[1]] - radius}, {j, radius + 1, dims[[2]] - radius}]
  ],
  CompilationTarget -> "C", RuntimeOptions -> "Speed"
];

Get some data:

data = Table[
  With[{m = RandomReal[1, {n + 2 r, n + 2 r}], nbrhdind = nbdind[r], flatnbrhdind = flatnbdind[r]},
    {n, r, MaxMemoryUsed[fbag[m, r, nbrhdind]]/1024.^2, MaxMemoryUsed[fsimbag[m, r, nbrhdind, flatnbrhdind]]/1024.^2}
], {n, 10, 100, 10}, {r, 10, 70, 10}];

It appears that the memory usage of fsimbag scales as $n^2 + r^2$, as I would have expected -- $n^2$ for the array and $r^2$ for the neighbourhood which gets recycled in each execution of the module. But fbag's memory use scales as $n^2r^2$ (approximately). Not what I would have expected, but exactly what it should be if it's storing an $r$-neighbourhood for each of the $n^2$ cells in the array. The Bag, apparently, is not being recycled.

GraphicsRow[{
  ListPlot[{#[[1]]^2 #[[2]]^2, #[[3]]} & /@ Flatten[data, 1], AxesLabel -> {n^2 r^2, "Memory"}, PlotLabel -> "Internal`Bag"],
  ListPlot[{#[[1]]^2 + #[[2]]^2, #[[4]]} & /@ Flatten[data, 1], AxesLabel -> {n^2 + r^2, "Memory"}, PlotLabel -> "Simulated Bag"]
}]

Memory comparison

So, to rephrase my earlier questions:

  1. Does this seem like a sensible description of what's going on?

  2. Is there anything that could be done to free up that memory?

$\endgroup$
  • $\begingroup$ I think the def. of flatnbdind has a \[Sigma] that should be an s. $\endgroup$ – Michael E2 Jun 19 '17 at 5:00
  • $\begingroup$ @Michael Indeed it does. Thanks for catching that. $\endgroup$ – aardvark2012 Jun 19 '17 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.