вектор :: оператор [] накладные расходы

Question

Очевидно, что после профилирования моего (научного вычисления) кода C ++ 25% (!) Времени тратится на вызовы vector::operator[].Правда, мой код тратит все свое время на чтение и запись за vector<float> с (и за несколько vector<int> с), но все же, я хотел бы знать, предполагаются ли какие-то существенные накладные расходы по сравнению с operator[]к массивам в стиле C?

(я видел еще один связанный с этим вопрос о SO, но относительно [] против at() - но, очевидно, даже [] слишком медленный для меня?!)

Спасибо, Антоний

(редактировать: только для информации: использование g ++ -O3 версии 4.5.2 в Ubuntu)

Answer 1

В современном компиляторе в режиме выпуска с включенной оптимизацией при использовании operator [] при использовании *1003* накладные расходы отсутствуют * по сравнению с необработанными указателями: вызов полностью встроен и разрешается только для доступа к указателю.

Я предполагаю, что вы каким-то образом копируете возвращаемое значение в присваивании и что this вызывает реальное 25% времени, потраченного на инструкцию. [Не имеет значениядля float и int]

Или остальная часть вашего кода просто невероятно быстра.

Answer 2

Да, будут некоторые издержки, так как обычно vector будет содержать указатель на динамически размещенный массив, где в качестве массива просто «там». Это означает, что в vector::operator[] обычно возникает дополнительная разыменование памяти по сравнению с использованием [] в массиве. (Обратите внимание, что если у вас есть указатель на массив, это обычно не лучше, чем vector.)

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

1012 * Е.Г. *

#include <vector>
extern std::vector<float> vf;
extern float af[];
extern float* pf;

float test1(long index)
{
        return vf[index];
}

float test2(long index)
{
        return af[index];
}

float test3(long index)
{
        return pf[index];
}

генерирует для меня следующий код на g ++ (некоторые урезаны):

.globl _Z5test1i
        .type   _Z5test1i, @function
_Z5test1i:
        movq    vf(%rip), %rax
        movss   (%rax,%rdi,4), %xmm0
        ret
        .size   _Z5test1i, .-_Z5test1i

.globl _Z5test2i
        .type   _Z5test2i, @function
_Z5test2i:
        movss   af(,%rdi,4), %xmm0
        ret
        .size   _Z5test2i, .-_Z5test2i

.globl _Z5test3i
        .type   _Z5test3i, @function
_Z5test3i:
        movq    pf(%rip), %rax
        movss   (%rax,%rdi,4), %xmm0
        ret
        .size   _Z5test3i, .-_Z5test3i

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

Answer 3

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

Answer 4

std::vector::operator[] должен быть довольно эффективным, однако компилятор должен быть параноиком, и для каждого вызова функции он должен предполагать, что вектор мог быть перемещен в другое место в памяти.

Например, в этомcode

for (int i=0,n=v.size(); i<n; i++)
{
    total += v[i] + foo();
}

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

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

double *vptr = &v[0]; // Address of first element
for (int i=0,n=v.size(); i<n; i++)
{
    total += vptr[i] + foo();
}

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

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

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

std::vector<double> v1(n), v2(n), v3(n), v4(n), v5(n);
for (int i=0; i<1000000; i++)
    for (int j=0; j<1000; j++)
    {
        v1[j] = v2[j] + v3[j];
        v2[j] = v3[j] + v4[j];
        v3[j] = v4[j] + v5[j];
        v4[j] = v5[j] + v1[j];
        v5[j] = v1[j] + v2[j];
    }

выполняется примерно за 8,1 секунды, если n == 8191, и за 3,2 секунды, если n == 10000.Обратите внимание, что внутренний цикл всегда от 0 до 999, независимо от значения n;отличается только адрес памяти.

В зависимости от процессора / архитектуры я наблюдал даже 10-кратное замедление из-за очистки кэша.

Answer 5

Чистый доступ к массиву - это (почти) прямое чтение из памяти, тогда как operator [] - это метод-член вектора <>.

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