Memoization using a map

Question

I am trying optimize a recursion problem using map to deal with the runtime errors. However, using memoization method and implementing a map still cannot solve the problem completely. By using the naive way of recursion, the segmentation fault error will not show up until the totalNum = 36. After optimization, the segmentation fault error will still show up when the totalNum getting really large, like 99999. Is there any way to solve this runtime problem even when the totalNum gets bigger than 99999? The following is my code for the header file:

using namespace std; 
static map<pair<int, int>, double> map;

double val(int r, int b){   
if (0 == r)
    return ((double) b);
if (0 == b)
    return (0);
if (map.find(make_pair(r, b)) != map.end()){
    return (double)map[make_pair(r, b)];
} else{
    double num1 = ((double) r/(r+b)) * value(r-1, b);
    double num2 = ((double) b/(r+b)) * value(r, b-1);
    double value = max((num1 + num2), (double) (b - r));
    map[make_pair(r, b)] = value;
    return value;
}
}

#endif

It is used in the main() to print out a message: cout << "Value = " << val(totalNum/2,totalNum/2) << endl;

Step through the code with a debugger and determine if the `map` is the **actual** culprit. — meowgoesthedog, Sep 28 '18 at 08:17
Aside: you've `using namespace std;`'ed, and then in the immediate next line introduced a naming conflict `map`. *Please* don't do **either**. You can move the map into `vals`, and define it `static std::map, double> memo;` — Caleth, Sep 28 '18 at 08:40
many compilers have an option to set the size of the stack. Have a look at https://stackoverflow.com/questions/2275550/change-stack-size-for-a-c-application-in-linux-during-compilation-with-gnu-com https://stackoverflow.com/questions/1156783/how-to-increase-the-gcc-executable-stack-size https://stackoverflow.com/questions/1825964/c-c-maximum-stack-size-of-program — Jerry Jeremiah, Feb 14 '19 at 21:08

D Drmmr · Answer 1 · 2019-02-15T13:03:27.810

1

Is there any way to solve this runtime problem even when the totalNum gets bigger than 99999? Get rid of the recursion. It's easy to figure out which values are required to calculate value (r, b). You can use a loop to calculate them.

The problem with the recursive version is that it requires a lot of stack space, which is quite limited. Therefore, this solution doesn't scale. The memoization doesn't change that, because function arguments and return value still need to be saved on the stack. Even if the recursion can be optimized (typically only with tail-recursion), an unoptimized build still won't run. This could mean you can't debug your program effectively.

When you change to a loop, you reuse the stack space for the function arguments and can store results on the heap.

edited Feb 15 '19 at 13:03

answered Feb 14 '19 at 21:04

D Drmmr

1,223
8
15

`The memoization doesn't change that, because function arguments and return value still need to be saved on the stack.` I think that is misleading. Say, for example, that function A takes 10 function calls to itself to compute input X, the memoized version will take roughly 1 function call if the input X was already cached with the result. This can make a difference in the stack space used - or not, it depends on how/when the function A is usually called. – Gabriel Francischini Feb 14 '19 at 21:31
1

@GabrielFrancischini I mean that memoization doesn't make a fundamental difference; a recursive approach still doesn't scale. Edited accordingly. – D Drmmr Feb 15 '19 at 13:05

Gabriel Francischini · Accepted Answer · 2019-02-14T18:38:31.330

Optimization (and memoization, as an optimization technique) is used to turn a slow code into a faster code, not an error-prone code into an error-free code.

It's very likely that your segfault (see common causes on the wiki) don't have anything to do with the memoization. Sure, adding the memoization changed the frequency and behavior of the segfault, but it didn't cause it neither removed it.

The most common cause of segfault is trying to use a freed (deleted in C++) pointer, but your code doesn't handle any raw pointer directly, so probably this isn't the cause.

The second most common cause of segfaults is returning a reference to a local variable, and this isn't happening in this case either.

However, because after memoization the segfault is happening at a bigger number (totalNum) it is probably related to stack size. In C++, recursion usually leads to an always increasing amount of stack usage, and you can easily use up all the stack normally provided by the operating system (causing a stack overflow which usually is signaled as a segfault). That's the likely source of segmentation fault. If you are on linux, try using ulimit -s to see your current stack size and increase it brutally (by using something like ulimit -s 65536 for 64 Mb of stack) to see if that makes you have a segfault at even bigger totalNum. If so, then you now know that your problem is a stack overflow. Then it will be easier to find solutions for it. The error-free solution, then, is to change the recursion algorithm to a task-based algorithm (i.e. set up a queue of values to process, loop through it and process items of it instead of using recursion).

Otherwise would be great to have more code to look, because the segfault is unlikely to be caused by this memoization code.

Also, it would be very good if you provided a minimal working example, with a dummy main function and everything required to compile.

Memoization using a map

2 Answers2