Идея языка программирования: Избегание поиска в vtable
Я уже некоторое время играю с идеей языка программирования: по сути, это будет C ++ и Java-подобный по синтаксису, предназначенный для системного программирования (или действительно любого программирования, требующего высокой производительности), но с, по моему мнению , более приятный синтаксис, чем C ++. Я думал о том, как я буду обрабатывать виртуальные методы в иерархических структурах классов (мой язык не будет включать множественное наследование), и о способах избежать поиска в vtable. Мой вопрос двоякий:
- Насколько я понимаю, причина того, что поиск в vtable так сильно сказывается на производительности (по крайней мере, в критических по времени сценариях, таких как разработка игр), заключается в том, что он требует указателя vtable на объектах, а этот vtable обычно является пропуском кэша. Это правильно, или я пропускаю какую-то часть проблемы?
- Моя идея частичного решения заключается в следующем: если компилятор может полностью определить тип объекта (т. Е. Он не может быть типом, производным от того типа, который, как он думает), и этот объект передается функции в качестве аргумента, тип которого суперкласс типа объекта, тогда местоположение виртуального метода, вызываемого в функции, может быть передано как своего рода «скрытый» аргумент, который добавляется во время компиляции. Возможно, пример поможет:
Рассмотрим следующий псевдокод для иерархии классов:
class Animal {
public void talk() { /* Generic animal noise... */ }
// ...
}
class Dog extends Animal {
public void talk() { /* Override of Animal::talk(). */ }
// ...
}
void main() {
Dog d = new Dog();
doSomethingWithAnimal(d);
}
void doSomethingWithAnimal(Animal a) {
// ...
a.talk();
// ....
}
Имейте в виду, что это псевдокод, а не C ++, Java или что-то подобное. Также предположим, что аргумент Animal неявно передается по ссылке, а не по значению. Потому что компилятор может видеть это d определенно типа Dog, это может перевести doSomethingWithAnimal определение в нечто вроде этого:
void doSomethingWithAnimal(Animal a, methodptr talk = NULL) {
// ...
if ( talk != NULL ) {
talk(a);
} else {
a.talk();
}
// ...
}
затем main будет выглядеть переводится компилятором что-то вроде этого:
void main() {
Dog d = new Dog();
doSomethingWithAnimal(d, Dog::talk);
}
Очевидно, что это не полностью устранит необходимость в vtable, и, вероятно, все еще нужно предусмотреть случаи, когда точный тип объектов не может быть определен, но что вы думаете об этом как об оптимизации производительности? Я планирую использовать регистры для передачи аргументов всякий раз, когда это возможно, и даже если аргументы должны были перетекать в стек, более вероятно, что аргумент methodptr в стеке будет попадать в кеш, чем значения vtable, верно? Любые мысли высоко ценится.
Решение
Re Q1: На самом деле использование кэша — это только одна часть «проблемы» с виртуальными вызовами. Весь смысл virtual Функции и позднее связывание в целом состоят в том, что сайт вызова может вызывать любую реализацию без изменений. Это требует некоторой косвенности:
- Непрямость подразумевает использование пространства и / или времени для устранения косвенности.
- Независимо от того, как вы делаете косвенное обращение, и косвенный вызов может быть таким же быстрым, как статический вызов, если у ЦПУ есть хороший предсказатель ветвления а также сайт вызова является мономорфным (то есть, когда-либо вызывается только одна реализация). И я даже не уверен, является ли предсказанная ветвь такой же быстрой, как статическая ветвь для всех разработчиков аппаратного обеспечения.
- Незнание вызываемой функции во время компиляции также препятствует оптимизации, основанной на знании вызываемой функции (встраивание, но также движение инвариантного кода цикла и, возможно, многое другое).
Ваш подход не меняет этого и, следовательно, оставляет большинство проблем с производительностью на месте: он по-прежнему тратит некоторое время и пространство (только на дополнительные аргументы и ветви, а не на поиск в vtable), он не допускает встраивание или другие оптимизации, и это не удаляет косвенные вызовы.
Re 2: Это своего рода межпроцедурное вращение при девиртуализации, которое компиляторы C ++ уже делают в некоторой степени (локально, с ограничениями, описанными @ us2012 в комментариях). Есть несколько «незначительных» проблем с этим, но это может стоить того если применяется выборочно. В противном случае вы генерируете гораздо больше кода, передавая много из дополнительных аргументов, сделайте много из дополнительных веток, и только получить очень мало или даже чистый убыток.
Я предполагаю, что главная проблема заключается в том, что это не решает большинство проблем производительности, описанных выше. Генерация специализированных функций (а не одного общего тела) для подклассов и других вариаций той же темы, может помочь с этим. Но это порождает дополнительный код, который должен оправдывать себя приростом производительности, и общее мнение состоит в том, что такие агрессивные оптимизации не стоят этого для большинства кода даже в программах, критичных к производительности.
В частности, накладные расходы на виртуальные вызовы имеют значение только в тестах той же функции, или если вы уже оптимизировали вечно любящий ад из всего остального и вам потребуется огромное количество крошечных косвенных вызовов (пример из разработки игры: несколько виртуальных методов вызовов на геометрический объект для рисования или отбраковки усеченного конуса). В большинстве кода виртуальные вызовы не имеют значения или, по крайней мере, недостаточны для оправдания дальнейших попыток оптимизации. Кроме того, это относится только к компиляторам AOT, поскольку JIT-компиляторы имеют другие способы решения этих проблем. Посмотрите полиморфные встроенные кэши и обратите внимание, что трассировка JIT-компиляторов может быть тривиально встроенной все звонки, виртуальные или нет.
Итак, vtables — это быстрый и общий способ реализации виртуальных функций (если они Можно использоваться, что имеет место здесь). Маловероятно, что вы сможете значительно улучшить их, не говоря уже о том, чтобы заметить улучшение, за исключением, возможно, некоторых редких случаев. Однако, если вы хотите попробовать это, вы можете попробовать написать проход LLVM, который делает что-то вроде этого (хотя вам придется работать на более низком уровне абстракции).
Другие решения
Других решений пока нет …