Встроенное кэширование
Встроенное кэширование — это метод оптимизации , используемый некоторыми средами выполнения языков и впервые разработанный для Smalltalk . [1] Цель встроенного кэширования — ускорить связывание методов во время выполнения за счет запоминания результатов предыдущего поиска метода непосредственно на месте вызова . Встроенное кэширование особенно полезно для динамически типизированных языков, где большая часть, если не все, связывание методов происходит во время выполнения и где таблицы виртуальных методов часто невозможно использовать .
Привязка метода времени выполнения
[ редактировать ]Следующая функция ECMAScript получает объект, вызывает его метод toString и отображает результаты на странице, в которую встроен скрипт.
function dump(obj) {
document.write(obj.toString());
}
Поскольку тип объекта не указан и из-за потенциальной перегрузки метода невозможно заранее решить, какая конкретная реализация метода toString будет вызываться. Вместо этого во время выполнения необходимо выполнять динамический поиск. В средах выполнения языка, которые не используют какую-либо форму кэширования, этот поиск выполняется каждый раз при вызове метода. Поскольку методы могут быть определены на нескольких этапах цепочки наследования , динамический поиск может оказаться дорогостоящей операцией.
Для достижения более высокой производительности во многих средах выполнения языков используется та или иная форма невстроенного кэширования, при которой результаты ограниченного числа поисков методов сохраняются в ассоциативной структуре данных. Это может значительно повысить производительность при условии, что выполняемые программы «дружественны к кэшу» (т. е. существует ограниченный набор часто вызываемых методов). Эту структуру данных обычно называют кэшем поиска методов первого уровня . [1]
Встроенное кэширование
[ редактировать ]Концепция встроенного кэширования основана на эмпирическом наблюдении, что объекты, возникающие на определенном месте вызова, часто относятся к одному и тому же типу. В этих случаях производительность можно значительно повысить, сохранив результат поиска метода «встроенным»; т. е. непосредственно на месте вызова. Чтобы облегчить этот процесс, местам вызова присваиваются разные состояния. Изначально точка вызова считается «неинициализированной». Как только среда выполнения языка достигает определенного неинициализированного места вызова, она выполняет динамический поиск, сохраняет результат в месте вызова и меняет свое состояние на «мономорфное». Если среда выполнения языка снова достигает того же места вызова, она извлекает из него вызываемого абонента и вызывает его напрямую, не выполняя дополнительных поисков. Чтобы учесть возможность появления объектов разных типов в одном и том же месте вызова, среда выполнения языка также должна вставлять защитные условия в код . Чаще всего они вставляются в преамбулу вызываемого абонента, а не в место вызова, чтобы лучше использовать прогнозирование ветвей и экономия места за счет одной копии в преамбуле по сравнению с несколькими копиями на каждом месте вызова. Если сайт вызова, находящийся в «мономорфном» состоянии, обнаруживает тип, отличный от ожидаемого, он должен вернуться в «неинициализированное» состояние и снова выполнить полный динамический поиск.
Каноническая реализация [1] представляет собой загрузку регистра константы, за которой следует инструкция вызова. «Неинициализированное» состояние лучше называть «несвязанным». В регистр загружается селектор сообщений (обычно адрес какого-либо объекта), и вызывается процедура времени выполнения, которая будет искать сообщение в классе текущего получателя, используя кэш поиска метода первого уровня, указанный выше. . Затем процедура выполнения перезаписывает инструкции, изменяя инструкцию загрузки для загрузки регистра с типом текущего получателя и инструкцию вызова для вызова преамбулы целевого метода, теперь «связывая» место вызова с целевым методом. . Затем выполнение продолжается сразу после преамбулы. Последующее выполнение вызовет преамбулу напрямую. Затем преамбула определяет тип текущего получателя и сравнивает его с типом в регистре; если они согласны, получатель относится к тому же типу, и метод продолжает выполняться. Если нет, преамбула снова вызывает среду выполнения, и возможны различные стратегии, одна из которых заключается в повторном связывании места вызова для нового типа получателя.
Прирост производительности достигается за счет необходимости выполнять одно сравнение типов вместо, по крайней мере, сравнения типов и сравнения селекторов для кэша поиска методов первого уровня, а также за счет использования прямого вызова (который выиграет от предварительной выборки инструкций и конвейерной обработки). в отличие от косвенного вызова при поиске метода или отправке виртуальной таблицы .
Мономорфное встроенное кэширование
[ редактировать ]Если конкретный сайт вызова часто видит разные типы объектов, преимущества в производительности встроенного кэширования могут быть легко сведены на нет из-за накладных расходов, вызванных частыми изменениями состояния сайта вызова. Следующий пример представляет собой наихудший сценарий для мономорфного встроенного кэширования:
var values = [1, "a", 2, "b", 3, "c", 4, "d"];
for (var i in values) {
document.write(values[i].toString());
}
Опять же, метод toString вызывается для объекта, тип которого заранее неизвестен. Но что еще более важно, тип объекта меняется с каждой итерацией окружающего цикла. Таким образом, наивная реализация мономорфного встроенного кэширования будет постоянно циклически проходить через «неинициализированные» и «мономорфные» состояния. Чтобы этого не произошло, большинство реализаций мономорфного встроенного кэширования поддерживают третье состояние, часто называемое «мегаморфным» состоянием. Это состояние переходит в тот момент, когда на конкретном месте вызова обнаружено заранее определенное количество различных типов. Как только сайт вызова перейдет в «мегаморфное» состояние, он будет вести себя так же, как и в «неинициализированном» состоянии, за исключением того, что он больше никогда не перейдет в «мономорфное» состояние (некоторые реализации мономорфного встроенного кэширования изменятся « megamorphic» возвращают сайты в состояние «неинициализированное» по прошествии определенного времени или после сборки мусора выполнения полного цикла ).
Полиморфное встроенное кэширование
[ редактировать ]Чтобы лучше справляться с сайтами вызовов, которые часто видят ограниченное количество различных типов, в некоторых языковых средах выполнения используется метод, называемый полиморфным встроенным кэшированием. [2] При полиморфном встроенном кэшировании, как только сайт вызова, находящийся в «мономорфном» состоянии, видит свой второй тип, вместо того, чтобы вернуться в «неинициализированное» состояние, он переключается в новое состояние, называемое «полиморфным». «Полиморфный» сайт вызова решает, какой из ограниченного набора известных методов вызывать, в зависимости от типа, который ему представлен в данный момент. Другими словами, благодаря полиморфному встроенному кэшированию результаты поиска нескольких методов могут быть записаны на одном сайте вызова. Поскольку каждый сайт вызова в программе потенциально может видеть каждый тип в системе, обычно существует верхняя граница количества результатов поиска, записанных на каждом сайте вызова. Как только эта верхняя граница достигнута, сайты вызовов становятся «мегаморфными», и встроенное кэширование больше не выполняется.
Каноническая реализация [2] представляет собой таблицу переходов, состоящую из преамбулы, определяющей тип получателя, и серии константных сравнений и условных переходов, которые переходят к коду, следующему за преамбулой в соответствующем методе для каждого типа получателя. Таблица переходов обычно выделяется для определенного сайта вызова, когда мономорфный сайт вызова встречается с другим типом. Таблица переходов будет иметь фиксированный размер и сможет расти, добавляя наблюдения по мере появления новых типов до некоторого небольшого максимального количества случаев, например 4, 6 или 8. Как только таблица достигнет максимального размера, выполнение для нового получателя type «отвалится» от конца и войдет во время выполнения, обычно для выполнения поиска метода, начиная с кэша методов первого уровня.
Наблюдение, что мономорфные и полиморфные встроенные кэши вместе собирают информацию о типе приемника для каждого узла вызова как побочный эффект оптимизации выполнения программы. [2] привело к разработке адаптивной оптимизации в Self , где среда выполнения оптимизирует «горячие точки» в программе, используя информацию о типах во встроенных кэшах для принятия спекулятивных решений по встраиванию.
Мегаморфное встроенное кэширование
[ редактировать ]Если во время выполнения используется как мономорфное, так и полиморфное встроенное кэширование, то в устойчивом состоянии единственные несвязанные отправки будут происходить в результате отправки, выпадающей из концов полиморфного встроенного кэша. Поскольку такие отправки выполняются медленно, теперь может быть выгодно оптимизировать эти сайты. Мегаморфный встроенный кэш можно реализовать путем создания кода для выполнения поиска метода первого уровня для определенного сайта вызова. В этой схеме, как только отправка выходит за пределы полиморфного встроенного кэша, создается мегаморфный кеш, специфичный для селектора сайта вызова (или используется совместно, если он уже существует), и сайт отправки повторно связывается для его вызова. Код может быть значительно более эффективным, чем обычный зонд поиска метода первого уровня, поскольку селектор теперь является константой, что уменьшает нагрузку на регистры, код для поиска и отправки выполняется без вызова среды выполнения, а диспетчеризация может извлечь выгоду из предсказания ветвей .
Эмпирические измерения [3] показывают, что в больших программах Smalltalk около 1/3 всех сайтов отправки в активных методах остаются несвязанными, а из оставшихся 2/3 90% мономорфны, 9% полиморфны и 1% (0,9%) мегаморфны.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с Л. Питер Дойч, Аллан М. Шиффман, «Эффективная реализация системы smalltalk-80», POPL '84: Материалы 11-го симпозиума ACM SIGACT-SIGPLAN по принципам языков программирования, январь 1984 г.
- ^ Jump up to: а б с Хельцле У., Чемберс К. И Унгар Д. 1991. Оптимизация объектно-ориентированных языков с динамической типизацией и полиморфными встроенными кэшами. В материалах ЭКООП '91 Конференция. Конспекты лекций по информатике, том. 512. Шпрингер-Верлаг, Берлин.
- ^ PIC [были первые впечатления от v8] в списке рассылки Strongtalk.