Почему std :: bitset <8> 4 байта?

Question

Кажется, для std :: bitset <от 1 до 32> размер установлен в 4 байта.Для размеров от 33 до 64 он прыгает прямо до 8 байтов.Не может быть никаких издержек, потому что std :: bitset <32> имеет четные 4 байта.

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

Это под VS2010.

Answer 1

Наиболее вероятное объяснение состоит в том, что bitset использует целое число машинных слов для хранения массива.

Это, вероятно, сделано из-за пропускной способности памяти: обычно чтение / запись файла относительно дешевоСлово, которое выровнено по границе слова.С другой стороны, чтение (и особенно запись!) Произвольно выровненного байта может быть дорогим на некоторых архитектурах.

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

Answer 2

Если ваш std :: bitset <8> был членом структуры, вы могли бы иметь это:

struct A
{
  std::bitset< 8 > mask;
  void * pointerToSomething;
}

Если битовый набор <8> был сохранен в одном байте (и структура упакована в 1-байтовых границ), тогда указатель, следующий за ним в структуре, будет выровнен, что будет A Bad Thing.Единственный случай, когда было бы безопасно и полезно хранить набор битов <8> в одном байте, это если бы он был в упакованной структуре и сопровождался некоторыми другими однобайтовыми полями, с которыми он мог бы быть упакован вместе.Я полагаю, что это слишком узкий вариант использования для того, чтобы стоить предоставлять реализацию библиотеки.

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

Answer 3

Поскольку 32-разрядный Intel-совместимый процессор не может обращаться к байтам по отдельности (или, что лучше, он может неявно применять некоторые битовые маски и сдвиги), но только 32-битные слова за раз.1004 *

, даже если библиотека реализует его как char, a, b и c будут выровнены на 32 бита, поэтому существует такое же потерянное пространство.Но процессор будет вынужден предварительно маскировать байты, прежде чем позволить битовому коду создавать свою собственную маску.

По этой причине MS использовала int[1+(N-1)/32] в качестве контейнера для битов.

Answer 4

У меня была такая же особенность в реализациях Aix и Linux.В Aix внутреннее хранилище битовых массивов основано на символах:

typedef unsigned char _Ty;
....
_Ty _A[_Nw + 1];

В Linux внутреннее хранилище имеет длинную основу:

typedef unsigned long _WordT;
....
_WordT            _M_w[_Nw];

В целях совместимости мы модифицировали версию Linux с хранилищем на основе символов

Проверьте, какую реализацию вы используете внутри bitset.h

Answer 5

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

int wordIndex = (index & 0xfffffff8) >> 3;
int bitIndex = index & 0x7;

И тогда вы можете сделать это, что тоже очень быстро:

int word = m_pStorage[wordIndex];
bool bit = ((word & (1 << bitIndex)) >> bitIndex) == 1;

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

Для 1025 битов этот подход использует 132 байта вместо 129, для 2,3% служебных данных (и это уменьшается по мере роста сайта битов). Звучит разумно, учитывая возможные преимущества в производительности.

Answer 6

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

bitset<4> foo = 0;
if (foo) {
    // ...
}

, скорее всего, не удастся.Кроме того, я помню, как читал некоторое время назад, что был способ объединить несколько битрейтов, но я точно не помню.Я думаю, что когда у вас есть несколько наборов битов в структуре, они могут занимать «общую» память, что неприменимо к большинству случаев использования битовых полей.

Answer 7

Может быть, потому что он использует int по умолчанию и переключается на long long, если он переполняется? (Просто предположение ...)