Встроенное кэширование - это метод оптимизации, используемый некоторыми языковыми средами выполнения и впервые разработанный для Smalltalk . [1] Целью встроенного кэширования является ускорение привязки методов во время выполнения за счет запоминания результатов предыдущего поиска метода непосредственно на месте вызова . Встроенное кэширование особенно полезно для языков с динамической типизацией, где большая часть, если не вся привязка методов происходит во время выполнения и где часто нельзя использовать таблицы виртуальных методов .
Привязка метода времени выполнения
Следующая функция ECMAScript получает объект, вызывает его метод toString и отображает результаты на странице, в которую встроен скрипт.
функция дампа ( объект ) { документ . записи ( OBJ . ToString ()); }
Поскольку тип объекта не указан и из-за возможной перегрузки метода , невозможно заранее решить, какая конкретная реализация toString-метода будет вызвана. Вместо этого во время выполнения должен выполняться динамический поиск. В языковых средах выполнения, которые не используют какую-либо форму кэширования, этот поиск выполняется каждый раз, когда вызывается метод. Поскольку методы могут быть определены на нескольких шагах вниз по цепочке наследования , динамический поиск может оказаться дорогостоящей операцией.
Для достижения лучшей производительности многие языковые среды исполнения используют некоторую форму не встроенного кэширования, когда результаты ограниченного числа поисков методов сохраняются в ассоциативной структуре данных. Это может значительно повысить производительность при условии, что выполняемые программы «дружественны к кешу» (т. Е. Имеется ограниченный набор часто вызываемых методов). Эта структура данных обычно называется кешем поиска метода первого уровня . [1]
Встроенное кеширование
Концепция встроенного кэширования основана на эмпирическом наблюдении, что объекты, которые появляются в определенном месте вызова, часто бывают одного типа. В таких случаях производительность может быть значительно увеличена за счет сохранения результата поиска метода «в строке», т. Е. Непосредственно на месте вызова. Чтобы облегчить этот процесс, узлам вызова назначаются разные состояния. Первоначально место вызова считается «неинициализированным». Как только языковая среда достигает определенного неинициализированного сайта вызова, она выполняет динамический поиск, сохраняет результат в сайте вызова и меняет свое состояние на «мономорфное». Если языковая среда выполнения снова достигает того же сайта вызова, она извлекает из него вызываемого и вызывает его напрямую, не выполняя дополнительных поисков. Чтобы учесть возможность того, что объекты разных типов могут встречаться в одном и том же месте вызова, среда выполнения языка также должна вставить в код условия защиты . Чаще всего они вставляются в преамбулу вызываемого, а не на сайте вызова, чтобы лучше использовать предсказание ветвления и сэкономить место за счет одной копии в преамбуле по сравнению с несколькими копиями на каждом сайте вызова. Если сайт вызова, находящийся в «мономорфном» состоянии, встречает тип, отличный от ожидаемого, он должен вернуться в «неинициализированное» состояние и снова выполнить полный динамический поиск.
Каноническая реализация [1] - это загрузка регистра константы, за которой следует инструкция вызова. «Неинициализированное» состояние лучше называть «несвязанным». В регистр загружается селектор сообщений (обычно адрес некоторого объекта), и вызывается подпрограмма времени выполнения, которая будет искать сообщение в классе текущего получателя, используя кеш поиска метода первого уровня выше. . Затем подпрограмма времени выполнения перезаписывает инструкции, изменяя инструкцию загрузки, чтобы загрузить регистр с типом текущего получателя, и инструкцию вызова для вызова преамбулы целевого метода, теперь "связывая" сайт вызова с целевым методом. . Затем исполнение продолжается сразу после преамбулы. Последующее выполнение вызовет преамбулу напрямую. Затем преамбула выводит тип текущего получателя и сравнивает его с этим в регистре; если они согласны, получатель принадлежит к тому же типу, и метод продолжает выполняться. В противном случае преамбула снова вызывает среду выполнения, и возможны различные стратегии, одна из которых состоит в том, чтобы повторно связать сайт вызова для нового типа получателя.
Повышение производительности достигается за счет необходимости выполнять сравнение одного типа вместо, по крайней мере, сравнения типов и сравнения селекторов для кеша поиска метода первого уровня, а также за счет использования прямого вызова (который выиграет от предварительной выборки инструкций и конвейерной привязки) в отличие от косвенного вызова в поиске метода или отправке vtable .
Мономорфное встроенное кэширование
Если конкретный сайт вызова часто видит различные типы объектов, преимущества в производительности встроенного кэширования могут быть легко сведены на нет накладными расходами, вызванными частыми изменениями состояния сайта вызова. Следующий пример представляет собой наихудший сценарий для мономорфного встроенного кэширования:
var values = [ 1 , «a» , 2 , «b» , 3 , «c» , 4 , «d» ]; for ( var i in values ) { document . запись ( значения [ я ]. toString ()); }
Опять же, метод toString вызывается для объекта, тип которого заранее не известен. Что еще более важно, тип объекта меняется с каждой итерацией окружающего цикла. Поэтому наивная реализация мономорфного встроенного кэширования будет постоянно циклически проходить через «неинициализированное» и «мономорфное» состояния. Чтобы этого не произошло, большинство реализаций мономорфного встроенного кэширования поддерживают третье состояние, часто называемое «мегаморфным» состоянием. В это состояние входит, когда конкретный объект вызова видел заранее определенное количество различных типов. После того, как сайт вызова перешел в «мегаморфное» состояние, он будет вести себя так же, как и в «неинициализированном» состоянии, за исключением того, что он больше никогда не войдет в «мономорфное» состояние (некоторые реализации мономорфного встроенного кэширования изменятся » мегаморфный «обратный вызов сайтов в« неинициализированный »по прошествии определенного времени или после выполнения полного цикла сборки мусора ).
Полиморфное встроенное кэширование
Чтобы лучше работать с сайтами вызовов, которые часто видят ограниченное количество различных типов, некоторые языковые среды выполнения используют метод, называемый полиморфным встроенным кэшированием. [2] При полиморфном встроенном кэшировании, как только вызывающий сайт, находящийся в «мономорфном» состоянии, видит свой второй тип, вместо того, чтобы вернуться в «неинициализированное» состояние, он переключается в новое состояние, называемое «полиморфным». «Полиморфный» сайт вызова решает, какой из ограниченного набора известных методов вызывать, в зависимости от типа, которым он представлен в настоящее время. Другими словами, при полиморфном встроенном кэшировании результаты поиска нескольких методов могут быть записаны на одном сайте вызова. Поскольку каждый сайт вызова в программе потенциально может видеть каждый тип в системе, обычно существует верхняя граница того, сколько результатов поиска записывается на каждом сайте вызова. Как только эта верхняя граница достигнута, сайты вызовов становятся «мегаморфными» и больше не выполняется встроенное кэширование.
Каноническая реализация [2] представляет собой таблицу переходов, которая состоит из преамбулы, определяющей тип приемника, и серии сравнений констант и условных переходов, которые переходят к коду, следующему за преамбулой в соответствующем методе для каждого типа приемника. Таблица переходов обычно выделяется для конкретного места вызова, когда мономорфный сайт вызова встречает другой тип. Таблица переходов будет иметь фиксированный размер и сможет увеличиваться, добавляя случаи по мере обнаружения новых типов до некоторого небольшого максимального количества случаев, таких как 4, 6 или 8. Как только он достигнет своего максимального размера, выполнение для нового типа получателя "отвалится" от конца и войдет во время выполнения, обычно для выполнения поиска метода, начиная с кеша методов первого уровня.
Наблюдение за тем, что вместе мономорфные и полиморфные встроенные кеши собирают информацию о типе получателя для каждого сайта вызова в качестве побочного эффекта оптимизации выполнения программы [2], привело к разработке адаптивной оптимизации в Self , где во время выполнения оптимизируются «горячие точки». "в программе, используя информацию о типе во встроенных кэшах, чтобы руководствоваться спекулятивными решениями о встраивании.
Мегаморфное встроенное кеширование
Если во время выполнения используется как мономорфное, так и полиморфное встроенное кэширование, то в устойчивом состоянии единственными несвязанными отправками будут отправления, отправленные с концов полиморфных встроенных кешей. Поскольку такие рассылки происходят медленно, теперь может быть выгодно оптимизировать эти сайты. Мегаморфный встроенный кеш может быть реализован путем создания кода для выполнения поиска метода первого уровня для конкретного сайта вызова. В этой схеме, как только отправка падает с конца полиморфного встроенного кеша, создается мегаморфный кеш, специфичный для селектора сайта вызова (или совместно используемый, если он уже существует), и сайт отправки повторно связывается для его вызова. Код может быть значительно более эффективным, чем обычная проверка поиска метода первого уровня, поскольку селектор теперь является константой, что снижает давление в регистре, код для поиска и отправки выполняется без вызова среды выполнения, а отправка может выгода от предсказания ветвления .
Эмпирические измерения [3] показывают, что в больших программах Smalltalk около 1/3 всех сайтов отправки в активных методах остаются несвязанными, а из оставшихся 2/3 90% являются мономорфными, 9% полиморфными и 1% (0,9%) мегаморфными. .
Смотрите также
Рекомендации
- ^ a b c Л. Питер Дойч, Аллан М. Шиффман, «Эффективная реализация системы smalltalk-80», POPL '84: Материалы 11-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования, январь 1984 г.
- ^ a b c Hölzle, U., Chambers, C., AND Ungar, D. 1991. Оптимизация динамически типизированных объектно-ориентированных языков с полиморфными встроенными кэшами. В материалах конференции ECOOP '91. Конспект лекций по информатике, т. 512. Springer-Verlag, Берлин.
- ^ PICs [было первым впечатлением от v8] в списке рассылки Strongtalk