Qual è la dimensione del mio Bitset?

Question

Desidero memorizzare System.currentTimeInMillis nella memoria con il minimo spazio possibile. perché devo memorizzarne milioni in memoria.

ho convertito a binaryString che mi ha dato 41 bits

Ecco il mio programma di

public class BitSetSize { 
    public static void main(final String[] args) { 
     final long currentTimeMillis = System.currentTimeMillis(); 
     final String currentTimeToBinaryString = Long.toBinaryString(currentTimeMillis); 
     System.out.println("Size in bits: " + currentTimeToBinaryString.length()); 

     final BitSet bitSet = BitSet.valueOf(new long[]{currentTimeMillis}); 
     System.out.println("Bitset length: " + bitSet.length()); 
     System.out.println("Bitset size: " + bitSet.size()); 

     System.out.println("Size of biset object(bytes): " + MemoryMeasurer.measureBytes(bitSet)); 
    } 
} 

Ma quando l'eseguo ottengo

Size in bits: 41 
Bitset length: 41 
Bitset size: 64 
Size of biset object(bytes): 48 

Domanda
- Perché bitSet.length() e bitSet.size() differiscono? Presumo che lo length() sia corretto?
- Sto usando memory-measurer per conoscere le dimensioni di bitSet, ma mi dice 48 bytes, perché non è (41/8) byte?

Sono confuso

Answer 1

Prima di tutto voglio consigliare lo strumento giusto per analizzare gli schemi di layout degli oggetti nelle JVM - JOL. Nel tuo caso (java -jar jol-cli/target/jol-cli.jar internals java.util.BitSet) JOL produce il seguente risultato:

Running 64-bit HotSpot VM. 
Using compressed references with 3-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] 

java.util.BitSet object internals: 
OFFSET SIZE TYPE DESCRIPTION     VALUE 
     0  4   (object header)    01 00 00 00 (00000001 00000000 00000000 00000000) (1) 
     4  4   (object header)    00 00 00 00 (00000000 00000000 00000000 00000000) (0) 
     8  4   (object header)    f4 df 9f e0 (11110100 11011111 10011111 11100000) (-526393356) 
    12  4  int BitSet.wordsInUse    0 
    16  1 boolean BitSet.sizeIsSticky   false 
    17  3   (alignment/padding gap)  N/A 
    20  4 long[] BitSet.words     [0] 
Instance size: 24 bytes (reported by Instrumentation API) 
Space losses: 3 bytes internal + 0 bytes external = 3 bytes total 

per i calcoli non sono corretti a causa di campi statici, così un vuoto BitSet si riserva 24 byte. Si noti che questi calcoli non sono esatti al 100% perché non è stata presa in considerazione la dimensione dell'oggetto long[]. Così i giusti risultati sono java -jar jol-cli/target/jol-cli.jar externals java.util.BitSet:

Running 64-bit HotSpot VM. 
Using compressed references with 3-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] 

java.util.BitSet@6b25f76bd object externals: 
      ADDRESS  SIZE TYPE    PATH       VALUE 
     7ae321a48   24 java.util.BitSet        (object) 
     7ae321a60   24 [J    .words       [0] 

questo significa un vuoto BitSet si utilizza 48 byte, compresi lunga serie. Inoltre è possibile ottenere il layout stimato dell'oggetto in diverse modalità VM java -jar jol-cli/target/jol-cli.jar estimates java.util.BitSet

Answer 2

Sede java doc di BitSet.

Ogni bit impostato ha una dimensione corrente, ovvero il numero di bit di spazio attualmente in uso dal bit impostato. Si noti che la dimensione è correlata all'implementazione di di un set di bit, pertanto potrebbe cambiare con l'implementazione. La lunghezza di un bit di si riferisce alla lunghezza logica di un bit impostato ed è definita indipendentemente dall'implementazione.

Answer 3

Il codice attuale non può essere lo stoccaggio per milioni di long (System.currentTimeInMillis). È possibile utilizzare trove TLongHashSet o si dovrebbe guardare a sparse bitset. Ma BitSet ha indice int, quindi dovresti comprimere da longTimeInMillis a int. Per esempio. bitSetIndex = (int) (currentTimeInMillis - initialTime). Ti dà un intervallo di 2^32 millisec (~ 50 giorni) a partire da Initial Time.

//store sample for bitset: 
bitSet.set(System.currentTimeInMillis()); 

EDIT

Uno scopo BitSet alloca più di 100 byte sul mucchio. Quindi dovresti riutilizzare un oggetto BitSet per molti valori lunghi. Il modo più semplice è utilizzare il valore lungo come indice all'interno di BitSet e impostare il valore come true in questo indice. Ma ci sono diversi problemi (li ho descritto sopra):

1. BitSet ha indice int non molto tempo
2. java.util.BitSet non è la memoria efficiente.

Answer 4

Come menzionato da BetaRide, la dimensione effettiva di BitSet è specifica dell'implementazione. Detto questo, nelle implementazioni Oracle/OpenJDK (almeno, in 6, 7 e 8), l'elemento base di stato è un long[] of words. Ciò significa che la dimensione è sempre un multiplo di 64.

quanto riguarda i 48 byte, conto nel codice:

• 16 byte for the BitSet object itself
• 20 byte per l'oggetto long[] (16 per l'oggetto, 4 per la lunghezza)
• 8 byte per il contenuto della matrice (ogni elemento è 8 byte, ma basta uno)
• 4 byte per int wordsInUse
• 1 byte per boolean sizeIsSticky

Quali rendimenti 49 - non lontano dai 48 che stai vedendo. Se quelli object headers are compressed, ma anche il padding viene introdotto, probabilmente è da dove viene il 48.

Answer 5

Perché bitSet.length() e bitSet.size() differiscono? Presumo che la lunghezza() sia corretta?

Il BitSet.size() è la dimensione della struttura dati interna utilizzata per memorizzare i valori di bit. Poiché lo standard BitSet utilizza internamente un array long[], la dimensione è sempre un multiplo di 64 bit. Per esempio. se si imposta il 64 ° bit in un BitSet lo BitSet deve aumentare la capacità dell'array long[] per archiviare tale valore, poiché ogni lungo può "solo" memorizzare 64 bit. Per esempio.

BitSet bitSet = new BitSet(); 
for (int i = 0; i <= 64; i++) { 
    bitSet.set(i, true); 
    System.out.println(bitSet.size()); 
} 

BitSet.length() restituisce i bit occupati effettivi nel BitSet. Quindi, se si crea un nuovo BitSet la sua lunghezza è 0. Se si imposta quindi il 4 ° bit, la lunghezza sarà 5. Lo size rimarrà 64, poiché è necessario solo uno lungo per memorizzare 5 bit.

BitSet bitSet = new BitSet(); 
System.out.println(bitSet.length()); // 0 
bitSet.set(4, true); 
System.out.println(bitSet.size()); // 64 
System.out.println(bitSet.length()); // 5 

Sto usando la memoria-misuratore per conoscere la dimensione del bitset, ma mi dicono 48 byte, perché non è (41/8) Byte?

A causa del riempimento della memoria. Conosciuto anche come data structure alignment. L'oggetto BitSet ha bisogno di 41 byte matematici in memoria.

• 8 byte per l'intestazione oggetto
• 20 byte per i long[]
• 8 byte per la long nell'array
• 4 byte per i wordsInUseint variabili
• 1 byte per il sizeIsStickyboolean

Ma jvm non può allocare 41 bit in modo da arrotondarlo al multiplo successivo di 8. Questo è 48.

Questa dimensione può variare, poiché la dimensione dell'intestazione dell'oggetto può variare da un'implementazione JVM a un'altra. Quindi se l'intestazione dell'oggetto è 16 byte. Il totale sarà 49 e il jvm lo arrotolerà al prossimo multiplo di 8.In questo caso 56.