У меня есть рекурсивная функция, написанная на C ++, которая динамически распределяет 2D-массивы, используя new
,
Как я могу измерить общий объем пространства, выделяемого функцией в куче и стеке в течение всего срока ее службы?
Вот пример (это не мой код) того, как измерить стек.
unsigned int maxStackLocation ;
unsigned int minStackLocation ;
main ()
{
//get the address of a local variable before calling Quicksort
//the stack grows down, so this is the max stack location
int localVariable;
void *currPtrLocation = (void*)(&localVariable);
maxStackLocation = *(unsigned int *)(&currPtrLocation);
//we get the value for the minimum stack location in quicksort itself
//call quicksort
Quick (A, num);
space = maxStackLocation - minStackLocation;
}
//some redundant function whose stack usage will be measured
void Quick (unsigned int A[], int num)
{
if (num <= 1)
{
//check the stack usage
//figure out where we are on the stack by looking at the byte
// address of the local variable
//we do this by making a pointer to a local variable, and then
//casting it to a integer
void *currPtrLocation = (void*)(&num);
unsigned int currStackLocation = *(unsigned int*)(&currPtrLocation);
if (currStackLocation < minStackLocation)
minStackLocation = currStackLocation;
return;
}
}
редактировать
Borgleader указывает, что мой первоначальный вопрос «Измерение функции максимального пространства, выделяемой в куче и стеке в течение всего времени ее существования», неверен. Я изменил «Макс» на «Всего».
Ваш пример для измерения использования стека точен и даст вам (почти) правильный ответ. У меня есть предложение для определения использования кучи, но сначала ….
В своей книге «Более эффективный C ++» в пункте 27 Скотт Мейерс (между прочим, мой любимый автор на C ++) описывает, почему в общем смысле и в рамках портативного или полупортативного C ++ невозможно определить, был ли объект размещается в стеке, куче или статически. Но его объяснение относится к выделенным объектам с точки зрения самих объектов, а не к распределению с точки зрения кода, который запрашивает такое распределение. С точки зрения кода, который запрашивает выделение, вы можете точно знать, размещен ли объект, независимо от его типа, в куче или стеке в зависимости от того, как вы запросили его выделение. (Боковая панель: Конечно, это зависит от того, действительно ли ваша система использует стек времени выполнения, что некоторые быстро указывают на то, что стандарт C ++ не гарантирует, однако ни один из этих снобов стандартов никогда не указывает на какой-либо реальный пример другого стандартного стандарта. соответствующий компилятор C ++, который не использует стек времени выполнения. Вернуться к нашему обсуждению …) Например:
int Fred; // Fred is allocated on the stack
int *Barney = new int; // Barney is allocated on the heap
Фред уничтожит, когда выйдет за рамки; Вы должны явно удалить Барни, когда закончите с ним. Это работает так же для пользовательских типов, включая типы STL:
std::string Fred; // Fred is allocated on the stack (see disclaimer*)
std::string *Barney = new std::string(); // Barney is allocated on the heap
// *Disclaimer: May not be totally true on some small embedded processors that
// implement the runtime stack in a special small address space
// separate from “normal” RAM.
…НО: хотя объект std :: string, известный как Fred, сам по себе расположен в стеке, мы, конечно, знаем, что его данные не могут быть распределены в стеке, потому что его данные имеют переменную длину и должны иметь возможность неограниченного расширения при добавлении символов к этому. Таким образом, только часть управления std :: string (т.е. сам объект std :: string) может быть размещена в стеке.
Вернемся к пункту 27 Скотта Мейера и его применимости к этому обсуждению:
myClass *someFunction() {
int someInputParameter = 42;
myClass Fred(someInputParameter); // Fred is allocated on the stack
myClass *Barney = new myClass(someInputParameter); // Barney is allocated on the heap
return Barney;
}
Согласно пункту 27 Скотта Мейера, ни Фред, ни Барни не могут сами знать, распределены ли они по стеку или куче, или, в этом отношении, статически (то есть «глобально» или «область действия файла» или «статический член некоторого другой класс »). Но внутри someFunction () мы можем знать, потому что мы знаем, как мы запрашивали распределение.
Теперь вернемся к вашей проблеме:
Как я уже сказал, пример, который вы показываете для измерения использования стека, является точным. В main () вы наверняка знаете, что «localVariable» размещается в стеке. И вы наверняка знаете в Quick (), что currPtrLocation находится в стеке. И если ваш стек уменьшается, вы наверняка знаете, что поскольку main () вызывает Quick (), адрес currPtrLocation в Quick () будет ниже адреса localVariable в main (), поэтому ваша арифметика работает , Он не даст совершенно правильный ответ, потому что в Quick () могут быть другие переменные, которые расположены в ячейках стека, но ниже, чем «currPtrLocation», но ваши измерения будут действительно близки; конечно, так близко, как вы должны заботиться. Какой бы ни была величина ошибки, она является фиксированной ошибкой независимо от того, насколько глубоким является ваш стек вызовов, и если вы повторяете какое-либо значительное количество раз, ошибка в процентах от целого будет незначительной. И последнее: если вы хотите, чтобы решение было переносимым даже в те системы, где стек растет, вы можете определить направление разницы между адресами localVariable и currPtrLocation и вычислить разницу (т. Е. Поменять местами аргументы в вычитание) соответственно.
Что касается использования кучи:
В вашей системе могут быть зацепки, которые вы можете использовать для измерения статистики использования кучи, но если вы не хотите вникать в это, вы можете сделать что-то в соответствии с предложением Synxis, но есть некоторые серьезные проблемы с этим ответом. Прежде всего, предложение Synxis пропускает все служебные данные стека, включая адреса возврата, разлитые регистры и т. Д., Которые не являются незначительными. Во-вторых, если вы используете технику измерения стека, как показано в своем вопросе, нет необходимости тщательно поддерживать сумму выделений для объектов, выделенных в стеке. В-третьих, предполагая, что вы только суммируете выделения объектов, выделенных в куче (размер которых вы можете получить с помощью оператора sizeof ()), вы не можете просто продолжать их суммировать. Вам придется вычесть размеры выделений при их удалении, чтобы ваш «totalSize» сохранял общий размер всех В настоящее время выделенные объекты, и вы хотели бы отдельно отслеживать верхнюю отметку totalSize. Таким образом, вы можете узнать самый большой объем памяти, который использовался вашим алгоритмом за один раз. Без этого вы можете запутаться, когда ваш алгоритм сообщает, что он использует что-то вроде 758 гигабайт, даже если у вас есть только 4 ГБ ОЗУ. И, наконец, независимо от того, выделяете ли вы данный объект в стеке или куче, он может делать свои собственные внутренние выделения в куче. (Если при вызове метода для этого объекта он временно выделяется в стеке, если только вы не добавили свой код отслеживания стека в этот метод, общая сумма стека будет не совсем правильной, как я уже описывал, но ошибка будет продолжайте быть более или менее постоянной, в зависимости от того, выполняет ли метод условные выражения, которые могут изменить его поведение при вызове.) В любом случае, относительно этого «данного объекта», который вы размещаете в стеке или куче; если он выделяет собственную внутреннюю память кучи, если вы не добавите отслеживание выделения кучи для внутренних объектов, вы пропустите любой объем памяти кучи, выделенный этим внутренним объектам. Поэтому, возможно, вам лучше изучить хуки статистики, которые ваша система может сделать доступными.
Теперь, предполагая, что вы хотите самостоятельно выполнять выделение кучи треков … Другой вариант, который вы могли бы изучить, — написать базовый класс, из которого ваш алгоритм может получить все объекты, которые он создает. Ваш базовый класс может переопределить оператор new & Оператор удаления так, что сам базовый класс выполняет все отслеживание totalSize (добавляя для «нового» и вычитая для «удаления»), используя переменную статического класса в базовом классе.
Valgrind действительно может сделать довольно точное измерение для вас. Все, что вам нужно, это написать как можно более простой пример, который вызывает вашу функцию.
например, программа, которая просто печатает свои аргументы (передается в main()
функция) с помощью цикла for и std::cout
произвести следующий вывод:
zaufi@gentop /work/tests $ valgrind --tool=drd --show-stack-usage=yes ./stack-usage-test-1
==26999== drd, a thread error detector
==26999== Copyright (C) 2006-2012, and GNU GPL'd, by Bart Van Assche.
==26999== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==26999== Command: ./stack-usage-test-1
==26999==
./stack-usage-test-1
==26999== thread 1 finished and used 11944 bytes out of 8388608 on its stack. Margin: 8376664 bytes.
==26999==
==26999== For counts of detected and suppressed errors, rerun with: -v
==26999== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Как можно видеть, единственный поток будет потреблять почти 12 КБ в стеке. И определенно большая часть этого пространства была «потрачена впустую» до main()
, Для лучшего измерения необходимо запустить целевую функцию в отдельном потоке. Что-то вроде этого:
#include <iostream>
#include <thread>
int main(int argc, char* argv[])
{
auto thr = std::thread([](){std::cout << __PRETTY_FUNCTION__ << std::endl;});
thr.join();
return 0;
}
Этот код выдаст следующий вывод:
==27029== thread 2 finished and used 1840 bytes out of 8384512 on its stack. Margin: 8382672 bytes.
==27029== thread 1 finished and used 11992 bytes out of 8388608 on its stack. Margin: 8376616 bytes.
это определенно лучше. Таким образом, измеряя функцию, которая ничего не делает, у вас есть минимальное использование стека (в последнем примере это около 1840 байт). Так что, если бы вы вызывали вашу целевую функцию в отдельном потоке, вы должны вычесть 1840 байт (или даже меньше) из результата …
Почти то же самое вы можете сделать сами, используя следующий простой алгоритм:
pthread_attr_setstack()
(или друзья))pthread_join()
успешно, проанализируйте ваш буфер, чтобы найти область, где шаблон, который вы назначили ранее, не сохранился(даже) в этом случае вам лучше сделать первое измерение в потоке, которое ничего не делает — просто чтобы получить минимальный размер использования, как указано выше.
Получить точный общий размер практически невозможно, так как это зависит от вашей платформы, соглашений о вызовах, режима оптимизации и т. Д. Но вы можете получить оценку. Я не считаю параметры, так как они не всегда обрабатываются вызываемой функцией (в зависимости от соглашения о вызовах).
Для этого нет ни C ++, ни возможностей C.
Я не знаю ни одного отладчика, который бы указывал этот номер. Я никогда не использовал Valgrind и co, поэтому я не могу сказать вам, могут ли они показать вам этот номер (я сомневаюсь, что они делают)
Итак, последний вариант: посчитайте сами …
unsigned int totalSize = 0;
int partition(unsigned int A[], int num, int left, int right, int pivot)
{
/// UpdateTotalSize
totalSize += sizeof(unsigned int);
/// /UpdateTotalSize
unsigned int value = A[pivot];
A[pivot] = A[right];
A[right] = value;
/// UpdateTotalSize
totalSize += sizeof(int);
/// /UpdateTotalSize
int store = left;
for(int i = left; i < right; i++)
if(A[i] < value)
{
// This variable does not count in the total size:
// allocated, then deallocated, and so on...
unsigned int tmp = A[i];
A[i] = A[store];
A[store] = tmp;
store++;
}
/// UpdateTotalSize
totalSize += sizeof(int);
/// /UpdateTotalSize
int tmp = A[store];
A[store] = A[right];
A[right] = tmp;
return store;
}
void quick(unsigned int A[], int num, int left = -1, int right = -1)
{
if(num <= 1)
return;
if(left <= -1)
left = 0;
if(right <= -1)
right = right = num - 1;
if(left >= right)
return;
/// UpdateTotalSize
totalSize += sizeof(int);
/// /UpdateTotalSize
int pivot = (left + right) / 2;
/// UpdateTotalSize
totalSize += sizeof(int);
/// /UpdateTotalSize
int pivotNew = partition(A, num, left, right, pivot);
quick(A, num, left, pivotNew - 1);
quick(A, num, pivotNew + 1, right);
}
Обратите внимание, что это просто предварительный расчет от общего размера. Также для этого примера это можно сделать мысленно.
Последний, но тем не менее важный: Этот показатель ненадежен, когда оптимизация включена, поэтому используйте его только без оптимизации!