С++ STL: Array vs Vector: элемент Raw, получающий доступ к производительности

Ответ 1

Время доступа элемента в типичной реализации std::vector совпадает с временем доступа элемента в обычном массиве, доступном через объект-указатель (то есть значение указателя времени выполнения)

std::vector<int> v;
int *pa;
...
v[i];
pa[i]; 
// Both have the same access time

Однако время доступа к элементу массива, доступному как объект массива, лучше, чем оба вышеупомянутых доступа (эквивалент доступа через значение указателя времени компиляции)

int a[100];
...
a[i];
// Faster than both of the above

Например, типичный доступ для чтения к массиву int, доступный через значение указателя времени выполнения, будет выглядеть следующим образом в скомпилированном коде на платформе x86

// pa[i]
mov ecx, pa // read pointer value from memory
mov eax, i
mov <result>, dword ptr [ecx + eax * 4]

Доступ к элементу вектора будет выглядеть примерно так же.

Типичный доступ к локальному массиву int, доступному как объект массива, будет выглядеть следующим образом

// a[i]
mov eax, i
mov <result>, dword ptr [esp + <offset constant> + eax * 4]

Типичный доступ к глобальному массиву int, доступному как объект массива, будет выглядеть следующим образом

// a[i]
mov eax, i
mov <result>, dword ptr [<absolute address constant> + eax * 4]

Разница в перфомансе возникает из этой дополнительной команды mov в первом варианте, которая должна сделать дополнительный доступ к памяти.

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

Таким образом, утверждение о том, что "массивы становятся быстрее" справедливо в узком случае, когда массив доступен непосредственно через объект массива, а не через объект-указатель. Но практическая ценность этой разницы практически ничто.

Ответ 2

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

Ответ 3

Нет. Под капотом как std::vector, так и С++ 0x std::array найдите указатель на элемент n, добавив n к указателю на первый элемент.

vector::at может быть медленнее, чем array::at, потому что первое должно сравниваться с переменной, в то время как последнее сравнивается с константой. Это функции, которые обеспечивают проверку границ, а не operator[].

Если вы имеете в виду массивы C-стиля вместо С++ 0x std::array, то нет элемента at, но точка остается.

EDIT: Если у вас есть таблица опкодов, глобальный массив (например, с помощью extern или static linkage) может быть быстрее. Элементы глобального массива адресуются индивидуально как глобальные переменные, когда константа помещается внутри скобок, а коды операций часто являются константами.

В любом случае, это преждевременная оптимизация. Если вы не используете какие-либо функции изменения размера vector, он выглядит достаточно, как массив, который вы можете легко преобразовать между ними.

Ответ 4

Вы сравниваете яблоки с апельсинами. Массивы имеют постоянный размер и автоматически распределяются, тогда как векторы имеют динамический размер и динамически распределяются. Что вы используете, зависит от того, что вам нужно.

Как правило, массивы "быстрее" выделяются (в кавычках, потому что сравнение бессмысленно), поскольку динамическое распределение происходит медленнее. Однако доступ к элементу должен быть одинаковым. (Предоставленный массив, вероятно, скорее всего будет в кеше, хотя это не имеет значения после первого доступа.)

Кроме того, я не знаю, о какой "безопасности" вы говорите, vector имеет множество способов получить поведение undefined так же, как массивы. Хотя они имеют at(), которые вам не нужно использовать, если вы знаете, что индекс действителен.

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

Ответ 5

Для достижения достойных результатов используйте std::vector в качестве хранилища резервной копии и возьмите указатель на свой первый элемент перед вашим основным циклом или что-то еще:

std::vector<T> mem_buf;
// stuff
uint8_t *mem=&mem_buf[0];
for(;;) {
    switch(mem[pc]) {
    // stuff
    }
}

Это позволяет избежать любых проблем с чрезмерно полезными реализациями, которые выполняют проверку границ в operator[], и упрощает одноэтапную операцию при входе в выражения, такие как mem_buf[pc] далее в коде.

Если каждая команда выполняет достаточную работу, и код достаточно разнообразен, это должно быть быстрее, чем использование глобального массива с помощью незначительной суммы. (Если разница заметна, коды операций должны быть сложнее.)

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

Я не уверен, что оптимизация цикла отправки интерпретатора таким образом обеспечит хороший возврат вовремя вложенных средств - действительно, инструкции должны быть сделаны, чтобы делать больше, если это проблема, но я полагаю, t возьмите много времени, чтобы опробовать несколько разных подходов и измерить разницу. Как всегда в случае непредвиденного поведения, сгенерированный язык ассемблера (и на x86, машинный код, как длина инструкции может быть фактором) следует проконсультироваться, чтобы проверить на очевидную неэффективность.