Qual a velocidade do D comparado ao C ++?

133

Eu gosto de alguns recursos do D, mas estaria interessado se eles vierem com uma penalidade de tempo de execução?

Para comparar, implementei um programa simples que calcula produtos escalares de muitos vetores curtos, tanto em C ++ quanto em D. O resultado é surpreendente:

  • D: 18,9 s [veja abaixo o tempo de execução final]
  • C ++: 3,8 s

C ++ é realmente quase cinco vezes mais rápido ou cometi um erro no programa D?

Compilei C ++ com g ++ -O3 (gcc-snapshot 2011-02-19) e D com dmd -O (dmd 2.052) em uma área de trabalho Linux recente moderada. Os resultados são reproduzíveis em várias execuções e os desvios padrão são insignificantes.

Aqui o 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;
}

E aqui a versão 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;
}
Lars
fonte
3
A propósito, seu programa tem um erro nesta linha: avg = avg / N*N(ordem das operações).
Vladimir Panteleev 28/02
4
Você pode tentar reescrever o código usando operações Array / vetor digitalmars.com/d/2.0/arrays.html
Michal Minich
10
Para fornecer uma comparação melhor, você deve usar o mesmo back-end do compilador. Ou DMD e DMC ++ ou GDC e G ++
he_the_great
1
@Sion Sheevok Infelizmente, o perfil dmd parece não estar disponível para Linux? (corrija-me se estiver errado, mas se eu disser dmd ... trace.defque recebo um error: unrecognized file extension def. E os documentos dmd para optlink mencionam apenas o Windows.
Lars
1
Ah, nunca se preocupou com o arquivo .def que ele cospe. Os horários estão dentro do arquivo .log. "Ele contém a lista de funções na ordem em que o vinculador deve vinculá-las" - talvez isso ajude o optlink a otimizar alguma coisa? Observe também que "Além disso, o ld suporta totalmente os arquivos" * .def "padrão, que podem ser especificados na linha de comando do vinculador como um arquivo de objeto" - para que você possa tentar passar o trace.def via -L, se desejar para.
Trass3r

Respostas:

64

Para ativar todas as otimizações e desativar todas as verificações de segurança, compile seu programa D com os seguintes sinalizadores DMD:

-O -inline -release -noboundscheck

Edição : Eu tentei seus programas com g ++, dmd e gdc. O dmd fica para trás, mas o gdc alcança um desempenho muito próximo ao g ++. A linha de comando que eu usei era gdmd -O -release -inline(gdmd é um wrapper em torno do gdc que aceita opções de dmd).

Observando a lista do assembler, parece que nem o dmd nem o gdc estão alinhados scalar_product, mas o g ++ / gdc emitiu instruções MMX, portanto, eles podem auto-vetorizar o loop.

Vladimir Panteleev
fonte
3
@ CyberShadow: mas se você remover a verificação de segurança ... não está perdendo alguns recursos importantes do D?
Matthieu M.
33
Você está perdendo recursos que o C ++ nunca teve. A maioria dos idiomas não oferece uma escolha.
Vladimir Panteleev 28/02
6
@ CyberShadow: podemos pensar nisso como uma espécie de compilação de debug vs release?
Francesco
7
@ Bernard: no lançamento, a verificação de limites está desativada para todo o código, exceto para funções seguras. para realmente desativar a verificação de limites, use a opção -release e-noboundscheck.
Michal Minich 28/02
5
@CyberShadow Thanks! Com esses sinalizadores, o tempo de execução melhora consideravelmente. Agora D está em 12,9 s. Mas ainda corre mais de três vezes mais. @ Matthieu M. Eu não me importaria de testar um programa com verificação de limites em câmera lenta e, uma vez depurado, faça seus cálculos sem verificação de limites. (I fazer o mesmo com C ++ agora.)
Lars
32

Uma grande coisa que desacelera o D é uma implementação de coleta de lixo abaixo da média. Os benchmarks que não enfatizam muito o GC mostrarão desempenho muito semelhante ao código C e C ++ compilado com o mesmo back-end do compilador. Os benchmarks que enfatizam fortemente o GC mostrarão que D apresenta um desempenho abismal. Entretanto, tenha certeza de que esse é um problema único (embora grave) de qualidade de implementação, e não uma garantia de lentidão. Além disso, D oferece a capacidade de optar por não participar do GC e ajustar o gerenciamento de memória em bits críticos para o desempenho, enquanto ainda o utiliza nos 95% menos críticos para o desempenho do seu código.

Ultimamente, tenho me esforçado para melhorar o desempenho do GC e os resultados têm sido bastante dramáticos, pelo menos nos benchmarks sintéticos. Esperamos que essas alterações sejam integradas em um dos próximos lançamentos e mitiguem o problema.

dsimcha
fonte
1
Notei que uma de suas alterações foi uma mudança de divisão para mudança de bits. Isso não deveria ser algo que o compilador faz?
GManNickG 28/02
3
@ GMan: Sim, se o valor que você está dividindo for conhecido em tempo de compilação. Não, se o valor for conhecido apenas em tempo de execução, foi o caso em que eu fiz essa otimização.
dsimcha
@dsimcha: Hum. Eu acho que se você souber fazê-lo, o compilador também pode. Problema de qualidade de implementação, ou sinto falta de alguma condição que o compilador não possa provar, mas você sabe? (Estou aprendendo D agora, para estas coisas pouco sobre o compilador são subitamente interessante para mim :).)
GManNickG
13
@ GMan: A troca de bits só funciona se o número que você está dividindo for uma potência de dois. O compilador não pode provar isso se o número for conhecido apenas no tempo de execução, e os testes e ramificações seriam mais lentos do que apenas usando a instrução div. Meu caso é incomum, porque o valor é conhecido apenas no tempo de execução, mas eu sei que, em tempo de compilação, será uma potência de dois.
dsimcha
7
Observe que o programa publicado neste exemplo não faz alocação na parte demorada.
Vladimir Panteleev 28/02
27

Este é um tópico muito instrutivo, obrigado por todo o trabalho para o OP e os auxiliares.

Uma observação - esse teste não está avaliando a questão geral da penalidade de abstração / recurso ou mesmo a da qualidade de back-end. Ele se concentra em praticamente uma otimização (otimização de loop). Eu acho que é justo dizer que o back-end do gcc é um pouco mais refinado que o do dmd, mas seria um erro supor que a diferença entre eles é tão grande para todas as tarefas.

Andrei Alexandrescu
fonte
4
Eu concordo completamente. Como adicionado mais adiante, estou interessado principalmente em desempenho para cálculos numéricos em que a otimização de loop provavelmente é a mais importante. Quais outras otimizações você acha que seriam importantes para a computação numérica? E quais cálculos os testariam? Eu estaria interessado em complementar meu teste e implementar mais alguns testes (se eles forem mais ou menos simples). Mas evtl. essa é outra questão por si só?
Lars
11
Como engenheiro que cortou os dentes em C ++, você é um herói meu. Respeitosamente, no entanto, isso deve ser um comentário, não uma resposta.
Alan
14

Definitivamente, parece um problema de qualidade de implementação.

Fiz alguns testes com o código do OP e fiz algumas alterações. Na verdade, eu consegui o D indo mais rápido para o LDC / clang ++, operando no pressuposto de que as matrizes devem ser alocadas dinamicamente ( xse escalares associados). Veja abaixo alguns números.

Perguntas para o OP

É intencional que a mesma semente seja usada para cada iteração de C ++, enquanto não é assim para D?

Configuração

Ajustei a fonte D original (apelidada de scalar.d ) para torná-la portátil entre plataformas. Isso envolveu apenas alterar o tipo dos números usados ​​para acessar e modificar o tamanho das matrizes.

Depois disso, fiz as seguintes alterações:

  • Usado uninitializedArraypara evitar inits padrão para escalares em xs (provavelmente fez a maior diferença). Isso é importante porque D normalmente insere tudo no padrão, o que o C ++ não faz.

  • Código de impressão fatorado e substituído writeflnporwriteln

  • Importações alteradas para serem seletivas
  • Operador pow usado ( ^^) em vez de multiplicação manual para a etapa final do cálculo da média
  • Removido size_typee substituído adequadamente pelo novo index_typealias

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

Após o teste scalar2.d(que priorizou a otimização da velocidade), por curiosidade, substituí os loops mainpor foreachequivalentes e o chamei 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;
    }

Compilei cada um desses testes usando um compilador baseado em LLVM, pois o LDC parece ser a melhor opção para a compilação de D em termos de desempenho. Na minha instalação do x86_64 Arch Linux, usei os seguintes pacotes:

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

Eu usei os seguintes comandos para compilar cada um:

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

Resultados

Os resultados ( captura de tela da saída bruta do console ) de cada versão da fonte da seguinte maneira:

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

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

    C ++ define o padrão em 2582 ms .

  2. scalar.d (fonte 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 

    Isso foi executado por ~ 2957 ms . Mais lento que a implementação de C ++, mas não muito.

  3. scalar2.d (alteração do tipo de índice / comprimento e otimização não inicializada da matriz):

    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

    Em outras palavras, ~ 1860 ms . Até agora, isso está na liderança.

  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 é mais lento que scalar2.d, mas mais rápido que na versão C ++.

Conclusão

Com as otimizações corretas, a implementação D realmente foi mais rápida que sua implementação equivalente em C ++ usando os compiladores baseados em LLVM disponíveis. A lacuna atual entre D e C ++ para a maioria dos aplicativos parece basear-se apenas nas limitações das implementações atuais.

Erich Gubler
fonte
8

O dmd é a implementação de referência da linguagem e, portanto, a maior parte do trabalho é colocada no front-end para corrigir erros, em vez de otimizar o back-end.

"in" é mais rápido no seu caso, porque você está usando matrizes dinâmicas que são tipos de referência. Com ref, você introduz outro nível de indireção (que normalmente é usado para alterar a própria matriz e não apenas o conteúdo).

Os vetores são geralmente implementados com estruturas em que const ref faz todo o sentido. Veja smallptD vs. smallpt para obter um exemplo do mundo real, com cargas de operações vetoriais e aleatoriedade.

Observe que 64 bits também pode fazer a diferença. Uma vez eu perdi isso no x64 gcc compila o código de 64 bits, enquanto o dmd ainda é 32 (o valor mudará quando o codegen de 64 bits amadurecer). Houve uma notável aceleração com "dmd -m64 ...".

Trass3r
fonte
7

Se C ++ ou D é mais rápido, provavelmente será altamente dependente do que você está fazendo. Eu pensaria que, ao comparar C ++ bem escrito com código D bem escrito, eles geralmente teriam velocidade semelhante ou C ++ seria mais rápido, mas o que o compilador em particular consegue otimizar pode ter um grande efeito, além da linguagem em si.

No entanto, não são poucos os casos em que D tem uma boa chance de bater C ++ para a velocidade. O principal que vem à mente seria o processamento de strings. Graças às capabalidades de fatiamento da matriz de D, seqüências de caracteres (e matrizes em geral) podem ser processadas muito mais rapidamente do que você pode fazer facilmente em C ++. Para o D1, o processador XML do Tango é extremamente rápido , graças principalmente aos recursos de corte de matriz do D (e, esperançosamente, o D2 terá um analisador de XML igualmente rápido depois que o que estiver sendo trabalhado no Phobos for concluído). Portanto, se o D ou C ++ será mais rápido, dependerá muito do que você está fazendo.

Agora eu estou surpreso que você esteja vendo uma diferença de velocidade nesse caso específico, mas é o tipo de coisa que eu esperaria melhorar à medida que o dmd melhorar. O uso do gdc pode produzir melhores resultados e provavelmente seria uma comparação mais próxima do próprio idioma (e não do back-end), uma vez que é baseado no gcc. Mas não me surpreenderia se houvesse várias coisas que poderiam ser feitas para acelerar o código que o dmd gera. Eu não acho que haja muita dúvida de que o gcc é mais maduro que o dmd neste momento. E as otimizações de código são um dos principais frutos da maturidade do código.

Por fim, o que importa é o desempenho do dmd para seu aplicativo em particular, mas concordo que seria definitivamente bom saber o quão C ++ e D se comparam em geral. Em teoria, eles devem ser praticamente iguais, mas realmente depende da implementação. Penso que seria necessário um conjunto abrangente de parâmetros para testar realmente como os dois atualmente se comparam.

Jonathan M Davis
fonte
4
Sim, eu ficaria surpreso se a entrada / saída fosse significativamente mais rápida nos dois idiomas, ou se a matemática pura fosse significativamente mais rápida nos dois idiomas, mas operações com strings, gerenciamento de memória e algumas outras coisas poderiam facilmente deixar um idioma brilhar.
Max Lybbert
1
É fácil fazer melhor (mais rápido) que os iostreams C ++. Mas isso é principalmente um problema de implementação de biblioteca (em todas as versões conhecidas dos fornecedores mais populares).
Ben Voigt
4

Você pode escrever o código C é D, na medida em que for mais rápido, isso dependerá de muitas coisas:

  • Qual compilador você usa
  • Qual recurso você usa
  • quão agressivamente você otimiza

As diferenças no primeiro não são justas para se arrastar. O segundo pode dar ao C ++ uma vantagem, pois, se houver, possui menos recursos pesados. O terceiro é o mais divertido: o código D, de certa forma, é mais fácil de otimizar, porque em geral é mais fácil de entender. Também tem a capacidade de executar um alto grau de programação generativa, permitindo que coisas como código detalhado e repetitivo, mas rápido, sejam escritas de forma mais curta.

BCS
fonte
3

Parece um problema de qualidade de implementação. Por exemplo, aqui está o que eu tenho testado:

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

Com ManualInline definido, recebo 28 segundos, mas sem recebo 32. Portanto, o compilador nem sequer está embutindo essa função simples, o que acho claro que deveria estar.

(Minha linha de comando é dmd -O -noboundscheck -inline -release ....)

GManNickG
fonte
1
Seus horários não têm sentido, a menos que você faça uma comparação com os horários em C ++.
Deceleratedcaviar
3
@ Daniel: Você está perdendo o ponto. Foi para demonstrar as otimizações de D isoladamente, ou seja, para a conclusão que afirmei: "Portanto, o compilador nem sequer está incorporando essa função simples, o que acho claro que deveria ser". Estou até tentando compará-lo ao C ++, como afirmei claramente na primeira frase: "Parece um problema de qualidade de implementação".
GManNickG
Ah verdade, desculpe :). Você também verá que o compilador DMD também não vetoriza os loops.
deceleratedcaviar