Me gustan algunas características de D, pero ¿estaría interesado si vienen con una penalización de tiempo de ejecución?

Para comparar, implementé un programa simple que computa productos escalares de muchos vectores cortos tanto en C ++ como en D. El resultado es sorprendente:

• D: 18.9 s [ver abajo para el tiempo de ejecución final]
• C ++: 3.8 s

¿C ++ es realmente casi cinco veces más rápido o cometí un error en el programa D?

Compilé C ++ con g ++ -O3 (gcc-snapshot 2011-02-19) y D con dmd -O (dmd 2.052) en un escritorio Linux reciente moderado. Los resultados son reproducibles en varias ejecuciones y las desviaciones estándar son insignificantes.

Aquí el programa 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;
}

Y aquí la versión 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;
}

Para habilitar todas las optimizaciones y deshabilitar todas las comprobaciones de seguridad, compile su programa D con los siguientes indicadores DMD:

-O -inline -release -noboundscheck

EDITAR : he probado sus programas con g ++, dmd y gdc. dmd se queda atrás, pero gdc logra un rendimiento muy cercano a g ++. La línea de comandos que utilicé fue gdmd -O -release -inline(gdmd es un contenedor alrededor de gdc que acepta opciones dmd).

Mirando la lista del ensamblador, parece que ni dmd ni gdc están en línea scalar_product, pero g ++ / gdc emitió instrucciones MMX, por lo que podrían estar auto-vectorizando el bucle.

Una gran cosa que ralentiza D es una implementación de recolección de basura deficiente. Los puntos de referencia que no enfatizan demasiado el GC mostrarán un rendimiento muy similar al código C y C ++ compilado con el mismo backend del compilador. Los puntos de referencia que hacen mucho hincapié en el GC mostrarán que D funciona abismalmente. Sin embargo, tenga la seguridad de que este es un problema único (aunque grave) de calidad de implementación, no una garantía de lentitud. Además, D le da la posibilidad de optar por no usar GC y ajustar la administración de memoria en bits críticos para el rendimiento, mientras lo sigue utilizando en el 95% menos crítico para su código.

Últimamente me he esforzado por mejorar el rendimiento de GC y los resultados han sido bastante dramáticos, al menos en puntos de referencia sintéticos. Esperemos que estos cambios se integren en uno de los próximos lanzamientos y mitiguen el problema.

Este es un hilo muy instructivo, gracias por todo el trabajo para el OP y los ayudantes.

Una nota: esta prueba no evalúa la cuestión general de la abstracción / penalización de características o incluso la de la calidad del backend. Se centra en prácticamente una optimización (optimización de bucle). Creo que es justo decir que el backend de gcc es algo más refinado que el de dmd, pero sería un error suponer que la brecha entre ellos es tan grande para todas las tareas.

Definitivamente parece un problema de calidad de implementación.

Ejecuté algunas pruebas con el código del OP e hice algunos cambios. De hecho, obtuve D yendo más rápido para LDC / clang ++, operando bajo el supuesto de que las matrices deben asignarse dinámicamente ( xsy escalares asociados). Vea a continuación algunos números.

Preguntas para el OP

¿Es intencional que se use la misma semilla para cada iteración de C ++, mientras que no es así para D?

Preparar

He ajustado la fuente D original (doblada scalar.d) para que sea portátil entre plataformas. Esto solo implicaba cambiar el tipo de los números utilizados para acceder y modificar el tamaño de las matrices.

Después de esto, hice los siguientes cambios:

• Se usa uninitializedArraypara evitar inits predeterminados para escalares en xs (probablemente hizo la mayor diferencia).Esto es importante porque D normalmente inicia por defecto todo silenciosamente, lo que C ++ no hace.

• Se factorizó el código de impresión y se reemplazó writefln porwriteln

• Se cambiaron las importaciones para ser selectivas
• Operador pow usado (^^ ) en lugar de la multiplicación manual para el paso final del cálculo del promedio
• Eliminado size_typey reemplazado apropiadamente con el nuevo index_typealias

... resultando así 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;
    }

Después de la prueba scalar2.d(que priorizó la optimización de la velocidad), por curiosidad, reemplacé los bucles maincon foreachequivalentes y lo llamé scalar3.d( 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
      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;
    }

Compilé cada una de estas pruebas usando un compilador basado en LLVM, ya que LDC parece ser la mejor opción para la compilación D en términos de rendimiento. En mi instalación de x86_64 Arch Linux utilicé los siguientes paquetes:

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

Usé los siguientes comandos para compilar cada uno:

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

Resultados

Los resultados ( captura de pantalla de salida de consola sin formato ) de cada versión de la fuente son los siguientes:

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

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

   C ++ establece el estándar en 2582 ms .

2. scalar.d (fuente OP modificada):

   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 

   Esto corrió por ~ 2957 ms . Más lento que la implementación de C ++, pero no demasiado.

3. scalar2.d (cambio de tipo de índice / longitud y optimización de matriz no inicializada):

   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

   En otras palabras, ~ 1860 ms . Hasta ahora esto está a la cabeza.

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 es más lento que scalar2.d, pero más rápido que la versión C ++.

Conclusión

Con las optimizaciones correctas, la implementación de D en realidad fue más rápida que su implementación equivalente de C ++ usando los compiladores basados ​​en LLVM disponibles. La brecha actual entre D y C ++ para la mayoría de las aplicaciones parece basarse únicamente en las limitaciones de las implementaciones actuales.

dmd es la implementación de referencia del lenguaje y, por lo tanto, la mayor parte del trabajo se realiza en la interfaz para corregir errores en lugar de optimizar el backend.

"in" es más rápido en su caso porque está utilizando matrices dinámicas que son tipos de referencia. Con ref introduce otro nivel de indirección (que normalmente se usa para alterar la matriz en sí y no solo el contenido).

Los vectores generalmente se implementan con estructuras donde const ref tiene mucho sentido. Vea smallptD vs. smallpt para ver un ejemplo del mundo real que presenta muchas operaciones vectoriales y aleatoriedad.

Tenga en cuenta que 64 bits también puede marcar la diferencia. Una vez me perdí eso en x64 gcc compila código de 64 bits, mientras que dmd todavía tiene el valor predeterminado de 32 (cambiará cuando madure el codegen de 64 bits). Hubo una notable aceleración con "dmd -m64 ...".

Si C ++ o D es más rápido, es probable que dependa mucho de lo que esté haciendo. Creo que al comparar C ++ bien escrito con código D bien escrito, generalmente tendrían una velocidad similar o C ++ sería más rápido, pero lo que el compilador particular logra optimizar podría tener un gran efecto completamente aparte del lenguaje sí mismo.

Sin embargo, no son pocos casos donde D es una buena oportunidad de vencer a C ++ para la velocidad. El principal que viene a la mente sería el procesamiento de cadenas. Gracias a las capacidades de corte de matriz de D, las cadenas (y las matrices en general) se pueden procesar mucho más rápido de lo que se puede hacer fácilmente en C ++. Para D1, el procesador XML de Tango es extremadamente rápido , gracias principalmente a las capacidades de corte de matriz de D (y con suerte D2 tendrá un analizador XML similarmente rápido una vez que se haya completado el que se está trabajando actualmente para Phobos). Entonces, en última instancia, si D o C ++ será más rápido dependerá mucho de lo que esté haciendo.

Ahora, yo estoy sorprendido de que se está viendo una diferencia tal en velocidad en este caso en particular, pero es el tipo de cosas que yo esperaría a mejorar a medida que mejora la DMD. El uso de gdc podría arrojar mejores resultados y probablemente sería una comparación más cercana del lenguaje en sí (en lugar del backend) dado que está basado en gcc. Pero no me sorprendería en absoluto si se pueden hacer varias cosas para acelerar el código que genera dmd. No creo que haya muchas dudas de que gcc es más maduro que dmd en este momento. Y las optimizaciones de código son uno de los principales frutos de la madurez del código.

En última instancia, lo que importa es qué tan bien se desempeña dmd para su aplicación en particular, pero estoy de acuerdo en que definitivamente sería bueno saber qué tan bien se comparan C ++ y D en general. En teoría, deberían ser más o menos lo mismo, pero realmente depende de la implementación. Sin embargo, creo que se requeriría un conjunto completo de puntos de referencia para probar realmente qué tan bien se comparan actualmente los dos.

Puede escribir el código C es D, por lo que, en la medida en que sea más rápido, dependerá de muchas cosas:

• ¿Qué compilador usas?
• Qué característica usas
• cuán agresivamente optimizas

Las diferencias en el primero no son justas. El segundo podría darle a C ++ una ventaja ya que, en todo caso, tiene menos funciones pesadas. El tercero es divertido: el código D de alguna manera es más fácil de optimizar porque en general es más fácil de entender. También tiene la capacidad de hacer un alto grado de programación generativa que permite escribir cosas como código detallado y repetitivo pero rápido en formas más cortas.

Parece un problema de calidad de implementación. Por ejemplo, esto es lo que he estado probando con:

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);
}

Con ManualInlinedefinido obtengo 28 segundos, pero sin obtener 32. Por lo tanto, el compilador ni siquiera incluye esta función simple, que creo que está claro que debería ser.

(Mi línea de comando es dmd -O -noboundscheck -inline -release ...).