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

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

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

Опубликовано: 2015.01.30, последняя правка: 2021.04.29    23:22

ОценитеОценки посетителей
   █████████████████ 5 (38.4%)
   ████ 1 (7.69%)
   ████ 1 (7.69%)
   ████████████████████ 6 (46.1%)

Отзывы

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

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

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

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

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

Компилятор 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, Прохожий          #3 

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

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

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

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

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

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

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

✅  2016/03/25 02:27, rst256          #7 

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

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

✅  2019/01/01 18:08, Comdiv          #8 

сравнивалась ли скорость выделения памяти в двух стековой модели со скоростью выделения памяти в куче

Некоторые и воплощают кучу через стек, когда это подходит. Я как-то тестировал этот подход для настоящего приложения в GNU/Linux, строящего динамические деревья. Прогон в valgrind показывал приблизительно 10-кратное ускорение операции выделения и около 10% для приложения в целом.

Добавить свой отзыв

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

Авторизация

Регистрация

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

Карта сайта


Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

●●  Помеченные комментарии

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

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

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

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

●  Циклы

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

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

●  Изменение приоритетов операций

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

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

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

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

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

●●  О неправомерном доступе к памяти через указатели

●  Обработка ошибок

●  Функциональное программирование

●●  Нечистые действия в чистых функциях

●●  О чистоте и нечистоте функций и языков

●●  Макросы — это чистые функции, исполняемые во время компиляции

●●  Хаскелл, детище британских учёных

●●  Измеряем замедление при вызове функций высших порядков

●●  C vs Haskell: сравнение скорости на простом примере

●●  Уникальность имён функций: за и против

●●  Каррирование: для чего и как

●●  О тестах, доказывающих отсутствие ошибок

●  Надёжные программы из ненадёжных компонентов

●●  О многократном резервировании функций

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

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

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

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

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

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

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

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

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

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

●●  Изменение длины объекта в стеке во время исполнения

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

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

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

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

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

●  Реализация параметрического полиморфизма

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

Компилятор

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

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

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

Новости и прочее




Последние отзывы

2024/10/15 22:49 ••• Неслучайный читатель
Русский язык и программирование

2024/10/14 18:05 ••• MihalNik
Энтузиасты-разработчики компиляторов и их проекты

2024/10/01 09:36 ••• Иван
О русском ассемблере

2024/09/30 00:08 ••• Автор сайта
Новости и прочее

2024/09/29 23:40 ••• Автор сайта
Десятка худших фич C#

2024/09/29 13:10 ••• Автор сайта
ЕС ЭВМ — это измена, трусость и обман?

2024/09/22 21:08 ••• Вежливый Лис
Бесплатный софт в мышеловке

2024/09/05 17:44 ••• Автор сайта
Правила языка: алфавит

2024/09/04 00:00 ••• alextretyak
Циклы

2024/09/02 22:24 ••• Автор сайта
Постфиксные инкремент и декремент

2024/08/26 00:37 ••• Автор сайта
Что нового с 1966 года?

2024/07/26 13:32 ••• Бурановский дедушка
Программирование исчезнет. Будет дрессировка нейронных сетей

2024/06/21 00:20 ••• Gudleifr
О превращении кибернетики в шаманство