Как часто значения дублируются в стеке?

Question

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

Кто-нибудь знает, как часто стеки содержат дублирующие указатели на практике?

РЕДАКТИРОВАТЬ

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

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

Answer 1

Во-первых, ответ будет зависеть от вашего приложения.

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

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

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

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

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

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

Answer 2

Могу ли я предложить получить некоторую информацию о реальной настройке производительности? (Вот мой канонический пример.)

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

ЕслиПрограмма P написана для выполнения задачи T, существует множество других программ P ', которые также могут выполнять задачу T. Некоторые из них занимают меньше циклов, чем все другие, и они являются оптимальными.Отличие оптимальных от неоптимальных заключается в том, что неоптимальные делают то, что можно сделать без .

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

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