Почему внутренние данные BitSet в java хранятся как long [] вместо int [] в Java?

Ответ 1

При запросе или обработке одного бита нет существенной разницы. Вам нужно рассчитать индекс слова и прочитать это слово, а в случае обновления - обработать один бит этого слова и записать его обратно. Это все равно для int[] и long[].

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

С другой стороны, вы получаете большой выигрыш при обработке нескольких бит одновременно. Когда вы выполняете операции типа and, or или xor для всего BitSet, вы можете выполнить операцию над целым словом, прочитав 64 бита сразу при использовании массива long.

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

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

Ответ 2

На 64-битных машинах, выполняющих поразрядные операции с одним значением long, значительно более эффективны, чем те же операции над двумя значениями int, поскольку 64-битные значения напрямую поддерживаются аппаратным обеспечением. На 32-битных машинах разница, вероятно, не очень значительна.

Ответ 3

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

BitSets упаковываются в массивы "слов". В настоящее время слово длинный, который состоит из 64 бит, требующих 6 адресных бит. Выбор размера слова определяется чисто соображениями производительности.

Ответ 4

Конечно, проблема оптимизации: одно значение long хранит до 64 бит, а int - только 32. Таким образом, любая длина пользователя под 64 требует только одной записи в массиве. Если это массив из int, ему потребуется две записи, которые медленнее и тяжелее поддерживать.

Ответ 5

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