C++ STL: Массив по сравнению с Вектором: Необработанное выполнение доступа элемента
Попробуйте следующее:
select id,name
from friends
order by case when id=5 then -1 else id end
, если у вас есть больше одного, которое вы можете сделать:
select id,name
from friends
order by case when id in (5,15,25) then -1 else id end,id
5 ответов
Время доступа к элементу в типичной реализации 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 в первом варианте, который должен сделать дополнительный доступ к памяти.
Однако разница незначительна. И он легко оптимизируется до такой же степени, что и в контексте множественного доступа (путем загрузки целевого адреса в регистр).
Таким образом, утверждение о том, что «массивы работают немного быстрее», является правильным в узком случае, когда массив доступен непосредственно через объект массива, а не через объект указателя. Но практическая ценность этой разницы практически ничто.
Для получения достойных результатов используйте 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, с машинным кодом, поскольку длина инструкции может быть фактором), чтобы проверить очевидную неэффективность.
Нет. Под капотом и std :: vector , и C ++ 0x std :: array находят указатель на элемент n , добавляя n к указателю на первый элемент.
vector :: at может быть медленнее, чем array :: at , потому что первый должен сравниваться с переменной, а второй - с константой. Эти - это функции, обеспечивающие проверку границ, а не оператор [] .
Если вы имеете в виду массивы в стиле C вместо C ++ 0x std :: array , тогда нет в члене, но суть остается.
РЕДАКТИРОВАТЬ: Если у вас есть таблица кодов операций, глобальный массив (например, со связью extern или static ) может быть быстрее. К элементам глобального массива можно будет обращаться индивидуально как к глобальным переменным, если константа помещена в скобки, а коды операций часто являются константами.
В любом случае, это все преждевременная оптимизация. Если вы не используете какие-либо функции изменения размера vector , он будет достаточно похож на массив, который вы сможете легко преобразовать между ними.
Вы сравниваете яблоки с апельсинами. Массивы имеют постоянный размер и выделяются автоматически, а векторы имеют динамический размер и распределяются динамически. Что вы используете, зависит от того, что вам нужно.
Обычно массивы выделяются «быстрее» (в кавычках, потому что сравнение бессмысленно), потому что динамическое размещение выполняется медленнее. Однако доступ к элементу должен быть таким же. (Допустим, что массив, вероятно, будет в кеше, хотя это не имеет значения после первого доступа.)
Кроме того, я не знаю, о какой «безопасности» вы говорите, vector имеет множество способов получить неопределенное поведение, как и массивы. Хотя у них есть at () , который вам не нужно использовать, если вы знаете, что индекс действителен.
Наконец, профилируйте и посмотрите на созданную сборку. Никто ничего не догадается.
Возможно, вы лаете не на то дерево. Пропуски кэша могут быть гораздо важнее, чем количество выполненных инструкций.