How to calculate the maximum allocated memory when recursively calling a function

Question

How to calculate the maximum allocated stack memory when recursively calling a function, I created a variable max memory, and I also have a variable memory. Max memory should read the allocated memory during recursive calls to the quicksort function. Please tell me what the condition looks like in which the maximum of the two values is processed (memory and allocated memory recursively)

void QuickSort(int* a, int n)
{
    int x, i, j; 
    int maxmemory = 0; 
    MEMORY += 7 * sizeof(int); 
    x = a[n / 2];
    i = 0; j = n - 1; 
    do
    {
        while (a[i] < x) 
        {
            headoperators++;
            i++;
        }
        headoperators++;

        while (x < a[j]) 
        {
            headoperators++;
            j--;
        }
        headoperators++;

        SIDE_OPERATIONS++;
        if (i <= j) 
        {
            swap(a[i], a[j]); 
            i++;
            j--;
        }
        SIDE_OPERATIONS++;
    } while (i < j); 

    SIDE_OPERATIONS++;
    if (j > 0) 
        QuickSort(a, j + 1); 

    SIDE_OPERATIONS++;
    if (i < n - 1) 
        QuickSort(a + i, n - i); 
}

I don't know exactly how to solve this problem, I'm new to C+=

What do you mean by "allocated memory"? Your code does not contain any invocations of `new` or `malloc` so it does not allocate any heap memory. Does that mean you are actually trying to track the usage of *stack* memory? (which is a proxy for the maximum stack depth) Do you need the answer in bytes or is the number of stack frames enough? Also, where did you get the magic value `7 * sizeof(int)` from? This does not include things like the amd64 "red zone". — Botje, Jun 02 '23 at 07:47
Measuring stack use is pretty easy if you can just read the SP through inline asm. Then you can store it in a "max depth" variable before launching the recursive function, then have each recursive call check it too and update the "max depth" if the value is less than/greater than "max depth", depending on incrementing/decrementing stack. But you need to clarify what you mean with allocated memory indeed. — Lundin, Jun 02 '23 at 07:51
@Botje Yes, I need an answer in bytes. In fact, it should be something like this - Make two variables, the current and maximum memory At the beginning of the function, increase the current one and if it is greater than the maximum, replace the maximum At the end of the function reduces the current — deynchik, Jun 02 '23 at 07:51
please do not tag c and c++, unless the question is about interoperation or differences between those two languages. Your code looks like c, hence the c++ tag was removed. If you are compiling this as c++ you should not add the c tag — 463035818_is_not_an_ai, Jun 02 '23 at 07:53
please read about [mcve]. The code you posted is hard to understand because most stuff is missing — 463035818_is_not_an_ai, Jun 02 '23 at 07:54
7 * sizeof(int) = 4 int in body, 1 swap function, 2 int in parameters — deynchik, Jun 02 '23 at 07:55
That makes several wrong assumptions: 1) "all variables actually reside in the stack" (no, this can vary with compiler optimizations) 2) "the swap function takes up stack space" (it doesn't) 3) "parameters are passed via the stack" (not necessarily). Additionally, this ignores the space for the [amd64 red zone](https://en.wikipedia.org/wiki/Red_zone_%28computing%29) (if compiling for that architecture), frame pointers and activation records (eg return address). — Botje, Jun 02 '23 at 07:58
It is not really possible as far as the C language as defined by the standard goes. There is no guarantee there is a stack to begin with. If you need to estimate how much memory the program uses when executed on a specific OS built with a specific compiler and specific compilation flags, you should mention these details. — n. m. could be an AI, Jun 02 '23 at 07:58
Is your swap function actually a function? Because `swap(a[i], a[j])` cannot swap any values in the array if it is a C function. Parameters are passed by value in C. (C++ supports reference parameters like `int& a`, but C does not.) — Ian Abbott, Jun 02 '23 at 10:42

nielsen · Answer 1 · 2023-06-02T08:09:42.300

In this case, memory is allocated on the stack. Normally, the stack grows downwards and we can estimate the current usage by looking at the address of a recently allocated variable at some time during the program execution compared to the address of a stack variable allocated initially in the program. We can then store the maximal usage that was detected.

#include <stddef.h>
#include <stdio.h>

char *stack_base;
size_t max_stack_usage = 0;

size_t current_stack_usage()
{
    char c;   // "c" is allocated on the stack at the current position
    size_t current_usage = stack_base - &c;  // Estimate of current usage (note that stack usually grows downwards (towards lower addresses)
    if(current_usage > max_stack_usage) max_stack_usage = current_usage;
    return current_usage;
}


int main()
{
    char a;
    stack_base = &a;   // "a" is stored on the stack and at this point we should be close to the top of the stack area
    ...
    printf("Maximal detected stack usage: %zu\n", max_stack_usage); 
    return 0;
}

In the OP case, the update of MEMORY can be replaced by a call to current_stack_usage() to monitor the stack usage.

Note that this method makes use of common behavior which is not guaranteed by the C Standard. Thus, it may not work in all environments, but it should work in most cases and it is simple to try.

[Pointer arithmetic on `void*` is illegal](https://stackoverflow.com/q/3523145). Use `char*` instead. — Siguza, Jun 02 '23 at 07:55
@Siguza Yes, that was a blunder. Fixed now. Thank you for noticing this. — nielsen, Jun 02 '23 at 07:57
@Siguza pointer arithmetic is illegal unless done on pointers that point to elements of the same array. One can cast to `uintptr_t` and hope for the best. — n. m. could be an AI, Jun 02 '23 at 08:01
@n.m. You are right. I have added a note that this method is not guaranteed by the C standard to work. On the other hand, I think it will give useful results on most systems and is an easy way to obtain some empirical information on the stack usage which can be difficult to estimate theoretically. — nielsen, Jun 02 '23 at 08:16

score 0 · Answer 2 · answered Jun 02 '23 at 09:15

The C language doesn't know about the stack or recognize its existence, so you have to use assembler at least for checking the stack pointer.

Conceptually:

Read the SP before calling the function, to know the base offset. Store this.
From inside the recursive function, keep track of the maximum SP value. Depending on CPU the stack will either grow downwards or upwards. If you find a new maximum (minimum...?) value then store that one.

Here's a conceptual example for gcc x86_64:

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

static uintptr_t base;
static uintptr_t max_depth;

static uintptr_t read_sp (void)
{
  uintptr_t result=0;
  __asm("movq %%rsp, %0" : "=r" (result) :  );
  return result;
}

#define muck_around_with_the_stack() \
  volatile int x[42];                \
  volatile int y = 1;                \
  int* xptr = (int*)x;               \
  memset(xptr,y,sizeof(x));          

void recursion (int n)
{
  muck_around_with_the_stack();

  uintptr_t sp = read_sp();
  if(sp < max_depth)
  {
    printf("New max use: %" PRIuPTR " bytes\n", base - sp);
    max_depth = sp;
  }

  if(n==0)
    return;
  else if(n&1)
    recursion (n-1);
  else
    recursion (n/2 - 1);
  printf("%d\n", n);
}

int main (void)
{
  base = read_sp();
  printf("SP base: %p\n", (void*)base);
  max_depth = base;

  recursion(1000);
}

Explanation:

I made some silly down-counting function recursion that lowers n by 1 in case it's an odd number, otherwise divide by 2 first in case it's an even number. And it prints the results in the end (and so they will be in the reverse order). This just serves to topple over tail call optimization and inlining, forcing the compiler to actually carry out the recursive calls in the machine code.
To further increase stack use, a made some nonsense macro that forces the compiler to stack allocate some array at each function call.
Each time the function spots a new maximum stack use, it deports it and updates a max depth variable.

Example output for n=1000 (gcc x86_64 Linux):

SP base: 0x7fff05f81a20
New max use: 48 bytes
New max use: 1312 bytes
New max use: 1360 bytes
New max use: 2624 bytes
New max use: 2672 bytes
New max use: 3936 bytes
New max use: 3984 bytes
New max use: 5248 bytes
New max use: 5296 bytes
New max use: 6560 bytes
1
4
5
12
13
28
29
60
122
123
248
498
499
1000

How to calculate the maximum allocated memory when recursively calling a function

2 Answers2