Двухстековая модель: тесты на скорость
После исследования двухстековой модели
Алексей Маркин задал вопрос:
сравнивалась ли скорость выделения памяти в двух стековой модели со скоростью выделения памяти в куче.
На тот момент такого сравнения не проводись.
Не хотелось тратить на это время: «и так всё понятно».
Но некоторые сомнения посетителей сайта,
высказанные в комментариях, подвигли на создание теста.
Затем делаем то же самое, только выделяем 4 байта не в куче, а стеке. И, конечно, засекаем потраченное время для обоих случаев. При резервировании памяти функцией malloc() полученный указатель сохраняем в ячейке, которая была выделена на предыдущем шаге. Ведь мы же не должны терять этот указатель, он нам нужен будет при освобождении памяти. Количество циклов назначаем такое, чтобы свести к минимуму погрешности замеров. Это число, равное 1024*1024*64, было подобрано экспериментальным путём так, чтобы тестирование на компьютере с процессором AMD A8-4555M c 4Гб памяти занимало несколько минут. Затем ровно такое же количество раз занимаем память в стеке. Точно так же будем записывать полученный указатель в ячейку, выделенную шагом ранее. Вот только мы не можем написать функцию освобождения памяти в стеке. Дело в том, что она освобождается автоматически при выходе из функции командой «xchg ESP, другой стек». Т.е. эта одна команда будет делать то же, что и функция free() в цикле, выполненном 1024*1024*64 раз. А вот и сам тест:
#define СКОЛЬКО 1024*1024*64
//-------------------------------------------------------------------------
int* Размещение в куче (int* предыдущий указатель) {
int* выделенный участок памяти = (int*) malloc (4);
* выделенный участок памяти = (int) предыдущий указатель;
return выделенный участок памяти;
} //-----------------------------------------------------------------------
int* Удаление из кучи (int* текущий указатель) {
int* предыдущий указатель = (int*) *текущий указатель;
free (текущий указатель);
return предыдущий указатель;
} //-----------------------------------------------------------------------
void Тестирование кучи () {
int* предыдущий указатель = 0;
for (int i=0; i < СКОЛЬКО; ++i)
предыдущий указатель = Размещение в куче (предыдущий указатель);
for (i=0; i < СКОЛЬКО; ++i)
предыдущий указатель = Удаление из кучи (предыдущий указатель);
} //-----------------------------------------------------------------------
int* Размещение в стеке (int* предыдущий указатель) {
int* выделенный участок памяти;
Выделить память в другом стеке(выделенный участок памяти, 4);
* выделенный участок памяти = (int) предыдущий указатель;
return выделенный участок памяти;
} //-----------------------------------------------------------------------
void Тестирование стека () {
int* предыдущий указатель = 0;
for (int i=0; i < СКОЛЬКО; ++i) {
ПЕРЕКЛЮЧИТЬ СТЕК;
предыдущий указатель = Размещение в стеке (предыдущий указатель);
ПЕРЕКЛЮЧИТЬ СТЕК;
}
} //-----------------------------------------------------------------------
int main() {
другой стек = Создать другой стек (РАЗМЕР СТЕКА);
time_t start_time, finish_time;
time (&start_time);
Тестирование кучи ();
time (&finish_time);
printf("Время тестирования кучи: %d сек.\n", finish_time - start_time);
time (&start_time);
ПЕРЕКЛЮЧИТЬ СТЕК;
Тестирование стека ();
ПЕРЕКЛЮЧИТЬ СТЕК;
time (&finish_time);
printf("Время тестирования стека: %d сек.\n", finish_time - start_time);
return 0;
};
Запускаем и получаем:
Время тестирования кучи: 190 сек. Время тестирования стека: 7 сек.Разница — в 29 раз. Лучше один раз увидеть, чем сто раз услышать. Читаем далее следующую статью: Размещение объектов переменной длины с использованием одного стека. Почитайте ещё:
Опубликовано: 2015.01.30, последняя правка: 2021.04.29 23:22
Отзывы
Конечно, стек не столь универсален, как куча. Но я и не утверждаю, что стек универсальное решение «всегда и везде». временный объект в стеке будет существовать только пока существует фрейм вызвавшей функции, а если функция возвращает указатель на объект, то наверное предполагается что этот объект можно будет куда то ещё передать / где то сохранить Значит, память в должна выделяться в стеке именно той функции, где данные потребовались. Вот фрагменты обсуждения темы с одним из читателей:Пишу: Возьмём такую функцию на PHP: // Функция: содержимое файла — в строкуКак под строку зарезервировать память, притом не в «куче»? В Си не обойтись без malloc(), в PHP просто это всё спрятано «за кулисами», там всё равно есть что-то аналогичное malloc(). А я резервирую необходимую память в стеке на этапе выполнения. Но не в стеке функции, подобной file2str(), а в стеке той функции, которая вызвала file2str. Задают вопрос: А что если есть цепочка вызовов foo(bar(file2str()))? Отвечаю: Тоже об этом думал — достаточно ли двух стеков или же надо иметь множество стеков. И пришёл к такому выводу. Зачем file2str() вызывается из bar(), а не из foo()? 1) Если результат, возвращаемый file2str(), требуется функции foo() в неизменном виде, то его надо вызывать из foo(): foo () {В этом случае двух стеков достаточно.2) Если функции foo () требуется не результат file2str() в чистом виде, а нужен результат, преобразованный функцией bar(file2str()), то двух стеков тоже достаточно. Ибо в foo () результат file2str() помещён не будет. Там будет что-то другое. О мыши: она не может толкать провод, может только тащить.
Выделяем память под ячейку памяти размером 4 байта функцией malloc(), Хм. Издеваемся над malloc? Ну тогда что бы ему не было так обидно одному страдать. Пусть стек попробует сделать работу malloc. Начнем с 214748364 байт. Хотя что мы — звери? Давайте начнем с 214748360, дадим стеку шанс.
сравнивалась ли скорость выделения памяти в двух стековой модели со скоростью выделения памяти в куче Некоторые и воплощают кучу через стек, когда это подходит. Я как-то тестировал этот подход для настоящего приложения в GNU/Linux, строящего динамические деревья. Прогон в valgrind показывал приблизительно 10-кратное ускорение операции выделения и около 10% для приложения в целом.Написать автору можно на электронную почту |
2015/02/11 12:50, Павел