Быстрее ли const_iterators?

Question

Наши рекомендации по кодированию предпочитают const_iterator, потому что они немного быстрее по сравнению с обычным iterator. Кажется, что компилятор оптимизирует код, когда вы используете const_iterator.

Это действительно так? Если да, то что действительно происходит внутри, что делает const_iterator быстрее ?.

EDIT: Я написал небольшой тест, чтобы проверить const_iterator против iterator и обнаружили различные результаты:

Для переборе 10000 объектов const_terator вез несколько миллисекунд (около 16 мс) меньше. Но не всегда. Были итерации, в которых оба были равны.

Answer 1

Если ничего еще, const_iteratorчитает лучше, так как он говорит читающий код «Я просто итерация этого контейнера, а не возиться с объектами содержали».

Это большая большая победа, не говоря уже о различиях в производительности.

Answer 2

container<T>::const_iterator::operator* возвращает const T& вместо T&, поэтому компилятор может выполнять обычные оптимизации для объектов const.

Answer 3

Я не понимаю, почему они были бы - constness - это проверка времени компиляции. Но очевидный ответ - написать тест.

Edit: Вот мой тест - это дает одинаковые тайминги на моей машине:

#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

Я мой опыт, компилятор не выполняет никакой измеримой оптимизации при использовании константных итераторов. Хотя утверждение «оно может» истинно, и ссылки не определены как указатели в стандарте.

Однако у вас может быть две ссылки на один и тот же объект, поэтому можно создать константу, одну неконстантную. Затем, я думаю, ответы в this thread on restrict pointers применяются: компилятор не может знать, изменен ли объект другим потоком, например, или некоторым кодом обработки прерываний.

Answer 5

Наши принципы кодирования говорят, предпочитают const_iterator

Посмотрите на эту article by Scott Meyers here. Он объясняет, почему следует использовать итератор над const_iterator.

Answer 6

В руководстве мы используем:

Всегда предпочитает сопзЬ над неконстантным

Если вы склонны использовать константный объект, вы привыкнете к использованию только постоянные операций на объектах вы получаете и что как можно использовать const_iterator по возможности.

Constness имеет viral Недвижимость. Как только вы его используете, он распространяется на весь ваш код.Ваши не мутирующие методы становятся постоянными, и для этого требуется использовать только постоянные операции над атрибутами и передавать постоянные ссылки вокруг, что само по себе приводит к постоянным операциям ...

Для меня преимущество в производительности использования постоянных итераторов над не- постоянные итераторы (если они вообще есть) гораздо менее важны, чем улучшение самого кода. Операции, которые означают (спроектированы) быть не мутирующими, - константа.

Answer 7

«Const-ness», как ограничение доступа (public, protected, private), приносит пользу программисту больше, чем помогает оптимизация.
Составители не могут фактически оптимизировать столько ситуаций, как const, как можно подумать по многим причинам (например, const_cast, изменяемые элементы данных, сглаживание указателя/ссылки). Однако наиболее важной причиной этого является то, что только потому, что const_iterator не позволяет изменять данные, на которые он ссылается, не означает, что эти данные не могут быть изменены другими способами. И если компилятор не может определить, что данные доступны только для чтения, то он не может действительно оптимизировать гораздо больше, чем для случая неконстантного итератора.
Более подробную информацию и примеры можно найти по адресу: http://www.gotw.ca/gotw/081.htm

Answer 8

Они нетривиальных контейнеров/итераторы. Получите ваши привычки прямо, и вы не потеряете производительность, когда это имеет значение.

Кроме того, есть несколько причин, чтобы предпочесть const_iterator, независимо от того, что:

1. Использование сопзЬ выражает код намерения (т.е. не только для чтения, не мутирует этих объектов).
2. Использование константы (_iterator) предотвращает случайную модификацию данных. (см. выше)
3. Некоторые библиотеки используют недостаток-const begin() для флага данных как грязных (то есть OpenSG) и будут отправлять их другим потокам/по сети при синхронизации, поэтому там будут иметь реальные последствия для производительности.
4. Кроме того, для доступа к неконстантным функциям-членам могут быть побочные эффекты, которые вы не намерены (почти так же, как описано выше), например, отключение контейнеров для копирования на запись из общих данных. Qt для одного, делает именно это.

В качестве примера последнего пункта выше, вот выдержка из qmap.h в Qt:

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

Даже если итератор и const_iterator практически эквивалентны (за исключением const), detach() создает новая копия данных, если есть два или более объектов, использующих ее. Это совершенно бесполезно, если вы просто собираетесь прочитать данные, которые вы указываете, используя const_iterator.

Конечно, есть моменты, данные в другом направлении:

1. Для STL контейнеров и и многие просто от копирования семантических контейнеров это не имеет значения для исполнения. Код равен эквивалент. Тем не менее, умеет писать четкий код и избегать ошибок.
2. Const является вирусным, поэтому, если вы работаете в устаревшей кодовой базе, где const плохо (или просто нет) реализовано, вам, возможно, придется работать с неконстантными итераторами.
3. По-видимому, некоторые pre C++ 0x STL имеют ошибку, в которой const_iterators не могут использоваться для стирания() элементов из контейнеров.

Answer 9

Это зависит от используемого вами контейнера и реализации.

Да, const_iteratorмай выполнить лучше.

Для некоторых контейнеров реализация константных итераторов и изменяемых итераторов может отличаться.. Первый пример, который я могу представить, - это SGI's STL rope container. Уменяемый итератор имеет дополнительный указатель на родительскую веревку, чтобы поддерживать обновления. Это подразумевает дополнительные ресурсы, потраченные впустую для обновлений подсчета ссылок + память для указателя на родительскую веревку. См. implementation notes here.

Однако, как утверждают другие, компилятор не может использовать const сам по себе для оптимизации. const просто предоставляет доступ только для чтения к указанному объекту, а не говорит, что он неизменен. Для контейнера, такого как std::vector, итераторы которого обычно реализуются как простые указатели, не будет никакой разницы.

Answer 10

, когда вы сравниваете все это, убедитесь, что используете соответствующий уровень оптимизации - вы получите совершенно разные тайминги с использованием «-O0» по сравнению с «-O» и т. Д.

Answer 11

Они должны быть идентичными, поскольку константа - это проверка времени компиляции.

Чтобы доказать, что у меня не было причуд, я взял код анона, изменил его, чтобы использовать clock_gettime, добавил внешний цикл, чтобы избежать пристрастий к кешированию, и запускал его много раз. Результаты были неожиданно несогласованными - вверх и вниз на 20% (без свободных ящиков) - но минимум для обоих iterator и const_iterator были практически идентичными.

тогда я получил мой компилятор (GCC 4.5.2 -O3) для генерации выход сборки и визуально сравнить эти две петли: идентичны (за исключением того, порядка двух регистров нагрузок было отменено)

iterator петли

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 цикл:

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)