C++ STL: Array vs Vector: доступ к производительности исходного кода

Question

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

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

Теперь я собираюсь вылезти из окна и скажу:

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

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

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

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

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

No. Under The hood, std::vector и C++ 0x std::array найти указатель на элемент n, добавив n в указатель на первый элемент.

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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