Является ли С медленнее, чем Фортран, в спектральной норме (с использованием gcc, intel и других компиляторов)?

13

Вывод здесь:

Насколько лучше на самом деле компиляторы Фортрана?

в том, что gfortran и gcc так же быстры для простого кода. Поэтому я хотел попробовать что-то более сложное. Я взял пример спектральной нормы. Сначала я рассчитываю 2D матрицу A (:, :), а затем вычисляю норму. (Это решение не допускается в перестрелке, я думаю.) Я реализовал Fortran и C-версию. Вот код:

https://github.com/certik/spectral_norm

Самые быстрые версии gfortran - spectral_norm2.f90 и spectral_norm6.f90 (одна использует встроенные в Fortran matmul и dot_product, другая реализует эти две функции в коде - без разницы в скорости). Самый быстрый код C / C ++, который мне удалось написать, это spectral_norm7.cpp. Начиная с версии git 457d9d9 на моем ноутбуке:

$ time ./spectral_norm6 5500
1.274224153

real    0m2.675s
user    0m2.520s
sys 0m0.132s


$ time ./spectral_norm7 5500
1.274224153

real    0m2.871s
user    0m2.724s
sys 0m0.124s

Так что версия Gfortran немного быстрее. Это почему? Если вы отправите запрос извлечения с более быстрой реализацией C (или просто вставите код), я обновлю репозиторий.

В Фортране я передаю 2D-массив, в то время как в CI я использую 1D-массив. Не стесняйтесь использовать 2D-массив или любым другим способом, который вы считаете нужным.

Что касается компиляторов, давайте сравним gcc против gfortran, icc против ifort и так далее. (В отличие от страницы перестрелки, которая сравнивает ifort с gcc.)

Обновление : используя версию 179dae2, которая улучшает matmul3 () в моей версии C, они теперь так же быстры:

$ time ./spectral_norm6 5500
1.274224153

real    0m2.669s
user    0m2.500s
sys 0m0.144s

$ time ./spectral_norm7 5500
1.274224153

real    0m2.665s
user    0m2.472s
sys 0m0.168s

Векторизованная версия Педро ниже:

$ time ./spectral_norm8 5500
1.274224153

real    0m2.523s
user    0m2.336s
sys 0m0.156s

И, наконец, как сообщает laxxy ниже для компиляторов Intel, здесь нет большой разницы, и даже самый простой код на Фортране (spectral_norm1) является одним из самых быстрых.

Ондржей Чертик
источник
5
Сейчас я не нахожусь рядом с компилятором, но рассмотрите возможность добавления ключевого слова restrict к вашим массивам. Как правило, псевдонимы указателей - это разница между вызовами функций в Fortran и C в массивах. Кроме того, Fortran хранит память в мажорном столбце, а C - в мажорном ряду.
Мойнер
1
-1 Суть этого вопроса говорит о реализации, но заголовок спрашивает, какой язык быстрее? Как язык может иметь атрибут скорости? Вы должны отредактировать заголовок вопроса, чтобы он отражал основную часть вопроса.
Миланкурсик
@ IRO-бот, я исправил это. Дайте мне знать, если это выглядит хорошо, чтобы вы знали.
Ондржей Чертик
1
На самом деле выводы о том, "насколько лучше на самом деле компиляторы Фортрана?" не совсем правильно в этой теме. Я пробовал тест на Cray с компиляторами GCC, PGI, CRAY и Intel, а с 3 компиляторами Fortran был быстрее C (ч / б 5-40%). Компиляторы Cray создали самый быстрый код на Fortran / C, но код на Fortran оказался на 40% быстрее. Я опубликую подробные результаты, когда у меня будет время. Кстати, любой, у кого есть доступ к компьютерам Cray, может проверить тест. Это хорошая платформа, потому что доступно 4-5 компиляторов и соответствующие флаги автоматически включаются оболочкой ftn / cc.
Stali
также проверено с помощью pgf95 / pgcc (11.10) в системе Opteron: # 1 и # 2 - самые быстрые (быстрее, чем ifort на ~ 20%), затем # 6, # 8, # 7 (в этом порядке). pgf95 был быстрее, чем ifort для всех ваших кодов fortran, а icpc был быстрее, чем pgcpp для всех C - я должен отметить, что для своих вещей я обычно нахожу ifort быстрее, даже в той же системе AMD.
Laxxy

Ответы:

12

Прежде всего, спасибо за размещение этого вопроса / задачи! Как заявление об отказе от ответственности, я - нативный программист на Си с некоторым опытом работы на Фортране, и чувствую себя как дома в Си, поэтому я сосредоточусь только на улучшении версии Си. Я приглашаю всех хаков Фортрана, чтобы они тоже пошли!

Просто чтобы напомнить новичкам о том, что это такое: основная предпосылка в этом потоке заключалась в том, что gcc / fortran и icc / ifort должны, поскольку они имеют одинаковые серверные части соответственно, генерировать эквивалентный код для одной и той же (семантически идентичной) программы, независимо от того, это быть в C или Fortran. Качество результата зависит только от качества соответствующих реализаций.

Я немного поиграл с кодом и на своем компьютере (ThinkPad 201x, Intel Core i5 M560, 2,67 ГГц), используя gcc4.6.1 и следующие флаги компилятора:

GCCFLAGS= -O3 -g -Wall -msse2 -march=native -funroll-loops -ffast-math -fomit-frame-pointer -fstrict-aliasing

Я также пошел дальше и написал SIM-векторизованную версию C ++ на C-языке spectral_norm_vec.c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/* Define the generic vector type macro. */  
#define vector(elcount, type)  __attribute__((vector_size((elcount)*sizeof(type)))) type

double Ac(int i, int j)
{
    return 1.0 / ((i+j) * (i+j+1)/2 + i+1);
}

double dot_product2(int n, double u[], double v[])
{
    double w;
    int i;
    union {
        vector(2,double) v;
        double d[2];
        } *vu = u, *vv = v, acc[2];

    /* Init some stuff. */
    acc[0].d[0] = 0.0; acc[0].d[1] = 0.0;
    acc[1].d[0] = 0.0; acc[1].d[1] = 0.0;

    /* Take in chunks of two by two doubles. */
    for ( i = 0 ; i < (n/2 & ~1) ; i += 2 ) {
        acc[0].v += vu[i].v * vv[i].v;
        acc[1].v += vu[i+1].v * vv[i+1].v;
        }
    w = acc[0].d[0] + acc[0].d[1] + acc[1].d[0] + acc[1].d[1];

    /* Catch leftovers (if any) */
    for ( i = n & ~3 ; i < n ; i++ )
        w += u[i] * v[i];

    return w;

}

void matmul2(int n, double v[], double A[], double u[])
{
    int i, j;
    union {
        vector(2,double) v;
        double d[2];
        } *vu = u, *vA, vi;

    bzero( u , sizeof(double) * n );

    for (i = 0; i < n; i++) {
        vi.d[0] = v[i];
        vi.d[1] = v[i];
        vA = &A[i*n];
        for ( j = 0 ; j < (n/2 & ~1) ; j += 2 ) {
            vu[j].v += vA[j].v * vi.v;
            vu[j+1].v += vA[j+1].v * vi.v;
            }
        for ( j = n & ~3 ; j < n ; j++ )
            u[j] += A[i*n+j] * v[i];
        }

}


void matmul3(int n, double A[], double v[], double u[])
{
    int i;

    for (i = 0; i < n; i++)
        u[i] = dot_product2( n , &A[i*n] , v );

}

void AvA(int n, double A[], double v[], double u[])
{
    double tmp[n] __attribute__ ((aligned (16)));
    matmul3(n, A, v, tmp);
    matmul2(n, tmp, A, u);
}


double spectral_game(int n)
{
    double *A;
    double u[n] __attribute__ ((aligned (16)));
    double v[n] __attribute__ ((aligned (16)));
    int i, j;

    /* Aligned allocation. */
    /* A = (double *)malloc(n*n*sizeof(double)); */
    if ( posix_memalign( (void **)&A , 4*sizeof(double) , sizeof(double) * n * n ) != 0 ) {
        printf( "spectral_game:%i: call to posix_memalign failed.\n" , __LINE__ );
        abort();
        }


    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            A[i*n+j] = Ac(i, j);
        }
    }


    for (i = 0; i < n; i++) {
        u[i] = 1.0;
    }
    for (i = 0; i < 10; i++) {
        AvA(n, A, u, v);
        AvA(n, A, v, u);
    }
    free(A);
    return sqrt(dot_product2(n, u, v) / dot_product2(n, v, v));
}

int main(int argc, char *argv[]) {
    int i, N = ((argc >= 2) ? atoi(argv[1]) : 2000);
    for ( i = 0 ; i < 10 ; i++ )
        printf("%.9f\n", spectral_game(N));
    return 0;
}

Все три версии были скомпилированы с одинаковыми флагами и одинаковой gccверсией. Обратите внимание, что я обернул вызов основной функции в цикле с 0..9, чтобы получить более точные значения времени.

$ time ./spectral_norm6 5500
1.274224153
...
real    0m22.682s
user    0m21.113s
sys 0m1.500s

$ time ./spectral_norm7 5500
1.274224153
...
real    0m21.596s
user    0m20.373s
sys 0m1.132s

$ time ./spectral_norm_vec 5500
1.274224153
...
real    0m21.336s
user    0m19.821s
sys 0m1.444s

Таким образом, с «лучшими» флагами компилятора версия C ++ превосходит версию Fortran, а векторизованные циклы с ручным кодированием обеспечивают лишь незначительное улучшение. Беглый взгляд на ассемблер для версии C ++ показывает, что основные циклы также были векторизованы, хотя и развернуты более агрессивно.

Я также взглянул на ассемблер, сгенерированный gfortran и вот большой сюрприз: нет векторизации. Я связываю тот факт, что это только незначительно медленнее с проблемой ограничения пропускной способности, по крайней мере, в моей архитектуре. Для каждого умножения матрицы пройдено 230 МБ данных, что в значительной степени перекрывает все уровни кэша. Если вы используете меньшее входное значение, например100 , различия в производительности значительно возрастут.

В качестве дополнительного примечания, вместо того, чтобы зацикливаться на флагах векторизации, выравнивания и компилятора, наиболее очевидной оптимизацией будет вычисление первых нескольких итераций в арифметике с одинарной точностью, пока мы не получим ~ 8 цифр результата. Инструкции одинарной точности не только быстрее, но и объем памяти, который необходимо перемещать, также уменьшается вдвое.

Pedro
источник
Большое спасибо за ваше время! Я надеялся, что ты ответишь. :) Итак, сначала я обновил Makefile, чтобы использовать ваши флаги. Затем я поместил ваш C-код как spectral_norm8.c и обновил README. Я обновил тайминги на моей машине ( github.com/certik/spectral_norm/wiki/Timings ) и, как вы можете видеть, флаги компилятора не делали версию C быстрее на моей машине (т.е. gfortran все еще побеждает), но ваша SIMD-векторизация версия бьет гфортран.
Ондржей Чертик
@ OndřejČertík: Просто из любопытства, какая версия gcc/ gfortranвы используете? В предыдущих темах разные версии давали существенно разные результаты.
Педро
Я использую 4.6.1-9ubuntu3. У вас есть доступ к компиляторам Intel? Мой опыт работы с gfortran заключается в том, что иногда он (пока) не производит оптимальный код. IFort обычно делает.
Ондржей Чертик
1
@ OndřejČertík: Теперь результаты имеют больше смысла! Я упустил из виду, что matmul2в версии на Фортране это семантически эквивалентно matmul3моей версии на Си. Две версии на самом деле теперь одинаковы и, следовательно, gcc/ gfortran должны давать одинаковые результаты для обоих, например, ни один интерфейс / язык не лучше, чем другой в этом случае. gccпросто имеет то преимущество, что мы можем использовать векторизованные инструкции, если захотим.
Педро
1
@ cjordan1: я решил использовать vector_sizeатрибут для того, чтобы сделать код независимым от платформы, то есть, используя этот синтаксис, gccдолжен иметь возможность генерировать векторизованный код для других платформ, например, с использованием AltiVec в архитектуре IBM Power.
Педро
7

Ответ user389 был удален, но позвольте мне заявить, что я твердо нахожусь в его лагере: я не вижу того, что мы узнаем, сравнивая микропроцессоры на разных языках. Меня не удивляет, что C и Fortran показывают примерно одинаковую производительность в этом тесте, учитывая, насколько он короткий. Но эталонный тест также скучен, поскольку его легко можно записать на обоих языках в пару десятков строк. С точки зрения программного обеспечения это не типичный случай: мы должны заботиться о программном обеспечении, содержащем 10000 или 100000 строк кода, и о том, как это делают компиляторы. Конечно, в этом масштабе быстро обнаружатся другие вещи: этот язык A требует 10 000 строк, а язык B требует 50 000. Или наоборот, в зависимости от того, что вы хотите сделать. И вдруг это

Другими словами, для меня не имеет большого значения, что, возможно, мое приложение могло бы быть на 50% быстрее, если бы я разработал его в Fortran 77, если бы вместо этого мне потребовалось всего 1 месяц, чтобы заставить его работать правильно, в то время как это заняло бы 3 месяца. в F77. Проблема с этим вопросом заключается в том, что он фокусируется на аспекте (отдельных ядрах), который, на мой взгляд, не имеет отношения к практике.

Вольфганг Бангерт
источник
Согласовано. Что бы это ни стоило, кроме очень-очень незначительных правок (-3 символа, +9 символов), я согласился с основным настроением его ответа. Насколько я знаю, дебаты о компиляторе C ++ / C / Fortran имеют значение только тогда, когда исчерпаны все возможные пути повышения производительности, поэтому для 99,9% людей эти сравнения не имеют значения. Я не нахожу эту дискуссию особенно поучительной, но я знаю, по крайней мере, одного человека на сайте, который может подтвердить выбор Fortran вместо C и C ++ по соображениям производительности, поэтому я не могу сказать, что он абсолютно бесполезен.
Джефф Оксберри
4
Я согласен с вашей основной точкой, но я до сих пор считаю , что эта дискуссия полезна , поскольку есть есть много людей , которые там до сих пор почему - то полагают , что есть какая - то магия , что делает один язык «быстрее» , чем другие, несмотря на использовании идентичного компилятора движки. Я участвую в этих дебатах в основном, чтобы попытаться развеять этот миф. Что касается методологии, то здесь нет «репрезентативного случая», и, на мой взгляд, хорошо бы взять что-то столь же простое, как умножение матрицы на вектор, поскольку это дает компиляторам достаточно места, чтобы показать, что они могут делать или нет.
Педро
@ GeoffOxberry: Конечно, вы всегда найдете людей, которые используют один язык, а не другой, для более или менее четко сформулированных и аргументированных причин. Мой вопрос, однако, заключается в том, насколько бы быстрым был бы Фортран, если бы использовались структуры данных, которые появляются, скажем, в неструктурированных, адаптивных сетках с конечными элементами. Помимо того, что это было бы неудобно для реализации на Фортране (каждый, кто реализует это на C ++, активно использует STL), действительно ли Фортран будет быстрее для такого рода кода, в котором нет узких циклов, много косвенных обращений, много ifs?
Вольфганг Бангерт
@WolfgangBangerth: Как я уже сказал в своем первом комментарии, я согласен с вами и с пользователем 389 (Джонатан Дурси), поэтому задавать мне этот вопрос бессмысленно. Тем не менее, я хотел бы пригласить всех , кто делает верить , что выбор языка ( в том числе C ++ / C / Fortran) имеет важное значение для выполнения в их применении , чтобы ответить на ваш вопрос. К сожалению, я подозреваю, что такого рода дебаты могут иметь место для версий компилятора.
Джефф Оксберри
@ GeoffOxberry: Да, и я, очевидно, не имел в виду, что вам нужно было ответить на этот вопрос.
Вольфганг Бангерт
5

Оказывается, я могу писать код на Python (используя numpy для выполнения операций BLAS) быстрее, чем код на Fortran, скомпилированный с помощью моего системного компилятора gfortran.

$ gfortran -o sn6a sn6a.f90 -O3 -march=native
    
    $ ./sn6a 5500
1.274224153
1.274224153
1.274224153
   1.9640001      sec per iteration

$ python ./foo1.py
1.27422415279
1.27422415279
1.27422415279
1.20618661245 sec per iteration

foo1.py:

import numpy
import scipy.linalg
import timeit

def specNormDot(A,n):
    u = numpy.ones(n)
    v = numpy.zeros(n)

    for i in xrange(10):
        v  = numpy.dot(numpy.dot(A,u),A)
        u  = numpy.dot(numpy.dot(A,v),A)

    print numpy.sqrt(numpy.vdot(u,v)/numpy.vdot(v,v))

    return

n = 5500

ii, jj = numpy.meshgrid(numpy.arange(1,n+1), numpy.arange(1,n+1))
A  = (1./((ii+jj-2.)*(ii+jj-1.)/2. + ii))

t = timeit.Timer("specNormDot(A,n)", "from __main__ import specNormDot,A,n")
ntries = 3

print t.timeit(ntries)/ntries, "sec per iteration"

и sn6a.f90, очень слегка измененный spectral_norm6.f90:

program spectral_norm6
! This uses spectral_norm3 as a starting point, but does not use the
! Fortrans
! builtin matmul and dotproduct (to make sure it does not call some
! optimized
! BLAS behind the scene).
implicit none

integer, parameter :: dp = kind(0d0)
real(dp), allocatable :: A(:, :), u(:), v(:)
integer :: i, j, n
character(len=6) :: argv
integer :: calc, iter
integer, parameter :: niters=3

call get_command_argument(1, argv)
read(argv, *) n

allocate(u(n), v(n), A(n, n))
do j = 1, n
    do i = 1, n
        A(i, j) = Ac(i, j)
    end do
end do

call tick(calc)

do iter=1,niters
    u = 1
    do i = 1, 10
        v = AvA(A, u)
        u = AvA(A, v)
    end do

    write(*, "(f0.9)") sqrt(dot_product2(u, v) / dot_product2(v, v))
enddo

print *, tock(calc)/niters, ' sec per iteration'

contains

pure real(dp) function Ac(i, j) result(r)
integer, intent(in) :: i, j
r = 1._dp / ((i+j-2) * (i+j-1)/2 + i)
end function

pure function matmul2(v, A) result(u)
! Calculates u = matmul(v, A), but much faster (in gfortran)
real(dp), intent(in) :: v(:), A(:, :)
real(dp) :: u(size(v))
integer :: i
do i = 1, size(v)
    u(i) = dot_product2(A(:, i), v)
end do
end function

pure real(dp) function dot_product2(u, v) result(w)
! Calculates w = dot_product(u, v)
real(dp), intent(in) :: u(:), v(:)
integer :: i
w = 0
do i = 1, size(u)
    w = w + u(i)*v(i)
end do
end function

pure function matmul3(A, v) result(u)
! Calculates u = matmul(v, A), but much faster (in gfortran)
real(dp), intent(in) :: v(:), A(:, :)
real(dp) :: u(size(v))
integer :: i, j
u = 0
do j = 1, size(v)
    do i = 1, size(v)
        u(i) = u(i) + A(i, j)*v(j)
    end do
end do
end function

pure function AvA(A, v) result(u)
! Calculates u = matmul2(matmul3(A, v), A)
! In gfortran, this function is sligthly faster than calling
! matmul2(matmul3(A, v), A) directly.
real(dp), intent(in) :: v(:), A(:, :)
real(dp) :: u(size(v))
u = matmul2(matmul3(A, v), A)
end function

subroutine tick(t)
    integer, intent(OUT) :: t

    call system_clock(t)
end subroutine tick

! returns time in seconds from now to time described by t 
real function tock(t)
    integer, intent(in) :: t
    integer :: now, clock_rate

    call system_clock(now,clock_rate)

    tock = real(now - t)/real(clock_rate)
end function tock
end program
Арон Ахмадия
источник
1
Я полагаю, язык в щеке?
Роберт Харви
-1 за то, что не ответил на вопрос, но я думаю, ты уже знаешь это.
Педро
Интересно, какую версию gfortran вы использовали, и тестировали ли вы код C, доступный в репозитории, с флагами Педро?
Арон Ахмадиа
1
На самом деле, я думаю, что теперь все стало понятнее, если предположить, что вы не саркастичны.
Роберт Харви
1
Поскольку этот пост, а также ни один из других вопросов или постов, не редактируются Ароном таким образом, чтобы лучше соответствовать его мнению, несмотря на то, что весь мой смысл заключается в том, что все посты должны быть помечены именно таким «эти результаты не имеют смысла» предостережения, я просто удаляю это.
3

Проверял это с компиляторами Intel. С 11.1 (-быстрым, подразумевающим -O3) и с 12.0 (-O2) самыми быстрыми являются 1,2,6,7 и 8 (т. Е. «Простейшие» коды Фортрана и C, а также C с векторным векторизацией) - они неотличимы друг от друга на ~ 1,5 с. Тесты 3 и 5 (с массивом как функцией) медленнее; # 4 Я не мог скомпилировать.

Примечательно, что при компиляции с 12.0 и -O3, а не с -O2, первые 2 («простейших») кода на Фортране замедляются на LOT (1,5 -> 10,2 с) - это не первый раз, когда я вижу что-то подобное это, но это может быть самым драматичным примером. Если это все еще относится к текущей версии, я думаю, что было бы неплохо сообщить об этом в Intel, поскольку в их довольно простом случае явно что-то идет не так с их оптимизацией.

В противном случае я согласен с Джонатаном, что это не особенно информативное упражнение :)

laxxy
источник
Спасибо за проверку! Это подтверждает мой опыт, что гфортран еще не полностью созрел, потому что по какой-то причине операция с матмулами идет медленно. Поэтому для меня вывод состоит в том, чтобы просто использовать matmul и сохранить код на Фортране простым.
Ондржей Чертик
С другой стороны, я думаю, что gfortran имеет опцию командной строки для автоматического преобразования всех вызовов matmul () в вызовы BLAS (возможно, также dot_product (), не уверен). Никогда не пробовал, хотя.
лакси