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

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

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

char* f3 (. . .) {
   char* ptr = malloc(size);   . . .   return  ptr;
}
char* f2 (. . .) {
   char* ptr = f3(. . .);   . . .   return  ptr;
}
char* f1 (. . .) {
   char* ptr = f2(. . .);   . . .   return  ptr;
}
            Что будет, если память будет зарезервировано в стеке и указатель ptr из примера выше будет передан ниже по цепочке вызовов? Участок памяти, адресуемый ptr, может быть запорчен в любой момент последующими вызовами функций. Ведь вызванная функция может пользоваться тем же участком стека, что и функция f3.

            Как с этим бороться? Если переданный функции объект хранится не в её собственном стеке, а в стеке вызванной функции, то необходимо скопировать объект их одного стека в другой. Такая техника применяется в C++ при возврате объектов фиксированной длины не элементарных типов. Это не очень хорошая идея. Любое копирование, особенно больших объектов – это неэффективная трата ресурсов процессора. Такое копирование должно делаться, чтобы избежать порчи данных, но компилятор обязан отследить такую ситуацию и выдать предупреждение, чтобы программист задумался об ином построение алгоритма.

            Чтобы возвращать из функций указатель, не копируя данные, можно предусмотреть механизм вызова функций со многими стеками (мы его обсуждали выше). Это даст возможность резервировать память в стеке той функции, которая является «конечным потребителем». Многостековая модель окажется немного сложнее двухстековой. Но, в сравнении с хранением данных в «куче», эта разница будет даже не в разы, а в десятки и сотни раз не пользу «кучи».

            В подавляющем большинстве случаев за счёт иного порядка вычислений можно избежать как копирования (при нашей одно- или двухстековой модели) объектов, так и размещения их в «куче». Здесь уместно привести две аналогии. Программирование с «goto» – это модель вычислений с бо́льшими возможностями, чем без него. Программирование без «goto» – это усечённый вариант программирования с «goto». Но за счёт такого ампутирования вычисления приобретают строгий вид и делают возможным (в теории) доказательное программирование. Другая аналогия. Чистые функции – это усеченный вариант обычных функций в программировании. Но за счёт отказа от взаимодействия с контекстом чистые функции легки в отладке, хорошо распараллеливаются, их можно использовать в «ленивых» вычислениях и т.д. Этих преимуществ достаточно, чтобы выделить их в отдельную сущность.

            Использование «кучи» и прочие послабления в дисциплине пользования памятью – это «goto» в алгоритмах. «goto» провоцирует спагетти-код; как может выглядеть такой код – прекрасно знаем. А на какие кусочки порезана память в «куче»? Редкая птица долетит до средины Днепра, чтобы рассмотреть, что же творится в этой «куче». Преимущества стекового хранения данных очевидны, за ним будущее (хотя кому-то это покажется слишком смелым заявлением).

            Чтобы окончательно ответить на вопрос о нужности или ненужности «кучи», хорошо было бы определиться: есть ли вообще такие задачи, которые в принципе исключают хранение данных где-то кроме кучи? На ум приходит только многопоточное программирование. Чтобы организовать передачу данных между потоками, нужно им выделить общий участок памяти. Выделить его в «куче» - самое простое решение. Но не факт, что стек в данном случае может быть отвергнут.

            В каком случае опасно размещать объект в стеке? Когда время его «жизни» меньше (которое совпадает с временем «жизни» стека родительской подпрограммы), чем этого требуют взаимодействующие задачи. Если же время существования объекта в стеке гарантированно перекрывает требуемое время, то для его хранения надо выбирать стек.

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

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

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

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

Отзывы

     2015/01/22 13:18, programmer

Не понял идеи. Стек - это по сути, упрощенная "куча", для быстродействия. Автор, не нужно писать бред - достаточно использовать оптимизированную для определенной задачи кучу, хотя это потребует ассемблерных программ, но в результате быстродействие может быть лучше чем с использованием операций со стеком.

     2015/01/22 19:30, Автор сайта

Стек и «куча» - это разные концепции использования памяти. Стек – это гораздо более простая дисциплина пользования памятью. За счёт своей простоты она поддерживается процессором. Для резервирования в памяти требуется всего одна операция процессора. Если сложную модель использования памяти удаётся свести к очень простой – так это здорово! Растёт скорость программ, их надёжность, экономится память. Не утверждаю, что это можно всегда и везде, но, вероятно, в более половины случаев.
Почитайте поподробнее о стеке (лучше всего – в учебниках по ассемблеру), вам понравится.

     2015/01/22 18:58, programmer

Ваше предположение о моем незнании принципов работы стека несколько некорректное, т.к. с ассемблером мне приходится работать достаточно глубоко и непосредственно. Как модель, "куча" может иметь разные алгоритмы выделения и освобождения, в том числе в форме стека. Скорость работы как раз в современных процессорах сомнительная в качестве универсального решения, есть смысл использовать альтернативные алгоритмы - посмотрите тайминги операций, даже команды оставлены скорее для маркетинга и совместимости, чем для реальной необходимости, поскольку они часто могут быть заменены более эффективной последовательностью команд, а иногда проще отказаться от стека по причине производительности подсистемы памяти (когда это возможно) и использовать один дополнительный регистр, а в случае необходимости использовать несколько стеков, в то время как набор "стековых" команд предусматривает один регистр стека - поэтому поддержка стековых операций или кривая или вообще ненужная (как команды LEAVE и ENTER), остается только необходимость впарить еще несколько поколений процессоров, по кусочку. Если хотите, можно подискутировать на тему - по командам наиболее распространенных современных процессоров - сейчас даже компиляторы более не используют стековые операции как раньше - и в процессорах не предвидится дополнительных блоков полезного ускорения стековых операций, типа объединения многочисленных извлечений или записей в стек. А архитектуры типа Itanium не общедоступны и неоправданно дороги для обычных пользовательских задач.

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

Куча предполагает произвольный порядок выделения памяти и произвольный порядок её освобождения. Всё таки посоветовал бы сходить по этой ссылке и посмотреть на код, выделяющий память в куче. Как бы не напускали тумана маркетологи Intel, код в одну-две-три машинной инструкции всегда предпочтительнее кода в несколько сот инструкций. Потому что сотни команд в конвейер процессора не поместятся. К тому же в этих сотнях есть множество команд перехода, которые ломают возможность одновременного исполнения команд из конвейера. Да, сейчас упор делаю не на стек, а больше на регистры. Вызовы функций в стиле «fastcall» помещают операнды не в стек, а в регистры.

Но вот какое дело. При всё более активном упоре на объектно-ориентированное программирование выплывает одна проблема: объекты нельзя поместить в регистр. Объекты имеют внутри себя ссылку на vtable (таблицу виртуальных методов). Размер этой ссылки совпадает по размерности с регистром процессора. Получается, что объект поместиться в регистр не может, только в память. Следовательно, мы не можем вернуть из функции объект, поместив его в регистр. В регистре может быть только указатель на него, а сам он должен быть в памяти. Мы не можем вернуть объект из функции в регистре – опять только через память.

     2015/01/23 17:37, programmer

Нет, все определяется, можно ли поместить алгоритм в 32к памяти, все остальное - просто для бекапа (точнее данные), а также возможность распределить доступ по выровненных участках размером 4к (грубо говоря, кеш остается беспроблемным, пока это условие соблюдается). А количество команд не имеет роли, если они распределены пачками в 16 байт и имеют минимальное количество внутренних операций - грубо говоря, процессор их интерпретирует и распределяет на несколько мелких специализированных, благодаря чему достигается производительность в несколько операций на такт. А 16 байт процессор загружает за каждый такт, вопрос только сколько из них используется рационально - и как раз в этом и есть обман маркетологов, потому что следовало уже давно изменить архитектуру так, чтобы можно было впихнуть максимальное количество операций. И то, следует учитывать, что доступ к этим самым 32к занимает целых 4 такта.

     2015/01/23 17:47, programmer

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

     2015/01/25 13:50, Автор сайта

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

А какой смысл в этом? Достаточно в цепочке вычислений иметь команду перехода или команду вызова подпрограммы – и всё, что идёт после таких команд, часто не пригождается. Процессор вынужден загрузить в конвейер новую цепочку. Вы сами заметили это:

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

Длинные цепочки без переходов – скорее исключение, чем правило.

Возможно в будущих поколениях это будет исправлено

А как? Этого не могут сделать компании с миллиардными бюджетами. Понадобится дерево (точнее – граф), предвосхищающее ход вычислений и процессор, который производит вычисления во всём графе.

Здесь же предлагаются эффективные решения, которые будут работать, не дожидаясь светлого будущего.

     2015/01/25 19:19, programmer

Очень большой и очевидный смысл - можно использовать, например, условные команды (как в архитектуре ARM), чтобы избежать переходов во многих случаях. Но маркетологи, видимо, решили иначе. По поводу возможных возражений об архитектуре - нет, там просто стоит что-то вроде интерпретатора и очереди команд, оптимизированных по времени выполнения для более быстрых процессоров (и вообще, CISC и RISC - это чистые условности), могли бы и сделать без особых трудностей.

     2015/01/25 19:24, programmer

Если команда имеет очевидное указание адреса, адрес доступен непосредственно во время декодирования, его содержимое можно загрузить как адрес перехода, возможный, все равно его потом нужно проверять. Никаких графов не нужно. При неявном указании тоже можно оптимизировать несколько случаев, когда содержание регистра становится очевидным до выполнения команды.

     2015/01/26 13:14, Автор сайта

Наша дискуссия стала течь в непродуктивном русле. Я считаю, что короткий, компактный код без переходов лучше, быстрее длинного, содержащего переходы. Вы считаете иначе? Прекрасно, Ваше право. Но не будем больше плести словесные кружева вокруг одного и того же.

     2015/01/26 23:54, programmer

Пока что дискуссии нет в принципе - я лишь указываю на недостатки или отсутствие какой-либо обоснованной позиции автора. Интересно посмотреть на заблуждения в диалоге (т.е. для меня лично информативность всего этого в составлении или расширении списка популярных заблуждений, они обычно очень стандартные и редко получается увидеть что-либо новое) - т.к. по статье не всегда видно - сейчас даже приводятся аргументы вроде преимуществ линейного кода, о которых речь собственно не шла. Я, естественно, смотрел другие статьи, но они менее противоречивы, и собственно, нет толку спорить, т.к. будет просто разница в подходах и объективно сказать будет нечего.
Хотите задать тему для дискуссии по которой Ваши знания достаточны и действительно можно о чем-то дискутировать, задавайте (и для меня тоже интересно проверить свои знания, т.к. в прошлом у меня все же было несколько ситуаций, когда я сморозил чего-то не то, что впредь заставило меня быть более осторожным и проверять свои собственные выводы).

     2015/01/27 14:49, Автор сайта

Если я Вас не убедил, что компактный код быстрее, давайте я сошлюсь на мнение посторонних людей о том, что он лучше. Почитайте: энергопотребление сервера под управлением ОС «Колибри» уменьшается в 1,5-4 раза и он может работать при пониженном на 25-30% входном напряжении (в отличие от Windows и Linux). Ветка форума «KolibriOS на производстве».

     2015/01/27 12:40, programmer

Я посмотрел дискуссию. В целом, можно выделить следующие моменты:
Энергопотребление в современных процессорах скорее будет зависеть от использования функций перевода их в соответствующие состояния, вне зависимости от размера кода.
Код операционной системы обычно включает множество сервисов, в которых можно выделить достаточно много отдельных компонентов. То, что Линукс и Windows неэффективны при интенсивном использовании средств операционной системы, не значит, что это происходит только из-за размера кода. Он ограничен кучей стандартов (типа для вызова одной функции ОС нужно сделать десяток вызовов внутренних функций и переадресаций) и его неэффективностью.
Ошибок может быть меньше из-за того, что внутренний кеш процессора защищен кодами коррекции, если код меньше подгружается, вероятность ошибок меньше.
Для отдельного алгоритма, а не для приложения с кучей компонентов размер кода не является критическим в пределах нескольких десятков килобайт, что вообще то справедливо для выделенных алгоритмов, оптимизированных для выполнения строго определенной задачи без интенсивного использования средств операционной системы или кучи модулей.
В чем, собственно, это все должно убедить меня лично ?

     2015/01/30 00:23, Автор сайта

Проведённые тесты показывают, что в куче память выделяется во много раз медленнее. Практика не посрамила здравый смысл.

     2015/01/31 13:58, programmer

Практика показывает эффективность определенных реализаций. Они обычно стандартные, эффективные можно увидеть только в некоторых специализированных программах - например, базы данных - в них выделение памяти под новые записи достаточно хорошо оптимизировано. Более того, для эффективной работы следует иметь несколько альтернатив выделения памяти - несколько реализаций "кучи", заточенных под разные сценарии.

     2015/01/31 19:48, Автор сайта

Если вы мне покажите специализированные версии malloc() или new в пакете MS Visual Studio – тогда можно будет поверить, что широкие массы разработчиков могут пользоваться специализированными решениями. Microsoft применила при реализации Word нестандартный менеджер памяти, но вы видели его где-то в продаже? Или в GCC есть специализорованные версии? Я уж промолчу про языки, где управление памятью автоматическое. В них вообще невозможно поменять дисциплину использования памяти.

     2015/02/02 08:39, programmer

Естественно, в стандартных пакетах специализированные версии не представлены. Разработчикам остается использовать или собственные разработки или не общедоступные средства разработки. Тем не менее, при наличии таковых проблема с быстродействием кучи решается.

     2015/02/11 13:36, Павел

Достать или написать специализированную версию malloc проще, нежели внедрить двух и более стековую модель (для этого возможно потребуется написать компилятор). Комментарии ни-о-чём. Какие то кеши, страницы, набор инструкций. А тема статьи - отказ от объектов в куче.

     2015/02/11 18:08, Автор сайта

Да что вы, отчего же проще? Прямо сейчас берите приведённые макросы с ассемблерным кодом и вставляйте в свою программу. Но я задался целью не C/C++ усовершенствовать, а именно написать компилятор. Правда, сначала надо язык придумать :)

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

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

Авторизация

Регистрация

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

Карта сайта


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комментарии

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

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

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

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

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

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

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

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

Циклы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Компилятор

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

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

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

Прочее

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

2018/04/16 15:09, Олег
Русский язык и программирование

2018/04/02 22:42, rst256
Программирование без программистов — это медицина без врачей

2018/03/25 21:14, Денис Будяк
Энтузиасты-разработчики компиляторов и их проекты

2018/03/21 23:37, Marat
Почему обречён язык Форт

2018/03/10 20:05, Comdiv
«Двухмерный» синтаксис Python

2018/02/24 14:51, Эникейщик
Русской операционной системой должна стать ReactOS

2017/12/12 13:32, Comdiv
Отечественные разработки

2017/11/05 17:26, rst256
Электроника без электронщиков