Почему динамическое распределение памяти — это плохо
Читаем далее следующую статью: Как обеспечить возврат функциями объектов переменной длины? Почитайте ещё:
Опубликовано: 2014.07.27, последняя правка: 2018.10.29 16:01
Отзывы
Вот поэтому есть сомнения насчёт Java. C++ позволяет проверить догадки, предоставляя исполняемый код. Кода Java не видел, поэтому не могу ни подтвердить Ваши слова, ни опровергнуть. Вы можете взять на себя труд: создать массив с размером, известным только во время выполнения, и посмотреть код виртуальной машины?
Автозамена кучи на стек имеет смысл для маленьких объектов: 1) локальность данных 2) сокращение труда сборщика мусора — ему не нужно будет чистить память от мелких временных объектов 3) так как другой поток не может залезть в наш стек, не нужно применять блокирование, даже если оно прописано в программе
Язык, лишённый кучи, будет неполноценным, придётся делать костыли.
Можно ли вообще избавиться от кучи? Интересный вопрос как с точки зрения теории, так и практики. Можно ли алгоритмы с произвольным порядком освобождения памяти преобразовать в эквивалентные, но со строгим порядком? Например, оттягивая фактическое освобождение памяти, помечая её, как освобождённую. Ну и практический вопрос: можно ли выделить какой-то особый класс задач, который нуждается именно в произвольном порядке освобождения памяти? В чисто функциональных языках программирования предлагаемый метод, мне видется, имеет высокие шансы вообще обходиться без кучи.
Ссылки на участки памяти в «куче» могут быть потеряны. Ну таким Макаром можно с тем же успехом и в стеке данные про.. хм потерять, или на ноль поделиться, хотя последнее уже кое где закрыли (видать были прецеденты) в некоторых языках 1/0 возвращает или NaN(тупо переносим ошибку подальше от места возникновения) или huge(означает "большое число" — бесконечность, 80% ошибок успешно исправляется, оставшиеся 20% всплывут не скоро). Как то неправильно ошибки, возникшие в прикладном коде, вешать на библиотеку.
f1(f2(f3(...)))Функция f3 выделяет память в стеке функции f2 и записывает указатель на неё в стеке f2. Когда f2 заканчивает работу и передаёт управление f1, то перестают существовать как указатель на память в стеке f2, так и сама память в стеке f2 (она освобождается).
f1(f2(f3(...))) А зачем такие заморочки? Можно ведь выделять сразу всё в стеке f1 и запоминать указатель на стек при входе в следующие функции. А при выходе просто смещать указатель да и всё. И не надо кучи стеков.Я просто не могу понять как это реализовать в другом виде. Ну вот есть f3, да? Вот насоздавал я там кучу объектов, типа 1,2,3,4,5. Но вот удалять мне их потом надо фиг пойми как да ещё каждый раз по-разному. Вот в первый прогон функции удаляются 4,5,1,3,2. Вот второй прогон удаляются 5,1,4,3,2. Как это будет реализовано в стеке? И стек и куча они ведь "плоские", типа лента адресов и любое удаление в порядке отличающимся от создания "рвет" эту ленту создавая "дыры" в занятой памяти. Какой такой простой алгоритм есть для того чтобы уменьшать стек при произвольном удалении объектов да ещё и быстрей кучи чтобы получилось? Стек красота, когда Вы точно знаете как и что будет удаляться, тогда и данные можно пихать так, чтобы просто потом сместить указатель на вершину стека одной-двумя командами. Да и многостековость легко переносится на многокучевость. Создал на каждую функцию свою кучу — вышел из функции, потер весь блок да и вся проблема.
Потеря эффективности. Простейшие реализации функций malloc() и free() имеют длину несколько сотен строк. А уж продвинутые — тем паче длиннее. Но дают возможность работы с объектами динамической природы. То есть это не то чтобы грех. Это просто решение других задач. От стека ведь как правило никто не отказывается — простые переменные обычно там и лежат.Некорректная работа с памятью в куче может приводить к её утечкам. Причиной может быть как ошибки в библиотечных функциях управления памятью, так и ошибки в программе при ручном управлении. Ну это так же "Некорректная работа с памятью в стеке может приводить к её утечкам". Я вот как отчаянный паскалист скажу так: программист на С++ с легкостью решает не существующие в Паскале проблемы. Откажитесь Вы от прямого доступа к памяти, да и все проблемы. Есть классы и объекты, есть динамические массивы. Зачем вот ковыряться в этих указателях? Оно вот надо только для очень узких задач. Вон в C# для этого надо специально переключаться на неуправляемый код. Вот Вам идеальное решение, раз переключились значит понимаете, что "Некорректная работа с памятью в куче может приводить к её утечкам.", то есть сами себе Буратино, что не смогли корректно составить алгоритм, а не валить всё на компилятор.Фрагментация памяти. Если «до упора» выделять память по одному байту, а потом освободить занятые блоки памяти, но не все, а через один, то память будет нарезана на множество маленьких кусочков, которые невозможно использовать. Сложные алгоритмы распределения памяти могут обходить эту проблему путём перемещения фрагментов и изменения указателей. Но это опять расходование вычислительных ресурсов. Не знаю, в какой куче память выделяется побайтно. Память выделяется поблочно. Размер блока определяет создатель системы исходя из каких-то своих измышлений (может тесты проводит, а может ему так нравится, а может ось любит давать память приложению кратно 16-ти байтам). По поводу ресурсов — да, но других решений нет. Варианта там 2 обычно. Самый простой — сразу перемещать последний блок на место освободившегося. Вариант 2 — это дефрагментация по наступлению определенного события (например, 30 процентов блоков не используются и т.д.). Вот раньше была такая частая процедура на XP — дефрагментация диска. Вот Вам прямая аналогия — диск, он ведь тоже не произвольное расположение, а лента (физически наверно спираль или круги).Алгоритмы динамического распределения памяти либо просты, либо хороши. Более того, одни алгоритмы хорошо работают для одного класса задач, а другие — для другого. Так и стек. Иначе бы других структур не было бы в принципе. Ни очередей, ни массивов, ни более сложных коллекций. Зачем всё усложнять, когда есть такой вот эффективный стек? Это ведь можно так напороться на скальпель монаха Оккама, который говорит в стиле Маяковского — если звезды на небе зажигаются, значит это кому-нибудь нужно. Иными словами, если помимо стека придумывают что-то ещё, значит стек не может решить всех задач. Это я даже без всяческих тестов могу утверждать.Некоторые алгоритмы динамического распределения памяти выделяют память быстро, но в ситуациях, когда память заканчивается и нужно обеспечить «сборку мусора», начинают «тормозить». Имея хорошее среднее время отклика, они не могут обеспечить его гарантированный минимум. Поэтому в системах реального времени используют другие алгоритмы. Они имеют гарантированное время отклика, но среднее время отклика у них выше. Это специализация. Она не означает, что стек круче чем всё остальное. Стек круче в своей области применения (иначе бы его просто не использовали). Но в других задачах круче другие структуры (иначе их бы не использовали :) ).Ссылки на участки памяти в «куче» могут быть потеряны. В этом случае память не может быть освобождена, поскольку её адрес становится неизвестен программе. Для решения проблемы используют «умные указатели», которые хоть и решают задачу, но опять же, ценой дальнейшей потери эффективности. Как это ссылка на участок памяти в "куче" может быть потеряна? Это что-то из области зеленых человечков. Если программист напортачил в коде, то так и надо говорить — это программист уже неделю не был на свежем воздухе и глаза у него в куче, а не ссылка там. Я выше уже написал Вам как решаются подобные проблемы — оторвать руки программисту, решающего прикладную (не системную!) задачу с помощью прямого доступа к памяти по указателям. И дело здесь не а куче, а в человеческом факторе, будете маскировать источник проблемы, будете всё время бороться с её проявлением. Нужно честно поставить диагноз — у программ проблемы с утечками памяти потому что у программистов руки из задницы растут, а язык позволяет им оттуда расти. И решение соответствующие — либо руки за спину скотчем замотать либо в языке сделать выстрел в ногу жутко утомительным занятием.
Если Вы считаете, что пользоваться кучей в таких случаях — не грех («Десятки языков делают это!»), то Вы — сторонник развития языков программирования по второму пути (см. классификацию языков программирования в начале статьи «философия языка»). Наша же цель — сделать язык программирования первого типа, т.е. пригодного для системного программирования, выжимающий из оборудования максимум. Если есть возможность обойтись без кучи и сборки мусора для целого класса задач, то мы не можем это игнорировать.
Весьма часто память под объект можно выделить в стеке. Для этого, казалось бы, есть все условия: время существования объекта совпадает со временем существования функции, которая им владеет. Но есть загвоздка: существующие языки умеют хранить объекты в стеке только тогда, когда они фиксированного размера. А если переменного — пиши пропало. Без кучи обходиться не умеют. Этот цикл статей как раз посвящён тому, чтобы научить некоторый класс задач обходиться без кучи. Это не вопрос языка. Это вопрос реализации языка. Тут, наверно, нужно провести моделирование имеющейся проблемы. Построить стек и пытаться реализовать алгоритм предсказания уничтожения данных.Если Вы считаете, что пользоваться кучей в таких случаях — не грех («Десятки языков делают это!»), то Вы — сторонник развития языков программирования по второму пути (см. классификацию языков программирования в начале статьи «философия языка»). Я не то, чтобы против. Я хочу понять, что это действительно эффективно и за счет чего. Вот простой вопрос — можно ли полностью заменить кучу? Ведь по сути если нельзя, то получается, что куча и её неэффективная (по сравнению со стеком) реализация останется. В таком случае, нужно рассматривать весь путь полностью.Сейчас это выглядит так — мальчики налево (в стек), девочки направо (в кучу). То есть тип данных определяет, кто и где будет находится. Вы предлагаете не упростить, а усложнить алгоритм — мальчики налево (в стек), на девочках вводим новый алгоритм предсказания, а там уже по результату в стек или в кучу. В стеке быстрей, но кто будет считать время затраченное на предсказание? Или оно будет только на этапе компиляции? Тогда чем это будет отличаться от механизма, заложенного в Ява? А максимальная эффективность очевидно, это когда кучи нет в программе вовсе. Вы же предполагаете некоторое увеличение эффективности, поскольку, как я понял, точно неизвестно, можно ли быстро и эффективно располагать динамические данные в стеке. Наша же цель — сделать язык программирования первого типа, т.е. пригодного для системного программирования, выжимающий из оборудования максимум. Если есть возможность обойтись без кучи и сборки мусора для целого класса задач, то мы не можем это игнорировать. В C# код есть управляемый и не управляемый. В управляемом всё просто и красиво, в неуправляемом Вы сами заботитесь о проблемах. Исполнение можно комбинировать. Подумайте, может это можно прикрутить?
Да, сейчас тип объекта (а именно его размер — известный во время компиляции или нет) определяет, где он будет храниться. Есть намерение изменить этот порядок вещей. Способ хранения должен определяться исключительно дисциплиной его использования. Пример: f (...) {ptr = конструктор объекта(...);}Если ptr с созданным объектом должен жить дольше, чем функция f (например, при многопоточном программировании), то объект должен создаваться в куче. Если же ptr с объектом живут не дольше, чем f, то они должны храниться локально в стеке функции f. Решение о месте выделения памяти под объект должно приниматься системой владения/заимствования объектов. Над этим ещё надо думать. Можно обратить внимание на эту концепцию в языке Rust.
Если ptr с созданным объектом должен жить дольше, чем функция f (например, при многопоточном программировании), то объект должен создаваться в куче. Если же ptr с объектом живут не дольше, чем f, то они должны храниться локально в стеке функции f. Решение о месте выделения памяти под объект должно приниматься системой владения/заимствования объектов. У Вас могут возникнуть проблемы с функциями высшего порядка (это когда функция в качестве аргумента получает другую функцию или возвращает её в качестве аргумента). Наверно всё-таки тут стоит строить какой-то макет/модель. И отрабатывать уже на ней.Можно обратить внимание на эту концепцию в языке Rust. Где его описание на русском?
Если вы случайно забыли указать mut и изменили связывание, компилятор заметит это, и сообщит вам, что вы попытались изменить не то, что собирались. А если я случайно поставил mut там, где он быть не должен? А если я действительно ДОЛЖЕН это менять и действительно просто забыл поставить mut? Сомнительная эффективность защиты очевидна. Почему бы вместо let x=5; не написать правду? const x=5;Область видимости и затенение это ЕСТЕСТВЕННОЕ поведение в других языках программирования, а в связке с mut вообще подозрительны. И так много чего ещё. В общем-то первое впечатление — попытка из Си сделать Хаскелл.
Не нравится, как он это делает? Мне кажется он слегка жульничает, когда так много говорится в новой форме о старых дырах :). Насчет оптимального решения — его, наверно, нет вообще. Поэтому и идёт специализация языков программирования на сферы использования.Насчет неизменяемости, там слишком много внимания уделяется этому вопросу, в конце концов, если бы всё было неизменяемым, то и программы нужны были только на один раз — посчитал и всё на этом. Если исходные данные неизменяемы, то и результат очевидно не поменяется. Если же говорить о стеке, то идеальное решение тоже не очевидно, есть же Форт, на нём всё и закончилось бы, если всё было бы легко и просто. Тут 2 крайности — эффективность и выразительность. Выразительные средства не эффективны и компилировать их (да даже с кучей) весьма не просто. Эффективные средства не выразительны. Вот где там середина, которая всем бы нравилась?
Выразительные средства не эффективны ... Эффективные средства не выразительны. Вот где там середина, которая всем бы нравилась? Наверное, это асимптотические функции :) В золотой средине графики этих функций не существуют. Они стремятся к этой точке, но не пересекают.
В C++, чтобы выделить память, нужно в куче найти свободный фрагмент подходящего размера и отделить от него участок нужного размера (т.е. оставить в куче остаток от найденного фрагмента). Точные действия зависят от реализации кучи (простой двусвязный список, близнецовый метод и т.д.), но понятно, что нужно какое-то количество процессорных циклов. Причём неопределённое, поскольку на поиск требуется время, зависящее от размера кучи. В C# выделение памяти выполняется инструкцией top += sizeof(T). Т.е. указатель кучи просто сдвигаем вперёд на размер объекта. Одна машинная инструкция. Плата за эту простоту хорошо известна: сборка мусора. Чтобы, не задумываясь, выделять объекты один за другим, нужно при каждой сборке мусора уплотнять кучу. А это не только перемещение объектов в памяти, но и правка всех указателей, которые ссылаются на перемещаемые объекты. Конечно, там используются не просто алгоритмы «утрамбовки», а копирующие сборщики мусора по поколениям. Т.е. когда «нулевое» поколение заполнилось, все живые объекты из него перекладываются в другую область памяти, «первое» поколение, а участок «нулевого» снова свободен. Когда заполняется первое — перекладываются объекты во второе. И т.д. А в случае явного delete в C++ можно добиться удаления объекта за константное время.
Например, алгоритм двойников (https://en.wikipedia.org/wiki/Buddy_memory_allocation) позволяет снизить фрагментацию (при достаточно быстрой аллокации и деаллокации) ценой расхода памяти — участки могут выделяться только размера, пропорционального степени двойки.
Без уплотняющего сборщика мусора фрагментацию исключить нельзя. По крайней мере, я не представляю как. Но можно уменьшить её степень. Если у Вас блоки одинакового размера, просто копируете последний блок на место удаляемого с заменой адреса в ссылке.
Если у Вас блоки одинакового размера, просто копируете последний блок на место удаляемого с заменой адреса в ссылке. Спасибо! Не подумал об этом. Кстати, возможный вариант.Только нужен механизм для эффективного обнаружения всех ссылок на перемещаемый последний блок — не сканировать же всю память. Возможный вариант — провязывать все указатели в двусвязный список, с добавлением в него новых указателей при копировании и удалении при выходе из области видимости. Это можно сделать в C++, разработав соответствующий класс умного указателя (есть в книге Александреску «Современное проектирование на C++»). Интересно, как обобщить этот метод дефрагментации на фрагменты произвольного размера (или, хотя бы, степени двойки), минимизируя число и объём перемещаемых блоков. Вкусная пища для размышлений!
Интересно, как обобщить этот метод дефрагментации на фрагменты произвольного размера (или, хотя бы, степени двойки), минимизируя число и объём перемещаемых блоков. Вкусная пища для размышлений! Это старая задача. Общий алгоритм — копируются сначала блоки большего размера и т.д.
Отдельная тема: элементы какого-либо контейнера ссылаются друг на друга. В случае, когда контейнер занимает непрерывный участок памяти, можно подумать об относительной адресации. Тогда контейнер свободно перемещаем без изменения своего содержимого. И даже в файл сохраняется и назад извлекается.
Найти все ссылки на перемещаемый объект — задача не всегда тривиальная. Проблему можно было бы решить, если бы ссылки были двунаправленными: на кого ссылка и от кого ссылка. Это как в бухгалтерии метод двойной записи: у кого-то расход, а у кого-то приход. Всё правильно, нужна связь (можно и двунаправленный список) :).Отдельная тема: элементы какого-либо контейнера ссылаются друг на друга. В случае, когда контейнер занимает непрерывный участок памяти, можно подумать об относительной адресации. Генерируется уникальный идентификатор блока и всё. Поиск происходит не по адресу в памяти, а по таблице, которая содержит идентификатор и адрес. Работа идет с идентификаторами. Компилятор в своих операциях оперирует идентификаторами и только в момент обращения производит перевод в адреса для доступа к данным.
Я излагал другое. Получение относительного адреса элемента (смещения): относительный адрес = адрес начала контейнера - адрес элементаПолучение адреса элемента: адрес элемента = адрес начала контейнера + относительный адресНа каждую операцию — одна-единственная команда процессора: вычитание или сложение. Понятно, что Вы не гонитесь за эффективностью в своём языке. Но тут не только эффективность, но и простота. Впрочем, рассуждения давно ушли от первоначальной темы, что динамического распределения памяти лучше по возможности избегать.
Не понимаю, как компилятор может знать адреса в «куче». Если он их знает, то может выделить память либо статически, либо автоматически (в стеке). А как он получает данные из кучи :) ? Называйте это как хотите — адрес, ссылка, имя. Факт — у компилятора есть информация для доступа к данным.Решение по стеку по-прежнему не очевидно. Я у Вас спрашивал решение с 3 массивами. Вы в идеале хотите отказаться от кучи, это понятно. Но насколько мне известно, такого решения у Вас нет. На каждую операцию — одна-единственная команда процессора: вычитание или сложение. Понятно, что Вы не гонитель за эффективностью в своём языке. Но тут не только эффективность, но и простота. Я сторонник решения задачи, а не поклонения машинам. Не я должен изгибаться перед машиной, а она должна решать мои проблемы. Считайте это машиноненавистническим шовинизмом.Впрочем, рассуждения давно ушли от первоначальной темы, что динамического распределения памяти лучше по возможности избегать. По-моему, мы в русле. Опять же возвращаясь к классу задач, для которых у Вас пока нет решений на стеке.
Есть сложившееся знание о том, что от «кучи» в общем случае отказаться невозможно. Стеку (не важно, в каком количестве) нужен LIFO-порядок запросов на получение/освобождение памяти. Произвольный порядок может обслужить только «куча». Нет, мы тут не в русле, в заголовке статьи — про «кучу», а не про стек. Написать автору можно на электронную почту |
2014/08/05 19:01, Илья