C і C++ (C++17) досі немає нормальних багатовимірних масивів, які були в Fortran починаючи з Fortran 90

Це стаття про багатовимірні масиви. А ще про ключове слово restrict, до появи якого в C мову Fortran був швидше C. Трохи про те, навіщо я це написав, див. у кінці.

Багатовимірні масиви. Почну з багатовимірних масивів. Припустимо, вам потрібно максимально ефективно працювати з великими квадратними матрицями в C++ (скажімо, множити їх один на одного). Причому розмір матриць стає відомим лише в runtime. Що робити?

Всякі
double a[n][n]
та
std::array<std::array<double, n> n>
не спрацюють, оскільки порядок матриці (n) буде відомий лише в runtime.
new double[n][n]
не спрацює з цієї ж причини (лише перший вимір масиву, створюваного new, може бути runtime-виразом). Спробуємо так:

double **a = new double *[n]; // Масив довжини n покажчиків на double
for (int i = 0; i != n; ++i)
{
a[i] = new double[n];
}


Начебто нормально. Тепер до i-го j-го елемента можна звернутися за допомогою a[i][j]. Ось тільки є один нюанс. Масив a — масив покажчиків. А не єдиний двовимірний масив, одним шматком розміщений у пам'яті. Отже, звернення до i-го j-го елементу буде повільніше, ніж могло б бути, якщо б дані були розміщені одним двовимірним масивом. І робота з такою матрицею (множення на іншу матрицю і т. д.) теж буде повільніше. Те ж саме відноситься до
std::vector<std::vector<
double>>
.

А тепер правильна відповідь:
double *a = new double[n * n];


Так, тепер до i-го j-го елементу доведеться звертатися так: a[i * n + j]. Зате ефективно.

А як зробити так, щоб синтаксис був нормальним (a[i][j]), але щоб було ефективно? Потрібно написати свій клас, який буде робити саме це. У стандартній бібліотеці такого немає.

Невелике зауваження. У C99 є variable length arrays (VLA), але вони тут не допоможуть, т. к. gcc виділяє місце для VLA на стеку, а матриці у нас великі (я попереджав) і в стек не влізуть.

А ось в Fortran є стандартний спосіб роботи з динамічними двовимірними масивами. Ефективно і з гарним синтаксисом звернення до i-го j-го елементу.

Було б дуже ефектно, якщо б я написав тут, що цей спосіб був в Fortran з самого початку. Що він підтримувався ще в першому компіляторі Fortran'а, написаному в 1957-му році. У першому компіляторі Fortran'а (FORmula TRANslation), майже першої мови програмування на Землі (C створено не раніше 1969-го року). Що він підтримувався ще коли програми на Fortran'е набиралися на перфокартах. Я б ще розмістив тут фотографію перфокарти для більшої переконливості. Але немає. Ця фіча з'явилася в Fortran 90.

Однак Fortran 90 не такий вже і новий. 26 років минуло. 26 років ця фіча є в Fortran'є. А в C++ її немає до цих пір.

Ось так виглядає код для виділення пам'яті:
REAL, ALLOCATABLE :: A (:,:)
...
ALLOCATE (A (N,N))


І звернення до i-го j-го елемента відбувається так: A(I, J) (втім, потрібно враховувати, що в Fortran порядок індексів не співпадає з таким в C і C++).

Втім, нормальний метод роботи з багатовимірними масивами все-таки є в C++. У Boost.MultiArray. Але це Boost, це не стандартна бібліотека, а тому не зараховується.

restrict. Тепер про restrict. У Fortran'е в функцію можна передати два масиву (мабуть, за посиланням). І компілятор буде знати, що це два різних масиву, а тому зміна одного не може призвести до зміни іншого. Тобто якщо в функцію передано масив масив a і b, то компілятор знає, що зміна a[2] (пишу тут в синтаксисі C) не призведе до зміни b[3]. А отже, якщо в коді йде запис a[2], а потім читання з b[3], то необов'язково реально писати a[2] в пам'ять, а потім читати b[3] з пам'яті. Можна просто записати поки в регістр. Шукайте в інтернеті за словом aliasing.

Так от, а в C передати масив в функцію не можна. Точніше, можна, не має спеціального синтаксису, щоб показати компілятору, що в функцію передається саме масив. Якщо написати
void f (int a[2])

ну або
void f (int a[])

то це буде еквівалентно такого коду:
void f (int *a)

Тобто фактично передаватися буде покажчик.
А значить, якщо ми передаємо в функцію «масив» і «масив» b, то передаватися будуть вказівники. А значить, у компілятора немає ніякої інформації про те, чи збираємося ми, використовуючи один покажчик, читати/писати пам'ять, доступну з іншого, чи ні (це було про C89, далі буде пояснення). Тобто він не знає, може так вийде, що a[2] — це насправді b[3]. А значить, якщо ми пишемо в a[2], а потім читаємо з b[3], то компілятор не може це соптімізіровать і змушений зробити commit в реальну пам'ять. А значить, код буде повільніше еквівалентного на Fortran'е.

Лише в C99 в мові нарешті з'явилася фіча restrict, яка дозволила явно показати, що «ось ці покажчики далекі один від одного», тобто рухаючись починаючи від одного, ми не потрапимо у другий. А значить, C ніби як наздогнав Fortran.

Але Fortran має величезну історію використання для високопродуктивних математичних обчислень. Не виключено, що в Fortran є ще кілька фіч, які ще чекають своєї години: включення в C. І які, можливо, все ще роблять Fortran швидше C.

Про статтю. Почав писати відповідь на коментар aso. Комент розрісся, довелося перетворити його в статтю. Плюс давно хотів написати про багатовимірні масиви в Fortran'е. Стаття вийшла сумбурною, особливо друга частина, про restrict. І взагалі Fortran я не знаю. :) Щодо першої частини, про багатовимірні масиви, я майже впевнений в усьому, що кажу. У другій частині я впевнений щодо того, що відноситься до C. А от як там влаштовані правила аліасінга в Fortran'е, я не знаю, просто десь в інтернеті я прочитав, що поява restrict дозволило C нарешті наблизитися Fortran. А посилання втратив. :)
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.