2010-10-24 19 views
5

Come viene solitamente implementato il vettore STL? Ha una memoria raw di char [] che occasionalmente ridimensiona di un certo fattore e chiama il posizionamento new quando un elemento è pushed_back (una forma grammaticale molto interessante che dovrei notare - i linguisti dovrebbero studiare tali forme di verbo come pushed_back :)
E poi ci sono i requisiti di allineamento. Quindi sorge spontanea una domanda: come posso chiamare un posizionamento nuovo su un carattere [] e accertarsi che i requisiti di allineamento siano soddisfatti. Così ho cercato di serie C++ del 2003 per la parola "allineamento" ed ho trovato questi:Allineamento dei char char array

Paragrafo 3.9 clausola 5

tipi di oggetti hanno requisiti di allineamento (3.9.1, 3.9.2). L'allineamento di un tipo di oggetto completo è un valore intero definito dall'implementazione che rappresenta un numero di byte; un oggetto viene assegnato a un indirizzo che soddisfa i requisiti di allineamento del suo tipo di oggetto.

Paragrafo 5.3.4 Clausola 10:

Una nuova espressione passa la quantità di spazio richiesto per la funzione di assegnazione come primo argomento di tipo std :: size_t. Tale argomento non deve essere inferiore alla dimensione dell'oggetto che si sta creando; potrebbe essere maggiore della dimensione dell'oggetto che si sta creando solo se l'oggetto è un array. Per gli array di char e unsigned char, la differenza tra il risultato della nuova espressione e l'indirizzo restituito dalla funzione di allocazione deve essere un multiplo integrale del requisito di allineamento più stringente (3.9) di qualsiasi tipo di oggetto la cui dimensione non sia maggiore di la dimensione della matrice che si sta creando. [Nota: poiché si presume che le funzioni di allocazione restituiscano puntatori allo spazio di archiviazione che è allineato in modo appropriato per oggetti di qualsiasi tipo, questo vincolo sul sovraccarico dell'allocazione dell'array consente l'idioma comune di allocare matrici di caratteri in cui verranno successivamente collocati gli oggetti di altri tipi. ]

Questi due danno una risposta del tutto soddisfacente per la mia domanda di cui sopra, ma ...

istruzione1:
Un requisito di allineamento per un oggetto di tipo X, dove sizeof (X) == n è almeno il requisito che l'indirizzo di X sia divisibile per n o qualcosa di simile (metti tutte le cose dipendenti dall'architettura in "o qualcosa di simile").

Question1: Si prega di confermare, raffinare, o negare l'istruzione1 sopra.

istruzione2: Se statement1 è corretto quindi dalla seconda citazione nello standard ne consegue che un array di 5.000.000 caratteri viene allocato un indirizzo divisibile per 5000000, completamente inutile se devo solo la matrice di char in quanto tale, non come memoria grezza per il possibile posizionamento di altri oggetti.

Question2: Così, sono le probabilità di successo assegnazione 1000 chars davvero inferiore a 500 short (forniti a breve è di 2 byte)? È praticamente un problema?

risposta

3

Un requisito allineamento di un oggetto di tipo X dove sizeof (X) == n è al almeno il requisito che l'indirizzo di X sia divisibile per n o qualcosa di simile che

No. Il requisito di allineamento di un tipo è sempre un fattore della sua dimensione, ma non deve essere uguale alla sua dimensione. Solitamente è uguale al massimo dei requisiti di allineamento di tutti i membri di una classe.

Un array di 5M char, per proprio conto, deve avere solo un requisito di allineamento pari a 1, uguale al requisito di allineamento di un singolo char.

Così, il testo citate circa l'allineamento di memoria allocata tramite operatore globale new, (e malloc ha una simile anche se IIRC non requisito identico) in effetti significa che una grande ripartizione deve rispettare il requisito di allineamento più rigoroso di qualsiasi tipo nel sistema. Inoltre, le implementazioni spesso escludono i tipi di SIMD di grandi dimensioni e richiedono che la memoria per SIMD sia allocata appositamente. Questo è un po 'dubbio, ma penso che lo giustificano sulla base del fatto che i tipi di estensione non standard possono imporre requisiti arbitrari speciali.

Quindi, in pratica, il numero che si pensa è 5000000 è spesso 4 :-)

1

Q1: l'allineamento non è correlato alla dimensione.

Q2: Teoricamente sì, ma difficilmente troverai un'architettura che abbia un tipo con un allineamento così grande. SSE richiede 16 byte di allineamento (il più grande che ho visto).

+0

@Let_Me_Be: La ragione per cui dovrei l'allineamento ** ** è correlata alla dimensione è che se prendo una serie di X e di tutti dovrebbero obbedire ai requisiti di allineamento, quindi gli indirizzi a, a + sizeof (X), a + 2 * sizeof (X) ... ecc. dovrebbero soddisfare tutti questi requisiti. Il che mi ha portato a definire la dichiarazione. Ho sbagliato? –

+0

@Armen: hai messo sottosopra. La dimensione dell'oggetto deve essere un multiplo del suo allineamento. Un 'char' di solito ha l'allineamento 1, e un' int' di solito deve essere allineato su un limite di 4 byte. Una 'struct' contenente entrambi viene data l'allineamento del suo membro più strettamente allineato (quindi se contiene un' char' e un 'int', allora la struct nel suo insieme richiede lo stesso allineamento di un' int'). L'oggetto deve quindi avere anche una dimensione che è un multiplo di un int. Lo stesso vale per il tuo enorme array di caratteri. Non contiene nient'altro che caratteri e ogni char può essere inserito in qualsiasi byte (qualsiasi indirizzo divisibile per 1) – jalf

+0

quindi l'array nel suo complesso ha lo stesso requisito di allineamento (e deve anche essere un multiplo di 1, che non è difficile per raggiungere.;)) – jalf

4

Quando si alloca dinamicamente memoria utilizzando operator new, si ha la garanzia che:

Il puntatore restituito deve essere opportunamente posizionato in modo che può essere convertito in un puntatore di qualunque tipo di oggetto completo e quindi utilizzato per accedere l'oggetto o l'array nella memoria allocata (fino a quando la memorizzazione non viene deallocata esplicitamente da una chiamata a una funzione di deallocazione corrispondente) (C++ 03 3.7.3.1/2).

vector non crea un array di caratteri; usa un allocatore. L'allocatore predefinito utilizza ::operator new per allocare memoria.