Можно ли сэкономить память при копипасте?

Question

[Виталий]

Представьте такой пример. Есть несколько функций, которые частично повторяют функционал, например содержат одинаковый цикл присваивания массива. Таких повторов может быть много, что сказывается на размере исполняемого файла и скорости его загрузки в оперативную память. Существуют ли способы компиляции (скажем так) ссылочным методом? Имею ввиду такой пример:

<раздел "a">
<command 1>
<command 2>
...
</a>

<функция "f">
<command 1>
<alias "a">
<command n>
...
</f>

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

Comments

[15432]

вынести повторяющийся код в отдельную процедуру, да и всё

[Виталий]

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

[15432]

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

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

вот у нас был (не очень оптимальный) код, часть которого (memset) нам хочется вынести как дублирующийся:

...
    mr    r3,   r31 //адрес начала
    mr    r4,   r30 //значение
    mr    r5,   r29 //размер
loop:
    cmp  r5,  0
    beq   exit_loop
    stb    r4,   0(r3) 
    addi  r3,   r3,  1
    addi  r5,   r5,  -1
    b  loop
exit_loop:
    ...

мы просто берём этот кусок кода и выносим отдельно, а затем прыгаем на него

//наш кусок в виде отдельной функции
memset:
    cmp  r5,  0
    beq   exit_loop
    stb    r4,   0(r3)
    addi  r3,   r3,  1
    addi  r5,   r5,  -1
    b  memset
exit_loop:
    blr //прыгнуть на запомненное место возврата
    ...
//в основном коде осталась лишь передача параметров и прыжок
    mr    r3,   r31
    mr    r4,   r30
    mr    r5,   r29
    bl     memset //прыгнуть и сохранить место возврата 
    ... //сюда вернется процессор после исполнения функции

[Денис Загаевский]

Вы уверены, что эти несколько инструкций - бутылочное горлышко? Почему?

[Виталий]

15432, спасибо за пример, мы как раз обсуждаем это в комментариях к ответу ниже и там я задал такой вопрос: каким образом тело функции понимает, по какому адресу находится вершина стека?

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

И ещё: если вызов подпрограммы - это просто прыжок с обработкой стека, зачем написаны оптимизаторы, которые подставляют вместо вызова методов get/set тело функции? Почему считается, что вызов подпрограммы дороже, чем например использование цикла?

[15432]

Виталий,

каким образом тело функции понимает, по какому адресу находится вершина стека?

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

но если попытаться делать прыжок на один участок кода из разных функций

ничего не изменится, всё будет точно так же, как если бы этот участок кода был просто вставлен в тело функций

общий код не будет понимать, с каким контекстом ему работать в данный момент

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

Но что, если мы имеем дело с многопоточностью

совсем отдельная тема. там отдельная фигня, которая глобально переключает потоки и состояния. переключится поток - переключатся и все значения регистров. вообще никаких проблем

Почему считается, что вызов подпрограммы дороже, чем например использование цикла?

для вызова процедуры нужно сохранить адрес возврата, старое значение стека, если процедура меняет non-volatile регистры, то ещё и их сохранить. пихается это всё в стек, а запись в память не самая быстрая операция. поэтому небольшие часто вызываемые функции оптимальнее вставлять в код напрямую, без вызовов call.

Answer 1

[Арсений Ефремов]

В общем случае эта задача не решаема из-за различия контекстов исполнения.
Чтобы добиться схожего эффекта, люди и придумали функции ведь. Думаю, что вы знаете, что функция - в сущности, инструкция call, которая обвешена дополнительным кодом для организации изолированного контекста. Если вам это поведение не нужно, то почему бы не использовать обычные инструкции jmp/call и писать в goto-стиле? Тогда отдельные участки кода будут полагаться на определённые предположения о контексте и переиспользоваться, в зависимости от оного. Но учтите, что такой подход крайне сложен и является источником большого числа ошибок.

Comments

[Вадим Ш]

goto ооочень плохой codeStyle

[Виталий]

Вы уловили мысль, предлагаю продолжить. Я не силён в assembler, но сейчас мне важно понять в теории, что это в принципе возможно или невозможно.

Насколько мне известно, контекст - это набор значений в стеке, который формируется перед выполнением call. Мешает ли что-нибудь делать jmp из тела функции (в контексте) в общую область памяти? Знаю, что в С++ нельзя, но если смотреть с уровня ассемблера, то приходит мысль: ведь такой участок кода будет также работать с верхушкой стека в текущем контексте. Вопрос в том, откуда возьмётся ссылка на этот контекст во внешней области, поэтому вероятно, что эта идея недееспособна. Как в теле функции определяется, по какому адресу находится вершина активного стека?

[res2001]

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

[Виталий]

res2001, комментарий ни о чём.

Нужный контекст создается в функции передаваемыми ей параметрами.

Контекст не создаётся параметрами. Он создаётся инструкциями процессора.

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

Уже было такое предложение в комментарии выше и это не решение задачи.

[res2001]

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

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

PS: вам это уже посоветовало несколько человек, может пора прислушаться?

[Виталий]

res2001, вы немножко не в теме, повторю специально для вас:

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

Если я не прав - прошу поправить. Иначе мне не нужны советы по красивому оформлению кода, мне нужно эффективное решение по скорости выполнения.

И да, я не говорил, что контекст - это код. Я сказал, что любые данные создаются кодом, а не другими данными. Данные - это материал, из которого что-то строится, но материал - это не строитель.

[15432]

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

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

и вуаля, вы получили функцию...
из вашего описания я приблизительно понял, что вы хотите хардварные макросы. для x86 можно посмотреть в сторону MMX / SSE / AVX расширений, там есть много интересных команд, которые легко заменяют несколько строчек кода. Или можете спроектировать свой собственный процессор с своей системой команд на FPGA :)

[Виталий]

15432, я так понял, что участки кода получится вынести, только если сохранять адрес возврата (состояние стека и регистров можно оставлять нетронутыми). Получаем 4 лишних действия: сохранить адрес, прыжок, достать адрес, прыжок - правильно?
Но всё равно многовато. Узнал, что существуют алгоритмы сжатия исполняемого файла, частично это может решить задачу. Но единственным решением пока что вижу различное поведение (дублирование или вызов подпрограммы) в зависимости от количества операций.
Спасибо за участие, по-размышлять было полезно.

[15432]

Виталий, в архитектуре PowerPC это всего два действия, bl и blr :) ... в x86 кстати тоже, call и ret
ну да, можно запаковать код и на лету небольшим скриптом его распаковывать в ОЗУ, очень часто в микроконтроллерах встречается