Почему эти структуры данных обычно имеют размер 2 ^ n?

Question

Есть историческая причина или что-то? Я видел несколько раз что-то вроде char foo[256]; или #define BUF_SIZE 1024. Даже я в основном использую только буферы размером 2 ⁿ , в основном потому, что я думаю, что это выглядит более элегантно, и мне не нужно думать о конкретном числе. Но я не совсем уверен, что именно по этой причине большинство людей используют их, мы будем благодарны за дополнительную информацию.

Answer 1

Может быть несколько причин, хотя многие люди, как вы говорите, просто делают это по привычке.

Одним из мест, где это очень полезно, является эффективная реализация кольцевых буферов, особенно на архитектурах, где оператор% стоит дорого (без аппаратного деления - в основном 8-битные микроконтроллеры). Использование буфера 2 ^ n в этом случае по модулю - это просто случай маскирования битов старших бит или, скажем, 256-байтовый буфер, просто использование 8-битного индекса и возможность его обтекания.

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

Answer 2

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

Answer 3

Хеш-таблицы, Распределение по страницам

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

Глядя на старую книгу по Intel i386, and - это 2 цикла, а div - это 40 циклов. Несоответствие сохраняется и сегодня из-за гораздо большей фундаментальной сложности деления, даже несмотря на то, что общее время цикла в 1000 раз быстрее скрывает влияние даже самых медленных операций.

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

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

Answer 4

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

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

Answer 5

Я могу придумать несколько причин из головы:

1. 2 ^ n является очень распространенным значением для всех размеров компьютеров. Это напрямую связано с тем, как биты представлены в компьютерах (2 возможных значения), что означает, что переменные, как правило, имеют диапазоны значений, границы которых составляют 2 ^ n.
2. Из-за вышеприведенного пункта вы часто найдете значение 256 в качестве размера буфера. Это потому, что это наибольшее число, которое может быть сохранено в байте. Итак, если вы хотите сохранить строку вместе с размером строки, то вы будете наиболее эффективны, если вы сохраните ее как: SIZE_BYTE+ARRAY, где байт размера сообщает вам размер массива. Это означает, что массив может быть любого размера от 1 до 256.
3. Во многих других случаях размеры выбираются исходя из физических характеристик (например, размер памяти, из которой может выбирать операционная система, связан с размером регистров ЦП и т. Д.), И они также будут конкретное количество бит. Это означает, что объем памяти, который вы можете использовать, обычно равен 2 ^ n (для 32-битной системы 2 ^ 32).
4. Для таких значений могут быть проблемы с производительностью / выравниванием. Большинство процессоров могут одновременно получать доступ к определенному количеству байтов, поэтому, даже если у вас есть переменная, размер которой, скажем, 20 бит, 32-битный процессор все равно будет считывать 32 бита, несмотря ни на что. Поэтому часто бывает эффективнее сделать 32-битную переменную. Кроме того, некоторые процессоры требуют, чтобы переменные были выровнены с определенным количеством байтов (поскольку они не могут считывать память, например, из адресов в памяти, которые являются нечетными). Конечно, иногда речь идет не о нечетных ячейках памяти, а о местах, кратных 4 или 6 из 8 и т. Д. Поэтому в этих случаях более эффективно просто создавать буферы, которые будут всегда выровненными.

Хорошо, эти пункты вышли немного смешанными. Дайте мне знать, если вам нужно дальнейшее объяснение, особенно пункт 4, который ИМО является наиболее важным.

Answer 6

Из-за простоты (см. Также стоимость ) арифметики с основанием 2 в электронике: сдвиг влево (умножение на 2), сдвиг вправо (деление на 2).

В области CPU многие конструкции вращаются вокруг арифметики с основанием 2. Шины (управление и данные) для доступа к структуре памяти часто выровнены по мощности 2. стоимость логической реализации в электронике (например, CPU) делает арифметику в базе 2 неотразимой.

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

---

К вашему сведению: атрибуты системы, расположенной на уровне X, являются прямым следствием атрибутов уровня server системы, расположенной ниже, то есть layer

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

Answer 7

В хеш-таблицах 2 ^ n облегчает определенную обработку столкновений клавиш. В общем, когда происходит столкновение клавиш, вы либо создаете подструктуру, например, список всех записей с одинаковым хеш-значением; или вы найдете другой свободный слот. Вы можете просто добавить 1 к индексу слота, пока не найдете свободный слот; но эта стратегия не является оптимальной, потому что она создает кластеры заблокированных мест. Лучшей стратегией является вычисление второго хеш-числа h2, так что gcd (n, h2) = 1; затем добавьте h2 к индексу слота, пока не найдете свободный слот (с переворотом). Если n - степень 2, найти h2, который удовлетворяет gcd (n, h2) = 1, легко, каждое нечетное число подойдет.

Answer 8

В базе 2 получаются хорошие круглые числа. Так же, как 10, 100 или 1000000 - хорошие круглые числа в базе 10.

Если бы это не было степенью 2 (или чем-то близким, например, 96 = 64 + 32 или 192 = 128 + 64), тогда вы могли бы задаться вопросом, почему есть дополнительная точность. Округленный размер не по основанию 2 может быть вызван внешними ограничениями или незнанием программиста. Вы хотите знать, какой это.

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

Answer 9

Размер страницы также может быть равен 2.

В linux я люблю использовать getpagesize (), когда делаю что-то вроде разбивки буфера и записи его в сокет или дескриптор файла.

Answer 10

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

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

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

Если бы это не было степенью двойки, необходим разрыв. В старые времена (и в настоящее время на небольших фишках) это имело значение.