Производительность PascalABC.NET, C#, C++ и Free Pascal

Статья дополнена 19.03.19 (см. конец статьи).

Насколько быстро выполняется программа на PascalABC.NET? Наверняка ведь медленнее, чем на C# или на C++. Или нет? Давайте проверим.

Проверку будем вести на компьютере с процессором Intel Core i5-2500 3,3 ГГц, 8 Гб памяти.

Начнем с программы на C#, перемножающей две квадратные матрицы размера 1000 на 1000, заполненные случайными вещественными в диапазоне от 1 до 1.1. Для экономии места приведем здесь только сам метод умножения:

static void Mult2(double[,] a, double[,] b, double[,] c, int n)
{
  for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
  {
    var cc = 0.0;
    for (int k = 0; k < n; k++)
      cc += a[i, k] * b[k, j];
    c[i, j] = cc;
  }
}

Запустим программу в режиме Release.

Результат: 7.7 с.

Напишем аналогичную программу на PascalABC.NET:

uses Arrays;

procedure Mult1(a,b,c: array [,] of real; n: integer);
begin
  for var i:=0 to n-1 do
    for var j:=0 to n-1 do
    begin  
      var cc := 0.0;
      for var k:=0 to n-1 do
        cc += a[i,k]*b[k,j];
      c[i,j] := cc; 
    end;
end;

const n = 1000;

begin
  var a := Arrays.CreateRandomRealMatrix(n,n,1,1.1);
  var b := Arrays.CreateRandomRealMatrix(n,n,1,1.1);
  var c := new real[n,n];
  var d := Milliseconds;
  Mult1(a,b,c,n);
  writeln((Milliseconds-d)/1000);
end.

Честно снимем флажок «Генерировать отладочную информацию (Debug-версия)» в настройках опций компиляции. Это будет соответствовать Release-версии. Запустим, нажав F9.

Результат: 19.7 с.

О, как долго!

Давайте сделаем это аккуратнее. Программа по умолчанию запускается в режиме связи с оболочкой — это позволяет ей за счет некоторого замедления работы осуществлять вывод в окно PascalABC.NET. Если же мы хотим добиться максимальной производительности, то запустим еще раз, нажав Shift-F9 — в режиме без связи с оболочкой. Результаты будут выведены в появившееся черное консольное окно, но они будут интереснее:

Результат: 7.7 с.

Такой же, как и у C#. Как говорится в рекламе: «а если результаты одинаковы, то зачем платить больше?».

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

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

cc += a[i,k]*b[k,j];

видно, что матрица a считывается по строкам, а матрица b — по столбцам, то транспонируем матрицу b перед умножением (эта операция займет всего n² операций, что пренебрежимо мало по сравнению с n³ операций при умножении матриц). Приведем новый код:

uses Arrays;

procedure Mult2(a,b,c: array [,] of real; n: integer);
begin
  for var i:=0 to n-1 do
    for var j:=0 to i-1 do
      Swap(b[i,j],b[j,i]);
  for var i:=0 to n-1 do
    for var j:=0 to n-1 do
    begin  
      var cc := 0.0;
      for var k:=0 to n-1 do
        cc += a[i,k]*b[j,k];
      c[i,j] := cc; 
    end;
end;

const n = 1000;

begin
  var a := Arrays.CreateRandomRealMatrix(n,n,1,1.1);
  var b := Arrays.CreateRandomRealMatrix(n,n,1,1.1);
  var c := new real[n,n];
  var d := Milliseconds;
  Mult2(a,b,c,n);
  writeln((Milliseconds-d)/1000);
end.

Запустим, нажав Shift-F9. Ого!

Результат: 1.8 с.

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

Прирост производительности — 4 раза. И это — за счет того, что мы знаем, что у процессора есть кеш. И язык программирования тут ни при чем. Просто алгоритмы надо уметь готовить.

Спортивный интерес не позволяет нам просто так остановиться. И мы вспоминаем, что в PascalABC.NET есть такая замечательная штука, как OpenMP, позволяющая на многоядерном процессоре распараллеливать циклы простой директивой компилятора.

Алгоритм умножения матриц замечательно распараллеливается, поэтому теоретически, поскольку в используемом процессоре 4 ядра, ускорение должно составить 4 раза. Проверим.

Вот как будет выглядеть измененная программа с директивами OpenMP:

uses Arrays;

procedure Mult3(a,b,c: array [,] of real; n: integer);
begin
  {$omp parallel for }
  for var i:=0 to n-1 do
    for var j:=0 to i-1 do
      Swap(b[i,j],b[j,i]);
  {$omp parallel for }
  for var i:=0 to n-1 do
    for var j:=0 to n-1 do
    begin  
      var cc := 0.0;
      for var l:=0 to n-1 do
        cc += a[i,l]*b[j,l];
      c[i,j] := cc;   
    end;
end;

const n = 1000;

begin
  var a := Arrays.CreateRandomRealMatrix(n,n,1,1.1);
  var b := Arrays.CreateRandomRealMatrix(n,n,1,1.1);
  var c := new real[n,n];
  var d := Milliseconds;
  Mult3(a,b,c,n);
  writeln((Milliseconds-d)/1000);
end.

Запустим дрожащими руками.

Результат: 0.46 с.

Как и было обещано теорией. В 4 раза.

Вывод, собственно, прост. PascalABC.NET — хорошая система программирования :)

Постскриптум. На этом можно было бы закончить, но лавры локального победителя не дают покоя. Сравним-ка мы производительность нашей программы с программой, написанной на хваленом Free Pascal, а также с программой на C++. Сразу заметим, что программа на C++ должна иметь существенно лучшую производительность, поскольку C++ не проверяет выход за границы массива. Что ж, проверим.

Вначале программа на Free Pascal. Несколько минут мучения с устаревшим текстовым интерфейсом синего цвета, и — вот код:

uses Windows;

const n = 1000;

type
  Matr = array[0..n-1,0..n-1] of real;

procedure Mult1(const a,b: Matr; var c: Matr; n: integer);
var
  i,j,k: integer;
  cc: real;
begin
  for i:=0 to n-1 do
    for j:=0 to n-1 do
    begin
      cc := 0.0;
      for k:=0 to n-1 do
        cc := cc + a[i,k]*b[k,j];
      c[i,j] := cc;
    end;
end;

var
  i,j: integer;
  a,b,c: Matr;
  t: Cardinal;

begin
  for i:=0 to n-1 do
    for j:=0 to n-1 do
    begin
      a[i,j] := Random() * 0.1 + 1.0;
      b[i,j] := Random() * 0.1 + 1.0;
    end;

  t := GetTickCount;
  Mult1(a,b,c,n);
  writeln((GetTickCount-t)/1000:8:3);
end.

Зайдем в опции компилятора и установим Mode — Release и самые крутые настройки оптимизации. В частности, отключим проверку выхода за границы диапазона. Запустим.

Результат: 8.0 с.

То есть, такой же, как и у аналогичной программы на PascalABC.NET.

Трюк с транспонированием второй матрицы уже не дает того прироста скорости.

Результат: 3.1 с.

Наконец, напишем программу на C++, выбрав в качестве компилятора C++ из комплекта Visual Studio 2012:

#include <iostream>
#include <cstdio>
#include <ctime>

using namespace std;

const int n=1000;
double a[n][n];
double b[n][n];
double c[n][n];

int _tmain(int argc, _TCHAR* argv[])
{
  for (int i=0; i<n; i++)
  for (int j=0; j<n; j++)
  {
    a[i][j] = (rand() % 100)/100.0+1.0;
    b[i][j] = (rand() % 100)/100.0+1.0;
  }

  long t1 = clock();

  for (int i=0; i<n; i++)
  for (int j=0; j<n; j++)
  {
    double cc = 0;
    for (int k=0; k<n; k++)
      cc += a[i][k]*b[k][j];
    c[i][j] = cc;
  }

  long t2 = clock();

  cout<<c[n-1][n-1]<<endl;
  cout<<(t2-t1)/1000.0<<endl;
  return 0;
}

Запустим в режиме Release. Напоминаю, что в этом режиме C++ не проверяет выход за границы диапазона.

Результат: 7.8 с.

Такой же, как и у аналогичной программы на PascalABC.NET.

Трюк с транспонированием матрицы приносит отличный результат.

Результат: 0.99 с.

Почти в 2 раза быстрее, чем в PascalABC.NET. Что ж, отдадим пальму первенства C++ — ведь мы здесь честно не использовали распараллеливание.

Приведем итоговую таблицу:

Компилятор, алгоритм	Время работы
C#	7.7 с
PascalABC.NET	7.7 с
PascalABC.NET, алгоритм со считыванием данных по строкам	1.8 с
PascalABC.NET, алгоритм с директивами OpenMP	0.45 с
Free Pascal, максимальная оптимизация	8.0 с
C++	7.8 с
C++, алгоритм со считыванием данных по строкам	0.99 с
Ваш компилятор	???

Update 03.03.13

Провел более точные измерения. Вот неожиданные результаты:

n	C++	C++ транспонир	PABC	PABC транспонир
400	0,07	0,05	0,17	0,11
500	0,12	0,11	0,35	0,2
600	1,12	0,19	1,1	0,35
700	2,5	0,31	2,3	0,57
800	3,6	0,48	3,5	0,86
900	3,6	0,71	5,8	1,25
1000	7,9	1	7,7	1,74
1100	10,7	1,34	10,7	2,3
1200	13,6	1,77	13,7	3,04

В алгоритме без транспонирования вмешивается оптимизация, по-видимому, сильно ориентированная на кеш процессора. Особенно интересен переход от n=500 к n=600 во втором столбце — на C++.

В алгоритмах с транспонированной матрицей, где данные располагаются максимально удобно для кеша — и у C++, и у PascalABC.NET — график роста времени в зависимости от n — чистая кубическая парабола.

Замеры производительности, выполненные с помощью компилятора gcc под Windows со всеми включенными оптимизациями, показывают процентов на 5–10% лучшие результаты, чем аналогичные для компилятора VS 2012.

Дополнение от 19.03.19

Всё меняется. За время после написания статьи сменилось несколько поколений процессоров.

Общий вывод статьи не поменялся — PascalABC.NET столь же производителен, что и C#, и опережает на многих тестах Free Pascal со всеми включёнными оптимизациями.

Приведу некоторые результаты статьи на шестиядерном процессоре I7 8700K 3.7 ГГц.

Первая Pascal-программа (n=1000). В режиме Debug — 5.5 с. В режиме Release — 2.4 с. То есть, более чем в 2 раза по сравнению с процессором Intel Core i5-2500 3,3 ГГц.

Аналогичная программа на Free Pascal (приводится в тексте): в режиме Debug — 4.3 с. В режиме Release со всеми включёнными оптимизациями — 2.4 с.

Вторая Pascal-программа (n=1000) с транспонированием. В режиме Release — 1.6 с.

Третья Pascal-программа (n=1000) с распараллеливанием. В режиме Release — 0.29 с. (что хорошо: теоретический минимум при 6 ядрах = 1.6/6 = 0.27 с)

Таблица для 1 и 2 программы:

n	PABC	PABC транспонир
600	0,44	0,35
700	0,73	0,55
800	1,09	0,83
900	1,58	1,16
1000	2,4	1,6
1100	3,54	2,15
1200	4,46	2,8
1300	7,1	3,5
1400	8,5	4,4

Меряем производительность

Update 03.03.13

Дополнение от 19.03.19