О векторах или необычное рядом

[rosvald1]

Для перебора элементов списка в C++ есть два основных способа - по индексам или итераторам. Для оптимизации процесса перебора обычно используется второй, т.к. компилятор в состоянии его хорошо заоптимизировать. Особняком в стандартных списках стоит вектор - по сути это обычный массив в обертке.

И вот недавно, просматривая очередное ревью, наткнулся на кусок кода, перебирающий std::vector по индексам. Этот код вызвал из глубин памяти некогда увиденную на просторах интернета информацию, что по индексам к вектору быстрее обращаться, чем по итераторам. Не доверяя памяти (а тем более интернету) решил проверить и вот какие результаты получились:

Iterator sum: 0, elapsed: 1060.44 (прогон по итераторам)
Index sum: 0, elapsed: 950.36 (прогон по индексам)
CIterator sum: 0, elapsed: 1055.48 (прогон по константным итераторам)

[Код теста, кому интересно]

#include
#include

void vectorPerformace()
{
#define SECTION_NAME_SIZE 8
typedef char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned int uint32_t;

typedef struct {
uint8_t Name[SECTION_NAME_SIZE];
union {
uint32_t PhysicalAddress; // same value as next field
uint32_t VirtualSize;
} Misc;
uint32_t VirtualAddress;
uint32_t SizeOfRawData;
uint32_t PointerToRawData;
uint32_t PointerToRelocations; // always zero in executables
uint32_t PointerToLinenumbers; // deprecated
uint16_t NumberOfRelocations;
uint16_t NumberOfLinenumbers; // deprecated
uint32_t Characteristics; // SectionCharacteristics
} IMAGE_SECTION_HEADER;

std::vector a(1000, IMAGE_SECTION_HEADER());
printf("size=%d\n", a.size());

uint32_t sum = 0;
LARGE_INTEGER frequency;
LARGE_INTEGER t1, t2, elapsed;

QueryPerformanceFrequency(&frequency);

// By iterator
QueryPerformanceCounter(&t1);

for (int i = 0; i < 1000000; ++i)
for (std::vector::iterator it = a.begin(), e = a.end(); it != e; ++it)
sum += it->VirtualAddress + it->PointerToRawData + it->SizeOfRawData;

QueryPerformanceCounter(&t2);
elapsed.QuadPart = ((t2.QuadPart - t1.QuadPart) * 1000000) / frequency.QuadPart;
printf("Iterator sum: %u, elapsed: %.2f\n", sum, elapsed.QuadPart/1000.0);

// By index
QueryPerformanceCounter(&t1);

for (int i = 0; i < 1000000; ++i)
for (size_t n = 0; n < a.size(); ++n)
sum += a[n].VirtualAddress + a[n].PointerToRawData + a[n].SizeOfRawData;

QueryPerformanceCounter(&t2);
elapsed.QuadPart = ((t2.QuadPart - t1.QuadPart) * 1000000) / frequency.QuadPart;
printf("Index sum: %u, elapsed: %.2f\n", sum, elapsed.QuadPart / 1000.0);

// By const_iterator
QueryPerformanceCounter(&t1);

for (int i = 0; i < 1000000; ++i)
for (std::vector::iterator it = a.begin(), e = a.end(); it != e; ++it)
sum += it->VirtualAddress + it->PointerToRawData + it->SizeOfRawData;

QueryPerformanceCounter(&t2);
elapsed.QuadPart = ((t2.QuadPart - t1.QuadPart) * 1000000) / frequency.QuadPart;
printf("CIterator sum: %u, elapsed: %.2f\n", sum, elapsed.QuadPart / 1000.0);
}

int _tmain(int argc, _TCHAR* argv[])
{
vectorPerformace();
vectorPerformace();
vectorPerformace();
return 0;
}



Несколько прогонов подряд дали один и тот же результат - по индексам на 10% (!) быстрее. Итераторы или константные итераторы в данном случае не роялют. Проверял на Visual Studio 2013, release x86 (в x64 такая же картина). В дизассемблер заглядывал - действительно немного разный код получается (точнее для индексов он выходит немного короче). Внутренность цикла - почти копи-паст из того ревью.

Понимая, что зависит от кода внутри цикла, компилятора и фаз луны, решил проверить еще и на маке. Вот результаты того же теста на Маке (Xcode 7.2, release):

Iterator sum: 0, elapsed: 847.05
Index sum: 0, elapsed: 857.32
CIterator sum: 0, elapsed: 846.70

Т.е. тут наоборот, индексы на 3,5% медленнее.

[Код адаптированого по XCode теста]

#include
#include
#include
#include
#include

double MachTimeToMSecs(uint64_t time)
{
mach_timebase_info_data_t timebase;
mach_timebase_info(&timebase);
return (double)time * (double)timebase.numer /
(double)timebase.denom / 1e6;
}

void vectorPerformace()
{
#define SECTION_NAME_SIZE 8
typedef char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned int uint32_t;

typedef struct {
uint8_t Name[SECTION_NAME_SIZE];
union {
uint32_t PhysicalAddress; // same value as next field
uint32_t VirtualSize;
} Misc;
uint32_t VirtualAddress;
uint32_t SizeOfRawData;
uint32_t PointerToRawData;
uint32_t PointerToRelocations; // always zero in executables
uint32_t PointerToLinenumbers; // deprecated
uint16_t NumberOfRelocations;
uint16_t NumberOfLinenumbers; // deprecated
uint32_t Characteristics; // SectionCharacteristics
} IMAGE_SECTION_HEADER;

std::vector a(1000, IMAGE_SECTION_HEADER());
printf("size=%lu\n", a.size());

uint32_t sum = 0;
uint64_t start;
uint64_t end;

// By iterator
start = mach_absolute_time();

for (int i = 0; i < 1000000; ++i)
for (std::vector::iterator it = a.begin(), e = a.end(); it != e; ++it)
sum += it->VirtualAddress + it->PointerToRawData + it->SizeOfRawData;

end = mach_absolute_time();
printf("Iterator sum: %u, elapsed: %.2f\n", sum, MachTimeToMSecs(end - start));

// By index
start = mach_absolute_time();

for (int i = 0; i < 1000000; ++i)
for (size_t n = 0; n < a.size(); ++n)
sum += a[n].VirtualAddress + a[n].PointerToRawData + a[n].SizeOfRawData;

end = mach_absolute_time();
printf("Index sum: %u, elapsed: %.2f\n", sum, MachTimeToMSecs(end - start));

// By const_iterator
start = mach_absolute_time();

for (int i = 0; i < 1000000; ++i)
for (std::vector::iterator it = a.begin(), e = a.end(); it != e; ++it)
sum += it->VirtualAddress + it->PointerToRawData + it->SizeOfRawData;

end = mach_absolute_time();
printf("CIterator sum: %u, elapsed: %.2f\n", sum, MachTimeToMSecs(end - start));
}

int main(int argc, const char * argv[]) {
vectorPerformace();
vectorPerformace();
vectorPerformace();
return 0;
}



Понимая, что тест в какой-то степени синтетический (миллиард итераций в сумме получается), вывод тут напрашивается очень простой: не парьтесь, пишите кошерный код и будет вам скорость и счастье :)

JFYI: Использование в циклах auto из C++11 - это тоже самое, что и итераторы