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

7

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

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

<code>class Base {
     private:
        int m;
     public:
        virtual metha();
};
</code>

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

<code>struct Base {
    void (**vtable)();
    int m;
}
</code>

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

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

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

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

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

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

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

Член m, вероятно, все еще будет выровнен по границе DWORD, так что вы ничего не получите. Henrik
Проблема с этой схемой, вероятно, будет связана с выравниванием. Здесь структура Base в вашем втором примере не будет (обычно) занимать 5 байтов, экономя 3 байта на объект. В любом случае m, вероятно, будет выровнен на границе 4 байта, поэтому у вас будет 3 байта потерянного пространства. Tom Quarendon
+1 за интересный вопрос Tom Quarendon
Я не знаю ни одного компилятора, который бы делал что-то подобное. Если вы работаете во встроенной системе, в которой вам нужно выжать каждый байт, вам будет лучше написать саму отправку, чтобы выexact контроль. В любой другой ситуации просто позвольте компилятору делать то, что он хочет. На современных машинах с несколькими гигабайтами памяти лишние 160 Кбайт ничего не значат. Mark B
Я думаю, что этот метод реализации виртуальных таблиц является почти универсальным. Я, конечно, никогда не сталкивался с другим методом или какими-либо опциями в GCC или Visual C ++, которые бы управляли его реализацией. Tom Quarendon

Ваш Ответ

4   ответа
3

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

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded ManiP
Error: User Rate Limit Exceeded
3

Yes, a smaller value could be used to represent the class, but some processors require data to be aligned so that saving in space may be lost by the requirement to align data values to e.g. 4 byte boundaries. Further, the class-id must be in a well defined place for all members of a polymorphic inheritance tree, so it is likely to be ahead of other date, so alignment problems can't be avoided.

The cost of storing the pointer has been moved to the code, where every use of a polymorphic function requires code to translate the class-id to either a vtable pointer, or some equivalent data structure. So it isn't for free. Clearly the cost trade-off depends on the volume of code vs numer of objects.

If objects are allocated from the heap, there is usually space wasted in orer to ensure objects are alogned to the worst boundary, so even if there is a small amount of code, and a large number of polymorphic objects, the memory management overhead migh be significantly bigger than the difference between a pointer and a char.

In order to allow programs to be independently compiled, the number of classes in the whole program, and hence the size of the class-id must be known at compile time, otherwise code can't be compiled to access it. This would be a significant overhead. It is simpler to fix it for the worst case, and simplify compilation and linking.

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

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

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

Error: User Rate Limit ExceededvtableError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceededcall [vtable_section_base + rax]Error: User Rate Limit Exceededcall [rax]Error: User Rate Limit ExceededHow do objects work in x86 at the assembly level?Error: User Rate Limit Exceededvtable_section_baseError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded ManiP
3

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

Затем виртуальность реализуетсяswitch наenumи соответствующее приведение перед вызовом метода. Снова,closed,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 например). Можно реально обеспечитьboth интерфейсы (и мосты):

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

Error: User Rate Limit Exceeded ManiP
Error: User Rate Limit ExceededcodebaseError: User Rate Limit Exceeded
2

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

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

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

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

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

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

Error: User Rate Limit Exceeded ManiP
Error: User Rate Limit Exceeded
The end result would be that objects of the class would occupy precisely the same amount of storage as if we used a pointer.Error: User Rate Limit Exceeded

Похожие вопросы