Меню Рубрики

Какой способ хранения переменных самый эффективный с точки зрения скорости распределения

В последнее время множество разработчиков программного обеспечения переходит с языков низкого уровня на С. Преимущества C перед ассемблером: более понятный код, повышающий скорость разработки; универсальность, не требующая изучать досконально архитектуру используемого процессора; лучшая документируемость и читаемость алгоритма; наличие библиотек функций; поддержка вычислений с плавающей точкой и так далее. Но, в то же время, С проигрывает по занимаемым ресурсам и скорости исполнения приложения. Для решения этой проблемы отдельные критические участки могут быть написаны на ассемблере и тем или иным способом включены в проект, но для улучшения всего проекта следует писать более оптимальный С-код.

При оптимизации С-кода для разных микроконтроллеров пользуются различными приёмами, но так как одним из свойств языка С является переносимость (портируемость), то алгоритм, описанный один раз на С, можно использовать для разных архитектур. При этом, используя общие приёмы оптимизации, можно сделать так, что скомпилированный код будет работать быстрее и/или требовать меньше памяти. Интересующимся внутренней структурой С-компилятора и принципами его работы, не зависящими от конкретной архитектуры, рекомендую ознакомиться с GCC www.gcc.gnu.org. Но, в то же время, следует помнить, что для отдельных архитектур (особенно 8-бит микроконтроллеров) могут существовать специфические приёмы оптимизации. Для пользователей IAR-C для AVR-микроконтроллеров следует ознакомиться с Application Note AVR035 http://www.atmel.com/atmel/products/prod201.htm. Так как AVR-микроконтроллеры имеют архитектуру, “удобную” для С-компилятора, то часть общих советов будет совпадать с Note AVR035. Для PIC-микроконтроллеров и HT С многие “общие” правила не действительны (всё-таки архитектура PIC не предназначена для языков высокого уровня), да и НТ С нельзя назвать настоящим С-компилятором, это скорее язык с синтаксисом, подобным С. В таких случаях наиболее правильной методикой по-видимому является следующая: нужно скомпилировать исходник не в объектный файл, а в ассемблерный и сравнить полученные коды для разных вариантов.

Правила, советы и механизм работы С-компилятора

Итак, первое правило, которое следует запомнить так же, как “жи, ши пиши через и” — не пользоваться глобальными переменными там, где этого можно избежать. При том, что это правило повторяется в каждом учебнике, очень часто разработчики, переходящие с ассемблера на С, допускают эту ошибку.

Для понимания правила следует обратить внимание на то, как работают компилятор и линкер: как и куда распределяется память. Линкер оперирует с секциями (section). Секции служат для группирования объектов в памяти определённого типа. В разных программных продуктах существуют различное число и различные названия секций. Пользователь может как создавать новые секции, так и изменять способ компоновки объектов по секциям и привязки секций к физической памяти проектируемого (target) устройства. Для этого используются командные файлы или скрипты линкера и специальные директивы компилятора. Для процессоров неймановской архитектуры (Intel x86, большинство 32-разрядных RISC-процессоров), имеющих общую память программ и данных, доступную по указателю любого типа, с секциями имеет дело линкер, а код, генерируемый компилятором, обычно не зависит от того, в какую секцию попадут адресуемые данные. Но для гарвардской архитектуры большинства 8-бит микроконтроллеров существуют различные механизмы доступа к разным типам памяти, следствием чего является различный код, генерируемый компилятором для доступа к объектам, лежащим в разных типах памяти. Для решения вопроса размещения объектов в памяти разработчики компилятора вынуждены отходить от стандарта ANSI и добавлять особые ключевые слова. Примером может служить модификатор flash, использующийся в IAR-C для AVR. Из-за разнообразия архитектур и С-компиляторов, работающих с ними, описание названий и типов секций следует искать в документации на компилятор.

В общем случае, компилятор работает с четырьмя типами секций: data, bss, code, rdata (в разных продуктах могут быть другие имена, но назначение сохраняется). Data содержит инициализированные данные, bss — неинициализированные данные, code — исполняемый код, rdata — различные константы. При этом data и bss располагаются в ОЗУ, а code, rdata и копируемый образ data — в ПЗУ. Также в ОЗУ должны быть расположены стек и “куча” (heap), то есть полностью занимать ОЗУ секциями data и bss нельзя.

Вернёмся к тому, как компилятор располагает переменные в памяти: инициализированные глобальные переменные попадают в data, неинициализированные — в bss.

В следующем примере

для переменной j будет выделено 4 байта в секции bss, а для переменной i — 1 байт в data. При этом начальное значение i=5 займёт место в загружаемом коде (в ПЗУ).

Такое же распределение памяти будет выполнено и для статических переменных, единственное отличие будет в том, что они не видны компилятору и линкеру где-либо ещё, кроме той функции, в которой объявлены.

Кроме того, перед передачей управления функции main() в исполняемом коде, сгенерированном С-компилятором для встраиваемой системы, исполняется так называемый startup-код. Пользователь может переписать этот код, который либо содержится в предопределённом объектном файле (например, crt0.o), либо даётся линкеру в явном виде (например, nostartfiles my_start_up.s). Поставляемый вместе с компилятором и линкуемый по умолчанию startup-код кроме начальной инициализации периферии должен заполнить нулями bss-секцию и скопировать из ПЗУ данные в data-секцию. Некоторые компиляторы имеют опцию, позволяющую пропустить инициализацию, но пользоваться этим надо осторожно, так как по стандарту ANSI глобальные переменные должны иметь определённое значение (неинициализированные явно равны 0) на момент начала исполнения main().

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

Рассмотрим, какие ещё методы распределения ОЗУ имеет С: стек — область памяти, в которой выделяется место для локальных переменных и параметров/результатов функции (в некоторых случаях для передачи параметров используется регистровый файл); “куча” — область памяти, с которой имеют дело функции calloc, malloc, free, realloc.

Распределение ОЗУ в стандартной С-программе выглядит следующим образом:

(последняя ячейка ОЗУ)
Стек, растет сверху вниз
граница стека
Свободная память
Куча (heap), растет снизу вверх
начало кучи
Память, распределенная во время компиляции секции bss, data
(начало ОЗУ)

Так как размеры стека и “кучи” изменяются в процессе выполнения программы (“куча” и стек растут навстречу друг другу), то при их пересечении данные будут утеряны. В “больших” системах за распределением памяти следит ОС и соответствующим образом обрабатывает ошибочную ситуацию, когда исчерпывается свободная память. Во встраиваемых системах подобная ошибка приводит к непредсказуемому результату, поэтому надо принимать определённые меры во время разработки программы. То есть малый объём ОЗУ в микроконтроллере может наложить ограничения на глубину вызовов функций и на количество локальных переменных, используемых в функциях.

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

В этом примере под локальные переменные будет выделено столько же места, сколько потребовалось при единственном вызове foo.

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

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

Единичным элементом, с которым работает С-компилятор, является С-функция, поэтому много вызовов простых С-функций не позволяет компилятору эффективно оптимизировать код. Дополнительные затраты требуются также на вызов, передачу параметров и возврат. Несмотря на то, что алгоритм, описанный в виде набора простых функций, является более понятным и проще отлаживаемым, для увеличения эффективности следует пользоваться другими методами. Это могут быть либо inline-функции, либо макросы. Не все С-компиляторы поддерживают inline-функции, хотя эта методика считается более правильной, и при переходе от С к С++ следует использовать inline для небольших функций. Макросы являются стандартным механизмом С и поддерживаются всеми компиляторами. Но так как макросы обрабатывает препроцессор, выполняя просто текстовую подстановку и не проводя никакого синтаксического анализа, то возможны ошибки, обнаружить которые бывает непросто. Классический пример неправильного макроса для вычисления квадрата:

При его использовании в случае

Для правильного использования этот макрос следует определить следующим образом:

Макросы также не проверяют параметры, поэтому пользоваться ими для замены функций следует с осторожностью. Во всех рекомендациях по языку С++, который поддерживает inline-функции, рекомендуется использовать функции и сквозную оптимизацию, а не макросы. Но если язык не имеет поддержки inline-функции, то можно достигнуть уменьшения размера кода и за счёт использования макроса.

Однако, увеличение размера функции ведёт не только к усложнению документируемости и читаемости, но и может привести к специфической для встраиваемых систем ошибке. Обычно алгоритм встраиваемой системы считывает данные с набора датчиков и подаёт воздействия на управляемые элементы. При этом, с точки зрения компилятора, подобные запись и чтение могут выглядеть “бессмысленными” и в процессе оптимизации могут быть удалены из кода. Для предотвращения этого служит слово volatile (об использовании этого модификатора речь пойдёт ниже). Но использование volatile не гарантирует сохранения последовательности обращений. То есть в случае большой функции хороший компилятор может изменить последовательность воздействий, а это, в свою очередь, может привести к неработоспособности системы. Для предотвращения этого следует пользоваться ассемблерными вставками (причём вставка должна содержать не одно обращение, а всю последовательность). GCC и построенные на его основе коммерческие компиляторы могут оптимизировать ассемблерный код, написанный пользователем. В этом случае следует пользоваться конструкцией asm volatile, например, asm volatile (“nop”). Но это специфика конкретного компилятора, и в любом другом случае нужно ознакомиться с тем, как управляется оптимизатор компилятора (это могут быть ключи командной строки, директивы #pragma, какие-либо атрибуты, нестандартные модификаторы).

Вернёмся к механизмам распределения ОЗУ в С-программах. Кроме глобальных и статических переменных, распределяемых линкером в секциях data и bss, и локальных переменных, размещаемых автоматически в процессе исполнения в рабочих регистрах или на стеке, существует так называемая “куча”. В микроконтроллерах с малым объёмом памяти “куча” и работа с ней не поддерживаются (по умолчанию, IAR-C для AVR требует для “кучи” 2К ОЗУ). Но в то же время, этот механизм выделения памяти контролируется пользователем, и во многих проектах вызовы malloc, calloc, free встречаются очень часто. Как и везде, здесь есть свои подводные камни. Эти функции работают со структурой, похожей на файловую систему (или цепочку кластеров). Поэтому возможны такие эффекты, как дефрагментация памяти. Но это приводит к более плохим последствиям, чем дефрагментация файловой системы: по запросу память должна выделяться целым куском, и освобождённые фрагменты не могут использоваться, если существует сколь угодно малый кусочек памяти, занятый позже и не освобождённый. То есть несложно написать такую программу, которая, реально используя один байт, займёт всё пространство “кучи”. Также при выделении памяти требуется место под заголовок, содержащий служебную информацию (размер памяти, указатель на следующий элемент и т.п.). Поэтому при выделении множества маленьких кусочков с помощью malloc память будет расходоваться неэффективно. Из этого можно сделать несколько выводов, применимых к программному обеспечению встраиваемых систем: так как из main возврата не бывает, то можно аллоцировать требуемую память один раз и использовать её (в терминах языка С++ вызываются только конструкторы объектов, деструкторы отсутствуют); объект, под который выделяется память, должен быть наибольшего возможного размера (отдельные запросы для его частей потребуют больше памяти); освобождать память следует по принципу стека, так как пока не удалён последний объект (созданный последним malloc), память не возвращается. Эти сложности являются следствием того, что язык С предоставляет пользователю мощные инструменты для работы с указателями, но при этом отсутствует автоматическая сборка отработанной памяти, так называемая “автоматическая сборка мусора”. Но в любом случае при динамическом выделении памяти надо следить, чтобы вся память, которая была взята, была возвращена в “кучу”: то есть каждому malloc должен соответствовать free. Иначе возникает эффект, называемый утечкой памяти (memory leakege), и возникает вероятность краха системы.

Читайте также:  Точка зрения на роль компьютера и всемирной паутины

Следует обратить особое внимание на работу с указателями. Они позволяют обеспечить передачу больших объёмов данных между функциями, реализовать эффективный доступ к элементам структуры и массивам. Но пользоваться указателями следует аккуратно и с пониманием архитектуры процессора, для которого генерируются коды. Особенно плохо (как и всегда J) обстоит дело с гарвардскими машинами, так как памяти каждого типа соответствуют свои типы указателей и команды для работы с ними. Для указателей, которые изменяются в процессе работы (инкрементируются, декрементируются, получают какие-либо новые значения), следует предусмотреть, чтобы они указывали на правильные данные. В С, выполняя операцию “++”, “+=” или подобную (то есть операцию с указателем и целым числом), компилятор учитывает тип данных, на которые указывает указатель.

— указатели будут указывать на разные ячейки памяти.

Поэтому существуют операции преобразования указателя, и в случае гарвардской архитектуры автоматическое преобразование указателя не всегда возможно. При этом в гарвардской архитектуре возможно существование указателей одного типа, работающих для разных областей памяти, преобразование которых может не поддерживаться компилятором. Ещё следует упомянуть модификаторы far и near, которые могут описывать указатели, имеющие различный размер и адресующие различные по размеру области памяти. Если архитектура поддерживает различные типы указателей, то компилятор обычно пытается воспользоваться указателем минимального размера.

Указатели следует применять для передачи параметров / возвращения результатов вызываемой функции. Этот метод позволяет избежать использования глобальных переменных для передачи параметров. То есть передаваемые значения следует объединить в структуру и передавать указатель. Пользуясь операциями “&” и “->”, можно обеспечить эффективный механизм передачи параметров, не использующий глобальных переменных и не занимающий время и память копированием данных.

В стандартной библиотеке таким механизмом передачи данных пользуется sprintf.

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

Для экономии памяти следует правильно описывать переменные. Если переменная принимает целочисленные значения из диапазона -100. +100, то для её хранения достаточного одного байта и описывать её следует как signed char, а не как int. Так же можно использовать ключевые слова short и long, так как int в некоторых случаях эквивалентен short и представляется 2-мя байтами, а в некоторых — эквивалентен long и представляется 4-мя байтами. При этом нужно представлять архитектуру используемого процессора, возможно такое задание опций компилятора/ликера, при котором элемент char будет занимать одну 32-разрядную ячейку памяти или на распаковку char потребуются дополнительные инструкции. Но на 8-разрядные архитектуры это не распространяется. Для более эффективного использования памяти можно пользоваться объединениями union — это не только позволяет сэкономить память в случае, когда две переменные разных типов не используются одновременно, но и проводить преобразования типов. Например, для получения представления 64-разрядного double можно воспользоваться объединением union . При этом следует обращать внимание на способ хранения данных в памяти (big endian или litle endian, intel или motorola). В приведённом примере, скомпилированном для ПК с x86 процессором, показатель будет хранится в “l[1]”, а если скомпилировать для ARM или PowerPC — то в “l[0]”. При этом процессорные ядра (тот же ARM) могут конфигурироваться как для big endian, так и для litle endian.

Вопрос с битовыми полями неоднозначен: они могут потребовать больших затрат, чем непосредственные операции с битами, но тем не менее битовые поля обеспечивают лучшую читаемость исходников.

Из старых трюков, применяемых или применявшихся при программировании на С, некоторые могут найти применение во встраиваемых системах, например, объявление констант с помощью ключевого слова enum — enum ; использование условных инструкций с предекрементом, например, наиболее эффективный цикл do <.>while (—i). Но это имеет смысл делать для старых компиляторов и носит скорее исторический смысл.

Специфическими ключевыми словами для программирования встраиваемых систем являются volatile и interrupt. Первое есть в ANSI, а второе — расширение языка. Для описания функции, вызываемой по внешнему событию (прерыванию), используется модификатор interrupt. Для описания переменной, которая может быть изменена в прерывании, или порта ввода/вывода в пространстве памяти используется модификатор volatile. Это ключевое слово запрещает компилятору сохранять значение переменной в рабочем регистре, заставляя каждый раз его считывать.

Если Вы дочитали эту статью и нашли в ней что-либо интересное, то это хорошо, но лучше будет написать интересующую конструкцию на конкретном компиляторе для конкретного процессора и посмотреть, в какой ассемблерный код она превращается при том или ином уровне оптимизации. Описать все методы и предусмотреть любую ошибку невозможно, также могут найтись примеры (процессоров и компиляторов), для которых предлагаемые способы будут бессмысленны или вредны. Но, в любом случае, использование С может существенно облегчить разработку встраиваемых систем. Тем более, что в настоящее время появляется всё больше С и С++-компиляторов и процессоров с архитектурой, позволяющей этим компиляторам генерировать эффективный код.

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

Потеря эффективности. Простейшие реализации функций malloc() и free() имеют длину несколько сотен строк. А уж продвинутые — тем паче длиннее.

  • Некорректная работа с памятью в куче может приводить к её утечкам. Причиной может быть как ошибки в библиотечных функциях управления памятью, так и ошибки в программе при ручном управлении.
  • Фрагментация памяти. Если «до упора» выделять память по одному байту, а потом освободить занятые блоки памяти, но не все, а через один, то память будет нарезана на множество маленьких кусочков, которые невозможно использовать. Сложные алгоритмы распределения памяти могут обходить эту проблему путём перемещения фрагментов и изменения указателей. Но это опять расходование вычислительных ресурсов.
  • Алгоритмы динамического распределения памяти либо просты, либо хороши. Более того, одни алгоритмы хорошо работают для одного класса задач, а другие — для другого.
  • Некоторые алгоритмы динамического распределения памяти выделяют память быстро, но в ситуациях, когда память заканчивается и нужно обеспечить «сборку мусора», начинают «тормозить». Имея хорошее среднее время отклика, они не могут обеспечить его гарантированный минимум. Поэтому в системах реального времени используют другие алгоритмы. Они имеют гарантированное время отклика, но среднее время отклика у них выше.
  • Ссылки на участки памяти в «куче» могут быть потеряны. В этом случае память не может быть освобождена, поскольку её адрес становится неизвестен программе. Для решения проблемы используют «умные указатели», которые хоть и решают задачу, но опять же, ценой дальнейшей потери эффективности.
  • Есть хорошая статья на эту тему: «4 вида утечек памяти в JavaScript и как с ними бороться»

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

    Опубликовано: 2014.07.27, последняя правка: 2018.10.29 16:01

    Оцените Оценки посетителей
    Нравится ██████████████████████████████████ 4 (80%)
    Неплохо █████████ 1 (20%)
    Так себе ▌ 0
    Не нравится ▌ 0

    2014/08/05 19:01, Илья #

    Escape analysis: Java 7 автоматически выделяет объекты не в куче, а на стеке, если это возможно.

    2014/08/15 10:38, Автор сайта #

    Есть сомнения, что объекты в Java создаются в стеке всегда, когда возможно. В C++ можно создать в стеке массив, размеры которого становятся известны в момент выполнения. Но это возможно лишь с помощью ассемблерных вставок (как это делается — описано в следующих статьях). Но средствами только C++ это невозможно, даже если у Вас отличный оптимизирующий компилятор. Т.е. даже в C++, чей конёк, чья визитная карточка — это скорость выполнения программы, не могут этого сделать, хотя такая возможность очевидна и напрашивается. А ведь один из главных минусов динамического распределения памяти — это потеря скорости.

    Вот поэтому есть сомнения насчёт Java. C++ позволяет проверить догадки, предоставляя исполняемый код. Кода Java не видел, поэтому не могу ни подтвердить Ваши слова, ни опровергнуть. Вы можете взять на себя труд: создать массив с размером, известным только во время выполнения, и посмотреть код виртуальной машины?

    2014/09/02 08:54, Илья #

    К сожалению, я не смогу посмотреть код в этом случае.
    Но думается, что большие массивы и не надо создавать на стеке, хотя бы для того, чтобы не нарваться на неожиданный stack overflow, если пользователь задал «немного бо́льшие» параметры.

    Автозамена кучи на стек имеет смысл для маленьких объектов:
    1) локальность данных
    2) сокращение труда сборщика мусора — ему не нужно будет чистить память от мелких временных объектов
    3) так как другой поток не может залезть в наш стек, не нужно применять блокирование, даже если оно прописано в программе

    2014/08/15 10:38, Автор сайта #

    Думается, для хранения больших объектов стек тоже вполне хорош. Когда память компьютера измеряется гигабайтами, то выделить по полгигабайта на два стека вполне возможно. По-хорошему, надо делать проверку доступного количества памяти в стеке.

    2015/08/02 16:51, Денис Будяк #

    Использование кучи в общем случае неизбежно из-за того, что не всегда известен порядок уничтожения объектов. Любое наперёд заданное количество стеков (или очередей) не справится с этой проблемой в общем случае. Именно поэтому сборка мусора присутствует в Java, в ядре Линукса и в базе данных Postgress.

    Язык, лишённый кучи, будет неполноценным, придётся делать костыли.

    2015/08/03 13:32, Автор сайта #

    Предлагаемая организация стеков в значительной мере уменьшит обращения к куче, и это хорошо.

    Можно ли вообще избавиться от кучи? Интересный вопрос как с точки зрения теории, так и практики. Можно ли алгоритмы с произвольным порядком освобождения памяти преобразовать в эквивалентные, но со строгим порядком? Например, оттягивая фактическое освобождение памяти, помечая её, как освобождённую. Ну и практический вопрос: можно ли выделить какой-то особый класс задач, который нуждается именно в произвольном порядке освобождения памяти?

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

    2015/08/04 18:34, Денис Будяк #

    Не думаю, что можно избавиться, да и неохота об этом думать.

    2015/08/05 13:03, Автор сайта #

    А вот мне этот вопрос интересен.

    2015/08/09 13:58, Денис Будяк #

    Пример: линковка программы. В программе на С определена куча функций, одни функции ссылаются на другие. Берём в качестве корня точку входа и от неё делаем сборку мусора по ссылкам функций между собой. Так определяем, какие функции нужны в исполняемом файле.

    2016/04/03 06:05, rst256 #

    Ссылки на участки памяти в «куче» могут быть потеряны.

    Ну таким Макаром можно с тем же успехом и в стеке данные про.. хм потерять, или на ноль поделиться, хотя последнее уже кое где закрыли (видать были прецеденты) в некоторых языках 1/0 возвращает или NaN(тупо переносим ошибку подальше от места возникновения) или huge(означает «большое число» — бесконечность, 80% ошибок успешно исправляется, оставшиеся 20% всплывут не скоро). Как то неправильно ошибки, возникшие в прикладном коде, вешать на библиотеку.

    Читайте также:  Медитативные упражнения для глаз для восстановления зрения панков олег

    2016/04/03 15:24, Автор сайта #

    Усовершенствование (о котором написано в последующих статьях) заключается вот в чём. Функция f3 выделяет память в стеке функции f2 и записывает указатель на неё в стеке f2. Когда f2 заканчивает работу и передаёт управление f1, то перестают существовать как указатель на память в стеке f2, так и сама память в стеке f2 (она освобождается).

    2016/05/05 10:16, utkin #

    А зачем такие заморочки? Можно ведь выделять сразу всё в стеке f1 и запоминать указатель на стек при входе в следующие функции. А при выходе просто смещать указатель да и всё. И не надо кучи стеков.
    Я просто не могу понять как это реализовать в другом виде. Ну вот есть f3, да? Вот насоздавал я там кучу объектов, типа 1,2,3,4,5. Но вот удалять мне их потом надо фиг пойми как да ещё каждый раз по-разному. Вот в первый прогон функции удаляются 4,5,1,3,2. Вот второй прогон удаляются 5,1,4,3,2. Как это будет реализовано в стеке? И стек и куча они ведь «плоские», типа лента адресов и любое удаление в порядке отличающимся от создания «рвет» эту ленту создавая «дыры» в занятой памяти. Какой такой простой алгоритм есть для того чтобы уменьшать стек при произвольном удалении объектов да ещё и быстрей кучи чтобы получилось? Стек красота, когда Вы точно знаете как и что будет удаляться, тогда и данные можно пихать так, чтобы просто потом сместить указатель на вершину стека одной-двумя командами. Да и многостековость легко переносится на многокучевость. Создал на каждую функцию свою кучу — вышел из функции, потер весь блок да и вся проблема.

    2016/05/05 10:38, utkin #

    Потеря эффективности. Простейшие реализации функций malloc() и free() имеют длину несколько сотен строк. А уж продвинутые — тем паче длиннее.

    Но дают возможность работы с объектами динамической природы. То есть это не то чтобы грех. Это просто решение других задач. От стека ведь как правило никто не отказывается — простые переменные обычно там и лежат.

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

    Ну это так же «Некорректная работа с памятью в стеке может приводить к её утечкам». Я вот как отчаянный паскалист скажу так: программист на С++ с легкостью решает не существующие в Паскале проблемы. Откажитесь Вы от прямого доступа к памяти, да и все проблемы. Есть классы и объекты, есть динамические массивы. Зачем вот ковыряться в этих указателях? Оно вот надо только для очень узких задач. Вон в C# для этого надо специально переключаться на неуправляемый код. Вот Вам идеальное решение, раз переключились значит понимаете, что «Некорректная работа с памятью в куче может приводить к её утечкам.», то есть сами себе Буратино, что не смогли корректно составить алгоритм, а не валить всё на компилятор.

    Фрагментация памяти. Если «до упора» выделять память по одному байту, а потом освободить занятые блоки памяти, но не все, а через один, то память будет нарезана на множество маленьких кусочков, которые невозможно использовать. Сложные алгоритмы распределения памяти могут обходить эту проблему путём перемещения фрагментов и изменения указателей. Но это опять расходование вычислительных ресурсов.

    Не знаю, в какой куче память выделяется побайтно. Память выделяется поблочно. Размер блока определяет создатель системы исходя из каких-то своих измышлений (может тесты проводит, а может ему так нравится, а может ось любит давать память приложению кратно 16-ти байтам). По поводу ресурсов — да, но других решений нет. Варианта там 2 обычно. Самый простой — сразу перемещать последний блок на место освободившегося. Вариант 2 — это дефрагментация по наступлению определенного события (например, 30 процентов блоков не используются и т.д.). Вот раньше была такая частая процедура на XP — дефрагментация диска. Вот Вам прямая аналогия — диск, он ведь тоже не произвольное расположение, а лента (физически наверно спираль или круги).

    Алгоритмы динамического распределения памяти либо просты, либо хороши. Более того, одни алгоритмы хорошо работают для одного класса задач, а другие — для другого.

    Так и стек. Иначе бы других структур не было бы в принципе. Ни очередей, ни массивов, ни более сложных коллекций. Зачем всё усложнять, когда есть такой вот эффективный стек? Это ведь можно так напороться на скальпель монаха Оккама, который говорит в стиле Маяковского — если звезды на небе зажигаются, значит это кому-нибудь нужно. Иными словами, если помимо стека придумывают что-то ещё, значит стек не может решить всех задач. Это я даже без всяческих тестов могу утверждать.

    Некоторые алгоритмы динамического распределения памяти выделяют память быстро, но в ситуациях, когда память заканчивается и нужно обеспечить «сборку мусора», начинают «тормозить». Имея хорошее среднее время отклика, они не могут обеспечить его гарантированный минимум. Поэтому в системах реального времени используют другие алгоритмы. Они имеют гарантированное время отклика, но среднее время отклика у них выше.

    Это специализация. Она не означает, что стек круче чем всё остальное. Стек круче в своей области применения (иначе бы его просто не использовали). Но в других задачах круче другие структуры (иначе их бы не использовали 🙂 ).

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

    Как это ссылка на участок памяти в «куче» может быть потеряна? Это что-то из области зеленых человечков. Если программист напортачил в коде, то так и надо говорить — это программист уже неделю не был на свежем воздухе и глаза у него в куче, а не ссылка там. Я выше уже написал Вам как решаются подобные проблемы — оторвать руки программисту, решающего прикладную (не системную!) задачу с помощью прямого доступа к памяти по указателям. И дело здесь не а куче, а в человеческом факторе, будете маскировать источник проблемы, будете всё время бороться с её проявлением. Нужно честно поставить диагноз — у программ проблемы с утечками памяти потому что у программистов руки из задницы растут, а язык позволяет им оттуда расти. И решение соответствующие — либо руки за спину скотчем замотать либо в языке сделать выстрел в ногу жутко утомительным занятием.

    2016/05/05 13:24, Автор сайта #

    Весьма часто память под объект можно выделить в стеке. Для этого, казалось бы, есть все условия: время существования объекта совпадает со временем существования функции, которая им владеет. Но есть загвоздка: существующие языки умеют хранить объекты в стеке только тогда, когда они фиксированного размера. А если переменного — пиши пропало. Без кучи обходиться не умеют. Этот цикл статей как раз посвящён тому, чтобы научить некоторый класс задач обходиться без кучи.

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

    2016/05/05 13:45, utkin #

    Весьма часто память под объект можно выделить в стеке. Для этого, казалось бы, есть все условия: время существования объекта совпадает со временем существования функции, которая им владеет. Но есть загвоздка: существующие языки умеют хранить объекты в стеке только тогда, когда они фиксированного размера. А если переменного — пиши пропало. Без кучи обходиться не умеют. Этот цикл статей как раз посвящён тому, чтобы научить некоторый класс задач обходиться без кучи.

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

    Если Вы считаете, что пользоваться кучей в таких случаях — не грех («Десятки языков делают это!»), то Вы — сторонник развития языков программирования по второму пути (см. классификацию языков программирования в начале статьи «философия языка»).

    Я не то, чтобы против. Я хочу понять, что это действительно эффективно и за счет чего. Вот простой вопрос — можно ли полностью заменить кучу? Ведь по сути если нельзя, то получается, что куча и её неэффективная (по сравнению со стеком) реализация останется. В таком случае, нужно рассматривать весь путь полностью.
    Сейчас это выглядит так — мальчики налево (в стек), девочки направо (в кучу). То есть тип данных определяет, кто и где будет находится. Вы предлагаете не упростить, а усложнить алгоритм — мальчики налево (в стек), на девочках вводим новый алгоритм предсказания, а там уже по результату в стек или в кучу. В стеке быстрей, но кто будет считать время затраченное на предсказание? Или оно будет только на этапе компиляции? Тогда чем это будет отличаться от механизма, заложенного в Ява?
    А максимальная эффективность очевидно, это когда кучи нет в программе вовсе. Вы же предполагаете некоторое увеличение эффективности, поскольку, как я понял, точно неизвестно, можно ли быстро и эффективно располагать динамические данные в стеке.

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

    В C# код есть управляемый и не управляемый. В управляемом всё просто и красиво, в неуправляемом Вы сами заботитесь о проблемах. Исполнение можно комбинировать. Подумайте, может это можно прикрутить?

    2016/05/05 14:23, Автор сайта #

    Это вопрос и языка, и реализации. В Си не нашли возможности возвратить в стек объект переменного размера, потому язык сделали так, как могли — возвращали в стек объекты только фиксированного размера.

    Да, сейчас тип объекта (а именно его размер — известный во время компиляции или нет) определяет, где он будет храниться. Есть намерение изменить этот порядок вещей. Способ хранения должен определяться исключительно дисциплиной его использования. Пример:Если ptr с созданным объектом должен жить дольше, чем функция f (например, при многопоточном программировании), то объект должен создаваться в куче. Если же ptr с объектом живут не дольше, чем f, то они должны храниться локально в стеке функции f. Решение о месте выделения памяти под объект должно приниматься системой владения/заимствования объектов. Над этим ещё надо думать. Можно обратить внимание на эту концепцию в языке Rust.

    2016/05/05 15:31, utkin #

    Если ptr с созданным объектом должен жить дольше, чем функция f (например, при многопоточном программировании), то объект должен создаваться в куче. Если же ptr с объектом живут не дольше, чем f, то они должны храниться локально в стеке функции f. Решение о месте выделения памяти под объект должно приниматься системой владения/заимствования объектов.

    Читайте также:  Почему не стоит делать лазерную коррекцию зрения

    У Вас могут возникнуть проблемы с функциями высшего порядка (это когда функция в качестве аргумента получает другую функцию или возвращает её в качестве аргумента). Наверно всё-таки тут стоит строить какой-то макет/модель. И отрабатывать уже на ней.

    Можно обратить внимание на эту концепцию в языке Rust.

    Где его описание на русском?

    2016/05/05 15:43, Автор сайта #

    Да, концепция требует проработки. Вот как это в Rust: http://rurust.github.io/rust_book_ru/src/lifetimes.html

    2016/05/06 08:57, utkin #

    За источник спасибо.

    2016/05/06 11:20, Автор сайта #

    Не за что. Он же из Википедии взят 🙂

    2016/05/06 15:21, utkin #

    Про ссылку — там черным по белому написано о ссылках на кучу и сборку мусора по выходу из блока функции. Можно какую угодно терминологию наводить, но суть-то та же :). Пример, где после присваивания первоначальный вектор нельзя присваивать, вообще убил. Попытка контроля ссылок по выдачи исключения. Типичный Access Violation в Дельфи.

    2016/05/06 15:40, utkin #

    Вообще Rust разочаровал, тот же Ява, только компилятор и со своей терминологией. Типажи ВЕЗДЕ интерфейсы, то есть синтаксический сахар. Модификатор mut(able):

    Если вы случайно забыли указать mut и изменили связывание, компилятор заметит это, и сообщит вам, что вы попытались изменить не то, что собирались.

    А если я случайно поставил mut там, где он быть не должен? А если я действительно ДОЛЖЕН это менять и действительно просто забыл поставить mut? Сомнительная эффективность защиты очевидна. Почему бы вместо let x=5; не написать правду? const x=5;

    Область видимости и затенение это ЕСТЕСТВЕННОЕ поведение в других языках программирования, а в связке с mut вообще подозрительны.

    И так много чего ещё. В общем-то первое впечатление — попытка из Си сделать Хаскелл.

    2016/05/07 11:12, Автор сайта #

    Да, в Rust объекты, чей размер известен только во время исполнения, располагаются в куче. Но это не уменьшает проблем, связанных с указателями. Можно, конечно, положиться на «умные» указатели и системы сборки мусора. Но чем больше забот мы перекладываем на программы, которые сами следят за собой, тем дальше мы отдаляемся от системного программирования. Но в тех же системах реального времени автоматическая сборка мусора просто не приемлема. Rust пытается это решить. Не нравится, как он это делает? Отлично, у нас есть шанс сделать лучше! Если бы языки были идеальны, то нам с Вами не нашлось бы работы 🙂

    2016/05/11 09:47, utkin #

    Не нравится, как он это делает?

    Мне кажется он слегка жульничает, когда так много говорится в новой форме о старых дырах :). Насчет оптимального решения — его, наверно, нет вообще. Поэтому и идёт специализация языков программирования на сферы использования.

    Насчет неизменяемости, там слишком много внимания уделяется этому вопросу, в конце концов, если бы всё было неизменяемым, то и программы нужны были только на один раз — посчитал и всё на этом. Если исходные данные неизменяемы, то и результат очевидно не поменяется. Если же говорить о стеке, то идеальное решение тоже не очевидно, есть же Форт, на нём всё и закончилось бы, если всё было бы легко и просто. Тут 2 крайности — эффективность и выразительность. Выразительные средства не эффективны и компилировать их (да даже с кучей) весьма не просто. Эффективные средства не выразительны. Вот где там середина, которая всем бы нравилась?

    2016/05/11 11:13, Автор сайта #

    Могу сказать твёрдо и однозначно, что концепция владения и заимствования в Rust переусложнена и в значительной части случаев она просто не нужна. Ведь какие проблемы решает эта концепция? Она позволяет разрешить коллизии, связанные с существованием объектов и их уничтожением. Но эти проблемы существуют при многопоточном программировании. А при однопоточном программировании их просто нет. Возьмём такой простейший код: y=sin(x). Зачем объект x передавать во владение функции sin? Ведь код в этом случае работает строго по очереди: либо код внутри sin, либо код до и после этой функции. Никаких коллизий тут быть не может, объекты возникают и исчезают строго по дисциплине LIFO. Ну зачем тут нужно владеть объектами?

    Выразительные средства не эффективны . Эффективные средства не выразительны. Вот где там середина, которая всем бы нравилась?

    Наверное, это асимптотические функции 🙂 В золотой средине графики этих функций не существуют. Они стремятся к этой точке, но не пересекают.

    2018/05/25 00:20, Александр Коновалов aka Маздайщик #

    Хочу рассказать об одном интересном моменте, о котором многие не знают/не задумываются. Оператор new в C# работает зачастую быстрее, чем в C++. Почему?

    В C++, чтобы выделить память, нужно в куче найти свободный фрагмент подходящего размера и отделить от него участок нужного размера (т.е. оставить в куче остаток от найденного фрагмента). Точные действия зависят от реализации кучи (простой двусвязный список, близнецовый метод и т.д.), но понятно, что нужно какое-то количество процессорных циклов. Причём неопределённое, поскольку на поиск требуется время, зависящее от размера кучи.

    В C# выделение памяти выполняется инструкцией top += sizeof(T). Т.е. указатель кучи просто сдвигаем вперёд на размер объекта. Одна машинная инструкция.

    Плата за эту простоту хорошо известна: сборка мусора. Чтобы, не задумываясь, выделять объекты один за другим, нужно при каждой сборке мусора уплотнять кучу. А это не только перемещение объектов в памяти, но и правка всех указателей, которые ссылаются на перемещаемые объекты.

    Конечно, там используются не просто алгоритмы «утрамбовки», а копирующие сборщики мусора по поколениям. Т.е. когда «нулевое» поколение заполнилось, все живые объекты из него перекладываются в другую область памяти, «первое» поколение, а участок «нулевого» снова свободен. Когда заполняется первое — перекладываются объекты во второе. И т.д.

    А в случае явного delete в C++ можно добиться удаления объекта за константное время.

    2018/05/26 00:47, Автор сайта #

    По-моему, есть какие-то методы распределения памяти, которые в среднем более медленны, но гарантируют минимальное время выделения и освобождения памяти. И при этом исключают фрагментацию памяти.

    2018/05/27 16:41, Александр Коновалов aka Маздайщик #

    Без уплотняющего сборщика мусора фрагментацию исключить нельзя. По крайней мере, я не представляю как. Но можно уменьшить её степень.

    Например, алгоритм двойников (https://en.wikipedia.org/wiki/Buddy_memory_allocation) позволяет снизить фрагментацию (при достаточно быстрой аллокации и деаллокации) ценой расхода памяти — участки могут выделяться только размера, пропорционального степени двойки.

    2019/01/14 08:21, utkin #

    Без уплотняющего сборщика мусора фрагментацию исключить нельзя. По крайней мере, я не представляю как. Но можно уменьшить её степень.

    Если у Вас блоки одинакового размера, просто копируете последний блок на место удаляемого с заменой адреса в ссылке.

    2019/01/30 11:53, Александр Коновалов aka Маздайщик #

    Если у Вас блоки одинакового размера, просто копируете последний блок на место удаляемого с заменой адреса в ссылке.

    Спасибо! Не подумал об этом. Кстати, возможный вариант.

    Только нужен механизм для эффективного обнаружения всех ссылок на перемещаемый последний блок — не сканировать же всю память. Возможный вариант — провязывать все указатели в двусвязный список, с добавлением в него новых указателей при копировании и удалении при выходе из области видимости. Это можно сделать в C++, разработав соответствующий класс умного указателя (есть в книге Александреску «Современное проектирование на C++»).

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

    2019/02/05 22:00, utkin #

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

    Это старая задача. Общий алгоритм — копируются сначала блоки большего размера и т.д.

    2019/02/06 23:03, Автор сайта #

    Найти все ссылки на перемещаемый объект — задача не всегда тривиальная. Проблему можно было бы решить, если бы ссылки были двунаправленными: на кого ссылка и от кого ссылка. Это как в бухгалтерии метод двойной записи: у кого-то расход, а у кого-то приход.

    Отдельная тема: элементы какого-либо контейнера ссылаются друг на друга. В случае, когда контейнер занимает непрерывный участок памяти, можно подумать об относительной адресации. Тогда контейнер свободно перемещаем без изменения своего содержимого. И даже в файл сохраняется и назад извлекается.

    2019/02/07 13:10, utkin #

    Найти все ссылки на перемещаемый объект — задача не всегда тривиальная. Проблему можно было бы решить, если бы ссылки были двунаправленными: на кого ссылка и от кого ссылка. Это как в бухгалтерии метод двойной записи: у кого-то расход, а у кого-то приход.

    Всё правильно, нужна связь (можно и двунаправленный список) :).

    Отдельная тема: элементы какого-либо контейнера ссылаются друг на друга. В случае, когда контейнер занимает непрерывный участок памяти, можно подумать об относительной адресации.

    Генерируется уникальный идентификатор блока и всё. Поиск происходит не по адресу в памяти, а по таблице, которая содержит идентификатор и адрес. Работа идет с идентификаторами. Компилятор в своих операциях оперирует идентификаторами и только в момент обращения производит перевод в адреса для доступа к данным.

    2019/02/08 16:37, Автор сайта #

    Не понимаю, как компилятор может знать адреса в «куче». Если он их знает, то может выделить память либо статически, либо автоматически (в стеке).

    Я излагал другое. Получение относительного адреса элемента (смещения):Получение адреса элемента:На каждую операцию — одна-единственная команда процессора: вычитание или сложение. Понятно, что Вы не гонитесь за эффективностью в своём языке. Но тут не только эффективность, но и простота.

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

    2019/02/09 08:13, utkin #

    Не понимаю, как компилятор может знать адреса в «куче». Если он их знает, то может выделить память либо статически, либо автоматически (в стеке).

    А как он получает данные из кучи 🙂 ? Называйте это как хотите — адрес, ссылка, имя. Факт — у компилятора есть информация для доступа к данным.

    Решение по стеку по-прежнему не очевидно. Я у Вас спрашивал решение с 3 массивами. Вы в идеале хотите отказаться от кучи, это понятно. Но насколько мне известно, такого решения у Вас нет.

    На каждую операцию — одна-единственная команда процессора: вычитание или сложение. Понятно, что Вы не гонитель за эффективностью в своём языке. Но тут не только эффективность, но и простота.

    Я сторонник решения задачи, а не поклонения машинам. Не я должен изгибаться перед машиной, а она должна решать мои проблемы. Считайте это машиноненавистническим шовинизмом.

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

    По-моему, мы в русле. Опять же возвращаясь к классу задач, для которых у Вас пока нет решений на стеке.

    2019/02/09 13:07, Автор сайта #

    Компилятор из кучи данные не получает. Он лишь знает имя функции, которая выделяет память. Знает символическое имя адреса, это символическое имя получит значение в период исполнения. Но в период компиляции значение адреса не известно.

    Есть сложившееся знание о том, что от «кучи» в общем случае отказаться невозможно. Стеку (не важно, в каком количестве) нужен LIFO-порядок запросов на получение/освобождение памяти. Произвольный порядок может обслужить только «куча».

    Нет, мы тут не в русле, в заголовке статьи — про «кучу», а не про стек.

    Источники:
    • http://compiler.su/pochemu-dinamicheskoe-raspredelenie-pamyati-eto-ploho.php