Добрый день! Заинтересовала подробная информация по низкоуровневой реализации виртуальных функций в разных языках программирования и в различных компиляторах. Т.е. реализации виртуальных таблиц (или, если есть какие-то альтернативные механизмы, тоже будет интересно узнать).

В целом ясно, что виртуальная таблица — это некая таблица соответствия между "индексом функции" и указателем на функцию, где "индекс функции" — числовой идентификатор функции в рамках иерархии наследования, генерируемый компилятором. Но вот как это реализовано на практике? Используются ли там просто массивы и порядковые номера функций, или какие-то хеш-таблицы, или что-то еще?

Здравствуйте, x-code, Вы писали:

XC>Добрый день! Заинтересовала подробная информация по низкоуровневой реализации виртуальных функций ... Но вот как это реализовано на практике? ..., или что-то еще?

Скажу за Delphi. Там используются три способа задания виртуальных функций и за этим стоят два механизма реализации.
Какой способ применяется, задаётся разработчиком класса.

Первый способ — с использованием ключевого слова virtual. В реализации наиболее простой и быстрый способ.
Каждому виртуальному методу компилятор присваивает индекс, (для переопреленного в наследнике — тот же , что и у предка)
для каждого класса строится массив указателей на виртуальные функции(VMT), у каждого объекта есть ссылка на этот массив,
поиск метода осуществляется выборкой из этого массива по индексу.
Накладные расходы на вызов — два лишних считывания из памяти.
Накладные расходы по памяти — для каждого класса нужен массив, содержащий указатели на все виртуальные методы,
даже если они не переопределяются в наследниках.

Второй способ — с использованием ключевого слова dynamic. Компилятор также присваивает индекс такому виртуальному методу,
но в этом случае в массив(DMT) попадают пары — (Индекс метода — Указатель на метод).
При вызове осуществляется поиск индекса, если находится- вызывается метод, если не находится- переходят на таблицу DMT предка.
Но в таблице DMT для класса находятся только методы, которые переопределены или созданы в данном классе.
Имеет смысл использовать в случае большого количества виртуальных методов, которые редко будут переопределятся в классах — наследниках.

И третий способ применяется для методов, реализующих реакции на Windows-messages.
По реализации — то же, что и dynamic, но индекс для метода задаётся явно.

Здравствуйте, x-code, Вы писали:

XC>Добрый день! Заинтересовала подробная информация по низкоуровневой реализации виртуальных функций в разных языках программирования и в различных компиляторах. Т.е. реализации виртуальных таблиц (или, если есть какие-то альтернативные механизмы, тоже будет интересно узнать).

XC>В целом ясно, что виртуальная таблица — это некая таблица соответствия между "индексом функции" и указателем на функцию, где "индекс функции" — числовой идентификатор функции в рамках иерархии наследования, генерируемый компилятором. Но вот как это реализовано на практике? Используются ли там просто массивы и порядковые номера функций, или какие-то хеш-таблицы, или что-то еще?

ЕМНИП выглядит это примерно так:

class Foo;
struct Foo_vtable;

typedef void (Foo::*Foo_vfunc0)(int);
typedef bool (Foo::*Foo_vfunc1)();

class Foo
{
  Foo_vtable* vtable;
  // обычные члены класса
  ...
  virtual void VFunc0(int);
  virtual bool VFunc1();

  Foo();
};

struct Foo_vtable
{
  union
  {
    struct
    {
      Foo_vfunc0 vfunc0;
      Foo_vfunc1 vfunc1;
    };
    void** funcptrs;
  };
};

static Foo_vtable Foo_vtable_instance = { &Foo::VFunc0, &Foo::VFunc1 };

Foo::Foo()
  : vtable(Foo_vtable_instance)
{ }

// вызов собсно Foo::VFunc1
Foo foo;
bool foobool = (foo->*(foo.vtable->vfunc1))();

Здравствуйте, Мишень-сан, Вы писали:

XC>>В целом ясно, что виртуальная таблица — это некая таблица соответствия между "индексом функции" и указателем на функцию, где "индекс функции" — числовой идентификатор функции в рамках иерархии наследования, генерируемый компилятором. Но вот как это реализовано на практике? Используются ли там просто массивы и порядковые номера функций, или какие-то хеш-таблицы, или что-то еще?

МС>ЕМНИП выглядит это примерно так:

Как в таком сценарии будет работать множественное наследование?

Здравствуйте, x-code, Вы писали:

XC>Добрый день! Заинтересовала подробная информация по низкоуровневой реализации виртуальных функций в разных языках программирования и в различных компиляторах. Т.е. реализации виртуальных таблиц (или, если есть какие-то альтернативные механизмы, тоже будет интересно узнать).

XC>В целом ясно, что виртуальная таблица — это некая таблица соответствия между "индексом функции" и указателем на функцию, где "индекс функции" — числовой идентификатор функции в рамках иерархии наследования, генерируемый компилятором. Но вот как это реализовано на практике? Используются ли там просто массивы и порядковые номера функций, или какие-то хеш-таблицы, или что-то еще?

И что-то еще http://rsdn.ru/forum/philosophy/1951886.aspx

Автор: Andrei N.Sobchuck
Дата: 13.06.06

Здравствуйте, x-code, Вы писали:

XC>Добрый день! Заинтересовала подробная информация по низкоуровневой реализации виртуальных функций в разных языках программирования и в различных компиляторах. Т.е. реализации виртуальных таблиц (или, если есть какие-то альтернативные механизмы, тоже будет интересно узнать).

Для C#, от Липперта:
Implementing the virtual method pattern in C#, Part One и далее по тегу.

Здравствуйте, Lloyd, Вы писали:

L>Здравствуйте, Мишень-сан, Вы писали:

XC>>>В целом ясно, что виртуальная таблица — это некая таблица соответствия между "индексом функции" и указателем на функцию, где "индекс функции" — числовой идентификатор функции в рамках иерархии наследования, генерируемый компилятором. Но вот как это реализовано на практике? Используются ли там просто массивы и порядковые номера функций, или какие-то хеш-таблицы, или что-то еще?

МС>>ЕМНИП выглядит это примерно так:

L>Как в таком сценарии будет работать множественное наследование?

Я ж примерно описал. А то получается — сыграл на гармошке, а Вы — "А как в таком сценарии будет звучать симфония Рахманинова?"

Здравствуйте, Мишень-сан, Вы писали:

L>>Как в таком сценарии будет работать множественное наследование?

МС>Я ж примерно описал.

А я примерно указал не узкие места такого подхода.

Здравствуйте, x-code, Вы писали:

XC>Добрый день! Заинтересовала подробная информация по низкоуровневой реализации виртуальных функций в разных языках программирования и в различных компиляторах. Т.е. реализации виртуальных таблиц (или, если есть какие-то альтернативные механизмы, тоже будет интересно узнать).

В GCC есть прекрасная опция -fdump-class-hierarchy

{code}
void do_something(void);

class X
{
public: virtual void foo() = 0;
};

class Y : public X
{
public: void foo() {
do_something();
}
};
{code}

Получаем:

{noformat}
Vtable for X
X::_ZTV1X: 3u entries
0 (int (*)(...))0
8 (int (*)(...))(& _ZTI1X)
16 __cxa_pure_virtual

Class X
size=8 align=8
base size=8 base align=8
X (0x7f53be4daaf0) 0 nearly-empty
vptr=((& X::_ZTV1X) + 16u)

Vtable for Y
Y::_ZTV1Y: 3u entries
0 (int (*)(...))0
8 (int (*)(...))(& _ZTI1Y)
16 Y::foo

Class Y
size=8 align=8
base size=8 base align=8
Y (0x7f53be4dabd0) 0 nearly-empty
vptr=((& Y::_ZTV1Y) + 16u)
X (0x7f53be4dac40) 0 nearly-empty
primary-for Y (0x7f53be4dabd0)
{noformat}

Таким же образом можно копать и более сложные случаи.