Можно ли забыть о «куче», если объекты переменной длины хранить в стеке
Когда объект переменной длины хранится в динамической памяти, это, помимо недостатков, имеет некоторые преимущества.
Зарезервировав память под такой объект и получив указатель на неё, можно передавать его сколь угодно назад по цепочке вызовов:
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» провоцирует спагетти-код; как может выглядеть такой код — прекрасно знаем.
А на какие кусочки порезана память в «куче»?
Редкая птица долетит до средины Днепра, чтобы рассмотреть, что же творится в этой «куче».
Преимущества стекового хранения данных очевидны, за ним будущее (хотя кому-то это покажется слишком смелым заявлением).
Чтобы окончательно ответить на вопрос о нужности или ненужности «кучи»,
хорошо было бы определиться: есть ли вообще такие задачи, которые в принципе исключают хранение данных где-то кроме кучи?
На ум приходит только многопоточное программирование.
Чтобы организовать передачу данных между потоками, нужно им выделить общий участок памяти.
Выделить его в «куче» — самое простое решение. Но не факт, что стек в данном случае может быть отвергнут.
В каком случае опасно размещать объект в стеке? Когда время его «жизни» меньше
(которое совпадает с временем «жизни» стека родительской подпрограммы),
чем этого требуют взаимодействующие задачи.
Если же время существования объекта в стеке гарантированно перекрывает требуемое время,
то для его хранения надо выбирать стек.
Читаем далее следующую статью:
Безопасность и размещение объектов переменной длины в стеке.
Почитайте ещё:
Опубликовано: 2014.07.27, последняя правка: 2021.10.20 22:12
Отзывы
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++ усовершенствовать, а именно написать компилятор. Правда, сначала надо язык придумать :)
2018/05/24 00:50, Александр Коновалов aka Маздайщик #
Чтобы окончательно ответить на вопрос о нужности или ненужности «кучи», хорошо было бы определиться: есть ли вообще такие задачи, которые в принципе исключают хранение данных где-то кроме кучи? Навскидку такой пример. Реализация компилятора. Синтаксический анализатор по одной берёт лексемы у лексера и строит из них синтаксическое дерево. Вид этого дерева определяется сугубо в рантайме, связи между узлами тоже. Более того, в дереве могут быть и перекрёстные ссылки, например, узел выражения может ссылаться на узел типа.
Как представлять такую структуру данных в куче, всем очевидно и понятно. Размещение такого дерева без кучи становится сильно неочевидным. Что такое «синтаксическое дерево». Это, например, вот это (иллюстрация, детали опускаю)class Expr {
public:
virtual ~Expr() {}
virtual void compile() = 0;
};
class UnaryOp {
char op; // '-', '&', '*', '!' ...
Expr *expr;
public:
UnaryOp(char op, Expr *expr): expr(expr), op(op) {}
virtual void compile() { . . . }
};
class BinaryOp {
char op; // '+', '-', '/', '*', '%' ...
Expr *left, *right;
public:
BinaryOp(char op, Expr *left, Expr *right)
: op(op), left(left), right(right) {}
virtual void compile() { . . . }
}В этой замечательной структуре данных у нас указатели на полиморфные объекты. Как их распределять на стеке и связывать в структуру данных? Мне это совсем не очевидно. Расскажите, пожалуйста.
2018/05/24 00:52, Александр Коновалов aka Маздайщик #
P.S. Как у Вас на сайте форматировать код в виде кода в комментариях?
2018/05/24 14:28, Автор сайта #
В чём коварство полиморфных объектов? В том, что они имеют разный размер занимаемой памяти. Своё двухстековое распределение памяти я и придумал, размышляя, как размещать полиморфные объекты. И это проблема решается! Но засада не тогда, когда объекты имеют потенциально разный размер, а тогда, когда память под объекты занимается и освобождается в произвольном порядке. А эту проблему можно решить исключительно с помощью «кучи». Так что ответ таков: «задачи, которые в принципе исключают хранение данных где-то, кроме кучи, существуют».
2018/05/24 14:31, Автор сайта #
Как у Вас на сайте форматировать код в виде кода в комментариях? Сайт самописный, сделан без CMS. Возможности тут небогатые, поэтому пока никак. Зато сайт не взламывают :)
2018/05/25 00:00, Александр Коновалов aka Маздайщик #
А про размещение синтаксического дерева на стеке я подумал вот что. Можно разрешить существование объектов, которые содержат внутри полиморфные объекты неизвестного размера (вроде синтаксического дерева, если оно действительно дерево). Но с одним ограничением: тип вложенных объектов фиксируется при конструировании и за время существования объекта не меняется.
Так что, наверное, на стеке (двух стеках) можно размещать и такое синтаксическое дерево. Правда, при конструировании будут вызываться конструкторы копирования для создания поддеревьев. И чем дольше строится дерево и больше оно становится, тем медленнее оно создаётся.
2018/05/26 00:50, Автор сайта #
А чтобы построить его одним махом, то и описать его надо одним махом. Добавить свой отзыв
Написать автору можно на электронную почту
mail(аt)compiler.su
|