Альтернативы vtable

[gegmopo4]

Возник тут теоретический вопрос, какие возможны реализации полиморфизма в C++, кроме таблицы виртуальных методов. В стандарте о vtable нет ни слова, но это самый очевидный и распространённый способ (по крайней мере я не знаю компиляторов, где иначе), к тому же, обладающий разумным балансом между потреблением памяти и скоростью. Интересно, могут ли быть варианты эффективнее?

Самый простой способ — указатели на методы внедрены прямо в каждый объект. Так делают ООП на C и в языках, допускающих переопределение метода для отдельного объекта. Для модели C++ последняя возможность излишня. Плюс — на один уровень косвенности меньше при вызове, минус — потребление памяти пропорционально количеству объектов и методов, больше время инициализации объекта. Размер многих объектов может вырасти в разы.

Но если в какой-то иерархии существует только один виртуальный метод и не используется RTTI, то оверхед исчезает и этот способ становится безусловно выгодным. Правда, это очень редкий случай, ведь если мы создаём обработчик и передаём владение, то нужен по крайней мере ещё и виртуальный деструктор. А если его нет, то почему бы не воспользоваться обычным указателем на функцию?

Можно уменьшить уровень косвенности, если размещать в таблице не указатели на методы, а сами методы. Такой себе «шитый код». Размер ячеек таблицы подбирается таким, чтобы в них влезали большинство небольших функций, для которых такое ускорение имеет смысл, а для больших будет помещаться начало и команда перехода на продолжение. Размер таблиц вырастет на порядок, но, в отличие от предыдущего случая, расход памяти не зависит от количества объектов. А эффект тот же.

Таблицы можно «развернуть» — создавать таблицы не для классов, а для методов. Тогда можно использовать разные типы и размеры таблиц для разных методов.

Можно избавиться от указателя на таблицу виртуальных методов, если размещать объекты разных классов в разных областях пространства. В принципе, это возможно уже на сегодняшних 64-битных компьютерах — благодаря тому, что 64-битное адресное пространство слишком велико и память виртуальна. Класс будем кодировать несколькими старшими битами адреса, объекты одного класса будут размещаться в непрерывной области памяти, ростом по мере потребности займётся железо и ОС. Оверхед порядка размера страницы на класс. Кстати, заодно получим простой и эффективный менеджер памяти — в каждой области объекты одинакового размера.

Некоторые проблемы представляют автоматические переменные, но их необязательно размещать в стеке, в стеке будут только указатели на них. Впрочем, некоторые классы можно реализовать классически, с vtable. И не уверен, что это вполне совместимо со стандартом, в частности, с пользовательскими операторами new/delete. Возможно, это будет не совсем совместимый диалект, расширение для особых случаев. Во всяком случае, этот приём более подходит к Java и C#.