Статья дополнена 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 перед умножением (эта операция займет всего n2 операций, что пренебрежимо мало по сравнению с n3 операций при умножении матриц). Приведем новый код:
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++ не проверяет выход за границы массива. Что ж, проверим.
Вначале программа на 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, алгоритм с |
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 |
27.08.24. Вышла версия PascalABC.NET 3.10.0. Список изменений - здесь.
01.02.24. На ресурсе Stepik в ознакомительном режиме открыт курс "PascalАВС.NЕТ: продвинутый уровень".
10.07.23. Вышел релиз версии PascalABC.NET 3.9.0. Нововведения описаны здесь.
20.05.23. На странице https://pascalabc.net/stepikcourse опубликованы новые курсы по PascalABC.NET от центра олимпиадного программирования DL Club.
08.05.23. Вышла версия PascalABC.NET 3.9.0.beta. Основное - ковариантные параметры обобщений, аргументы по умолчанию при вызове подпрограммы, модуль автоматической проверки LightPT.