Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Прочее

Двухстековая модель: тесты на скорость

После исследования двухстековой модели Алексей Маркин задал вопрос: сравнивалась ли скорость выделения памяти в двух стековой модели со скоростью выделения памяти в куче. На тот момент такого сравнения не проводись. Не хотелось тратить на это время: «и так всё понятно». Но некоторые сомнения посетителей сайта, высказанные в комментариях, подвигли на создание теста.

Тест на скорость
            Делаем небольшой эксперимент: многократно выделяем память под ячейку памяти размером 4 байта функцией malloc(), затем освобождаем занятую память функцией free().

            Затем делаем то же самое, только выделяем 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 раз. Лучше один раз увидеть, чем сто раз услышать.

            Читаем далее следующую статью: Размещение объектов переменной длины с использованием одного стека.

Почитайте ещё:

Последняя правка: 2016-03-18    09:43

ОценитеОценки посетителей
   █████████████████████ 1 (50%)
   ▌ 0
   ▌ 0
   █████████████████████ 1 (50%)

Отзывы

     2015/02/11 12:50, Павел

Не указан ни компилятор ни используемый менеджер кучи. Так то можно было и 1 к 9000 нарисовать. Плюс вопрос про адрес возврата (см. предыдущую статью), очевидно, не учтён, а это ещё накладные расходы. Однако очевидно, что операция sub esp, xxx быстрее чем обращение к менеджеру памяти. С другой стороны вопрос, когда целесообразно использовать именно такой подход - ведь такой временный объект в стеке будет существовать только пока существует фрейм вызвавшей функции, а если функция возвращает указатель на объект, то наверное предполагается что этот объект можно будет куда то ещё передать / где то сохранить, т.е. его придётся копировать из стека в динамическую память. Нужно это учитывать.

     2015/02/11 12:51, Павел

Кстати картинка к статье нерусская - у нас правостороннее движение. Хотя где у мыши перёд?

     2015/02/11 17:43, Автор сайта

Компилятор VC++, менеджер кучи – стандартный. Цели «накрутить» результат не было – иначе бы я не публиковал исходник теста. Кстати, было бы интересно попробовать на других компиляторах. Я ожидал большего превосходства стека, но что получилось – то получилось.

Конечно, стек не столь универсален, как куча. Но я и не утверждаю, что стек универсальное решение «всегда и везде».

временный объект в стеке будет существовать только пока существует фрейм вызвавшей функции, а если функция возвращает указатель на объект, то наверное предполагается что этот объект можно будет куда то ещё передать / где то сохранить

Значит, память в должна выделяться в стеке именно той функции, где данные потребовались. Вот фрагменты обсуждения темы с одним из читателей:

Пишу: Возьмём такую функцию на PHP:
// Функция: содержимое файла – в строку
function file2str($file_name) {
if (is_file($file_name)) {
$len = filesize ($file_name);
if ($len > 0) {
$hand = fopen ($file_name, "r");
$str = fread ($hand, $len);
fclose ($hand);
} }
return $str;
}
Как под строку зарезервировать память, притом не в «куче»? В Си не обойтись без malloc(), в PHP просто это всё спрятано «за кулисами», там всё равно есть что-то аналогичное malloc(). А я резервирую необходимую память в стеке на этапе выполнения. Но не в стеке функции, подобной file2str(), а в стеке той функции, которая вызвала file2str.

Задают вопрос: А что если есть цепочка вызовов foo(bar(file2str()))?

Отвечаю: Тоже об этом думал – достаточно ли двух стеков или же надо иметь множество стеков. И пришёл к такому выводу. Зачем file2str() вызывается из bar(), а не из foo()?

1) Если результат, возвращаемый file2str(), требуется функции foo() в неизменном виде, то его надо вызывать из foo():
foo () {
x = file2str();
bar (x);}
В этом случае двух стеков достаточно.

2) Если функции foo () требуется не результат file2str() в чистом виде, а нужен результат, преобразованный функцией bar(file2str()), то двух стеков тоже достаточно. Ибо в foo () результат file2str() помещён не будет. Там будет что-то другое.

О мыши: она не может толкать провод, может только тащить.

     2015/08/25 14:11, Прохожий

А почему нельзя называть испытания испытаниями, а не "тестами"?

     2015/08/26 11:51, Автор сайта

Можно, если они были. Но в данном случае проводились, согласно толковому словарю (tolkslovar.ru), тесты.

     2015/10/01 23:25, Прохожий

"Тесты" - это и есть испытания, если говорить по-русски.

     2015/10/01 23:51, Автор сайта

Укажите мне учебник русского языка или словарь, которыми должно руководствоваться.

     2016/03/25 02:27, rst256

Выделяем память под ячейку памяти размером 4 байта функцией malloc(),

Хм. Издеваемся над malloc?
Ну тогда что бы ему не было так обидно одному страдать.
Пусть стек попробует сделать работу malloc.
Начнем с 214748364 байт, хотя что мы звери давайте начнем с 2147483, дадим стеку шанс.

Написать отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Устарел ли текст как форма представления программы

Русский язык и программирование

Многоязыковое программирование

Синтаксис языков программирования

Синтаксический сахар

Некоторые «вкусности» Алгол-68

«Двухмерный» синтаксис Python

Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

Должна ли программа быть удобочитаемой?

Стиль языка программирования

Тексто-графическое представление программы

●  Разделители

●  Строки программы

●  Слева направо или справа налево?

Комментарии

●  Длинные комментарии

●  Короткие комментарии

●  Комментарии автоматической генерации документации

●  Нерабочий код

Нужны ли беззнаковые целые?

Шестнадцатиричные и двоичные константы

Условные операторы

Переключатель

Циклы

●  Продолжение цикла и выход из него

Некошерный «goto»

Операции присвоения и проверки на равенство. Возможно ли однаковое обозначение?

Так ли нужны операции «&&», «||» и «^^»?

Постфиксные инкремент и декремент

Почему в PHP для конкатенации строк используется «.»?

Указатели и ссылки в C++

Использование памяти

Почему динамическое распределение памяти – это плохо

Как обеспечить возврат функциями объектов переменной длины?

●  Типы переменного размера (dynamically sized types, DST) в языке Rust

●  Массивы переменной длины в C/C++

●  Размещение объектов в стеке, традиционный подход

●  Размещение объектов переменной длины с использованием множества стеков

●  Размещение объектов переменной длины с использованием двух стеков

●  Реализация двухстековой модели размещения данных

●  Двухстековая модель: тесты на скорость

●  Размещение объектов переменной длины с использованием одного стека

Можно ли забыть о «куче», если объекты переменной длины хранить в стеке

Безопасность и размещение объектов переменной длины в стеке

Массивы, структуры, типы, классы переменной длины

О хранении данных в стеке, вместо заключения

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Компьютерный юмор

Прочее

Последние комментарии

2018/07/03 03:27, rst256
Философия языка

2018/06/25 15:10, Автор сайта
Продолжение цикла и выход из него

2018/06/14 00:37, rst256
Лень — двигатель прогресса

2018/05/31 18:52, rst256
Программирование без программистов — это медицина без врачей

2018/05/31 17:57, rst256
Циклы

2018/05/31 17:50, Comdiv
Разбор цепочек знаков операций

2018/05/31 17:42, Comdiv
Как отличить унарный минус от бинарного

2018/05/30 18:57, Александр Коновалов aka Маздайщик
Раскрутка компилятора