Альтернативные схемы для реализации вптр?

Question

Этот вопрос не о самом языке C++ (т.е. не о стандарте), а о том, как вызвать компилятор для реализации альтернативных схем для виртуальной функции.

Общая схема реализации виртуальных функций заключается в использовании указателя на таблицу указателей.

class Base {
     private:
        int m;
     public:
        virtual metha();
};

эквивалентно, скажем, C будет что-то вроде

struct Base {
    void (**vtable)();
    int m;
}

первый член обычно является указателем на список виртуальных функций и т. д. (часть области в памяти, которую приложение не может контролировать). И в большинстве случаев это случается с размером указателя перед рассмотрением членов и т. Д. Таким образом, в 32-битной схеме адресации около 4 байтов и т. Д. Если вы создали список из 40 КБ полиморфных объектов в своих приложениях, это около 40 КБ. 4 байта = 160 Кбайт перед любыми переменными-членами и т. Д. Я также знаю, что это самая быстрая и распространенная реализация среди компиляций C++.

Я знаю, что это осложняется множественным наследованием (особенно с виртуальными классами в них, например, с алмазной структурой и т.д.).

Альтернативный способ сделать то же самое - использовать первую переменную в качестве идентификатора индекса для таблицы vptrs(эквивалентно в C, как показано ниже).

struct Base {
    char    classid;     // the classid here is an index into an array of vtables
    int     m;
}

Если общее число классов в приложении меньше 255(включая все возможные экземпляры шаблонов и т. Д.), То символ достаточно хорош для хранения индекса, тем самым уменьшая размер всех полиморфных классов в приложении (я исключаю проблемы с выравниванием, так далее).

Мои вопросы: есть ли в GNU C++, LLVM или любом другом компиляторе переключатель для этого? или уменьшить размер полиморфных объектов?

Изменить: я понимаю о проблемах выравнивания, указанных. Также еще один момент: если это было в 64-битной системе (при условии, что 64-битный vptr), а каждый член полиморфного объекта стоит около 8 байт, тогда стоимость vptr составляет 50% памяти. Это в основном относится к небольшим полиморфикам, созданным в массе, поэтому мне интересно, возможна ли эта схема хотя бы для конкретных виртуальных объектов, если не для всего приложения.

Answer 1

Ваше предложение интересное, но оно не будет работать, если исполняемый файл состоит из нескольких модулей, передавая объекты между ними. Если они скомпилированы отдельно (скажем, DLL), если один модуль создает объект и передает его другому, а другой вызывает виртуальный метод - как он узнает, какую таблицу classid относится к? Вы не сможете добавить еще moduleid потому что два модуля могут не знать друг о друге при компиляции. Так что, если вы не используете указатели, я думаю, что это тупик...

Answer 2

Нет, такого переключателя нет.

Кодовая база LLVM/Clang избегает виртуальных таблиц в классах, которые выделяются десятками тысяч: это хорошо работает в закрытой иерархии, потому что один enum может перечислить все возможные классы, а затем каждый класс связан со значением enum, Закрытый, очевидно, из-за enum,

Затем виртуальность реализуется switch на enumи соответствующее приведение перед вызовом метода. Еще раз закрыто. switch должен быть изменен для каждого нового класса.

---

Первая альтернатива: внешний впоинтер.

Если вы попадаете в ситуацию, когда налог на vpointer уплачивается слишком часто, то есть большинство объектов известного типа. Тогда вы можете вывести это из себя.

class Interface {
public:
  virtual ~Interface() {}

  virtual Interface* clone() const = 0; // might be worth it

  virtual void updateCount(int) = 0;

protected:
  Interface(Interface const&) {}
  Interface& operator=(Interface const&) { return *this; }
};

template <typename T>
class InterfaceBridge: public Interface {
public:
  InterfaceBridge(T& t): t(t) {}

  virtual InterfaceBridge* clone() const { return new InterfaceBridge(*this); }

  virtual void updateCount(int i) { t.updateCount(i); }

private:
  T& t; // value or reference ? Choose...
};

template <typename T>
InterfaceBridge<T> interface(T& t) { return InterfaceBridge<T>(t); }

Затем, представляя простой класс:

class Counter {
public:
  int getCount() const { return c; }
  void updateCount(int i) { c = i; }
private:
  int c;
};

Вы можете хранить объекты в массиве:

static Counter array[5];

assert(sizeof(array) == sizeof(int)*5); // no v-pointer

И все же используйте их с полиморфными функциями:

void five(Interface& i) { i.updateCount(5); }

InterfaceBridge<Counter> ib(array[3]); // create *one* v-pointer
five(ib);

assert(array[3].getCount() == 5);

Значение по отношению к эталону на самом деле является расчетным напряжением. В общем, если вам нужно clone вам нужно хранить по значению, и вам нужно клонировать, когда вы храните по базовому классу (boost::ptr_vector например). Можно на самом деле предоставить оба интерфейса (и мосты):

Interface <--- ClonableInterface
  |                 |
InterfaceB     ClonableInterfaceB

Это просто дополнительный набор текста.

---

Другое решение, гораздо более сложное.

Переключатель реализуется таблицей переходов. Такая таблица может быть идеально создана во время выполнения, в std::vector например:

class Base {
public:
  ~Base() { VTables()[vpointer].dispose(*this); }

  void updateCount(int i) {
    VTables()[vpointer].updateCount(*this, i);
  }

protected:
  struct VTable {
    typedef void (*Dispose)(Base&);
    typedef void (*UpdateCount)(Base&, int);

    Dispose dispose;
    UpdateCount updateCount;
  };

  static void NoDispose(Base&) {}

  static unsigned RegisterTable(VTable t) {
    std::vector<VTable>& v = VTables();
    v.push_back(t);
    return v.size() - 1;
  }

  explicit Base(unsigned id): vpointer(id) {
    assert(id < VTables.size());
  }

private:
  // Implement in .cpp or pay the cost of weak symbols.
  static std::vector<VTable> VTables() { static std::vector<VTable> VT; return VT; }

  unsigned vpointer;
};

А потом, Derived учебный класс:

class Derived: public Base {
public:
  Derived(): Base(GetID()) {}

private:
  static void UpdateCount(Base& b, int i) {
    static_cast<Derived&>(b).count = i;
  }

  static unsigned GetID() {
    static unsigned ID = RegisterTable(VTable({&NoDispose, &UpdateCount}));
    return ID;
  }

  unsigned count;
};

Что ж, теперь вы поймете, как здорово, что компилятор делает это за вас, даже ценой некоторых накладных расходов.

Ох, и из-за выравнивания, как только Derived класс вводит указатель, есть риск, что между байтами заполнения 4 Base и следующий атрибут. Вы можете использовать их, тщательно выбирая первые несколько атрибутов в Derived чтобы избежать заполнения...

Answer 3

Пара наблюдений:

1. Да, для представления класса можно использовать меньшее значение, но некоторые процессоры требуют, чтобы данные были выровнены так, чтобы экономия в пространстве могла быть потеряна из-за необходимости выравнивать значения данных, например, по 4-байтовым границам. Кроме того, идентификатор класса должен находиться в четко определенном месте для всех членов дерева полиморфного наследования, поэтому он, вероятно, будет опережать другую дату, поэтому проблем с выравниванием избежать не удастся.

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

3. Если объекты выделяются из кучи, обычно пространство тратится впустую или выше, чтобы гарантировать выделение объектов к наихудшей границе, поэтому даже при небольшом объеме кода и большом количестве полиморфных объектов накладные расходы на управление памятью могут быть значительно больше, чем разница между указателем и символом.

4. Чтобы позволить программам быть независимо скомпилированными, количество классов во всей программе и, следовательно, размер идентификатора класса должны быть известны во время компиляции, в противном случае код не может быть скомпилирован для доступа к нему. Это было бы значительным накладным расходом. Проще исправить это в худшем случае и упростить компиляцию и компоновку.

Пожалуйста, не позволяйте мне останавливать ваши попытки, но есть гораздо больше проблем, которые нужно решить, используя любую технику, которая может использовать идентификатор переменного размера для получения адреса функции.

Я настоятельно рекомендую вам взглянуть на колу Яна Пьюмарта и на Википедию Колу

На самом деле он использует другой подход и использует указатель более гибким способом для создания наследования, на основе прототипа или любого другого механизма, который требуется разработчику.

Answer 4

Короткий ответ: нет, я не знаю ни одного переключателя, который бы делал это с любым обычным компилятором C++.

Более длинный ответ заключается в том, что для этого вам понадобится встроить большую часть интеллекта в компоновщик, чтобы он мог координировать распределение идентификаторов по всем объектным файлам, связанным друг с другом.

Я также хотел бы отметить, что это не принесет ничего хорошего. По крайней мере, в типичном случае вы хотите, чтобы каждый элемент в структуре / классе имел "естественную" границу, что означает, что его начальный адрес кратен его размеру. Используя ваш пример класса, содержащего один int, компилятор выделит один байт для индекса vtable, за которым сразу следует три байта заполнения, так что следующий int приземлится по адресу, кратному четырем. Конечным результатом будет то, что объекты класса будут занимать точно такой же объем памяти, как если бы мы использовали указатель.

Я бы добавил, что это тоже не надуманное исключение. В течение многих лет стандартным советом по минимизации заполнения, вставляемого в структуры / классы, было размещение элементов, которые, как ожидается, будут самыми большими в начале, и продвижение к наименьшим. Это означает, что в большинстве кода вы получите те же три байта заполнения перед первым явно определенным членом структуры.

Чтобы извлечь из этого пользу, вы должны знать об этом и иметь структуру, содержащую (например) три байта данных, которые вы можете перемещать туда, куда хотите. Затем вы бы переместили эти элементы в качестве первых элементов, явно определенных в структуре. К сожалению, это также будет означать, что если вы отключите этот переключатель, чтобы получить указатель vtable, вы получите компилятор, добавляющий заполнение, которое в противном случае могло бы быть ненужным.

Подводя итог: это не реализовано, и если бы это было не так, как правило, многого добиться.