C ++ STL: массив vs Vector: доступ к производительности необработанных элементов

Question

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

Есть ли у вас какой-либо опыт или информация, что из них быстрее: Vector или Array? Все, что имеет значение, - это скорость, с которой я могу получить доступ к элементу (получение кода операции), меня не волнует вставка, размещение, сортировка и т. Д.

Я сейчас высунусь из окна и скажу:

• Массивы по крайней мере немного быстрее векторов с точки зрения доступа к элементу i.

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

(Почему) я не прав?

Нет, я не могу игнорировать разницу в производительности - даже если она , поэтому маленькая - я уже оптимизировал и свернул каждую другую часть виртуальной машины, которая выполняет коды операций:)

Answer 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 в первом варианте, которая должна обеспечить дополнительный доступ к памяти.

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

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

Answer 2

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

Answer 3

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

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

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

РЕДАКТИРОВАТЬ: Если у вас есть таблица кодов операций, глобальный массив (например, с extern или static связью)может быть быстрееЭлементы глобального массива можно адресовать индивидуально как глобальные переменные, когда константа помещается в скобки, а коды операций часто являются константами.

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

Answer 4

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

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

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

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

Answer 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-подобных целей должно быть меньше генерируемых инструкций (без поиска TOC) или неуклюжие 32-битные константы), поскольку все часто используемые значения находятся в кадре стека.

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