Проверьте использование памяти в radixsort C ++

Question

Я реализовал сортировку radix в c ++

...

void *countSort(int *tab, int size, int exp, string *comp, bool *stat) { 
    int output[size]; 
    int i, index, count[10] = {0}; 
    sysinfo(&amem);
    for (i = 0; i < size; i++){
        index =  (tab[i]/exp)%10;
        count[index]++; 
    }


    for (i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 

    for (i = size - 1; i >= 0; i--) { 
        index = count[ (tab[i]/exp)%10 ] - 1;
        output[index] = tab[i]; 
        count[ (tab[i]/exp)%10 ]--; 
    } 

    if((*comp).rfind("<",0) == 0){
        for (i = 0; i < size; i++){
            tab[i] = output[i]; 
            swap_counter++;
            if(!*stat){ fprintf(stderr, "przestawiam\n"); }
        }
    }else{
        for (i = 0; i < size; i++){
            tab[i] = output[size-i-1]; 
            swap_counter++;
            if(!*stat){ fprintf(stderr, "przestawiam\n"); }
        }
    }
} 

void *radix_sort(int size, int *tab, string *comp, bool *stat) { 
    int m; 
    auto max = [tab, size](){
        int m = tab[0]; 
        for (int i = 1; i < size; i++) {
            if (tab[i] > m) 
                m = tab[i]; 
        }  
        return m;
    };
    m = max();

    for (int exp = 1; m/exp > 0; exp *= 10) 
        countSort(tab, size, exp, comp, stat); 
} 

...

int main(){
   int tab = (int *) malloc(n*sizeof(int));
   for(int n = 100; n <=10000; n+=100){
      generate_random_tab(tab, n);
      radix_sort(sorted_tab, 0, n-1, ">=", 1);
      free(tab);
   }
}

Теперь я хочу проверить и распечатать информацию о том, сколько памяти использует сортировка radix. Я хочу сделать это, чтобы сравнить, сколько памяти использует разные алгоритмы сортировки. Как этого добиться?

Мне дали подсказку использовать sysinfo () для анализа того, как меняется использование системной памяти, но я не смог добиться постоянных результатов. (Я работаю над linux)

Answer 1

Ваша программа использует линейное использование памяти malloc(n*sizeof(int)) и int output[size]; --- один из них в куче, другой в стеке, поэтому в основном вам не нужно выполнять измерения во время выполнения, поскольку вы можете легко рассчитать их.

Поскольку вы находитесь на Linux, для более сложных случаев, например, есть инструмент массив в valgrind, но он ориентирован на измерения кучи (которые в обычных случаях, в которых вы хотите измерять использования памяти достаточно, так как стек обычно мал для больших объемов данных).

Answer 2

sysinfo показывает только всю системную память, а не отдельную память процесса.

Для использования памяти процесса вы можете попробовать mallinfo, например

struct mallinfo before = mallinfo();
// radix sort code
struct mallinfo after = mallinfo();

Теперь вы можете сравнивать различные записи до и после кода сортировки. Имейте в виду, что это не включает в себя стековую память.

Хотя я не знаю, насколько точны эти числа в контексте C ++.

---

Тестирование полного примера

#include <malloc.h>
#include <stdio.h>

#define SHOW(m) printf(#m "=%d-%d\n", after.m, before.m)

int main()
{
    struct mallinfo before = mallinfo();
    void *p1 = malloc(1000000);
    //int *p2 = new int[1000000];
    struct mallinfo after = mallinfo();
    SHOW(arena);
    SHOW(ordblks);
    SHOW(smblks);
    SHOW(hblks);
    SHOW(hblkhd);
    SHOW(usmblks);
    SHOW(fsmblks);
    SHOW(uordblks);
    SHOW(fordblks);
    SHOW(keepcost);
    return 0;
}

показывает различные значения, в зависимости от того, используете ли вы malloc

arena = 135168-0
ordblks = 1-1
smblks = 0-0
hblks = 1-0
hblkhd = 1003520-0
usmblks = 0-0
fsmblks = 0-0
uordblks = 656-0
fordblks = 134512-0
keepcost = 134512-0

или new

arena = 135168-135168
ordblks = 1-1
smblks = 0-0
hblks = 1-0
hblkhd = 4001792-0
usmblks = 0-0
fsmblks = 0-0
uordblks = 73376-73376
fordblks = 61792-61792
keepcost = 61792-61792

Похоже, что C ++ (Ubuntu, G CC 9.2.1) выполняет какое-то предварительное распределение, но соответствующее число, похоже, hblkhd (на моей машине).

Поскольку ваше единственное динамическое распределение c находится в начале main, вы должны выполнить первое mallinfo там. Тестирование только радикального кода сортировки показывает, что нет дополнительных динамических c выделений памяти.