Perché le strutture dati di solito hanno una dimensione di 2 ^ n?

Question

C'è una ragione storica o qualcosa del genere? Ho visto alcune volte qualcosa come char foo[256]; o #define BUF_SIZE 1024. Anche io uso principalmente solo 2 buffer di dimensioni ⁿ , principalmente perché penso che appaia più elegante e in questo modo non devo pensare a un numero specifico. Ma non sono del tutto sicuro se questo è il motivo per cui la maggior parte delle persone li utilizza, più informazioni sarebbero apprezzate.

Answer 1

Potrebbero esserci diverse ragioni, anche se molte persone, come dici tu, lo faranno semplicemente per abitudine.

Un punto in cui è molto utile è l'implementazione efficiente di buffer circolari, in particolare su architetture in cui l'operatore% è costoso (quelli senza una divisione dell'hardware - principalmente microcontroller a 8 bit). Utilizzando un buffer 2 ^ n in questo caso, il modulo, è semplicemente un caso di mascheramento di bit dei bit superiori, o nel caso di un buffer di 256 byte, semplicemente usando un indice di 8 bit e lasciandolo avvolgente.

In altri casi l'allineamento con i confini della pagina, le cache ecc. può offrire opportunità di ottimizzazione su alcune architetture, ma sarebbe molto specifico per l'architettura. Ma è possibile che tali buffer forniscano al compilatore possibilità di ottimizzazione, quindi, a parità di altre condizioni, perché no?

Answer 2

Le linee della cache sono in genere un multiplo di 2 (spesso 32 o 64). I dati che sono un multiplo integrale di quel numero sarebbero in grado di adattarsi (e utilizzare pienamente) il numero corrispondente di righe della cache. Maggiore è il numero di dati che puoi inserire nella cache, migliori sono le prestazioni .. quindi penso che le persone che progettano le loro strutture in quel modo si stiano ottimizzando per questo.

Answer 3

Un altro motivo in aggiunta a quello che tutti gli altri hanno menzionato è che le istruzioni SSE accettano più elementi e il numero di elementi immessi è sempre una potenza di due. Rendere il buffer una potenza di due garantisce che non leggerai la memoria non allocata. Questo vale solo se stai effettivamente utilizzando le istruzioni SSE.

Penso alla fine, tuttavia, la ragione schiacciante nella maggior parte dei casi è che ai programmatori piacciono i poteri di due.

Answer 4

Tabelle hash, allocazione per pagine

Questo aiuta davvero per le tabelle hash, perché si calcola l'indice modulo la dimensione, e se quella dimensione è una potenza di due, il modulo può essere calcolato con un semplice bit per bit e o & amp; anziché utilizzare un'istruzione di classe di divisione molto più lenta che implementa l'operatore % .

Guardando un vecchio libro Intel i386, e sono 2 cicli e div è 40 cicli. Una disparità persiste oggi a causa della complessità fondamentale della divisione molto maggiore, anche se i tempi di ciclo complessivi 1000 volte più veloci tendono a nascondere l'impatto anche delle operazioni più lente della macchina.

C'è stato anche un tempo in cui il sovraccarico malloc occasionalmente veniva evitato a lungo. L'allocazione disponibile direttamente dal sistema operativo sarebbe (lo è ancora) un numero specifico di pagine, e quindi una potenza di due potrebbe probabilmente sfruttare al meglio la granularità dell'allocazione.

E, come altri hanno notato, ai programmatori piacciono i poteri di due.

Answer 5

Riesco a pensare ad alcuni motivi dalla parte superiore della mia testa:

1. 2 ^ n è un valore molto comune in tutte le dimensioni di computer. Questo è direttamente correlato al modo in cui i bit sono rappresentati nei computer (2 valori possibili), il che significa che le variabili tendono ad avere intervalli di valori i cui confini sono 2 ^ n.
2. A causa del punto precedente, troverai spesso il valore 256 come dimensione del buffer. Questo perché è il numero più grande che può essere memorizzato in un byte. Quindi, se vuoi memorizzare una stringa insieme a una dimensione della stringa, sarai più efficiente se la memorizzi come: SIZE_BYTE + ARRAY , dove il byte size ti dice la dimensione di l'array. Ciò significa che l'array può avere qualsiasi dimensione da 1 a 256.
3. Molte altre volte, le dimensioni sono scelte in base a cose fisiche (ad esempio, la dimensione della memoria che un sistema operativo può scegliere è correlata alla dimensione dei registri della CPU ecc.) e queste saranno anche quantità specifica di bit. Ciò significa che la quantità di memoria che è possibile utilizzare sarà in genere un valore di 2 ^ n (per un sistema a 32 bit, 2 ^ 32).
4. Potrebbero esserci problemi di prestazioni / problemi di allineamento per tali valori. La maggior parte dei processori può accedere a un determinato numero di byte alla volta, quindi anche se si dispone di una variabile di dimensioni pari a 20 bit, un processore a 32 bit leggerà comunque 32 bit, indipendentemente da cosa. Quindi spesso è più efficiente creare semplicemente la variabile a 32 bit. Inoltre, alcuni processori richiedono che le variabili siano allineate a una determinata quantità di byte (poiché non sono in grado di leggere memoria, ad esempio, indirizzi nella memoria che sono dispari). Certo, a volte non si tratta di posizioni di memoria dispari, ma posizioni che sono multipli di 4, o 6 di 8, ecc. Quindi, in questi casi, è più efficiente creare buffer che saranno sempre allineati .

Ok, quei punti sono usciti un po 'confusi. Fammi sapere se hai bisogno di ulteriori spiegazioni, in particolare il punto 4 quale IMO è il più importante.

Answer 6

A causa della semplicità (leggi anche costo ) dell'aritmetica di base 2 in elettronica: sposta a sinistra (moltiplica per 2), sposta a destra (dividi per 2).

Nel dominio della CPU, molti costrutti ruotano attorno all'aritmetica di base 2. Gli autobus (controllo e dati) per accedere alla struttura della memoria sono spesso allineati alla potenza 2. Il costo dell'implementazione della logica nell'elettronica (ad es. CPU) rende l'aritmetica avvincente in base 2.

Naturalmente, se avessimo computer analogici, la storia sarebbe diversa.

---

FYI: gli attributi di un sistema che si trova al livello X è una conseguenza diretta degli attributi del livello server del sistema che si trovano al di sotto del livello < X. Il motivo per cui sto affermando questo deriva da alcuni commenti che ho ricevuto in merito al mio post.

es. le proprietà che possono essere manipolate nel "compilatore" livello sono ereditati & amp; derivato dalle proprietà del sistema sottostante, ad esempio l'elettronica nella CPU.

Answer 7

Stavo per usare l'argomento shift, ma potevo pensare a una buona ragione per giustificarlo.

Una cosa interessante di un buffer che è una potenza di due è che la gestione circolare del buffer può usare ands anziché dividere:

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

Se non fosse un potere di due, sarebbe necessaria una divisione. Ai vecchi tempi (e attualmente su piccoli chip) che contava.

Answer 8

È anche comune che le dimensioni delle pagine siano potenze di 2.

Su Linux mi piace usare getpagesize () quando faccio qualcosa come tagliare un buffer e scriverlo su un socket o un descrittore di file.

Answer 9

È un bel numero tondo nella base 2. Proprio come 10, 100 o 1000000 sono un bel numero tondo nella base 10.

Se non fosse una potenza di 2 (o qualcosa di simile come 96 = 64 + 32 o 192 = 128 + 64), allora potresti chiederti perché c'è la precisione aggiunta. Le dimensioni arrotondate non di base 2 possono derivare da vincoli esterni o ignoranza del programmatore. Ti consigliamo di sapere quale è.

Altre risposte hanno indicato anche una serie di ragioni tecniche che sono valide in casi speciali. Non ripeterò nessuno di questi qui.

Answer 10

Nelle tabelle hash, 2 ^ n semplifica la gestione delle collisioni chiave in un certo modo. In generale, quando si verifica una collisione chiave, si crea una sottostruttura, ad es. un elenco, di tutte le voci con lo stesso valore hash; o trovi un altro slot gratuito. Puoi semplicemente aggiungere 1 all'indice dello slot fino a trovare uno slot libero; ma questa strategia non è ottimale, perché crea cluster di luoghi bloccati. Una strategia migliore è calcolare un secondo numero di hash h2, in modo che gcd (n, h2) = 1; quindi aggiungi h2 all'indice dello slot fino a trovare uno slot libero (con avvolgimento). Se n è una potenza di 2, trovare un h2 che soddisfi gcd (n, h2) = 1 è facile, lo farà ogni numero dispari.