Содержание сайта
Главная Новичку Цитаты Реализации Статьи Документация
Компании Программы Ссылки Обсуждение Обсуждение 2 Гостевая

C++ и Smalltalk: обмен опытом
Крицкий Юрий, yuri_kritski@mail.ru
Специально для www.smalltalk.ru

Прочтя статью "C++ всегда быстрее Smalltalk?", я был приятно удивлён результатами современных систем программирования для языков с динамической типизацией. Возник вопрос: если подобные методы оптимизации так хорошо работают в языках, обычно считающихся "медлительными", то нельзя ли применить их в "традиционных" языках, имеющих статическую типизацию, например в C++?

От компилятора (использовался Visual C++ 6.0) помощи ждать не приходилось, поэтому я изучил статью, на которую ссылался автор, и попытался извлечь пользу из прочитанного.

Один из основных методов оптимизации, применяемых в Strongtalk - это полиморфный кэш подстановок (PIC). Суть его состоит в том, что в месте, где часто посылаются полиморфные сообщения, посылка заменяется вызовом процедуры PIC. В этой процедуре проверяется настоящий тип получателя сообщения и для часто встречающихся типов делается прямой вызов соответствующего обработчика. В конце цепочки проверок осуществляется обычная полиморфная посылка.

Итак, берём за пример с пятью методами из вышеуказанной статьи. Первое, что хочется сделать - это вынести выполнение вызова пяти методов в один метод. Основной цикл станет таким:

    for (int k = 0; k < 10000000; ++k)
        for (int m = 0; m < 2; ++m)
            c[m]->doCalls();
а соответствующий метод определяется в классе CA:
// в классе CA
    void doCalls()

void CA::doCalls()
{
    a();
    b();
    c();
    d();
    e();
}

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

Компилируем, пробуем: было 2474 мс, стало 2333 мс (см. замечание в конце).

Теперь пробуем оптимизировать вручную. Для этого прежде всего требуется информация о типе. Однако C++ не расчитан на интенсивное использование RTTI, поэтому во избежание издержек typeid объекта будем получать в конструкторе, а сравнивать будем на уровне указателей на type_info, а не ссылок, т.к. VC++ использует для оператора сравнения type_info статический вызов. После добавления RTTI время исполнения не изменилось, что и следовало ожидать.

// в классе CA
public:
    CA() { _typeid = &typeid(*this); }
    const type_info* typeId() const { return _typeid; }
protected:
    const type_info* _typeid;

// в классе CB
    CB() { _typeid = &typeid(*this); }

Далее приступаем к собственно оптимизации. Мы знаем, что объекты класса CA используются часто, потому добавляем его распознавание в тело метода doCalls:

void CA::doCalls()
{
    if( typeId() == &typeid(CA) )
    {
        CA::a();
        CA::b();
        CA::c();
        CA::d();
        CA::e();
        return;
    }

    a();
    b();
    c();
    d();
    e();
}

Теперь время выполнения теста стало 400 мс. Замечательно! Мы получили, пусть и в синтетическом тесте, повышение скорости в 8 раз! Дальнейшие действия очевидны. Добавляем распознавание класса CB в doCalls:

void CA::doCalls()
{
    if( typeId() == &typeid(CA) )
    {
        CA::a();
        CA::b();
        CA::c();
        CA::d();
        CA::e();
        return;
    }

    if( typeId() == &typeid(CB) )
    {
        CB *x = (CB*) this;
        x->CB::a();
        x->CB::b();
        x->CB::c();
        x->CB::d();
        x->CB::e();
        return;
    }

    a();
    b();
    c();
    d();
    e();
}

Полученное время выполнения (180 мс) позволяет считать дальнейшую оптимизацию излишней. Однако, для чистоты эксперимента можно объединить всё в один файл и сделать метод doCalls подставляемым (inline). Тогда время станет поистине чемпионским - 110 мс!

Однако выводы скорее печальны. Оптимизации, разработанные для динамически типизованных языков, вполне легко применимы и в C++, но только вручную и за счёт изменения исходного кода. А ведь с момента представления PIC-метода прошло уже 12 лет, и его использование для C++ рассматривалось в статье "Eliminating Virtual Function Calls in C++ Programs" в 1996 году...

 

Замечание.

Использовался ПК под управлением Windows 2000 Professional с процессором Celeron 1100MHz и ОЗУ 384 Mbyte. Опции компиляции: -O2 -GR

Исходный пример, скомпилированный Intel C++ Compiler 6.0 и Visual Studio .NET с теми же опциями, работал около 2650 мс.

 

Полный листинг


//----------------------------------------------------------
// файл test.h 


class CA
{
public:
	virtual int a();
	virtual int b();
	virtual int c();
	virtual int d();
	virtual int e();

	void doCalls();

	CA() { _typeid = &typeid(*this); }
	const type_info* typeId() const { return _typeid; }

protected:
	const type_info* _typeid;
};

class CB : public CA
{
public:
	virtual int a();
	virtual int b();
	virtual int c();
	virtual int d();
	virtual int e();

	CB() { _typeid = &typeid(*this); }
};

//----------------------------------------------------------
// файл main.cpp 


int main(int argc, char* argv[])
{
	CA ca;
	CB cb;
	CA *c[2];
	c[0] = &ca;
	c[1] = &cb;

	DWORD dwTime = GetTickCount();

	for (int k = 0; k < 10000000; ++k)
		for (int m = 0; m < 2; ++m)
			c[m]->doCalls();

	dwTime = GetTickCount() - dwTime;

	printf("time = %dms\n", dwTime);

	return 0;
}

//----------------------------------------------------------
// файл test.cpp 


int CA::a() { return 55; }
int CA::b() { return 55; }
int CA::c() { return 55; }
int CA::d() { return 55; }
int CA::e() { return 55; }

int CB::a() { return 110; }
int CB::b() { return 110; }
int CB::c() { return 110; }
int CB::d() { return 110; }
int CB::e() { return 110; }

void CA::doCalls()
{
	if( typeId() == &typeid(CA) )
	{
		CA::a();
		CA::b();
		CA::c();
		CA::d();
		CA::e();
		return;
	}

	if( typeId() == &typeid(CB) )
	{
		CB *x = (CB*) this;
		x->CB::a();
		x->CB::b();
		x->CB::c();
		x->CB::d();
		x->CB::e();
		return;
	}

	a();
	b();
	c();
	d();
	e();
}



Есть комментарии? Пишите.