Почему доступ к указателю медленнее, чем доступ к vector :: iterator? (генерация кода компилятора)

Question

Хорошо, заголовок вопроса немного дурацкий, но я не знал, как лучше это сформулировать.

Проблема, с которой я столкнулся, состоит в том, что при std::vector<T> против T* + size_t count мой компилятор (Visual Studio 2005 / VC ++ 8) будет генерировать худший код при циклическом перемещении по указателю, чем при циклическом перемещении по вектору .

То есть у меня есть тестовая структура, содержащая вектор, а другая - указатель + счетчик. Теперь при написании семантически точной циклической конструкции версия с std :: vector значительно (то есть> 10%) быстрее, чем версия с указателем.

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

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

И пожалуйста воздержитесь от ответов, говорящих мне, что мне все равно, преждевременная оптимизация, корень всего зла и т. Д. В этом конкретном случае я делаю заботу и в любом случае думаю, что это это довольно интересная головоломка! : -)

---

Настройки компилятора:

• Полная оптимизация (/ Ox)
• Опция всей программы. = НЕТ

А вот и код:

stdafx.h

// Disable secure STL stuff!
#define _SECURE_SCL 0
#define _SECURE_SCL_THROWS 0
#include <iostream>
#include <iomanip>
#include <vector>
#include <mmsystem.h>

заголовочный файл

// loop1.h
typedef int PodType;

const size_t container_size = 3;
extern volatile size_t g_read_size;

void side_effect();

struct RawX {
    PodType* pData;
    PodType wCount;

    RawX()
    : pData(NULL)
    , wCount(0)
    { }

    ~RawX() {
        delete[] pData;
        pData = NULL;
        wCount = 0;
    }

    void Resize(PodType n) {
        delete[] pData;
        wCount = n;
        pData = new PodType[wCount];
    }
private:
    RawX(RawX const&);
    RawX& operator=(RawX const&);
};

struct VecX {
    std::vector<PodType> vData;
};

void raw_loop(const int n, RawX* obj);
void raw_iterator_loop(const int n, RawX* obj);
void vector_loop(const int n, VecX* obj);
void vector_iterator_loop(const int n, VecX* obj);

файл реализации

// loop1.cpp
void raw_loop(const int n, RawX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(int j=0, e=obj->wCount; j!=e; ++j) {
            g_read_size = obj->pData[j];
            side_effect();
        }
        side_effect();
    }
}

void raw_iterator_loop(const int n, RawX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(PodType *j=obj->pData, *e=obj->pData+size_t(obj->wCount); j!=e; ++j) {
            g_read_size = *j;
            side_effect();
        }
        side_effect();
    }
}

void vector_loop(const int n, VecX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(size_t j=0, e=obj->vData.size(); j!=e; ++j) {
            g_read_size = obj->vData[j];
            side_effect();
        }
        side_effect();
    }
}

void vector_iterator_loop(const int n, VecX* obj)
{
    for(int i=0; i!=n; ++i) {
        side_effect();
        for(std::vector<PodType>::const_iterator j=obj->vData.begin(), e=obj->vData.end(); j!=e; ++j) {
            g_read_size = *j;
            side_effect();
        }
        side_effect();      
    }
}

тестовый основной файл

using namespace std;

volatile size_t g_read_size;
void side_effect()
{
    g_read_size = 0;
}

typedef size_t Value;

template<typename Container>
Value average(Container const& c)
{
    const Value sz = c.size();
    Value sum = 0;
    for(Container::const_iterator i=c.begin(), e=c.end(); i!=e; ++i)
        sum += *i;
    return sum/sz;

}

void take_timings()
{
    const int x = 10;
    const int n = 10*1000*1000;

    VecX vobj;
    vobj.vData.resize(container_size);
    RawX robj;
    robj.Resize(container_size);

    std::vector<DWORD> raw_times;
    std::vector<DWORD> vec_times;
    std::vector<DWORD> rit_times;
    std::vector<DWORD> vit_times;

    for(int i=0; i!=x; ++i) {
        const DWORD t1 = timeGetTime();
        raw_loop(n, &robj);
        const DWORD t2 = timeGetTime();
        vector_loop(n, &vobj);
        const DWORD t3 = timeGetTime();
        raw_iterator_loop(n, &robj);
        const DWORD t4 = timeGetTime();
        vector_iterator_loop(n, &vobj);
        const DWORD t5 = timeGetTime();
        raw_times.push_back(t2-t1);
        vec_times.push_back(t3-t2);
        rit_times.push_back(t4-t3);
        vit_times.push_back(t5-t4);
    }

    cout << "Average over " << x << " iterations for loops with count " << n << " ...\n";
    cout << "The PodType is '" << typeid(PodType).name() << "'\n";
    cout << "raw_loop: " << setw(10) << average(raw_times) << " ms \n";
    cout << "vec_loop: " << setw(10) << average(vec_times) << " ms \n";
    cout << "rit_loop: " << setw(10) << average(rit_times) << " ms \n";
    cout << "vit_loop: " << setw(10) << average(vit_times) << " ms \n";
}

int main()
{
    take_timings();
    return 0;
}

---

Здесь приводится сгенерированная сборка, отображаемая отладчиком Visual Studio (для двух функций с «итераторами».

* raw_iterator_loop *

void raw_iterator_loop(const int n, RawX* obj)
{
    for(int i=0; i!=n; ++i) {
00  mov         eax,dword ptr [esp+4] 
00  test        eax,eax 
00  je          raw_iterator_loop+53h (4028C3h) 
00  push        ebx  
00  mov         ebx,dword ptr [esp+0Ch] 
00  push        ebp  
00  push        esi  
00  push        edi  
00  mov         ebp,eax 
        side_effect();
00  call        side_effect (401020h) 
        for(PodType *j=obj->pData, *e=obj->pData+size_t(obj->wCount); j!=e; ++j) {
00  movzx       eax,word ptr [ebx+4] 
00  mov         esi,dword ptr [ebx] 
00  lea         edi,[esi+eax*2] 
00  cmp         esi,edi 
00  je          raw_iterator_loop+45h (4028B5h) 
00  jmp         raw_iterator_loop+30h (4028A0h) 
00  lea         esp,[esp] 
00  lea         ecx,[ecx] 
            g_read_size = *j;
00  movzx       ecx,word ptr [esi] 
00  mov         dword ptr [g_read_size (4060B0h)],ecx 
            side_effect();
00  call        side_effect (401020h) 
00  add         esi,2 
00  cmp         esi,edi 
00  jne         raw_iterator_loop+30h (4028A0h) 
        }
        side_effect();
00  call        side_effect (401020h) 
00  sub         ebp,1 
00  jne         raw_iterator_loop+12h (402882h) 
00  pop         edi  
00  pop         esi  
00  pop         ebp  
00  pop         ebx  
    }
}
00  ret              

* vector_iterator_loop *

void vector_iterator_loop(const int n, VecX* obj)
{
    for(int i=0; i!=n; ++i) {
00  mov         eax,dword ptr [esp+4] 
00  test        eax,eax 
00  je          vector_iterator_loop+43h (402813h) 
00  push        ebx  
00  mov         ebx,dword ptr [esp+0Ch] 
00  push        ebp  
00  push        esi  
00  push        edi  
00  mov         ebp,eax 
        side_effect();
00  call        side_effect (401020h) 
        for(std::vector<PodType>::const_iterator j=obj->vData.begin(), e=obj->vData.end(); j!=e; ++j) {
00  mov         esi,dword ptr [ebx+4] 
00  mov         edi,dword ptr [ebx+8] 
00  cmp         esi,edi 
00  je          vector_iterator_loop+35h (402805h) 
            g_read_size = *j;
00  movzx       eax,word ptr [esi] 
00  mov         dword ptr [g_read_size (4060B0h)],eax 
            side_effect();
00  call        side_effect (401020h) 
00  add         esi,2 
00  cmp         esi,edi 
00  jne         vector_iterator_loop+21h (4027F1h) 
        }
        side_effect();      
00  call        side_effect (401020h) 
00  sub         ebp,1 
00  jne         vector_iterator_loop+12h (4027E2h) 
00  pop         edi  
00  pop         esi  
00  pop         ebp  
00  pop         ebx  
    }
}
00  ret          

Answer 1

Хотя моя версия сгенерированного машинного кода отличается от вашей (MSVC ++ 2005), одно отличие между этими двумя вариантами почти такое же, как в вашем коде:

• В векторной версии кода значение «конечного итератора» предварительно рассчитывается и сохраняется как элемент объекта std::vector, поэтому внутренний цикл просто загружает легкодоступное значение.

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

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

void raw_iterator_loop(const int n, RawX* obj)
{
    PodType *e = obj->pData+size_t(obj->wCount);

    for(int i=0; i!=n; ++i) {
        side_effect();
        for(PodType *j=obj->pData; j!=e; ++j) {
            g_read_size = *j;
            side_effect();
        }
        side_effect();
    }
}

(или даже сохраните и сохраните указатель конца в вашем классе), в результате вы получите более "справедливое" сравнение.

Answer 2

Одна конкретная причина разницы в генерируемых инструкциях состоит в том, что Visual C ++ vector имеет элементы _Myfirst и _Mylast (соответствующие begin() и end()), которые упрощают настройку цикла.

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

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

Answer 3

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

Answer 4

Компилятор не может знать, что side_effect() не меняется obj->pData. Хранение вещей, которые не могут изменяться в локальных переменных, может ускорить сжатые циклы, особенно когда внутри цикла вызываются функции, которые не может анализировать компилятор.

p.S .: это влияет на raw_loop и vector_loop. raw_loop можно «исправить» с помощью локальных переменных, vector_loop нельзя. Это не может быть, потому что будет указатель массива внутри вектора, и компилятор также не может знать, что ничто не изменит указатель массива внутри вектора. В конце концов, side_effect может позвонить, например, push_back(). Конечно, если компилятор может встроить любую из функций цикла, он может оптимизироваться лучше. Например. если используемый вектор является локальной переменной, адрес которой неизвестен за пределами функции и передается только функциям цикла. Тогда компилятор может снова знать, что side_effect не может изменить вектор (потому что он не может знать его адрес), и оптимизировать лучше. -> Убедитесь, что компилятор не может встроить функцию, если вы хотите оптимизировать ее для нестандартных случаев.

Answer 5

Я знаю, что уже поздно, но одно быстрое наблюдение: неподписанные инструкции могут быть немного быстрее.Насколько я понимаю, аппаратная реализация немного проще, потому что нет знакового бита, который может изменяться при увеличении или уменьшении.Это всего лишь один такт для процессора с микроархитектурой P6, но все это складывается.

Я ожидаю, что size_t не имеет знака, так как нет отрицательных размеров.

Вы ДОЛЖНЫ профильс профилировщиком производителей микросхем (Intel VTUNE - 30-дневная пробная версия; AMD CodeAnalyzer бесплатен), потому что слишком много вещей, которые могут быть в игре: остановки конвейера, пропадание кэша, смещение данных, зависимости загрузки хранилища ...

Этот бизнес намного сложнее, чем 44 года назад, когда я писал свою первую программу на Фортране в старшей школе.Больше никто не программирует на ассемблере.Один настоящий сумасшедший человек смотрел на инструкции PA-Risc (системный чип HP Unix в 90-х годах), сгенерированные из программ на C ... операции были не в том порядке, как я ожидал, потому что генератор кода понимал внутренние операции PA-RiscЦПУ.Инструкции были заказаны смешно, потому что они будут иметь смысл в процессоре, но не на моем листе бумаги.

Answer 6

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

например

void countdown_loop(int n, RawX* obj)
{
    if (!n) return;
    size_t const wc = obj->wCount;
    if (!wc) return;
    PodType* const first = obj->pData;
    do {
        side_effect();
        size_t i = wc;
        PodType* p = first;
        do {
            g_read_size = *p;
            side_effect();
            ++p;
        } while (--i);
        side_effect();
    } while (--n);
}

Answer 7

Попробуйте изменить PodType с int на size_t.Преобразование там усложняет код инициализации цикла.

Answer 8

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

            g_read_size = *j; 
00  movzx       ecx,word ptr [esi]  
00  mov         dword ptr [g_read_size (4060B0h)],ecx  
            side_effect(); 
00  call        side_effect (401020h)  
00  add         esi,2  
00  cmp         esi,edi  
00  jne         raw_iterator_loop+30h (4028A0h)  

            g_read_size = *j;  
00  movzx       eax,word ptr [esi]   
00  mov         dword ptr [g_read_size (4060B0h)],eax   
            side_effect();  
00  call        side_effect (401020h)   
00  add         esi,2   
00  cmp         esi,edi   
00  jne         vector_iterator_loop+21h (4027F1h)   

У меня был похожий вопрос о синхронизации кода, где я не мог объяснить разницу в двух частях кода. Я никогда не получал однозначного ответа на этот вопрос, хотя в конце я убедил себя, что это был случай выравнивания кода. Как добавить код в цикл, чтобы он стал быстрее?