Каково теоретическое влияние прямого доступа к индексу с «высоким» использование памяти по сравнению со «сдвигом» индексный доступ с «низким» использование памяти?
Что ж, мне действительно любопытно, какую практику лучше придерживаться, я знаю, что (вероятно?) Не имеет никакого значения для производительности вообще (даже в приложениях, критичных для производительности?), Но мне больше любопытно влияние на сгенерированный код с оптимизация в виду (и ради полноты, а также «производительность», если это имеет значение).
Таким образом, проблема заключается в следующем:
индексы элементов варьируются от A до B, где A> 0 и B> A (например, A = 1000 и B = 2000).
Для хранения информации о каждом элементе существует несколько возможных решений, два из которых используют простые массивы, включают прямой доступ к индексу и доступ путем манипулирования индексом:
//declare the array with less memory, "just" 1000 elements, all elements used
std::array<T, B-A> Foo;
//but make accessing by index slower?
//accessing index N where B > N >= A
Foo[N-A];
//or declare the array with more memory, 2000 elements, 50% elements not used, not very "efficient" for memory
std::array<T, B> Foo;
//but make accessing by index faster?
//accessing index N where B > N >= A
Foo[N];
Я бы лично занял второе место, потому что мне действительно нравится выступление, но я думаю, что на самом деле:
- компилятор позаботится об обеих ситуациях?
- Как это влияет на оптимизацию?
- Как насчет производительности?
- это имеет значение вообще?
- Или это просто очередная «микрооптимизация», о которой не должен беспокоиться ни один человек?
- Есть ли какое-то соотношение между использованием памяти и скоростью, которое рекомендуется?
Решение
Доступ к любому массиву с индексом включает добавление индекса, умноженного на размер элемента, и добавление его к базовому адресу самого массива.
Так как мы уже добавляем одно число к другому, вносим корректировку для foo[N-A] может быть легко сделано путем корректировки базового адреса вниз N * sizeof(T) перед добавлением A * sizeof(T), а не на самом деле расчет (A-N)*sizeof(T),
Другими словами, любой достойный компилятор должен полностью скрыть это вычитание, предполагая, что это постоянное значение.
Если это не константа [скажем, вы используете std::vector инстред std::arrayтогда вы действительно вычтете A от N в какой-то момент в коде. Это все еще довольно дешево сделать это. Большинство современных процессоров могут сделать это за один цикл без задержки для результата, поэтому в худшем случае к доступу добавляется один тактовый цикл.
Конечно, если числа 1000-2000, вероятно, не имеет большого значения во всей схеме вещей — либо общее время обработки почти ничего, либо это много, потому что вы делаете сложные вещи. Но если вы сделаете из него миллион элементов, смещенный на полмиллиона, это может иметь значение для простого или сложного метода их распределения или для некоторого другого.
Кроме того, как предполагает Ганс Пассант: Современные ОС с виртуальной обработкой памяти неиспользуемой памяти не заполняются «реальной памятью». На работе я исследовал странный сбой на плате с 2 ГБ ОЗУ, и при просмотре использования памяти он показал, что для этого приложения было выделено 3 ГБ виртуальной памяти. На этой плате нет своп-диска (это встроенная система). Оказывается, какой-то код просто выделял большие куски памяти, которые не были заполнены чем-либо, и он прекращал работать только тогда, когда достигал 3 ГБ (32-разрядный процессор, 3 + 1 ГБ памяти, разделенной между пространством пользователя / ядра). Так что даже для БОЛЬШИХ кусков памяти, если у вас есть только половина ее, она фактически не будет занимать ОЗУ, если вы на самом деле не обращаетесь к ней.
Как ВСЕГДА, когда дело доходит до производительности, компиляторы и тому подобное, если это важно, не доверяют «Интернету», чтобы сказать вам ответ. Создайте тест с кодом, который вы на самом деле намереваетесь использовать, используя фактический компилятор (ы) и тип (ы) процессора, для которых вы планируете создавать код с / для, и запустите тесты. Некоторый компилятор может иметь ошибку (на процессоре типа XYZ9278), из-за чего он генерирует ужасный код для случая, когда большинство других компиляторов делают это «без дополнительных затрат».
Другие решения