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

ОценитеОценки посетителей
   █████████████████████ 2 (50%)
   ▌ 0
   ▌ 0
   █████████████████████ 2 (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 байт. Хотя что мы — звери? Давайте начнем с 214748360, дадим стеку шанс.

     2019/01/01 18:08, Comdiv          # 

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

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

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

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

Авторизация

Регистрация

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

Карта сайта


Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

●  Циклы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компилятор

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

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

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

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




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

2019/12/12 14:11 ••• Геннадий Тышов
Почему обречён язык Форт

2019/12/05 23:29 ••• Автор сайта
Слоны в комнате

2019/12/03 22:45 ••• Автор сайта
Следующие 7000 языков программирования: заключение

2019/12/03 22:36 ••• Автор сайта
Наблюдаемая эволюция языка программирования

2019/11/30 20:55 ••• Сергей
Каким должен быть язык программирования?

2019/11/09 21:27 ••• kt
Программирование без программистов — это медицина без врачей

2019/11/07 10:58 ••• kt
Признаки устаревшего языка

2019/10/28 23:55 ••• Автор сайта
Типы в инженерных задачах

2019/10/15 16:32 ••• kt
Модификация исполняемого кода как способ реализации массивов с изменяемыми границами

2019/10/07 14:15 ••• Автор сайта
О наименовании проекта и языка программирования

2019/09/19 15:23 ••• kt
Некошерный «goto»

2019/09/13 16:38 ••• Автор сайта
Программирование исчезнет. Будет дрессировка нейронных сетей