оптимизация доступа к членам в c ++

Question

Я сталкиваюсь с противоречивым поведением оптимизации с различными компиляторами для следующего кода:

class tester
{
public:
    tester(int* arr_, int sz_)
        : arr(arr_), sz(sz_)
    {}

    int doadd()
    {
        sm = 0;
        for (int n = 0; n < 1000; ++n) 
        {
            for (int i = 0; i < sz; ++i)
            {
                sm += arr[i];
            }
        }
        return sm;
    }
protected:
    int* arr;
    int sz;
    int sm;
};

Функция doadd имитирует некоторый интенсивный доступ к членам (игнорируйте переполнения в дополнение к этому вопросу). По сравнению с аналогичным кодом, реализованным как функция:

int arradd(int* arr, int sz)
{
    int sm = 0;
    for (int n = 0; n < 1000; ++n) 
    {
        for (int i = 0; i < sz; ++i)
        {
            sm += arr[i];
        }
    }
    return sm;
}

Метод doadd работает примерно в 1,5 раза медленнее, чем arradd функция при компиляции в режиме Release с Visual C ++ 2008. Когда я изменяю метод doadd следующим образом (наложение всех члены с местными жителями):

int doadd()
{
    int mysm = 0;
    int* myarr = arr;
    int mysz = sz;
    for (int n = 0; n < 1000; ++n) 
    {
        for (int i = 0; i < mysz; ++i)
        {
            mysm += myarr[i];
        }
    }
    sm = mysm;
    return sm;
}

Время выполнения становится примерно одинаковым. Прав ли я в заключении, что это недостающая оптимизация компилятором Visual C ++? g++, кажется, делает это лучше и запускает функцию-член и обычную функцию с одинаковой скоростью при компиляции с -O2 или -O3.

---

Сравнительный анализ выполняется путем вызова элемента doadd и функции arradd для некоторого достаточно большого массива (размером в несколько миллионов целых чисел).

---

РЕДАКТИРОВАТЬ: Некоторые мелкозернистые испытания показывают, что основным виновником является sm член. Замена всех остальных локальными версиями по-прежнему увеличивает время выполнения, но после замены sm на mysm время выполнения становится равным версии функции.

---

Разрешение

Разочаровавшись в ответах (извините, ребята), я избавился от своей лени и погрузился в списки разборки для этого кода. Мой ответ ниже обобщает результаты. Вкратце: он не имеет ничего общего с псевдонимами, он имеет отношение к развертыванию циклов, и с некоторой странной эвристикой MSVC применяется при принятии решения, какой цикл развернуть.

Answer 1

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

Answer 2

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

Поскольку sm не является локальной переменной, MSVC, очевидно, предполагаетчто это может быть псевдоним arr.Это довольно разумное предположение: поскольку arr защищено, производный класс может установить для него значение sm, поэтому arr может псевдоним sm.

GCC видитчто он на самом деле не имеет псевдонима arr, и поэтому он не записывает sm обратно в память до окончания цикла, что намного быстрее.

Конечно, можно создать экземпляр класса, чтобы arr указывает на sm, что MSVC будет обрабатывать, но GCC не будет.

Если предположить, что sz > 1, оптимизация GCC в целом допустима.

Поскольку функция перебирает arr, обрабатывая ее как массив элементов sz, вызывая функцию с sz > 1 приведет к неопределенному поведению независимо от того, arr псевдонимы sm, и поэтому GCC может с уверенностью предположить, что они не псевдоним.Но если sz == 1, или если компилятор не может быть уверен, какое значение может быть sz, то он рискует, что sz может быть 1, и поэтому arr иsm вполне может легально использовать псевдоним, и код GCC будет нарушен.

Так что, скорее всего, GCC просто сойдет с рук, включив все это, и увидев, что в этом случае , онине псевдоним.

Answer 3

Я разобрал код с помощью MSVC, чтобы лучше понять, что происходит. Оказывается, псевдонимы не были проблемой вообще, и при этом не была какая-то безопасность параноидальной нити.

Вот интересная часть функции arradd отключена:

    for (int n = 0; n < 10; ++n)
    {
        for (int i = 0; i < sz; ++i)
013C101C  mov         ecx,ebp 
013C101E  mov         ebx,29B9270h 
        {
            sm += arr[i];
013C1023  add         eax,dword ptr [ecx-8] 
013C1026  add         edx,dword ptr [ecx-4] 
013C1029  add         esi,dword ptr [ecx] 
013C102B  add         edi,dword ptr [ecx+4] 
013C102E  add         ecx,10h 
013C1031  sub         ebx,1 
013C1034  jne         arradd+23h (13C1023h) 
013C1036  add         edi,esi 
013C1038  add         edi,edx 
013C103A  add         eax,edi 
013C103C  sub         dword ptr [esp+10h],1 
013C1041  jne         arradd+16h (13C1016h) 
013C1043  pop         edi  
013C1044  pop         esi  
013C1045  pop         ebp  
013C1046  pop         ebx  

ecx указывает на массив, и мы можем видеть, что внутренний цикл развернут здесь x4 - обратите внимание на четыре последовательные add инструкции со следующих адресов и ecx продвигается на 16 байт (4 слова) за раз внутри цикла.

Для неоптимизированной версии функции-члена doadd:

int tester::doadd()
{
    sm = 0;
    for (int n = 0; n < 10; ++n)
    {
        for (int i = 0; i < sz; ++i)
        {
            sm += arr[i];
        }
    }
    return sm;
}

Разборка (это сложнее найти, так как компилятор вставил ее в main):

    int tr_result = tr.doadd();
013C114A  xor         edi,edi 
013C114C  lea         ecx,[edi+0Ah] 
013C114F  nop              
013C1150  xor         eax,eax 
013C1152  add         edi,dword ptr [esi+eax*4] 
013C1155  inc         eax  
013C1156  cmp         eax,0A6E49C0h 
013C115B  jl          main+102h (13C1152h) 
013C115D  sub         ecx,1 
013C1160  jne         main+100h (13C1150h) 

Примечание 2 вещи:

• Сумма хранится в регистре - edi. Следовательно, здесь нет псевдонима "заботы" . Значение sm не перечитывается постоянно. edi инициализируется только один раз, а затем используется как временный. Вы не видите его возврата, так как компилятор оптимизировал его и использовал edi непосредственно в качестве возвращаемого значения встроенного кода.
• Петля не развернута. Почему? Нет веской причины.

Наконец, вот «оптимизированная» версия функции-члена, в которой mysm хранит локальную сумму вручную:

int tester::doadd_opt()
{
    sm = 0;
    int mysm = 0;
    for (int n = 0; n < 10; ++n)
    {
        for (int i = 0; i < sz; ++i)
        {
            mysm += arr[i];
        }
    }
    sm = mysm;
    return sm;
}

(опять же, встроенная) разборка:

    int tr_result_opt = tr_opt.doadd_opt();
013C11F6  xor         edi,edi 
013C11F8  lea         ebp,[edi+0Ah] 
013C11FB  jmp         main+1B0h (13C1200h) 
013C11FD  lea         ecx,[ecx] 
013C1200  xor         ecx,ecx 
013C1202  xor         edx,edx 
013C1204  xor         eax,eax 
013C1206  add         ecx,dword ptr [esi+eax*4] 
013C1209  add         edx,dword ptr [esi+eax*4+4] 
013C120D  add         eax,2 
013C1210  cmp         eax,0A6E49BFh 
013C1215  jl          main+1B6h (13C1206h) 
013C1217  cmp         eax,0A6E49C0h 
013C121C  jge         main+1D1h (13C1221h) 
013C121E  add         edi,dword ptr [esi+eax*4] 
013C1221  add         ecx,edx 
013C1223  add         edi,ecx 
013C1225  sub         ebp,1 
013C1228  jne         main+1B0h (13C1200h) 

Цикл здесь развернут, но только х2.

Это довольно хорошо объясняет мои наблюдения за разницей в скорости. Для массива 175e6 функция выполняется ~ 1,2 с, неоптимизированный элемент ~ 1,5 с, а оптимизированный член ~ 1,3 с. (Обратите внимание, что это может отличаться для вас, на другой машине я получил более близкое время выполнения для всех 3 версий).

А как насчет gcc? При компиляции все 3 версии работали с ~ 1,5 сек. Подозревая отсутствие развёртывания, я посмотрел на разборку gcc и действительно: gcc не разворачивает ни одну из версий .

Answer 4

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

Answer 5

Ключ, вероятно, в том, что doadd записывается так, если вы делаете явный доступ к элементу с помощью this:

int doadd()
{
    this->sm = 0;

    for (int n = 0; n < 1000; ++n) 
    {
        for (int i = 0; i < this->sz; ++i)
        {
            this->sm += this->arr[i];
        }
    }

    return this->sm;
}

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

Почему это может быть?Насколько я понимаю, this обычно хранится в регистре, поэтому я не думаю, что в конечном итоге он будет медленнее, чем просто доступ к стеку (что также является смещением в указателе стека).Как указывают другие ответы, вероятно, это проблема псевдонимов, которая генерирует менее оптимальный код: компилятор не может определить, перекрывается ли какой-либо из адресов памяти.Обновление sm также теоретически может изменить содержимое arr, поэтому оно решает каждый раз записывать значение sm в основную память, а не отслеживать его в регистре.Когда переменные находятся в стеке, компилятор может предполагать , что они все по разным адресам памяти.Компилятор не видит программу так ясно, как вы: он может сказать, что находится в стеке (потому что вы объявили это так), но все остальное - просто произвольные адреса памяти, которые могут быть чем угодно, где угодно, перекрывая любой другой указатель.

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

Answer 6

Это не совсем тот же код вообще. Если вы поместите переменные sm, arr и sz в класс вместо того, чтобы делать тему локальной, компилятор не сможет (легко) догадаться, что какой-то другой класс не унаследует класс test и захочет получить доступ к этим членам, делая что-то как `arr = & sm; doadd () ;. Отныне доступ к этим переменным не может быть оптимизирован так, как если бы они были локальными для работы.

В конце концов, причина в основном та, на которую указал Пол: sm обновляется в реальной памяти при использовании члена класса, может храниться в регистре, когда находится в функции. Чтение памяти из add не должно сильно влиять на результирующее время, так как в любом случае для получения значения необходимо прочитать memomry.

В этом случае, если test не экспортируется в другой модуль и не имеет псевдонимов даже косвенно для экспортируемого объекта, и если нет псевдонимов, как описано выше. Компилятор может оптимизировать промежуточные записи в sm ... некоторые компиляторы, такие как gcc, похоже, оптимизируют достаточно агрессивно, чтобы обнаруживать вышеперечисленные случаи (будет ли это и в случае экспорта тестового класса). Но это действительно сложные предположения. Все еще есть гораздо более простые оптимизации, которые еще не выполняются компиляторами (например, встраивание через различные модули компиляции).

Answer 7

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

http://developers.sun.com/solaris/articles/cc_restrict.html