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

C++ всегда быстрее Smalltalk?

Продолжение темы.

При сравнении скоростных характеристик разных языков обычно используются простые тесты, измеряющие скорость выполнения примитивных операций. Например, арифметические операции с целыми и вещественными числами, чтение/запись в массив, статический вызов, виртуальный вызов, создание объектов и т.д. Такие тесты называются micro-benchmarks. Как правило, эти показатели позволяют примерно оценить сравнительную производительность языков и компиляторов.

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

  • Частота использование различных операций. Эта величина может различаться для разных приложений, в результате чего различные операции могут быть узким местом.
  • Масштабируемость примитивных операций. Будет ли скорость расти линейно при увеличении количества операций?
  • Влияние процессора. Сюда входит кэширование, возможность сочетания различных операций и т.д.

Проиллюстрируем один из этих факторов простым примером.

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

Поэтому для объектно-ориентированных приложений одним из наиболее критических факторов является скорость вызова виртуальных методов.

Рассмотрим следующий код для Visual C++ 6.0:

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

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

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)
		{
			CA *x = c[m];
			x->a();
			x->b();
			x->c();
			x->d();
			x->e();
		}
	}

	dwTime = GetTickCount() - dwTime;

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

	return 0;
}

И эквивалентный код на VisualWorks Smalltalk 7.1 (опуская объявление классов):

| a |
a := Array with: CA new with: CB new.
Transcript print: (Core.Time millisecondsToRun:
	[10000000 timesRepeat:
		[1 to: 2 do: [:i |
			| x |
			x := a at: i.
			x a. x b. x c. x d. x e]]]);
	cr.
Transcript flush

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

Замеры нескольких запусков дали сделующие лучшие результаты:

C++ 2766ms
Smalltalk 1188ms

Да, никакой ошибки здесь нет. C++ оказался намного медленее Smalltalk (в 2.3 раза) для простого цикла с множеством виртуальных вызовов!

А теперь, если вместо вызова пяти методов во внутреннем цикле оставить только один, то получается обратная картина:

C++ 187ms
Smalltalk 536ms

В этом случае Smalltalk большую часть времени тратит собственно на цикл, сам вызов проходит приблизительно за 160ms.

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

Объясняется это тем, что в C++ виртуальные вызовы происходят косвенным образом через таблицу диспетчеризации виртуальных методов. А, как известно, косвенный вызов является очень дорогостоящим на нынешнем поколении процессоров.

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

Указанная проблема не уникальна для Visual C++. Все классические компиляторы C++/Java/C# ведут себя точно таким же образом. Соответственно, и результаты следует ожидать примерно такие же (у C# они были идентичные).

В этом отношении технология HotSpot VM имеет потенциальное преимущество, так как она построена на динамическом компиляторе Self/Strongtalk. Правда, в версии 1.3 возможность оптимизации виртуальных вызовов, по-видимому, еще не была адаптирована.

Для иллюстрации возможностей технологии Strongtalk приведем сводную таблицу:

Язык 1 метод 5 методов
C++ 187ms 2766ms
Smalltalk 536ms 1188ms
Strongtalk 219ms 506ms

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

Отсюда видно, что текущие реализации C++/Java/C# выбрали не то направление, которое необходимо, чтобы наилучшим образом поддержать объектно-ориентированные возможности (которые у них и так сильно ограничены).

Дополнение

Тестовая конфигурация: Celeron 1.7GHz, 256MB DDR266

О технике реализации полиморфных вызовов в динамических языках можно прочитать в статье Optimizing Dynamically-Typed Object-Oriented Programming Languages with Polymorphic Inline Caches, by Urs Holzle, Craig Chambers and David Ungar.

В качестве дополнительного комментария к статье приведем цитату из научной работы Software and Hardware Techniques for Efficient Polymorphic Calls, by Karel Driesen. Указанные цифры относятся к архитектуре Pentium Pro (Pentium II) и RISC-архитектурам того же поколения.

We have analyzed the direct dispatch overhead of the standard virtual function table (VFT) dispatch on a suite of C++ applications with a combination of executable inspection and processor simulation. Simulation allows us to precisely define dispatch overhead as the overhead over an ideal dispatch implementation using direct calls only. On average, dispatch overhead is significant: on a processor resembling current superscalar designs, programs spend a median overhead of 5.2% and a maximum of 29% executing dispatch code. However, many of these benchmarks use virtual function calls quite sparingly and thus might underrepresent the actual "average" C++ program. For versions of the programs where every function was converted to a virtual function to simulate programming styles that extensively use abstract base classes defining virtual functions only (C++'s way of defining interfaces), the median overhead rose to 13.7% and the maximum to 47%. On future processors, this dispatch overhead is likely to increase moderately.




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