Perché tutti usano numeri 2^n per l'allocazione? -> new StringBuilder (256)

Question

15 anni fa, mentre programmavo con Pascal, ho capito perché usare la potenza di due per l'allocazione di memoria. Ma questo sembra ancora lo stato dell'arte.

C# Esempi:

new StringBuilder(256); 
new byte[1024]; 
int bufferSize = 1 << 12; 

ho ancora vedere questo migliaia di volte, io uso questo me stesso e sto ancora in discussione:

abbiamo bisogno di questo nei moderni linguaggi di programmazione e hardware moderno?
Immagino che sia una buona pratica, ma qual è la ragione?

EDIT
Ad esempio una matrice byte[], come affermato da risposte qui, una potenza di 2 avrà alcun senso: (?) L'array utilizzerà 16 byte, quindi ha senso usare 240 (= 256-16) per le dimensioni per un totale di 256 byte?

Answer 1

abbiamo bisogno di questo nei moderni linguaggi di programmazione e hardware moderno? Immagino che sia una buona pratica, ma qual è la ragione?

Dipende. Ci sono due cose da considerare qui:

1. Per dimensioni inferiori alla dimensione della pagina di memoria, non c'è differenza apprezzabile tra un power-of-two e un numero arbitrario per allocare lo spazio;
2. Si utilizzano principalmente strutture dati gestite con C#, quindi non si sa nemmeno quanti byte siano effettivamente allocati sotto.

Supponendo che si sta facendo l'allocazione di basso livello con malloc(), utilizzando multipli della dimensione della pagina sarebbe considerato una buona idea, vale a dire 4096 o 8192; questo perché consente una gestione più efficiente della memoria.

Il mio consiglio sarebbe semplicemente di allocare ciò che è necessario e lasciare che C# gestisca la gestione della memoria e l'allocazione per voi.

Answer 2

IMHO, qualsiasi cosa che termina con la potenza esatta dell'operazione aritmetica di due è come una corsia preferenziale. l'operazione aritmetica di basso livello per la potenza di due richiede un minor numero di giri e manipolazioni di bit rispetto a qualsiasi altro numero richiede un lavoro supplementare per la CPU.

e abbiamo trovato questo Eventuali duplicati: Is it better to allocate memory in the power of two?

Answer 3

In alcuni casi ha ancora senso, ma preferirei analizzare caso per caso se ho bisogno di quel tipo di specifica o no, piuttosto che usarlo ciecamente come buona pratica.

Ad esempio, potrebbero esserci casi in cui si desidera utilizzare esattamente 8 bit di informazioni (1 byte) per indirizzare una tabella.

In tal caso, avrei lasciato che la tabella avesse la dimensione di 2^8.

Object table = new Object[256]; 

Da questo, si sarà in grado di affrontare qualsiasi oggetto del tavolo utilizzando un solo byte.

Anche se la tabella è effettivamente più piccola e non utilizza tutti i 256 posti, si ha comunque la garanzia del mapping bidirezionale dalla tabella all'indice e dall'indice alla tabella, che potrebbe impedire errori che verrebbero visualizzati, ad esempio, se hai avuto:

Object table = new Object[100]; 

E quindi qualcuno (probabilmente qualcun altro) lo accede con un valore di byte fuori intervallo della tabella.

Forse questo tipo di comportamento biettivo potrebbe essere buono, forse potresti avere altri modi per garantire i tuoi vincoli.

Probabilmente, dato l'aumento di intelligenza degli attuali compilatori, non è più l'unica buona pratica.

Answer 4

Purtroppo, è piuttosto stupido se si desidera mantenere un blocco di memoria in una singola pagina di memoria di 4k ... E le persone non lo sanno nemmeno :-) (non l'ho fatto fino a 10 minuti fa .. . ho avuto solo un sospetto) ... un esempio ... e 'codice unsafe e l'attuazione dipendente (usando .NET 4.5 a 32/64 bits)

byte[] arr = new byte[4096]; 

fixed (byte* p = arr) 
{ 
    int size = ((int*)p)[IntPtr.Size == 4 ? -1 : -2]; 
} 

Così il CLR ha stanziato almeno 4096 + (1 o 2) sizeof (int) ... Quindi è passato oltre una pagina di memoria da 4k. Questo è logico ... Deve mantenere la dimensione dell'array da qualche parte, e tenerlo insieme alla matrice è la cosa più intelligente (per quelli che sanno che Pascal Strings e BSTR sono, sì, è lo stesso principio)

Aggiungo che tutti gli oggetti in .NET hanno un numero syncblck e uno RuntimeType ... Sono almenose non lo sono IntPtr, quindi un totale compreso tra 8 e 16 byte/oggetto (Questo è spiegato in vari luoghi ... prova a cercare .net object header se sei interessato)

Answer 5

Sì, è una buona pratica e ha almeno un motivo. I processori moderni hanno dimensioni cache L1 di 64 byte e se si utilizzerà la dimensione del buffer come 2^n (ad esempio 1024, 4096, ..), si utilizzerà completamente la cache-line, senza spreco di spazio. In alcuni casi, ciò consentirà di evitare problemi di condivisione errata (http://en.wikipedia.org/wiki/False_sharing).