Почему не проходит структурная ссылка по общей оптимизации? - программирование

Почему не проходит структурная ссылка по общей оптимизации?

До сегодняшнего дня я всегда думал, что достойные компиляторы автоматически преобразуют struct pass-by-value в pass-by-reference, если структура достаточно велика, чтобы последняя была быстрее. Насколько мне известно, это похоже на беспроблемную оптимизацию. Однако, чтобы удовлетворить мое любопытство относительно того, действительно ли это происходит, я создал простой тестовый пример как на С++, так и на D и посмотрел вывод как GCC, так и Digital Mars D. Оба настаивали на передаче 32-байтных структур по значению, когда вся эта функция была связана с добавлением членов и возвратом значений без изменения структуры, переданной в. Версия С++ приведена ниже.

#include "iostream.h"

struct S {
    int i, j, k, l, m, n, o, p;
};

int foo(S s) {
    return s.i + s.j + s.k + s.l + s.m + s.n + s.o + s.p;
}

int main() {
    S s;
    int bar = foo(s);
    cout << bar;
}

Мой вопрос в том, почему heck не хотел бы, чтобы это было оптимизировано компилятором для передачи по ссылке вместо фактического нажатия всех этих int в стек?

Примечание. Используются переключатели компилятора: GCC -O2 (-O3 inlined foo().), DMD -O -inline -release.

Edit: Очевидно, что в общем случае семантика pass-by-value vs. pass-by-reference не будет одинаковой, например, если задействованы конструкторы копирования или исходная структура изменяется в вызываемом. Однако во многих сценариях реального мира семантика будет идентичной с точки зрения наблюдаемого поведения. Это те случаи, о которых я прошу.

4b9b3361

Ответ 1

Не забывайте, что в C/С++ компилятор должен иметь возможность компилировать вызов функции, основанной только на объявлении функции.

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

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

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

Я не уверен, что если вы это сделаете (на самом деле, я был бы удивлен, если бы кто-нибудь это сделал, так как он, вероятно, не мог применяться очень часто).

Конечно, как программист (при использовании С++) вы можете заставить компилятор выполнить эту оптимизацию, используя параметры const&, когда это возможно. Я знаю, что вы спрашиваете, почему компилятор не может сделать это автоматически, но я полагаю, что это следующая лучшая вещь.

Ответ 2

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

Ответ 3

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

Если это будет созданное компилятором решение, это будет плохая идея. Причина в том, что это не позволяет рассуждать о потоке вашего кода. Вы не можете смотреть на звонок и знать, что именно он будет делать. Вы должны: a) знать код и b) угадывать оптимизацию компилятора.

Ответ 4

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

Ответ 5

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

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

Следует отметить, что оптимизация, изменяющая способ вызова функции, может работать только тогда, когда оптимизируемая функция является внутренней для компилируемого модуля (вы получаете это, объявляя функцию static в C и с шаблонами на С++), Оптимизатор должен исправить не только функцию, но и все точки вызова. Это делает такие оптимизации довольно ограниченными по охвату, если вы не делаете их во время связи. Кроме того, оптимизация никогда не будет вызываться, когда задействован конструктор копирования (как упоминались другие плакаты), поскольку он может потенциально изменить семантику программы, чего не должен делать хороший оптимизатор.

Ответ 6

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

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

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

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

Ответ 7

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

Ответ 8

Передача по ссылке - это просто синтаксический сахар для pass-by-address/pointer. Таким образом, функция должна неявно разыменовывать указатель для чтения значения параметра. Разделение указателя может быть более дорогостоящим (если в цикле), то копией структуры для копирования по значению.

Более того, как отмечали другие, у pass-by-reference есть другая семантика, чем pass-by-value. Ссылки const не означают, что ссылочное значение не изменяется. другие вызовы функций могут изменить ссылочное значение.

Ответ 9

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

Ваш компилятор должен будет обнаружить a), что foo не изменяет структуру; б) что foo не делает никаких вычислений по физическому расположению структурных элементов; И c), что вызывающий объект или другой поток, порожденный вызывающим, не изменяет структуру до того, как foo закончен.

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

Ответ 10

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

double x; // using non structs, oh-well

void Foo(double d)
{
      x += d; // ok
      x += d; // Oops
}

void main()
{
     x = 1;
     Foo(x);
}

Ответ 11

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

Хотя существует множество обстоятельств, при которых операции копирования фактически могут быть опущены, зачастую компилятору будет сложно доказать, что такие операции могут быть устранены. Например, учитывая:

struct FOO { ... };

void func1(struct FOO *foo1);
void func2(struct FOO foo2);

void test(void)
{
  struct FOO foo;
  func1(&foo);
  func2(foo);
}

нет никакого способа, чтобы компилятор мог знать, может ли foo быть модифицированным во время выполнения func2 (func1 мог бы сохранить копию foo1 или полученный от него указатель в объекте области области, который затем используется func2). Однако такие модификации не должны влиять на копию foo (т.е. foo2), полученную func2. Если foo были переданы по ссылке, а func2 не сделал копию, действия, которые влияют на foo будут неправильно влиять на foo2.

Обратите внимание, что даже void func3(const struct FOO); не имеет смысла: вызываемому разрешено отбрасывать const, а обычное соглашение о вызове asm по-прежнему позволяет вызываемому изменять память, хранящую копию по значению.

К сожалению, относительно мало случаев, когда рассмотрение вызывающей или вызываемой функции в изоляции было бы достаточным, чтобы доказать, что операция копирования может быть безопасно опущена, и есть много случаев, когда даже рассмотрение обоих будет недостаточным. Таким образом, замена pass-by-value на pass-by-reference представляет собой сложную оптимизацию, выигрыш которой часто недостаточен для обоснования сложности.


Сноска 1: Например, Windows x64 пропускает объекты размером более 8 байтов с помощью неконстантной ссылки (callle "владеет" заостренной памятью). Это не помогает избежать копирования вообще; мотивация заключается в том, чтобы все аргументы arg соответствовали по 8 байтов каждый, чтобы они формировали массив в стеке (после того, как регистр регистров переместился в теневое пространство), что упрощает реализацию вариационных функций.

Напротив, x86-64 System V выполняет то, что задает вопрос для объектов размером более 16 байт: копирование их в стек. (Меньшие объекты упакованы до двух регистров.)

Ответ 12

Эффективно передавая struct по ссылке, даже когда объявление функции указывает, что параметр pass-by-value является общей оптимизацией: это просто, что это обычно происходит косвенно через inline, поэтому это не очевидно из сгенерированного кода.

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

Это может произойти даже без встраивания!

Тем не менее, некоторые компиляторы осуществить эту оптимизацию, даже в отсутствии встраивания, хотя обстоятельства относительно ограничены, по крайней мере, на платформах, использующей SysV ABI (Linux, OSX, и т.д.) из - за ограничения компоновки стеки. Рассмотрим следующий простой пример, основанный непосредственно на вашем коде:

__attribute__((noinline))
int foo(S s) {
    return s.i + s.j + s.k + s.l + s.m + s.n + s.o + s.p;
}

int bar(S s) {
    return foo(s);
}

Здесь на уровне языка bar вызывает foo с семантикой pass-by-value, как требуется C++. Однако, если мы рассмотрим сборку, сгенерированную gcc, она выглядит так:

foo(S):
        mov     eax, DWORD PTR [rsp+12]
        add     eax, DWORD PTR [rsp+8]
        add     eax, DWORD PTR [rsp+16]
        add     eax, DWORD PTR [rsp+20]
        add     eax, DWORD PTR [rsp+24]
        add     eax, DWORD PTR [rsp+28]
        add     eax, DWORD PTR [rsp+32]
        add     eax, DWORD PTR [rsp+36]
        ret
bar(S):
        jmp     foo(S)

Обратите внимание, что bar просто вызывает foo, не делая копии: bar будет использовать ту же копию s которая была передана в bar (в стеке). В частности, это не делает никакой копии, как подразумевается семантикой языка (игнорируя, как будто). Таким образом, gcc выполнил именно ту оптимизацию, которую вы запросили. Clang не делает этого, хотя: он делает копию в стеке, которую он передает foo().

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

Это возможно в foo/bar, например, так как бар принимает его S в качестве первого параметра таким же образом, как foo и bar делает хвост вызов к foo, который позволяет избежать необходимости неявного обратного адреса толчка, который бы в противном случае разрушить способность к повторите использование аргумента стека.

Например, если мы просто добавим + 1 к вызову foo:

int bar(S s) {
    return foo(s) + 1;
}

Трюк разрушен, так как теперь позиция bar::s отличается от местоположения foo, ожидает его аргумент s, и нам нужна копия:

bar(S):
        push    QWORD PTR [rsp+32]
        push    QWORD PTR [rsp+32]
        push    QWORD PTR [rsp+32]
        push    QWORD PTR [rsp+32]
        call    foo(S)
        add     rsp, 32
        add     eax, 1
        ret

Это не означает, что bar() вызова bar() должна быть абсолютно тривиальной. Например, он может изменить свою копию s, прежде чем передавать ее:

int bar(S s) {
    s.i += 1;
    return foo(s);
}

... и оптимизация будет сохранена:

bar(S):
        add     DWORD PTR [rsp+8], 1
        jmp     foo(S)

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

Встраивание

Однако все это в сторону, главным образом, эта оптимизация происходит через inlining.

Например, в компиляции -O2 все clang, gcc и MSVC не делают никакой копии объекта S 1. Как clang, так и gcc вообще не создают объект, а просто вычисляют результат более или менее напрямую, даже не ссылаясь на неиспользуемые поля. MSVC выделяет пространство стека для копии, но никогда не использует его: он заполняет только одну копию только S и читает с нее, как и для передачи по ссылке (MSVC генерирует гораздо худший код, чем два других компилятора для этого случая),

Обратите внимание, что даже если foo встроен в main компиляторы также генерируют отдельную автономную копию функции foo() поскольку она имеет внешнюю связь и поэтому может использоваться этим объектным файлом. В этом компилятор ограничен бинарным интерфейсом приложения: SysV ABI (для Linux) или Win64 ABI (для Windows) точно определяет, как должны передаваться значения, в зависимости от типа и размера значения. Большие структуры передаются скрытым указателем, и компилятор должен уважать это при компиляции foo. Также необходимо учитывать, что компиляция некоторого вызывающего foo когда foo не может быть замечена: поскольку он не знает, что будет делать foo.

Таким образом, для компилятора очень мало окна, чтобы сделать эффективную оптимизацию, которая преобразует pass-by-value в pass-by-reference, потому что:

1) Если он может видеть как вызывающего абонента, так и вызываемого (main и foo в вашем примере), вполне вероятно, что вызываемый будет включен в вызывающий абонент, если он достаточно мал, а поскольку функция становится большой и не проницаемой, эффект фиксированных затрат, таких как накладные расходы на конвенцию, становится относительно меньшим.

2) Если компилятор не может одновременно видеть как вызывающего абонента, так и вызываемого абонента 2 он обычно должен скомпилировать каждый в соответствии с платформой ABI. Нет возможности для оптимизации вызова на сайте вызова, поскольку компилятор не знает, что сделает вызываемый, и нет возможности для оптимизации внутри вызываемого абонента, потому что компилятор должен сделать консервативные предположения о том, что сделал вызывающий.


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

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