Podoba mi się niektóre funkcje D, ale czy byłby zainteresowany, gdyby miały one karę w czasie wykonywania?

Dla porównania zaimplementowałem prosty program, który oblicza iloczyn skalarny wielu krótkich wektorów zarówno w C ++, jak iw D. Wynik jest zaskakujący:

• D: 18,9 s [patrz poniżej, aby zapoznać się z końcowym czasem pracy]
• C ++: 3,8 s

Czy C ++ jest naprawdę prawie pięć razy szybszy, czy popełniłem błąd w programie D?

Skompilowałem C ++ z g ++ -O3 (gcc-snapshot 2011-02-19) i D z dmd -O (dmd 2.052) na umiarkowanym, niedawnym pulpicie Linux. Wyniki są powtarzalne w kilku seriach, a odchylenia standardowe są pomijalne.

Tutaj program w C ++:

#include <iostream>
#include <random>
#include <chrono>
#include <string>

#include <vector>
#include <array>

typedef std::chrono::duration<long, std::ratio<1, 1000>> millisecs;
template <typename _T>
long time_since(std::chrono::time_point<_T>& time) {
      long tm = std::chrono::duration_cast<millisecs>( std::chrono::system_clock::now() - time).count();
  time = std::chrono::system_clock::now();
  return tm;
}

const long N = 20000;
const int size = 10;

typedef int value_type;
typedef long long result_type;
typedef std::vector<value_type> vector_t;
typedef typename vector_t::size_type size_type;

inline value_type scalar_product(const vector_t& x, const vector_t& y) {
  value_type res = 0;
  size_type siz = x.size();
  for (size_type i = 0; i < siz; ++i)
    res += x[i] * y[i];
  return res;
}

int main() {
  auto tm_before = std::chrono::system_clock::now();

  // 1. allocate and fill randomly many short vectors
  vector_t* xs = new vector_t [N];
  for (int i = 0; i < N; ++i) {
    xs[i] = vector_t(size);
      }
  std::cerr << "allocation: " << time_since(tm_before) << " ms" << std::endl;

  std::mt19937 rnd_engine;
  std::uniform_int_distribution<value_type> runif_gen(-1000, 1000);
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < size; ++j)
      xs[i][j] = runif_gen(rnd_engine);
  std::cerr << "random generation: " << time_since(tm_before) << " ms" << std::endl;

  // 2. compute all pairwise scalar products:
  time_since(tm_before);
  result_type avg = 0;
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j) 
      avg += scalar_product(xs[i], xs[j]);
  avg = avg / N*N;
  auto time = time_since(tm_before);
  std::cout << "result: " << avg << std::endl;
  std::cout << "time: " << time << " ms" << std::endl;
}

A tutaj wersja D:

import std.stdio;
import std.datetime;
import std.random;

const long N = 20000;
const int size = 10;

alias int value_type;
alias long result_type;
alias value_type[] vector_t;
alias uint size_type;

value_type scalar_product(const ref vector_t x, const ref vector_t y) {
  value_type res = 0;
  size_type siz = x.length;
  for (size_type i = 0; i < siz; ++i)
    res += x[i] * y[i];
  return res;
}

int main() {   
  auto tm_before = Clock.currTime();

  // 1. allocate and fill randomly many short vectors
  vector_t[] xs;
  xs.length = N;
  for (int i = 0; i < N; ++i) {
    xs[i].length = size;
  }
  writefln("allocation: %i ", (Clock.currTime() - tm_before));
  tm_before = Clock.currTime();

  for (int i = 0; i < N; ++i)
    for (int j = 0; j < size; ++j)
      xs[i][j] = uniform(-1000, 1000);
  writefln("random: %i ", (Clock.currTime() - tm_before));
  tm_before = Clock.currTime();

  // 2. compute all pairwise scalar products:
  result_type avg = cast(result_type) 0;
  for (int i = 0; i < N; ++i)
    for (int j = 0; j < N; ++j) 
      avg += scalar_product(xs[i], xs[j]);
  avg = avg / N*N;
  writefln("result: %d", avg);
  auto time = Clock.currTime() - tm_before;
  writefln("scalar products: %i ", time);

  return 0;
}

Aby włączyć wszystkie optymalizacje i wyłączyć wszystkie testy bezpieczeństwa, skompiluj swój program D z następującymi flagami DMD:

-O -inline -release -noboundscheck

EDYCJA : Próbowałem twoich programów z g ++, dmd i gdc. dmd pozostaje w tyle, ale gdc osiąga wydajność bardzo zbliżoną do g ++. Użyłem wiersza poleceń gdmd -O -release -inline(gdmd to opakowanie wokół gdc, które akceptuje opcje dmd).

Patrząc na listę asemblera, wygląda na to, że ani dmd, ani gdc nie są wbudowane scalar_product, ale g ++ / gdc emitowało instrukcje MMX, więc mogą one automatycznie wektoryzować pętlę.

Jedną wielką rzeczą, która spowalnia D, jest kiepska implementacja czyszczenia pamięci. Testy porównawcze, które nie obciążają zbytnio GC, pokażą bardzo podobną wydajność do kodu C i C ++ skompilowanego z tym samym zapleczem kompilatora. Testy, które silnie obciążają GC, pokażą, że D radzi sobie fatalnie. Zapewniamy jednak, że jest to pojedynczy (choć poważny) problem z jakością wdrożenia, a nie gwarancja powolności. Ponadto D daje możliwość rezygnacji z GC i dostrojenia zarządzania pamięcią w bitach o krytycznym znaczeniu dla wydajności, jednocześnie używając go w mniej krytycznych dla wydajności 95% kodu.

Mam włożyć trochę wysiłku w poprawę wydajności GC ostatnio i wyniki były dość dramatyczne, przynajmniej na syntetycznych benchmarków. Miejmy nadzieję, że te zmiany zostaną uwzględnione w jednej z kilku następnych wersji i złagodzą problem.

To bardzo pouczający wątek, dziękuję za całą pracę OP i pomocnikom.

Jedna uwaga - ten test nie ocenia ogólnej kwestii kary za abstrakcję / funkcję ani nawet jakości zaplecza. Koncentruje się na praktycznie jednej optymalizacji (optymalizacji pętli). Myślę, że można uczciwie powiedzieć, że backend gcc jest nieco bardziej wyrafinowany niż dmd, ale błędem byłoby zakładać, że luka między nimi jest tak duża dla wszystkich zadań.

Zdecydowanie wydaje się, że jest to problem z jakością wdrożenia.

Przeprowadziłem kilka testów z kodem OP i wprowadziłem kilka zmian. W rzeczywistości D działało szybciej dla LDC / clang ++, działając przy założeniu, że tablice muszą być przydzielane dynamicznie ( xsi powiązane skalary). Poniżej znajdziesz kilka liczb.

Pytania do PO

Czy jest zamierzone, aby to samo ziarno było używane w każdej iteracji C ++, a nie w przypadku D?

Ustawiać

Poprawiłem oryginalne źródło D (dubbing scalar.d), aby było przenośne między platformami. Wymagało to jedynie zmiany typu liczb używanych do uzyskania dostępu i modyfikacji rozmiaru tablic.

Następnie wprowadziłem następujące zmiany:

• Używane uninitializedArraydo unikania domyślnych initów dla skalarów w xs (prawdopodobnie zrobiło największą różnicę). Jest to ważne, ponieważ D normalnie domyślnie inicjuje wszystko po cichu, czego C ++ nie robi.

• Wykreślono kod drukowania i zastąpiono writeflngowriteln

• Zmieniono przywóz na selektywny
• Użyto operatora pow ( ^^) zamiast ręcznego mnożenia na ostatnim etapie obliczania średniej
• Usunięto size_typei odpowiednio zastąpiono nowym index_typealiasem

... w wyniku czego scalar2.cpp( pastebin ):

    import std.stdio : writeln;
    import std.datetime : Clock, Duration;
    import std.array : uninitializedArray;
    import std.random : uniform;

    alias result_type = long;
    alias value_type = int;
    alias vector_t = value_type[];
    alias index_type = typeof(vector_t.init.length);// Make index integrals portable - Linux is ulong, Win8.1 is uint

    immutable long N = 20000;
    immutable int size = 10;

    // Replaced for loops with appropriate foreach versions
    value_type scalar_product(in ref vector_t x, in ref vector_t y) { // "in" is the same as "const" here
      value_type res = 0;
      for(index_type i = 0; i < size; ++i)
        res += x[i] * y[i];
      return res;
    }

    int main() {
      auto tm_before = Clock.currTime;
      auto countElapsed(in string taskName) { // Factor out printing code
        writeln(taskName, ": ", Clock.currTime - tm_before);
        tm_before = Clock.currTime;
      }

      // 1. allocate and fill randomly many short vectors
      vector_t[] xs = uninitializedArray!(vector_t[])(N);// Avoid default inits of inner arrays
      for(index_type i = 0; i < N; ++i)
        xs[i] = uninitializedArray!(vector_t)(size);// Avoid more default inits of values
      countElapsed("allocation");

      for(index_type i = 0; i < N; ++i)
        for(index_type j = 0; j < size; ++j)
          xs[i][j] = uniform(-1000, 1000);
      countElapsed("random");

      // 2. compute all pairwise scalar products:
      result_type avg = 0;
      for(index_type i = 0; i < N; ++i)
        for(index_type j = 0; j < N; ++j)
          avg += scalar_product(xs[i], xs[j]);
      avg /= N ^^ 2;// Replace manual multiplication with pow operator
      writeln("result: ", avg);
      countElapsed("scalar products");

      return 0;
    }

Po przetestowaniu scalar2.d(gdzie priorytetami optymalizacja do prędkości), z ciekawość I otrzymuje się pętle mainz foreachekwiwalentów i nazwaliśmy je scalar3.d( wklejarka )

    import std.stdio : writeln;
    import std.datetime : Clock, Duration;
    import std.array : uninitializedArray;
    import std.random : uniform;

    alias result_type = long;
    alias value_type = int;
    alias vector_t = value_type[];
    alias index_type = typeof(vector_t.init.length);// Make index integrals portable - Linux is ulong, Win8.1 is uint

    immutable long N = 20000;
    immutable int size = 10;

    // Replaced for loops with appropriate foreach versions
    value_type scalar_product(in ref vector_t x, in ref vector_t y) { // "in" is the same as "const" here
      value_type res = 0;
      for(index_type i = 0; i < size; ++i)
        res += x[i] * y[i];
      return res;
    }

    int main() {
      auto tm_before = Clock.currTime;
      auto countElapsed(in string taskName) { // Factor out printing code
        writeln(taskName, ": ", Clock.currTime - tm_before);
        tm_before = Clock.currTime;
      }

      // 1. allocate and fill randomly many short vectors
      vector_t[] xs = uninitializedArray!(vector_t[])(N);// Avoid default inits of inner arrays
      foreach(ref x; xs)
        x = uninitializedArray!(vector_t)(size);// Avoid more default inits of values
      countElapsed("allocation");

      foreach(ref x; xs)
        foreach(ref val; x)
          val = uniform(-1000, 1000);
      countElapsed("random");

      // 2. compute all pairwise scalar products:
      result_type avg = 0;
      foreach(const ref x; xs)
        foreach(const ref y; xs)
          avg += scalar_product(x, y);
      avg /= N ^^ 2;// Replace manual multiplication with pow operator
      writeln("result: ", avg);
      countElapsed("scalar products");

      return 0;
    }

Skompilowałem każdy z tych testów przy użyciu kompilatora opartego na LLVM, ponieważ LDC wydaje się być najlepszą opcją dla kompilacji D pod względem wydajności. Na mojej instalacji Arch Linux x86_64 użyłem następujących pakietów:

• clang 3.6.0-3
• ldc 1:0.15.1-4
• dtools 2.067.0-2

Użyłem następujących poleceń do skompilowania każdego:

• C ++: clang++ scalar.cpp -o"scalar.cpp.exe" -std=c++11 -O3
• RE: rdmd --compiler=ldc2 -O3 -boundscheck=off <sourcefile>

Wyniki

Wyniki ( zrzut ekranu nieprzetworzonego wyjścia konsoli ) każdej wersji źródła w następujący sposób:

1. scalar.cpp (oryginalny C ++):

   allocation: 2 ms
   
   random generation: 12 ms
   
   result: 29248300000
   
   time: 2582 ms
   

   C ++ ustawia standard na 2582 ms .

2. scalar.d (zmodyfikowane źródło OP):

   allocation: 5 ms, 293 μs, and 5 hnsecs 
   
   random: 10 ms, 866 μs, and 4 hnsecs 
   
   result: 53237080000
   
   scalar products: 2 secs, 956 ms, 513 μs, and 7 hnsecs 
   

   Ten pobiegł za ~ 2957 ms . Wolniej niż implementacja C ++, ale nie za dużo.

3. scalar2.d (zmiana typu indeksu / długości i niezainicjowana optymalizacja tablicy):

   allocation: 2 ms, 464 μs, and 2 hnsecs
   
   random: 5 ms, 792 μs, and 6 hnsecs
   
   result: 59
   
   scalar products: 1 sec, 859 ms, 942 μs, and 9 hnsecs
   

   Innymi słowy, ~ 1860 ms . Jak dotąd jest to na czele.

4. scalar3.d (foreaches):

   allocation: 2 ms, 911 μs, and 3 hnsecs
   
   random: 7 ms, 567 μs, and 8 hnsecs
   
   result: 189
   
   scalar products: 2 secs, 182 ms, and 366 μs
   

   ~ 2182 ms jest wolniejsze niż scalar2.d, ale szybsze niż wersja C ++.

Wniosek

Dzięki poprawnym optymalizacjom implementacja D faktycznie poszła szybciej niż jej równoważna implementacja C ++ przy użyciu dostępnych kompilatorów opartych na LLVM. Obecna luka między D i C ++ dla większości aplikacji wydaje się wynikać jedynie z ograniczeń obecnych implementacji.

dmd jest referencyjną implementacją języka i dlatego większość pracy jest wkładana do frontendu, aby naprawić błędy, zamiast optymalizować backend.

"in" jest szybsze w twoim przypadku, ponieważ używasz tablic dynamicznych, które są typami referencyjnymi. Za pomocą ref wprowadzasz inny poziom pośrednictwa (który jest zwykle używany do zmiany samej tablicy, a nie tylko zawartości).

Wektory są zwykle implementowane w strukturach, w których const ref ma sens. Zobacz smallptD vs. smallpt, aby zapoznać się z rzeczywistym przykładem obejmującym mnóstwo operacji wektorowych i losowości.

Zwróć uwagę, że 64-bitowe również mogą mieć znaczenie. Kiedyś przegapiłem to, że na x64 gcc kompiluje 64-bitowy kod, podczas gdy dmd nadal ma domyślne ustawienie 32 (zmieni się, gdy dojrzeje 64-bitowy kod). Nastąpiło niezwykłe przyspieszenie z "dmd -m64 ...".

To, czy C ++ czy D jest szybsze, prawdopodobnie zależy w dużym stopniu od tego, co robisz. Wydaje mi się, że porównując dobrze napisany C ++ z dobrze napisanym kodem D, generalnie miałyby one podobną szybkość lub C ++ byłyby szybsze, ale to, co udaje się zoptymalizować konkretny kompilator, może mieć duży wpływ całkowicie poza językiem samo.

Jednak jest kilka przypadków, w których D ma duże szanse na pokonanie C ++ pod względem szybkości. Głównym, który przychodzi na myśl, byłoby przetwarzanie ciągów. Dzięki możliwościom cięcia tablic D, łańcuchy (i tablice w ogóle) mogą być przetwarzane znacznie szybciej niż w C ++. W przypadku D1 procesor XML Tango jest niezwykle szybki , głównie dzięki możliwościom dzielenia tablic D (i miejmy nadzieję, że D2 będzie miał podobnie szybki parser XML, gdy ten, nad którym obecnie pracujemy dla Phobosa, zostanie ukończony). Więc ostatecznie to, czy D czy C ++ będzie szybsze, będzie bardzo zależne od tego, co robisz.

Teraz jestem zaskoczony, że widzisz taką różnicę w szybkości w tym konkretnym przypadku, ale jest to coś, co spodziewałbym się poprawić wraz z poprawą dmd. Użycie gdc może dać lepsze wyniki i prawdopodobnie byłoby bliższym porównaniem samego języka (a nie zaplecza), biorąc pod uwagę, że jest on oparty na gcc. Ale nie zdziwiłbym się wcale, gdyby można było zrobić wiele rzeczy, aby przyspieszyć kod generowany przez dmd. Nie sądzę, żeby było wiele wątpliwości, że gcc jest w tym momencie bardziej dojrzałe niż dmd. Optymalizacje kodu są jednym z głównych owoców dojrzałości kodu.

Ostatecznie liczy się to, jak dobrze dmd działa w twojej konkretnej aplikacji, ale zgadzam się, że zdecydowanie byłoby miło wiedzieć, jak dobrze C ++ i D porównują się w ogóle. Teoretycznie powinny być prawie takie same, ale tak naprawdę zależy to od implementacji. Myślę, że aby naprawdę sprawdzić, jak dobrze te dwa obecnie porównują, potrzebny byłby obszerny zestaw wzorców.

Możesz napisać kod C to D, więc o ile jest szybszy, będzie to zależeć od wielu rzeczy:

• Jakiego kompilatora używasz
• Jakiej funkcji używasz
• jak agresywnie optymalizujesz

Różnice w pierwszym nie są sprawiedliwe. Drugi może dać C ++ przewagę, ponieważ ma mniej ciężkich funkcji. Trzeci jest zabawny: kod D pod pewnymi względami jest łatwiejszy do optymalizacji, ponieważ ogólnie jest łatwiejszy do zrozumienia. Ma również możliwość wykonywania dużego stopnia programowania generatywnego, umożliwiając takie rzeczy, jak rozwlekły i powtarzalny, ale szybki kod, który można napisać w krótszych formach.

Wydaje się, że problem z jakością wykonania. Na przykład, oto co testowałem z:

import std.datetime, std.stdio, std.random;

version = ManualInline;

immutable N = 20000;
immutable Size = 10;

alias int value_type;
alias long result_type;
alias value_type[] vector_type;

result_type scalar_product(in vector_type x, in vector_type y)
in
{
    assert(x.length == y.length);
}
body
{
    result_type result = 0;

    foreach(i; 0 .. x.length)
        result += x[i] * y[i];

    return result;
}

void main()
{   
    auto startTime = Clock.currTime();

    // 1. allocate vectors
    vector_type[] vectors = new vector_type[N];
    foreach(ref vec; vectors)
        vec = new value_type[Size];

    auto time = Clock.currTime() - startTime;
    writefln("allocation: %s ", time);
    startTime = Clock.currTime();

    // 2. randomize vectors
    foreach(ref vec; vectors)
        foreach(ref e; vec)
            e = uniform(-1000, 1000);

    time = Clock.currTime() - startTime;
    writefln("random: %s ", time);
    startTime = Clock.currTime();

    // 3. compute all pairwise scalar products
    result_type avg = 0;

    foreach(vecA; vectors)
        foreach(vecB; vectors)
        {
            version(ManualInline)
            {
                result_type result = 0;

                foreach(i; 0 .. vecA.length)
                    result += vecA[i] * vecB[i];

                avg += result;
            }
            else
            {
                avg += scalar_product(vecA, vecB);
            }
        }

    avg = avg / (N * N);

    time = Clock.currTime() - startTime;
    writefln("scalar products: %s ", time);
    writefln("result: %s", avg);
}

Z ManualInline definicją mam 28 sekund, ale bez 32. Więc kompilator nawet nie wstawia tej prostej funkcji, co, jak sądzę, jest jasne, że powinno.

(Moja linia poleceń to dmd -O -noboundscheck -inline -release ....)