Разве использование переменных-указателей не накладные расходы памяти?

29

В таких языках, как C и C ++, при использовании указателей на переменные нам требуется еще одно место в памяти для хранения этого адреса. Так разве это не накладные расходы памяти? Как это компенсируется? Используются ли указатели в приложениях с нехваткой памяти, критичных ко времени?

Судип Бхандари
источник
11
Преимущества динамического выделения памяти значительно перевешивают стоимость указателя.
Джеймс Маклеод
32
Как вы думаете, другие языки (Java, C #, ...) хранят ссылки на объекты? (Подсказка: они используют указатели).
Эрик Эйдт
6
Указатель может находиться в регистрах или передаваться в качестве аргумента. В обоих случаях нет очевидных накладных расходов памяти. И указатель может быть вычислен (например, через арифметику указателя, функции, возвращающие указатели и т. Д.)
Василий Старынкевич,
9
Как насчет передачи (большого) аргумента структуры по адресу? Если вы посчитаете это как переменную указателя, это неизбежно для многих алгоритмов и использует намного меньше места, чем передача структуры по значению!
PJTraill
4
Это похоже на домашнее задание. Вопрос предназначен для изучения того, понимает ли ответ указатели и как они используются.
Майкл Шоу

Ответы:

34

На самом деле, накладные расходы на самом деле не лежат в дополнительных 4 или 8 байтах, необходимых для хранения указателя. Чаще всего указатели используются для динамического выделения памяти , что означает, что мы вызываем функцию для выделения блока памяти, и эта функция возвращает нам указатель, который указывает на этот блок памяти. Этот новый блок сам по себе представляет значительные накладные расходы.

Теперь вам не нужно заниматься распределением памяти, чтобы использовать указатель: у вас может быть массив, intобъявленный статически или в стеке, и вы можете использовать указатель вместо индекса, чтобы посетить ints, и это все очень красиво, просто и эффективно. Выделение памяти не требуется, и указатель обычно занимает столько же места в памяти, сколько и целочисленный индекс.

Кроме того, как Джошуа Тейлор напоминает нам в комментарии, указатели используются для передачи чего-либо по ссылке. Например, struct foo f; init_foo(&f);выделит f в стеке, а затем вызовет init_foo()указатель на это struct. Это очень распространено. (Только будьте осторожны, чтобы не передавать эти указатели «вверх».) В C ++ вы можете увидеть, что это делается с помощью «reference» ( foo&) вместо указателя, но ссылки - это не что иное, как указатели, которые вы не можете изменять, и они занимают такое же количество памяти.

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

Кроме того, C ++ является объектно-ориентированным языком, и существуют определенные аспекты ООП, такие как абстракция , которые достижимы только с помощью указателей. Даже языки, такие как Java и C #, широко используют указатели, они просто не позволяют вам напрямую манипулировать указателями, чтобы помешать вам делать с ними опасные вещи, но, тем не менее, эти языки начинают иметь смысл только после того, как вы понял, что за кулисами все делается с помощью указателей.

Таким образом, указатели используются не только в критичных по времени приложениях с низким объемом памяти, они используются повсеместно .

Майк Накис
источник
5
«Основная причина, по которой указатели используются для динамического выделения памяти» Это может иметь место в C ++, но не обязательно в C. В C указатели - ваш единственный способ передать что-либо по ссылке. Если вы не хотите копировать всю структуру, вам понадобится указатель на нее. Это все еще имеет смысл, даже если вы вообще не делаете динамическое распределение. Например, struct foo f; init_foo(&f);были бы выделить fв стеке , а затем вызвать init_fooс указателем на эту структуру. Это очень распространено. (Только будьте осторожны, чтобы не пропустить эти указатели «вверх».)
Джошуа Тейлор
@JoshuaTaylor, это очень правильно, я забыл об этом. Могу ли я изменить его к своему ответу? (Это считается хорошей практикой для программистов SE, потому что комментарии эфемерны, а ответы нет.)
Майк Накис
Обязательно добавьте свой ответ. :)
Джошуа Тейлор
2
Это само по себе представляет значительные накладные расходы, потому что этот блок будет иметь (скрытый) заголовок, который обычно достигает нескольких указателей. => На самом деле, современные реализации mallocимеют ОЧЕНЬ НИЗКИЕ заголовки, поскольку они кластеризуют выделенные блоки в «сегменты». С другой стороны, это приводит к перераспределению в общем: вы запрашиваете 35 байтов и получаете 64 (без вашего ведома), тратя таким образом 29 ...
Матье М.
1
@MikeNakis: выглядит лучше, спасибо, что остались со мной :)
Матье М.
35

Так разве это не накладные расходы памяти?

Конечно, дополнительный адрес (как правило, 4/8 байтов в зависимости от процессора).

Как это компенсируется?

Нет. Если вам нужна косвенность, необходимая для указателей, то вы можете заплатить за это.

Используются ли указатели в приложениях с нехваткой памяти?

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

Telastyn
источник
1
@DavidGrinberg Это только в том случае, если нет оптимизации возвращаемого значения .
Даркхогг
3
Я использовал указатели при написании TSR-приложений для DOS, которые должны были умещаться в 15 тыс. Назад в восьмидесятых. Так что да, они используются в приложениях с низким объемом памяти.
Gort the Robot
1
@StevenBurnap Вы называете 15 КБ памяти для приложения TSR? Однажды я написал инструмент TSR, который потреблял только 16 байтов памяти.
kasperd
22
@kasperd: И в свое время у нас были только нули
Джек,
11

У меня не совсем то же самое, что и у Теластина.

Системные глобальные переменные во встроенном процессоре могут быть адресованы конкретными жестко закодированными адресами.

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

Локальные переменные появляются при вводе функции и адресуются как смещение от другого специального указателя, часто называемого «указатель кадра». Это включает в себя аргументы функции. Если вы внимательно относитесь к появлению и извлечению указателя стека, вы можете покончить с указателем кадра и получить доступ к локальным переменным прямо из указателя стека.

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

Роберт Бристоу-Джонсон
источник
6

Да, конечно. Но это балансирование.

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

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

Гонки легкости с Моникой
источник
5

В таких языках, как C и C ++, при использовании указателей на переменные нам требуется еще одно место в памяти для хранения этого адреса. Так разве это не накладные расходы памяти?

Вы предполагаете, что указатель должен быть сохранен. Это не всегда так. Каждая переменная хранится по некоторому адресу памяти. Скажем, вы longобъявили как long n = 5L;. Это выделяет память для nпо некоторому адресу. Мы можем использовать этот адрес, чтобы делать причудливые вещи, например, *((char *) &n) = (char) 0xFF;манипулировать частями n. Адрес nнигде не сохраняется как дополнительная служебная информация.

Как это компенсируется?

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

Используются ли указатели в приложениях с нехваткой памяти?

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

Лоренс
источник
Некоторые переменные хранятся не в памяти, а только в регистрах
Василий Старынкевич
@BasileStarynkevitch: Вы можете предложить, чтобы переменные оставались в регистрах, но компилятор не обязан это делать. Если вы не программируете на ассемблере, у вас действительно нет такого уровня контроля над немедленным хранением. И даже в ассемблере любая вызванная вами подпрограмма, скорее всего, выливает регистры в стек, поэтому она может использовать их для своих переменных. Так что для любой нетривиальной программы почти наверняка ваши переменные проведут в памяти хотя бы некоторое время.
TMN
Компилятору может быть разрешено хранить некоторые локальные переменные только в регистрах, и большинство оптимизирующих компиляторов делают это (попробуйте gcc -fverbose-asm -S -O2скомпилировать некоторый код на C)
Basile Starynkevitch
@BasileStarynkevitch Я не уверен в том, что вы пытаетесь сделать замечание о том, что переменные могут храниться исключительно в регистрах. Не могли бы вы уточнить?
Лоуренс
5

Наличие указателя определенно потребляет некоторые накладные расходы, но вы также можете увидеть и положительный эффект. Указатель подобен индексу. В C вы можете использовать сложные структуры данных, такие как строки и структуры только из-за указателей.

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

Даже ваши обычные переменные имеют запись в таблице символов, которая хранит адрес, на который указывает ваша переменная. Так что я не думаю, что это создает большие накладные расходы с точки зрения памяти (всего 4 или 8 байтов). Даже языки, такие как java, используют указатели внутри (ссылка), они просто не позволяют вам манипулировать ими, поскольку это сделает JVM менее защищенным.

Вы должны использовать указатели только тогда, когда у вас нет другого выбора, например отсутствующих типов данных, структур (в c), так как использование указателей может привести к ошибкам, если не обрабатываться должным образом, и сравнительно сложнее для отладки.

Krrish Raj
источник
3

Так разве это не накладные расходы памяти?

Да нет наверное?

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

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

Как мы отслеживаем, где хранятся аудиоданные? Нам нужен адрес памяти для этого. Программа не только должна отслеживать аудио порции данных в памяти , но и где она находится в памяти. Таким образом, нам нужно хранить адрес памяти (т. Е. Указатель). И размер хранилища, требуемый для адреса памяти, будет соответствовать диапазону адресов компьютера (например: 64-разрядный указатель для 64-разрядного диапазона адресов).

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

Как это компенсируется?

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

Другой способ - использовать более смежные структуры данных. Например, вместо двусвязного списка может использоваться последовательность на основе массива, для которой требуется два указателя на узел. Мы также можем использовать гибрид этих двух, как развернутый список, в котором хранятся только указатели между каждой смежной группой из N элементов.

Используются ли указатели в приложениях с нехваткой памяти?

Да, очень часто, так как многие критичные к производительности приложения написаны на C или C ++, в которых преобладает использование указателя (они могут находиться за интеллектуальным указателем или контейнером, подобным std::vectorили std::string, но основная механика сводится к используемому указателю). отслеживать адрес к динамическому блоку памяти).

Теперь вернемся к этому вопросу:

Как это компенсируется? (Часть вторая)

Указатели, как правило, очень дешевы, если только вы не храните их как миллион (что все равно составляет всего 8 мегабайт на 64-битной машине).

* Обратите внимание, как Бен указал, что «жалкие» 8 мегабайт по-прежнему размер кеша L3. Здесь я использовал «жалкое» больше в смысле общего использования DRAM и типичного относительного размера блоков памяти, на которые будет указывать правильное использование указателей.

Где указатели становятся дорогими, это не сами указатели, а:

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

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

Доступ к памяти

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

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

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

Многие компиляторы для таких языков в наши дни делают действительно большую работу по выбору инструкций и распределению регистров, но отсутствие более непосредственного контроля над управлением памятью здесь может быть убийственным (хотя часто менее подверженным ошибкам) ​​и по-прежнему делать такие языки, как C и C ++ довольно популярны.

Косвенная оптимизация доступа к указателю

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

В погоне за указателями

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

Foo->Bar->Baz->null

Проблема состоит в том, что если мы выделим все эти узлы отдельно от общего распределителя (и, возможно, не все сразу), фактическая память может быть распределена примерно так (упрощенная схема):

введите описание изображения здесь

Когда мы начинаем гоняться за указателями и получать доступ к Fooузлу, мы начинаем с принудительного промаха (и, возможно, сбоя страницы), перемещая порцию из области памяти из более медленных областей памяти в более быстрые области памяти, например так:

введите описание изображения здесь

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

введите описание изображения здесь

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

* Примечание: это очень упрощенная схема и обсуждение иерархии памяти и местоположения ссылок, но, надеюсь, она соответствует уровню вопроса.


источник
1
«ничтожные 8 мегабайт» - это типичный размер всего кэша L3 на современном процессоре
Бен Фойгт
1
@BenVoigt Я постараюсь это исправить. Конечно, это было бы ужасно, если бы каждый указатель указывал на 32-битный кусок памяти, например
@BenVoigt Добавлена ​​сноска, чтобы попытаться прояснить эту часть!
Это разъяснение выглядит хорошо.
Бен Фойгт
1

Так разве это не накладные расходы памяти?

Это действительно накладные расходы памяти, но очень маленькие (до незначительности).

Как это компенсируется?

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

Используются ли указатели в приложениях с нехваткой памяти?

Да.

utnapistim
источник
0

Вам нужно только дополнительное использование памяти (обычно 4-8 байт на указатель), пока вам нужен этот указатель. Есть много методов, которые делают это более доступным.

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

В чрезвычайно ограниченных ситуациях с памятью это можно использовать для минимизации затрат. Если вы работаете в очень узком пространстве памяти, у вас обычно есть хорошее представление о том, сколько объектов вам нужно манипулировать. Вместо того, чтобы выделять кучу целых чисел по одному и сохранять на них полные указатели, вы можете воспользоваться своим знанием разработчика, что у вас никогда не будет больше 256 целых чисел в этом конкретном алгоритме. В этом случае вы можете сохранить указатель на первое целое число и отслеживать индекс, используя символ (1 байт), а не полный указатель (4/8 байт). Вы также можете использовать алгоритмические приемы для генерации некоторых из этих индексов на лету.

Этот вид памяти добросовестности был очень популярен в прошлом. Например, игры NES будут в значительной степени полагаться на свою способность собирать данные и генерировать указатели алгоритмически, а не хранить их оптом.

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

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

Корт Аммон - Восстановить Монику
источник
0

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

Одним примером приложения, критичного ко времени, является сетевой стек. Хороший сетевой стек будет спроектирован так, чтобы быть «нулевой копией» - и для этого требуется умное использование указателей.

paj28
источник