I costitutori sono più veloci?

Question

Le nostre linee guida di codifica preferiscono const_iterator, perché sono un po 'più veloci rispetto a un normale iterator. Sembra che il compilatore ottimizzi il codice quando si utilizza const_iterator.

È veramente corretto? Se sì, ciò che realmente accade internamente rende const_iterator più veloce?

EDIT: ho scritto piccolo test per verificare const_iterator vs iterator e trovati risultati variabili:

Per iterazione 10.000 oggetti const_terator stava prendendo alcuni millisecondi (circa 16 ms) di meno. Ma non sempre. C'erano iterazioni in cui entrambi erano uguali.

Answer 1

Se non altro, un const_iteratorlegge meglio, dal momento che dice a chiunque la lettura del codice "Sto solo l'iterazione di questo contenitore, non scherzi con gli oggetti contenuti".

Questa è una grande vittoria, non importa eventuali differenze di prestazioni.

Answer 2

container<T>::const_iterator::operator* restituisce un const T& anziché T&, quindi il compilatore può effettuare le solite ottimizzazioni per gli oggetti const.

Answer 3

Non riesco a capire perché dovrebbero essere: la costanza è un controllo del tempo compilato. Ma la risposta ovvia è scrivere un test.

Edit: Ecco la mia prova - dà tempi identici sulla mia macchina:

#include <vector> 
#include <iostream> 
#include <ctime> 
using namespace std;; 


int main() { 
    vector <int> v; 
    const int BIG = 10000000; 
    for (int i = 0; i < BIG; i++) { 
     v.push_back(i); 
    } 
    cout << "begin\n"; 
    int n = 0; 
    time_t now = time(0); 
    for (int a = 0; a < 10; a++) { 
     for(vector <int>::iterator it = v.begin(); it != v.end(); ++it) { 
      n += *it; 
     } 
    } 
    cout << time(0) - now << "\n"; 
    now = time(0); 
    for (int a = 0; a < 10; a++) { 
     for(vector <int>::const_iterator cit = v.begin(); cit != v.end(); ++cit) { 
      n += *cit; 
     } 
    } 
    cout << time(0) - now << "\n";; 

    return n != 0; 

} 

Answer 4

ho la mia esperienza, il compilatore non fa alcuna ottimizzazione misurabile quando si utilizza iteratori const. Sebbene l'affermazione "potrebbe" è vera e i riferimenti non sono definiti come indicatori nello standard.

Tuttavia, è possibile avere due riferimenti allo stesso oggetto, in modo che uno possa essere const, uno non const. Quindi, suppongo che si applichino le risposte in this thread on restrict pointers: Il compilatore non può sapere se l'oggetto è stato modificato da un altro thread, ad esempio, o da qualche codice di gestione degli interrupt.

Answer 5

Le nostre linee guida di codifica dire Preferisco const_iterator

Date un'occhiata a questo article by Scott Meyers here. Spiega perché uno dovrebbe preferire iteratore su const_iterator.

Answer 6

La linea guida che usiamo è:

preferiscono sempre const over non-const

Se si tende ad utilizzare l'oggetto const, ci si abitua ad usare solo operazioni costanti sugli oggetti che si ottiene e che è tanto quanto usando const_iterator il più possibile.

Constness ha un virale proprietà. Una volta che lo usi, si propaga a tutto il tuo codice.I tuoi metodi non mutanti diventano costanti e richiedono l'utilizzo di operazioni costanti sugli attributi e il passaggio di riferimenti costanti attorno, che a sua volta impone solo operazioni costanti ...

Per me, il vantaggio in termini di prestazioni dell'utilizzo di iteratori costanti rispetto a non gli iteratori costanti (se del caso) sono molto meno importanti del miglioramento del codice stesso. Le operazioni hanno significato (progettato) di essere non mutanti sono costanti.

Answer 7

"Const-ness", come la restrizione di accesso (pubblica, protetta, privata), avvantaggia il programmatore più di quanto assista nell'ottimizzazione.
I compilatori non possono effettivamente ottimizzare per quante situazioni coinvolgono const come si potrebbe pensare, per molte ragioni (come const_cast, membri di dati mutabili, puntatore/alias di riferimento). La ragione più rilevante qui però è che, solo perché un const_iterator non consente di modificare i dati a cui fa riferimento, non significa che i dati non possano essere modificati con altri mezzi. E se il compilatore non è in grado di determinare che i dati sono di sola lettura, allora non può davvero ottimizzare molto di più di quanto farebbe per il caso di iteratore non const.
Ulteriori informazioni e esempi possono essere trovati a: http://www.gotw.ca/gotw/081.htm

Answer 8

Sono per contenitori/iteratori non banali. Ottieni le tue abitudini dirette e non perderai le prestazioni quando è importante.

Inoltre, ci sono diversi motivi per preferire const_iterator, non importa quale:

1. L'utilizzo di const esprime codice di intenti (vale a dire la lettura solo, nessun mutante di questi oggetti).
2. L'uso di const (_iterator) impedisce la modifica accidentale dei dati. (vedere sopra)
3. Alcune librerie utilizzano la mancanza di costante begin() per contrassegnare i dati come sporchi (ad esempio OpenSG) e li invieranno ad altri thread/over-network durante la sincronizzazione, quindi presentano implicazioni di prestazioni reali.
4. Inoltre, consentire l'accesso a funzioni membro non const può avere effetti indesiderati che non si intendono (più o meno allo stesso modo di quelli precedenti), ad esempio separando i contenitori copy-on-write dai dati condivisi. Qt per uno, fa esattamente questo.

Come esempio dell'ultimo punto sopra, ecco un estratto da qmap.h in Qt:

inline iterator begin() { detach(); return iterator(e->forward[0]); } 
inline const_iterator begin() const { return const_iterator(e->forward[0]); } 

Anche se iteratore e const_iterator sono praticamente equivalenti (ad eccezione del const), detach() crea una nuova copia dei dati se ci sono due o più oggetti che lo utilizzano. Questo è completamente inutile se stai andando a leggere i dati, che indichi usando const_iterator.

Naturalmente, ci sono punti di dati nella direzione opposta:

1. Per contenitori STL e molti contenitori e semplice copia-semantiche non importa per le prestazioni. Il codice è equivalente a. Tuttavia, l'in grado di scrivere codice chiaro ed evitare bug vince.
2. Const è virale, quindi se stai lavorando in una base di codice legacy in cui const è scarsamente (o semplicemente non) implementato, potresti dover lavorare con iteratori non const.
3. Apparentemente, alcuni pre-C++ 0x STL presentano un bug in cui non è possibile utilizzare const_iterators per cancellare() gli elementi dai contenitori.

Answer 9

Dipende dal contenitore e dall'implementazione in uso.

Sì, const_iteratorpuò eseguire meglio.

Per alcuni contenitori l'implementazione di iteratori const e iteratori mutabili può essere diversa. Un primo esempio che posso pensare è lo SGI's STL rope container. L'iteratore mutabile ha un puntatore aggiuntivo alla corda padre per supportare gli aggiornamenti. Ciò implica risorse aggiuntive sprecate per gli aggiornamenti del conteggio dei riferimenti + memoria per il puntatore alla corda padre. Vedi lo implementation notes here.

Tuttavia, come altri hanno detto, il compilatore non può utilizzare da solo const per eseguire l'ottimizzazione. const concede solo l'accesso in sola lettura all'oggetto di riferimento piuttosto che dire che è immutabile. Per un container come std::vector, i cui iteratori vengono solitamente implementati come semplici puntatori, non ci saranno differenze.

Answer 10

quando si esegue un benchmark di questo tipo, assicurarsi di utilizzare un livello di ottimizzazione appropriato - si avranno tempistiche molto diverse usando "-O0" rispetto a "-O" e così via.

Answer 11

Dovrebbero essere identici, poiché la costanza è un controllo in fase di compilazione.

Per provare a me stesso non c'erano stranezze, ho preso il codice di anon, l'ho modificato per usare clock_gettime, aggiunto un ciclo esterno per evitare i bias di cache, e l'ho eseguito molte volte. I risultati sono stati sorprendentemente incoerenti - su e giù del 20% (non sono disponibili box liberi) - ma i tempi minimi per entrambi iterator e const_iterator erano praticamente identici.

Poi ho ottenuto il mio compilatore (GCC 4.5.2 O3) per generare uscita assemblaggio e visivamente rispetto i due cicli: identici (tranne che l'ordine di un paio di carichi di registro è stata invertita)

iterator ciclo

call clock_gettime 
    movl 56(%esp), %esi 
    movl $10, %ecx 
    movl 60(%esp), %edx 
    .p2align 4,,7 
    .p2align 3 
.L35: 
    cmpl %esi, %edx 
    je .L33 
    movl %esi, %eax .p2align 4,,7 
    .p2align 3 
.L34: 
    addl (%eax), %ebx 
    addl $4, %eax 
    cmpl %eax, %edx 
    jne .L34 
.L33: 
    subl $1, %ecx 
    jne .L35 
    leal 68(%esp), %edx 
    movl %edx, 4(%esp) 
    leal 56(%esp), %esi 
    movl $1, (%esp) 

const_iterator ciclo:

movl 60(%esp), %edx 
    movl $10, %ecx 
    movl 56(%esp), %esi 
    .p2align 4,,7 
    .p2align 3 
.L38: 
    cmpl %esi, %edx 
    je .L36 
    movl %esi, %eax 
    .p2align 4,,7 
    .p2align 3 
.L37: 
    addl (%eax), %ebx 
    addl $4, %eax 
    cmpl %eax, %edx 
    jne .L37 
.L36: 
    subl $1, %ecx 
    jne .L38 
    leal 68(%esp), %edx 
    movl %edx, 4(%esp) 
    leal 56(%esp), %esi 
    movl $1, (%esp)