Встроенное кэширование — это метод оптимизации , используемый некоторыми языковыми средами выполнения и впервые разработанный для Smalltalk . [1] Цель встроенного кэширования — ускорить связывание методов во время выполнения путем запоминания результатов предыдущего поиска метода непосредственно в месте вызова . Встроенное кэширование особенно полезно для динамически типизированных языков, где большинство, если не все, связывание методов происходит во время выполнения и где виртуальные таблицы методов часто не могут быть использованы.
Следующая функция ECMAScript получает объект, вызывает его метод toString и отображает результаты на странице, в которую встроен скрипт.
функция дамп ( obj ) { документ . запись ( obj . toString ()); } Поскольку тип объекта не указан и из-за потенциальной перегрузки методов невозможно заранее решить, какая конкретная реализация метода toString будет вызвана. Вместо этого динамический поиск должен быть выполнен во время выполнения. В средах выполнения языка, которые не используют какую-либо форму кэширования, этот поиск выполняется каждый раз при вызове метода. Поскольку методы могут быть определены на несколько шагов ниже по цепочке наследования , динамический поиск может быть дорогостоящей операцией.
Для достижения лучшей производительности многие среды выполнения языка используют некоторую форму не-встроенного кэширования, где результаты ограниченного числа поисков методов сохраняются в ассоциативной структуре данных. Это может значительно повысить производительность, при условии, что выполняемые программы являются "дружественными к кэшу" (т. е. существует ограниченный набор методов, которые вызываются часто). Эта структура данных обычно называется кэшем поиска методов первого уровня . [1]
Концепция встроенного кэширования основана на эмпирическом наблюдении, что объекты, которые встречаются в определенном месте вызова, часто имеют один и тот же тип. В таких случаях производительность можно значительно повысить, сохраняя результат поиска метода «встроенным»; т. е. непосредственно в месте вызова. Для упрощения этого процесса местам вызова назначаются разные состояния. Изначально место вызова считается «неинициализированным». Как только среда выполнения языка достигает определенного неинициализированного места вызова, она выполняет динамический поиск, сохраняет результат в месте вызова и изменяет свое состояние на «мономорфное». Если среда выполнения языка снова достигает того же места вызова, она извлекает из него вызываемый объект и вызывает его напрямую, не выполняя дополнительных поисков. Чтобы учесть возможность того, что объекты разных типов могут встречаться в одном и том же месте вызова, среда выполнения языка также должна вставлять в код защитные условия . Чаще всего они вставляются в преамбулу вызываемого, а не в место вызова, чтобы лучше использовать предсказание ветвлений и сэкономить место из-за одной копии в преамбуле по сравнению с несколькими копиями в каждом месте вызова. Если место вызова, находящееся в состоянии «мономорфное», встречает тип, отличный от ожидаемого, оно должно вернуться в состояние «неинициализированное» и снова выполнить полный динамический поиск.
Каноническая реализация [1] представляет собой загрузку регистра константы, за которой следует инструкция вызова. Состояние «неинициализированное» лучше называть «несвязанным». Регистр загружается селектором сообщений (обычно адресом некоторого объекта), а вызов выполняется в подпрограмме времени выполнения, которая будет искать сообщение в классе текущего получателя, используя кэш поиска методов первого уровня выше. Затем подпрограмма времени выполнения переписывает инструкции, изменяя инструкцию загрузки для загрузки регистра с типом текущего получателя, а инструкцию вызова для вызова преамбулы целевого метода, теперь «связывая» место вызова с целевым методом. Затем выполнение продолжается сразу после преамбулы. Последующее выполнение вызовет преамбулу напрямую. Затем преамбула выводит тип текущего получателя и сравнивает его с типом в регистре; если они совпадают, получатель имеет тот же тип, и метод продолжает выполняться. Если нет, преамбула снова вызывает среду выполнения, и возможны различные стратегии, одна из которых заключается в повторном связывании места вызова с новым типом приемника.
Повышение производительности достигается за счет необходимости выполнять одно сравнение типов вместо как минимум сравнения типов и сравнения селекторов для кэша поиска методов первого уровня, а также за счет использования прямого вызова (который выиграет от предварительной выборки инструкций и конвейеризации) вместо косвенного вызова при поиске методов или диспетчеризации vtable .
Если конкретный сайт вызова часто видит различные типы объектов, преимущества производительности встроенного кэширования могут быть легко сведены на нет издержками, вызванными частыми изменениями состояния сайта вызова. Следующий пример представляет собой наихудший сценарий для мономорфного встроенного кэширования:
var значения = [ 1 , "a" , 2 , "b" , 3 , "c" , 4 , "d" ]; for ( var i in значения ) { document . write ( значения [ i ]. toString () ); } Опять же, метод toString вызывается для объекта, тип которого заранее неизвестен. Но что еще важнее, тип объекта меняется с каждой итерацией окружающего цикла. Поэтому наивная реализация мономорфного встроенного кэширования будет постоянно циклически проходить через состояния «неинициализированное» и «мономорфное». Чтобы этого не произошло, большинство реализаций мономорфного встроенного кэширования поддерживают третье состояние, часто называемое «мегаморфным». Это состояние достигается, когда конкретный сайт вызова видит предопределенное количество различных типов. Как только сайт вызова переходит в состояние «мегаморфное», он будет вести себя так же, как и в состоянии «неинициализированное», за исключением того, что он больше никогда не перейдет в состояние «мономорфное» (некоторые реализации мономорфного встроенного кэширования возвращают «мегаморфные» сайты вызова в состояние «неинициализированное» по истечении определенного времени или после выполнения полного цикла сборки мусора ).
Чтобы лучше справляться с местами вызова, которые часто видят ограниченное количество различных типов, некоторые среды выполнения языка используют технику, называемую полиморфным встроенным кэшированием. [2] При полиморфном встроенном кэшировании, как только место вызова, находящееся в своем «мономорфном» состоянии, видит свой второй тип, вместо того, чтобы вернуться в «неинициализированное» состояние, оно переключается в новое состояние, называемое «полиморфным». «Полиморфный» место вызова решает, какой из ограниченного набора известных методов вызвать, на основе типа, который ему в данный момент представлен. Другими словами, при полиморфном встроенном кэшировании результаты поиска нескольких методов могут быть записаны в одном и том же месте вызова. Поскольку каждое место вызова в программе потенциально может видеть каждый тип в системе, обычно существует верхняя граница того, сколько результатов поиска записано в каждом месте вызова. Как только эта верхняя граница достигнута, места вызова становятся «мегаморфными», и больше не выполняется встроенное кэширование.
Каноническая реализация [2] представляет собой таблицу переходов, которая состоит из преамбулы, которая выводит тип приемника, и серии сравнений констант и условных переходов, которые переходят к коду, следующему за преамбулой в соответствующем методе для каждого типа приемника. Таблица переходов обычно выделяется для конкретного места вызова, когда мономорфное место вызова встречает другой тип. Таблица переходов будет иметь фиксированный размер и сможет расти, добавляя случаи по мере того, как встречаются новые типы, до некоторого небольшого максимального числа случаев, например 4, 6 или 8. Как только она достигнет своего максимального размера, выполнение для нового типа приемника «отвалится» от конца и войдет во время выполнения, как правило, для выполнения поиска метода, начиная с кэша методов первого уровня.
Наблюдение за тем, что мономорфные и полиморфные встроенные кэши собирают информацию о типе получателя для каждого места вызова в качестве побочного эффекта оптимизации выполнения программы [2], привело к разработке адаптивной оптимизации в Self , где среда выполнения оптимизирует «горячие точки» в программе, используя информацию о типе во встроенных кэшах для принятия спекулятивных решений о встраивании.
Если среда выполнения использует как мономорфное, так и полиморфное встроенное кэширование, то в устойчивом состоянии единственными несвязанными отправками будут те, которые происходят из отправок, падающих с концов полиморфных встроенных кэшей. Поскольку такие отправки медленные, теперь может быть выгодно оптимизировать эти сайты. Мегаморфный встроенный кэш может быть реализован путем создания кода для выполнения поиска метода первого уровня для определенного места вызова. В этой схеме, как только отправка падает с конца полиморфного встроенного кэша, создается мегаморфный кэш, специфичный для селектора места вызова (или общий, если он уже существует), и место отправки повторно связывается для его вызова. Код может быть значительно более эффективным, чем обычный зонд поиска метода первого уровня, поскольку селектор теперь является константой, что снижает давление на регистр, код для поиска и отправки выполняется без вызова в среду выполнения, и отправка может выиграть от прогнозирования ветвлений .
Эмпирические измерения [3] показывают, что в больших программах Smalltalk около 1/3 всех сайтов отправки в активных методах остаются несвязанными, а из оставшихся 2/3 90% являются мономорфными, 9% — полиморфными и 1% (0,9%) — мегаморфными.