Это статья про многомерные массивы. А ещё про ключевое слово 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) То есть фактически передаваться будет указатель.
А значит, если мы передаём в функцию «массив» 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. А ссылку потерял. 🙂
ссылка на оригинал статьи https://habrahabr.ru/post/317300/
Добавить комментарий