leakage in recursive algorithm

[Ralf Goertz]

Hi,

I have a problem with a program implementing the backtracking algorithm
shown in <https://en.wikipedia.org/wiki/Backtracking>. Everything is
fine except for the fact that the program seems to be leaking. I use a
variant of the algorithm that finds all solutions (find_all=true). In my
case the memory usage still increases considerably although I already
found solutions and accordingly recursion_depth stays at or below its
maximum value of 65. According to my understanding this shouldn't
happen. The relevant snippets are:

struct BT {
…
void bt() { //the bt "procedure" from wikipedia
++recursion_depth; //global variable
static bool found(false);
if (reject()) {
--recursion_depth;
return;
}
if (accept()) {
found=true;
output();
if (find_all) solutions.push_back(state);
--recursion_depth;
return;
}
BT s=first();
while (s.isValid) {
s.bt();
if (found && ! find_all) break;
s.next();
}
--recursion_depth;
}
BT first() {
BT result(*this);
//modify result
return result;
}
bool accept();
bool reject();
void next();
}

first() creates a copy of its class variable, modifies it and returns
the copy by value. The variable "result" goes out of scope and gets
destroyed. In bt() the copy is assigned to s and then s itself calls
bt(). But s also gets destroyed when bt() returns. So where does the
leaking come from? (solutions.push_back() is not the problem, memory
gets consumed even though no new solutions are found.) Is it a problem
inherent to recursion?

[Barry Schwarz]

On Thu, 31 May 2018 14:55:50 +0200, Ralf Goertz
<m...@myprovider.invalid> wrote:

>Hi,
>
>I have a problem with a program implementing the backtracking algorithm
>shown in <https://en.wikipedia.org/wiki/Backtracking>. Everything is
>fine except for the fact that the program seems to be leaking. I use a
>variant of the algorithm that finds all solutions (find_all=true). In my
>case the memory usage still increases considerably although I already
>found solutions and accordingly recursion_depth stays at or below its
>maximum value of 65. According to my understanding this shouldn't
>happen. The relevant snippets are:

If you don't where or why the problem is occurring, then what is your
basis for deciding what is relevant? We need to see a complete
compilable example that demonstrates the problem. We don't need all
the internal details. If your sample exhibits the undesired behavior,
we have enough. The code you showed for first() is a suitable stub
for the function details we don't need and can be used as a template
for accept, reject, isValid, etc. We also need to see the actual
constructor for BT

I don't know if it is related or not but only one copy of a member
function exists, not a new copy for each class object. Consequently,
the variable found is common to all the objects and is initialized
before program execution begins. Once set to true, it is never set
back to false.

--
Remove del for email

[Paavo Helde]

If you don't have a new (or malloc;-S) in your program then you cannot
have a memory leak in the classical sense that the memory is lost and
cannot be freed. You can have accumulation of data somewhere where it
should not be.

You can also see an effect of memory fragmentation. In case of memory
fragmentation the apparent memory growth should eventually slow down and
approach a more or less stable level. However, if you have no explicit
dynamic allocations in your code you probably won't have memory
fragmentation either.

In recursive programs what takes memory is the stack, but if you say the
recursion depth is limited then it should not grow either.

So I guess there is either a bug in the code you did not show, or a bug
in the compiler related to recursion (very unlikely).

[Ralf Goertz]

Am Thu, 31 May 2018 21:25:39 +0300
schrieb Paavo Helde <myfir...@osa.pri.ee>:

> You can also see an effect of memory fragmentation. In case of memory
> fragmentation the apparent memory growth should eventually slow down
> and approach a more or less stable level. However, if you have no
> explicit dynamic allocations in your code you probably won't have
> memory fragmentation either.

I thought it could have to do with fragmentation but

> In recursive programs what takes memory is the stack, but if you say
> the recursion depth is limited then it should not grow either.
>
> So I guess there is either a bug in the code you did not show, or a
> bug in the compiler related to recursion (very unlikely).

the "bug" assumption is of course correct. It turns out I had two
containers storing the solutions, one a set<Status> ouside BT, one a
vector<Status> within BT which is actually a templated structure I often
use but rarely to find more than one solution. When counting the
solutions I looked at the set<Status> variable not noticing that I also
stuffed every (equivalent or not) solution into the vector.

Thanks for taking a look (also to Barry) and sorry for the noise.