Почему вычисляется адрес для длин элементов массива, делящихся по степеням 2 более эффективным?

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

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

Почему это так?

Вышеуказанная строка написана под заголовком "Использование"

Ответ 1

Умножение на 2 ⁿ выполняется сдвигом влево. Современные процессоры могут перемещаться за один цикл (и в x86, для небольших сдвигов до 8 или 16, встроенных в сам расчет адресов). Регулярная операция умножения занимает 4-10 тактов на машинах AMD64 и, скорее всего, аналогична на современных процессорах Intel. Существуют также ограничения на то, как можно "сблизить" две последовательные операции умножения.

Конечно, если размер массива достаточно велик, может быть более эффективным использовать инструкцию умножения и более аккуратно упаковывать данные (не используя отступы для расширения данных до 2-х размеров), из-за эффективность кэширования

Конечно, современные компиляторы умны, поэтому, если вам нужно умножить на X на 12, компилятор будет генерировать (X << 3) + (X << 2), например, который быстрее, чем одна операция умножения.

Ответ 2

Расчет адреса i-го элемента включает base + size_of_element * i.

Если размер элемента равен 2, например size_of_element = 2 ^ m, то это может быть достигнуто с помощью base + (i << m).

Сдвиг намного эффективнее по сравнению с умножением, связанным с более ранним расчетом.

Ответ 3

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

Ответ 4

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