Apakah C lebih lambat dari Fortran pada baku tembak norma spektral (menggunakan gcc, intel dan kompiler lain)?

Kesimpulannya di sini:

Seberapa jauh sebenarnya penyusun Fortran?

adalah gfortran dan gcc yang cepat untuk kode sederhana. Jadi saya ingin mencoba sesuatu yang lebih rumit. Saya mengambil contoh baku tembak norma spektral. Saya pertama-tama menghitung ulang matriks 2D A (:, :), dan kemudian menghitung norma. (Solusi ini tidak diperbolehkan pada baku tembak saya pikir.) Saya telah mengimplementasikan versi Fortran dan C. Ini kodenya:

https://github.com/certik/spectral_norm

Versi gfortran tercepat adalah spectral_norm2.f90 dan spectral_norm6.f90 (satu menggunakan matranul dan dot_prodp bawaan Fortran, yang lain mengimplementasikan kedua fungsi ini dalam kode - tanpa perbedaan kecepatan). Kode C / C ++ tercepat yang bisa saya tulis adalah spectral_norm7.cpp. Pengaturan waktu pada versi git 457d9d9 pada laptop saya adalah:

$ 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

Jadi versi gfortran sedikit lebih cepat. Mengapa demikian? Jika Anda mengirim permintaan tarik dengan implementasi C yang lebih cepat (atau hanya menempelkan kode), saya akan memperbarui repositori.

Di Fortran saya melewatkan array 2D, sedangkan di CI menggunakan array 1D. Jangan ragu untuk menggunakan array 2D atau cara lain yang Anda inginkan.

Mengenai kompiler, mari kita bandingkan gcc vs gfortran, icc vs ifort, dan sebagainya. (Berbeda dengan halaman shootout, yang membandingkan ifort vs gcc.)

Pembaruan : menggunakan versi 179dae2, yang meningkatkan matmul3 () dalam versi C saya, sekarang lebih cepat:

$ 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

Versi vektor Pedro di bawah ini lebih cepat:

$ time ./spectral_norm8 5500
1.274224153

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

Akhirnya, seperti yang dilaporkan laxxy di bawah ini untuk kompiler Intel, sepertinya tidak ada perbedaan besar di sana dan bahkan kode Fortran yang paling sederhana (spectral_norm1) adalah yang tercepat.

Pertama-tama, terima kasih telah mengirimkan pertanyaan / tantangan ini! Sebagai penafian, saya seorang programmer C asli dengan beberapa pengalaman Fortran, dan merasa paling nyaman di C, jadi dengan demikian, saya hanya akan fokus pada peningkatan versi C. Saya mengundang semua peretas Fortran untuk ikut serta!

Hanya untuk mengingatkan pendatang baru tentang apa ini: Premis dasar di utas ini adalah bahwa gcc / fortran dan icc / ifort harus, karena mereka masing-masing memiliki back-end yang sama, menghasilkan kode yang setara untuk program yang sama (identik secara semantik), terlepas dari itu berada di C atau Fortran. Kualitas hasil hanya tergantung pada kualitas implementasi masing-masing.

Saya bermain-main dengan kode sedikit, dan di komputer saya (ThinkPad 201x, Intel Core i5 M560, 2,67 GHz), menggunakan gcc4.6.1 dan flag kompiler berikut:

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

Saya juga pergi ke depan dan menulis versi C-bahasa SIMD-Vectorized dari C ++ code, 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;
}

Ketiga versi dikompilasi dengan bendera yang sama dan gccversi yang sama . Perhatikan bahwa saya membungkus panggilan fungsi utama dalam satu lingkaran dari 0..9 untuk mendapatkan pengaturan waktu yang lebih akurat.

$ 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

Jadi dengan flag kompiler "lebih baik", versi C ++ mengalahkan versi Fortran dan loop vektorisasi kode tangan hanya memberikan peningkatan marjinal. Pandangan cepat pada assembler untuk versi C ++ menunjukkan bahwa loop utama juga telah di-vektor-kan, meskipun tidak dikontrol lebih agresif.

Saya juga melihat assembler yang dihasilkan oleh gfortrandan inilah kejutan besar: tidak ada vektorisasi. Saya mengaitkan fakta bahwa hanya sedikit lebih lambat karena masalah terbatasnya bandwidth, setidaknya pada arsitektur saya. Untuk setiap perkalian matriks, data 230MB dilalui, yang cukup banyak menukar semua level cache. Jika Anda menggunakan nilai input yang lebih kecil, misalnya 100, perbedaan kinerja tumbuh secara signifikan.

Sebagai catatan tambahan, alih-alih terobsesi dengan vektorisasi, penjajaran, dan flag kompiler, optimasi yang paling jelas adalah menghitung beberapa iterasi pertama dalam aritmatika presisi tunggal, sampai kita memiliki ~ 8 digit hasilnya. Instruksi presisi tunggal tidak hanya lebih cepat, tetapi jumlah memori yang harus dipindahkan juga berkurang setengahnya.

jawaban user389 telah dihapus tetapi izinkan saya menyatakan bahwa saya dengan kuat di kampnya: Saya gagal melihat apa yang kita pelajari dengan membandingkan tolok ukur mikro dalam berbagai bahasa. Tidak terlalu mengejutkan bagi saya bahwa C dan Fortran mendapatkan kinerja yang hampir sama pada benchmark ini mengingat betapa pendeknya itu. Tetapi tolok ukur ini juga membosankan karena dapat dengan mudah ditulis dalam kedua bahasa dalam beberapa lusin baris. Dari sudut pandang perangkat lunak, itu bukan kasus representatif: kita harus peduli tentang perangkat lunak yang memiliki 10.000 atau 100.000 baris kode dan bagaimana kompiler melakukannya. Tentu saja, pada skala itu, seseorang akan dengan cepat menemukan hal-hal lain: bahwa bahasa A membutuhkan 10.000 baris sedangkan bahasa B membutuhkan 50.000. Atau sebaliknya, tergantung pada apa yang ingin Anda lakukan. Dan tiba-tiba '

Dengan kata lain, tidak masalah bagi saya bahwa mungkin aplikasi saya bisa 50% lebih cepat jika saya mengembangkannya di Fortran 77 jika sebaliknya hanya akan memakan waktu 1 bulan untuk menjalankannya dengan benar sementara itu akan memakan waktu 3 bulan dalam F77. Masalah dengan pertanyaan di sini adalah bahwa ia berfokus pada aspek (kernel individu) yang tidak relevan dalam praktik dalam pandangan saya.

Ternyata saya bisa menulis kode Python (menggunakan numpy untuk melakukan operasi BLAS) lebih cepat daripada kode Fortran yang dikompilasi dengan kompiler gfortran sistem saya.

$ 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"

dan sn6a.f90, spectral_norm6.f90 yang dimodifikasi dengan sangat ringan:

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

Memeriksa ini dengan kompiler Intel. Dengan 11.1 (-fast, menyiratkan -O3), dan dengan 12.0 (-O2) yang tercepat adalah 1,2,6,7, dan 8 (yaitu kode Fortran dan C "paling sederhana", dan C vektor tangan) - ini tidak bisa dibedakan satu sama lain di ~ 1.5s. Tes 3 dan 5 (dengan larik sebagai fungsi) lebih lambat; # 4 Saya tidak bisa mengkompilasi.

Cukup istimewa, jika mengkompilasi dengan 12.0 dan -O3, daripada -O2, 2 ("paling sederhana") pertama kode Fortran memperlambat BANYAK (1,5 -> 10,2 detik) - ini bukan pertama kalinya saya melihat sesuatu seperti ini, tapi ini mungkin contoh paling dramatis. Jika ini masih terjadi dalam rilis saat ini, saya pikir itu akan menjadi ide yang baik untuk melaporkannya ke Intel, karena jelas ada sesuatu yang salah dengan optimasi mereka dalam kasus yang agak sederhana ini.

Kalau tidak, saya setuju dengan Jonathan bahwa ini bukan latihan yang sangat informatif :)