LINUX.ORG.RU

Type erasure в C++

 , ,


1

2

Допустим, у нас есть простой класс с виртуальным методом:

class A {
public:
    virtual ~A() = default;
    virtual void f(void *ptr) = 0;
};

Подразумевается, что разные реализации A принимают в методе f указатели на разные объекты и как-то их обрабатывают. То есть, типичная реализация метода f такая:

void B::f(void *ptr) {
    auto data = (SomeType*) ptr; // SomeType разный для разных наследников A
    //делаем что-нибудь с data
}

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

И я делаю что-то вроде такого:

template<typename T> class ATemplate: public A {
protected:
    virtual void realF(T *t) = 0;

public:
    void f(void *ptr) final {
        realF(static_cast<T*>(ptr));
    }

};

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

Однако если посмотреть на результат компиляции, то теперь у нас при каждом вызове f происходит два косвенных перехода - сначала при вызове f (ведь это виртуальная функция), а затем при вызове realF (ведь это тоже виртуальная функция). А хотелось бы обойтись одним переходом. Ведь на самом деле можно было бы подложить адрес realF на место f в таблице виртуальных методов (кастование указателя это лишь синтаксический сахар и на уровне ассемблерного кода не создаёт инструкции, поскольку это лишь вопрос интерпритации указателя дальше по коду, а сам указатель не меняется).

В Java есть type erasure и поэтому можно было написать просто:

class A<T> {
    public abstract void f(T arg);
};

class B<SomeType> {
    public void f(SomeType arg) {
        // что-то делаем
    }
};

В C++ мы не можем сделать базовый класс (A) шаблонным, иначе сломается runtime полиморфизм. Чтобы и не надо было делать явный каст в наследниках, и полиморфизм работал, пришлось сделать костыль с промежуточным шаблоном-наследником, но он приводит к генерации неоптимального кода.

Какие ещё есть варианты повторить то, что можно сделать в Java?

★★★★★

Последнее исправление: KivApple (всего исправлений: 2)

void *ptr

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

ox55ff ★★★★★
()
Ответ на: комментарий от ox55ff

Я привёл слишком абстрактный пример. Сейчас попробую привести пример конкретнее.

Допустим, я реализую паттерн «стратегия» - есть некий набор алгоритмов с общим интерфейсом и я хочу иметь возможность в другом коде дёргать эти алгоритмы с runtime полиморфизмом. Но это ещё не всё - алгоритмы не простые, а многоэтапные и у алгоритма есть состояние.

Условно:

struct AbstractAlgorithmState {
    AbstractAlgorithm &algorithm;
};

class AbstractAlgorithm {
public:
    virtual AbstractAlgorithmState *createState() = 0;
    virtual void updateState(AbstractAlgorithmState *state) = 0;
    virtual void deleteState(AbstractAlgorithmState *state) = 0;
};

struct MyAlgorithmState: public AbstractAlgorithmState {
    int a;
}

class MyAlgorithm: public AbstractAlgorithm {
public:
    AbstractAlgorithmState *createState() override {
        return new MyAlgorithmState { *this, 0 };
    }
    void updateState(AbstractAlgorithmState *state) override {
        auto myState = (MyAlgorithmState*) state;
        myState->a++;
        std::cout << "A = " << myState->a << std::endl;
    }
    void deleteState(AbstractAlgorithmState *state) override {
        delete (MyAlgorithmState*) state; // Вдруг MyAlgorithmState содержит поля с нетривиальными деструктурами вроде vector или string
    }
}

...

AbstractAlgorithmState *state = findAlgorithmByName(...)->createState();
state->algoritm.updateState(state);
state->algoritm.updateState(state);
state->algoritm.updateState(state);
state->algoritm.deleteState(state);

Наследников у AbstractAlgorithm может быть много, методов вроде updateState может быть много. У наследников AbstractAlgorithm могут быть свои поля «глобального состояния», а не всё их состояние хранится в AbstractAlgorithmState. Полиморфизм обязательно нужен в runtime.

Я согласен на любую шаблонную магию, но хочу чтобы написание наследников AbstractAlgorithm было максимально простым и приятным. Требование явного каста всё портит. Хочется, чтобы тип для хранения состояния прописывался в одном месте и больше касты были не нужны (и тогда, например, нельзя выстрелить себе в ногу и создать состояние одного типа, а в функциях обновления работать с другим типом).

Можно было бы вынести обновление состояния в само состояние, но это имеет минус в том, что тогда состояние потолстеет - помимо указателя на экземпляр AbstractAlgorithm (ведь часть состояния, напомню, «глобальная») он будет ещё содержать указатель на vtable. А экземпляров состояний одновременно могут существовать сотни тысяч (при этом у каждого алгоритма состояние очень мало весит - считанные байты) и хочется поэкономить память.

Вариант с шаблонными костылями как я описал в стартовом посте (переопределять в шаблоне виртуальный метод и вызывать другой виртуальный метод, но уже с кастом) приводит к двойному косвенному переходу вместо одного (потеря скорости, а updateState будет вызываться очень-очень много раз).

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 3)
Ответ на: комментарий от const86

Как положить это в гомогенный контейнер?

ТСу: не занимайся онанизмом, бери std::variant и std::visit с overload структурой для pattern matching.

anonymous
()
Ответ на: комментарий от anonymous

Можно положить в контейнер std::unique_ptr. Самих статегий/алгоритмов не настолько много и они не создаются/удаляются активно, так что unique_ptr вполне пойдёт.

KivApple ★★★★★
() автор топика
Ответ на: комментарий от KivApple

Всё равно ничего не понял. Мне кажется ты перемудрил. Type erasure делается через std::function.

auto task = [/*захват состояния*/]() { /* любой код */ };

void process(const std::function<void()> &task)
{
    task(); // Любой код можно вызвать не зная ничего о нём. Только функтор.
}
// Или даже так, чтобы было оптимальнее
template<typename T>
void process(T &&task)
{
    task();
}

Но нужно понимать, что std::function жирные. Хотя я лучше бы на твоём месте излишни не теоретизировал, а попробовал написать. Может быть со скоростью будет всё в порядке даже с жирными фанкшинами.

delete (MyAlgorithmState*) state;

Не забывай про виртуальный деструктор в классе интерфейсе. А то нормально не удалит.

ox55ff ★★★★★
()
Последнее исправление: ox55ff (всего исправлений: 1)
Ответ на: комментарий от const86

Спасибо за подсказку! Сделал как-то так:

#include <optional>
#include <functional>
#include <iostream>
#include <variant>
#include <memory>

class BaseAlgorithm;

struct BaseState {
	BaseAlgorithm &algorithm;

    BaseState(BaseAlgorithm &algorithm): algorithm(algorithm) {
    }
};

class BaseAlgorithm {
public:
	virtual ~BaseAlgorithm() = default;
	virtual BaseState *newState() = 0;
	virtual void updateState(BaseState *state) = 0;
	virtual void deleteState(BaseState *state) = 0;
	
};

template<typename T, typename S> class Algorithm: public BaseAlgorithm {
public:
	BaseState *newState() override {
		return new S(*this);
	}
	
	void updateState(BaseState *state) override {
		static_cast<T*>(this)->T::updateState(static_cast<S*>(state));
	}
	
	void deleteState(BaseState *state) override {
		delete static_cast<S*>(state);
	}

};

struct MyAlgorithmState: public BaseState {
	int a = 10;

    MyAlgorithmState(BaseAlgorithm &algorithm): BaseState(algorithm) {
    }
};

class MyAlgorithm: public Algorithm<MyAlgorithm, MyAlgorithmState> {
public:
	void updateState(MyAlgorithmState *state) {
		state->a++;
		printf("%i\n", state->a);
	}
	
};

void test(BaseAlgorithm *algorithm) {
	BaseState *state = algorithm->newState();
	state->algorithm.updateState(state);
	state->algorithm.updateState(state);
	state->algorithm.updateState(state);
	state->algorithm.deleteState(state);
}

int main(int argc, char *argv[]) {
	MyAlgorithm algorithm;
	test(&algorithm);
	return 0;
}
KivApple ★★★★★
() автор топика
Ответ на: комментарий от ox55ff

Да, я профукал добавить виртуальный деструктор в AbstractAlgorithm, когда писал пример (в реальном коде я всегда добавляю виртуальный деструктор).

А вот MyAlgorithmState зачем виртуальный деструктор? По задумке его будет удалять только специальный виртуальный метод в MyAlgorithm, который знает точный тип аргумента (ведь он был создан другим методом этого же класса) и поэтому деструктор должен вызваться в любом случае правильный.

KivApple ★★★★★
() автор топика
Ответ на: комментарий от KivApple

Мне тут только не нравится, что можно не переопределить updateState при наследовании шаблона и получить бесконечную рекурсию. Тут либо называть метод как-то иначе, либо как-то проверять в шаблоне, что мы вызываем именно прямо переопределённый метод, а не сами себя. Мне нравится второй вариант, но не знаю как его реализовать.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 1)
Ответ на: комментарий от KivApple

Ты уверен, что этот код делает то, что тебе нужно? Он выглядит так, будто ты обманул сам себя и думаешь, что все Ok.

anonymous
()
Ответ на: комментарий от KivApple

CRTP это когда ты параметризуешь базовый класс наследником и можешь кастовать в базовых методах this базового к нему.

Вестимо, такую приблуду в контейнер не положишь, ибо каждый инстанцированный тип Derived : public Base - это уникальный неполиморфный тип.

anonymous
()
Ответ на: комментарий от anonymous

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

KivApple ★★★★★
() автор топика
Ответ на: комментарий от anonymous

Переделал вот так:

#include <cstdio>

class BaseAlgorithm;

struct BaseState {
	BaseAlgorithm &algorithm;
	
	BaseState(BaseAlgorithm &algorithm): algorithm(algorithm) {
	}
	void updateState();
	
};

class BaseAlgorithm {
public:
	virtual ~BaseAlgorithm() = default;
	virtual BaseState *invokeNewState() = 0;
	virtual void invokeUpdateState(BaseState *state) = 0;
	virtual void invokeDeleteState(BaseState *state) = 0;
	
};

void BaseState::updateState() {
	algorithm.invokeUpdateState(this);
}

template<typename T, typename S> class Algorithm: public BaseAlgorithm {
public:
	BaseState *invokeNewState() final {
		return new S(*this);
	}
	
	void invokeUpdateState(BaseState *state) final {
		static_cast<T*>(this)->T::updateState(static_cast<S*>(state));
	}
	
	void invokeDeleteState(BaseState *state) final {
		delete static_cast<S*>(state);
	}
	
};

struct MyAlgorithmState: public BaseState {
	int a = 10;
	
	MyAlgorithmState(BaseAlgorithm &algorithm): BaseState(algorithm) {
	}
	
	~MyAlgorithmState() {
		printf("~MyAlgorithmState\n"); // Non-trivial destructor
	}
	
};

class MyAlgorithm: public Algorithm<MyAlgorithm, MyAlgorithmState> {
public:
	void updateState(MyAlgorithmState *state) {
		state->a++;
		printf("%i\n", state->a);
	}
	
};

void test(BaseAlgorithm *algorithm) {
	BaseState *state = algorithm->invokeNewState();
	state->updateState();
	state->updateState();
	state->updateState();
	state->algorithm.invokeDeleteState(state);
}

int main(int argc, char *argv[]) {
	MyAlgorithm algorithm;
	test(&algorithm);
	return 0;
}

Теперь всё точно хорошо - виртуальные методы и методы наследника называются по-разному, двойной косвенный переход отсутствует (при включенных оптимизациях в invokeUpdateState тупо инлайнится без всяких условий updateState наследника, что и требуется), само состояние лёгковесное (хранит только указатель на algorithm, но не содержит лишнего дополнительного указателя на свой собственный vtable), если в одном из наследников класса состояния есть нетривиальный деструктор, он будет корректно вызван, для алгоритмов работает runtime полиморфизм, при реализации алгоритмов не нужно выполнять руками каст в нужный тип (соответственно, нельзя выстрелить себе в ногу, создав состояние одного типа, а работая с другим - шаблон гарантирует, что все касты состояния будут типобезопасными).

Интересно разве что, можно ли как-то описать прототипы методов, которые программист обязан описать в наследнике класса, чтобы заработал автокомплит в IDE при их определении, а также были более человекочитаемые ошибки компиляции...

P. S.: Я исхожу из нескольких допущений:

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

- Методов вроде updateState может быть много (см. предыдущий текст в скобках)

- State весит очень мало (несколько байт, поэтому хранение в нём двух указателей вместо одного это плохо)

- State может существовать в количестве сотен тысяч штук (поэтому размер структуры было бы приятно оптимизировать)

- Методы вроде updateState (то есть не обращающиеся к менеджеру памяти) могут быть вызваны очень много раз (так что не хочется двух косвенных переходов и более)

P. P. S.: В реальном проекте я создаю State с помощью placement new в большом заранее выделенном массиве (просто установил максимальный размер State (как я уже сказал, там всегда не больше нескольких байт) и сделал массив длины максимальный размер State * количество State байт, что это правило не нарушается проверяю с помощью static_assert в шаблоне), так что 100500 обращений к аллокатору не происходит.

KivApple ★★★★★
() автор топика
Последнее исправление: KivApple (всего исправлений: 2)
Ответ на: комментарий от anonymous

Сделал в Algorithm абстрактный виртуальный метод updateState, теперь компилятор будет красиво ругаться, если забыть его объявить, а также работать автокомплит. При этом метод всё равно инлайнится при включённых оптимизациях, так что цена вопроса - всего лишь одна лишняя строчка в vtable наследников Algorithm.

#include <cstdio>

class BaseAlgorithm;

struct BaseState {
	BaseAlgorithm &algorithm;
	
	BaseState(BaseAlgorithm &algorithm): algorithm(algorithm) {
	}
	void updateState();
	
};

class BaseAlgorithm {
public:
	virtual ~BaseAlgorithm() = default;
	virtual BaseState *invokeNewState() = 0;
	virtual void invokeUpdateState(BaseState *state) = 0;
	virtual void invokeDeleteState(BaseState *state) = 0;
	
};

void BaseState::updateState() {
	algorithm.invokeUpdateState(this);
}

template<typename T, typename S> class Algorithm: public BaseAlgorithm {
public:
	BaseState *invokeNewState() final {
		return new S(*this);
	}
	
	virtual void updateState(S *state) = 0;
	
	void invokeUpdateState(BaseState *state) final {
		static_cast<T*>(this)->T::updateState(static_cast<S*>(state));
	}
	
	void invokeDeleteState(BaseState *state) final {
		delete static_cast<S*>(state);
	}
	
};

struct MyAlgorithmState: public BaseState {
	int a = 10;
	
	MyAlgorithmState(BaseAlgorithm &algorithm): BaseState(algorithm) {
	}
	
	~MyAlgorithmState() {
		printf("~MyAlgorithmState\n"); // Non-trivial destructor
	}
	
};

class MyAlgorithm: public Algorithm<MyAlgorithm, MyAlgorithmState> {
public:
	void updateState(MyAlgorithmState *state) final {
		state->a++;
		printf("%i\n", state->a);
	}
	
};

void test(BaseAlgorithm *algorithm) {
	BaseState *state = algorithm->invokeNewState();
	state->updateState();
	state->updateState();
	state->updateState();
	state->algorithm.invokeDeleteState(state);
}

int main(int argc, char *argv[]) {
	MyAlgorithm algorithm;
	test(&algorithm);
	return 0;
}
KivApple ★★★★★
() автор топика
Ответ на: комментарий от KivApple

цена вопроса - всего лишь одна лишняя строчка в vtable наследников Algorithm

Можно сделать абстрактный невиртуальный

monk ★★★★★
()

Не знаю, говорили уже boost.org/libs/type_erasure

zerhud
()

Если это не дурь по типу «хочу сэкономить строчку с кастом», а попытка контролировать целостность типов в реализации наследников, то можно наколхозить такое:

template <typename T>class ATemplate: public A {
	protected:
	typedef T param_type;
	typedef T* param_ptr;
};

class IntegerB: public ATemplate<int> {
	public:
	void f(void*ptr) override {
		auto casted = static_cast<param_ptr>(ptr);
		std::cout<<*casted<<std::endl;
	}	
};
class DoubleB: public ATemplate<double> {
	public:
	void f(void*ptr) override {
		auto casted = static_cast<param_ptr>(ptr);
		std::cout<<*casted<<std::endl;
	}	
};

Ну а если принцпиально экономить касты и/или иметь realF с правильным названием типа в списке параметров, можно по типу QT запилить макрос A_DESCENDANT, который вставлять в начало объявления каждого потомка и чтоб он разворачивался вот в этот оверрайд f, только вместо вывода в cout там вызов realF.

khrundel ★★★★
()
Последнее исправление: khrundel (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.