Pull to refresh

В C++17 до сих пор нет нормальных многомерных массивов, которые были в Fortran начиная с Fortran 90

Reading time 5 min
Views 32K
Это статья про многомерные массивы. А ещё про ключевое слово 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>>.

UPD от 2016-12-11 0:00. Код выделения памяти выше можно написать и поэффективнее. Но моя статья не об этом, она об эффективности обращения к элементу.

А теперь правильный ответ:

double *a = new double[n * n];

Да, теперь к i-му j-му элементу придётся обращаться так: a[i * n + j]. Зато эффективно.

А как сделать так, чтобы синтаксис был нормальным (a[i][j]), но чтоб было эффективно? Нужно написать свой класс, который будет делать ровно это. В стандартной библиотеке такого нет.

Небольшое замечание. В C99 есть variable length arrays (VLA), но они здесь не помогут, т. к. gcc выделяет место для VLA на стеке, а матрицы у нас большие (я предупреждал) и в стек не влезут. (Тут я не прав, см. UPD.)

А вот в 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)

То есть фактически передаваться будет указатель. А значит, если мы передаём в функцию «массив» 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. А ссылку потерял. :)

UPD от 2016-12-10 14:03. Посмотрел на этот коммент от selgjos, поэкспериментировал с компилятором и понял, что с помощью C99 VLA всё-таки можно добиться нужного мне эффекта. Итак, написать вот так: double a[n][n] не получится, т. к. матрица может не влезь в стек. Зато можно так:

double (*a)[n] = malloc (n * n * sizeof (double));

Теперь a — это то, что мне нужно. Единый блок размера n на n, размещённый в динамической памяти. С обращением к i-му j-му элементу при помощи a[i][j]. Если теперь нужно куда-то этот массив передать, это нужно делать так:

void f (int n, double a[n][n])

В общем, окей, в C есть нужные мне массивы. Как и в Fortran. А в C++ их по-прежнему нет.

UPD от 2016-12-12 19:12. Процитирую свой коммент:
Лично я не говорил, что якобы фортран и вправду и по сей день имеет некие преимущества перед си. Не имеет. Я написал эту статью, просто чтобы обратить внимание на факт, который, может быть, многие не знают. А именно, что, оказывается, фортран в некоторых моментах удобнее си. И что лишь совсем недавно си наконец догнал фортран по скорости.


UPD от 2016-12-12 22:49. Процитирую ещё один свой коммент:
Да не предлагаю я добавить в C++ многомерные массивы в стиле Fortran или C. Вся моя статья нужна просто, чтобы рассказать про этот курьёзный, так сказать, факт. Что в Fortran есть «нормальные» многомерные массивы, а в C++ — нет. Этот факт был удивительным для меня в своё время.
Tags:
Hubs:
+24
Comments 226
Comments Comments 226

Articles