Почему BitSet реализован на массиве long

#java

Нигде, почему-то, в интернете не объясняется выбор long в качестве хранилица BitSet.
Например, почему нельзя использова вместо него short. Пусть мы заполняем структуру
N ( N< 64 ) элементами, тогда получится, что в сравнении с short , оверхед по памяти
будет больше.  
    

Ответы

Ответ 1

Не представляю что такое Bitset и с java не знаком. Но если делать какой то базовый
класс для работы с битами и не делать его с меняемым размером элементов хранения я
бы остановился на выборе максимального по размеру типа влезающего в регистр процессора
для данной архитектуры. С точки зрения процессора операция с short и long занимает
одинаковое время выполнения. Кроме того, операция с данными в оперативной памяти не
выравненными на ширину шины данных обычно происходит дольше. В связи с этим данные
стараются выравнивать на ширину шины. Попытки выровнять short приведет к образованию
неиспользуемого пространства, что сведет экономию памяти к 0

На современной архитектуре intel используется 64 разрядные регистры и необходимо
такое же выравнивание данных в памяти, для быстрой работы


Ответ 2

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

Если взять JOL и посмотреть, сколько памяти ест объект, то на 32bit jvm (OpenJDK
7u91 на i686 ubuntu 14.04 в virtualbox) картина будет такая:

Running 32-bit HotSpot VM.
Objects are 8 bytes aligned.
Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

java.util.BitSet object internals:
 OFFSET  SIZE    TYPE DESCRIPTION                    VALUE
      0     8         (object header)                N/A
      8     4     int BitSet.wordsInUse              N/A
     12     1 boolean BitSet.sizeIsSticky            N/A
     13     3         (alignment/padding gap)        N/A
     16     4  long[] BitSet.words                   N/A
     20     4         (loss due to the next object alignment)
Instance size: 24 bytes (estimated, the sample instance is not available)
Space losses: 3 bytes internal + 4 bytes external = 7 bytes total


8 байт ушло на заголовок объекта, еще 8 - на поля класса, и 4 байта на указатель
на массив long. Т.к. объекты выравниваются по 8 байт, то еще 4 байта потеряно на этом.

[S object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0     8       (object header)                N/A
      8     4   int [S.length                      N/A
     12     0 short [S.                  N/A
     12     4       (loss due to the next object alignment)
Instance size: 16 bytes (estimated, the sample instance is not available)
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

[S@8b6c39d object externals:
          ADDRESS       SIZE TYPE PATH                           VALUE
         6f5b9950         16 [S                                [5, 7]


Массив - тоже объект, и занимает 16 байт даже без данных (8 - заголовок, 4 - поле
length, 4 - пустые). Массив short[2] хранит данные в последних 4 байтах. Массив short[3]
уже занимает 24 байта.

Т.е. для N <= 32 (4 байта) мы могли бы сэкономить 8 байт, потратив на объекты 40 байт.

На 64bit (jdk 1.8.0_45 на Windows 7 64) даже такой экономии не получается:

Running 64-bit HotSpot VM.
Using compressed oop with 0-bit shift.
Using compressed klass with 0-bit shift.
Objects are 8 bytes aligned.
Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

[S object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0    12       (object header)                N/A
     12     4   int [S.length                      N/A
     16     0 short [S.                  N/A
Instance size: 16 bytes (estimated, the sample instance is not available)
Space losses: 0 bytes internal + 0 bytes external = 0 bytes total

[S@238e0d81d object externals:
          ADDRESS       SIZE TYPE PATH                           VALUE
         d5f14ce8         24 [S                                [5, 7]


т.к. заголовок объекта занимает 12 байт, и под массив ненулевой длины в любом случае
будет выделено еще 8 байт.

Ссылки:


Вопрос на SO про производительность long[] против int[].
Вопрос на SO про перерасход памяти.