Насколько быстро D по сравнению с C ++?

133

Мне нравятся некоторые функции D, но было бы интересно, если они будут иметь штраф за время выполнения?

Для сравнения я реализовал простую программу, которая вычисляет скалярные произведения многих коротких векторов как на C ++, так и на D. Результат удивительный:

  • D: 18,9 с [окончательное время выполнения см. Ниже]
  • C ++: 3,8 с

C ++ действительно почти в пять раз быстрее или я ошибся в программе D?

Я скомпилировал C ++ с g ++ -O3 (gcc-snapshot 2011-02-19) и D с dmd -O (dmd 2.052) на умеренном недавнем рабочем столе Linux. Результаты воспроизводимы в нескольких сериях, а стандартные отклонения незначительны.

Вот программа на 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;
}

А вот версия 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
источник
3
Кстати, в вашей программе есть ошибка в этой строке: avg = avg / N*N(порядок операций).
Владимир Пантелеев
4
Вы можете попробовать переписать код, используя операции с массивами / векторами digitalmars.com/d/2.0/arrays.html
Michal Minich
10
Чтобы обеспечить лучшее сравнение, вы должны использовать ту же внутреннюю часть компилятора. Либо DMD и DMC ++, либо GDC и G ++
he_the_great
1
@Sion Sheevok К сожалению, профилирование dmd недоступно для Linux? (пожалуйста, поправьте меня, если я ошибаюсь, но если я скажу, dmd ... trace.defчто получаю error: unrecognized file extension def. А в dmd docs для optlink упоминается только Windows.
Ларс,
1
Ах, никогда не заботился об этом файле .def, который он выплевывает. Время находится в файле .log. «Он содержит список функций в том порядке, в котором компоновщик должен их связывать» - может быть, это помогает optlink что-то оптимизировать? Также обратите внимание, что «Кроме того, ld полностью поддерживает стандартные файлы« * .def », которые могут быть указаны в командной строке компоновщика как объектный файл» - так что вы можете попробовать передать trace.def через -L, если очень хотите. к.
Trass3r 03

Ответы:

64

Чтобы включить все оптимизации и отключить все проверки безопасности, скомпилируйте вашу программу D со следующими флагами DMD:

-O -inline -release -noboundscheck

РЕДАКТИРОВАТЬ : Я пробовал ваши программы с g ++, dmd и gdc. dmd действительно отстает, но gdc по производительности очень близок к g ++. Я использовал gdmd -O -release -inlineкомандную строку (gdmd - это оболочка для gdc, которая принимает параметры dmd).

Глядя на листинг ассемблера, похоже, что ни dmd, ни gdc не встроены scalar_product, но g ++ / gdc действительно испускал инструкции MMX, поэтому они могли автоматически векторизовать цикл.

Владимир Пантелеев
источник
3
@CyberShadow: но если вы удалите проверку безопасности ... разве вы не потеряете некоторые важные функции D?
Matthieu M.
33
Вы теряете возможности, которых у C ++ никогда не было. Большинство языков не дают вам выбора.
Владимир Пантелеев
6
@CyberShadow: можем ли мы рассматривать это как своего рода сборку отладки и выпуска?
Francesco
7
@Bernard: в -release проверка границ отключена для всего кода, кроме безопасных функций. чтобы действительно отключить проверку границ, используйте как -release, так и-noboundscheck.
Михал Миних
5
@CyberShadow Спасибо! С этими флагами время выполнения значительно улучшается. Теперь D на 12,9 с. Но все равно работает более чем в 3 раза дольше. @Matthieu M. Я был бы не против протестировать программу с проверкой границ в замедленном режиме, и как только она будет отлажена, пусть она выполняет свои вычисления без проверки границ. (Сейчас я делаю то же самое с C ++.)
Ларс
32

Одна большая вещь, которая замедляет работу D, - это некачественная реализация сборки мусора. Тесты, которые не сильно нагружают сборщик мусора, покажут производительность, очень схожую с производительностью кода C и C ++, скомпилированного с использованием того же внутреннего модуля компилятора. Тесты, которые сильно нагружают GC, покажут, что D работает ужасно. Но будьте уверены, что это единственная (хотя и серьезная) проблема качества реализации, а не гарантия медлительности. Кроме того, D дает вам возможность отказаться от GC и настроить управление памятью в критических для производительности битах, при этом используя его в менее критичных для производительности 95% вашего кода.

В последнее время я приложил некоторые усилия для улучшения производительности GC, и результаты были довольно впечатляющими, по крайней мере, на синтетических тестах. Надеюсь, эти изменения будут внесены в один из следующих нескольких выпусков и устранят проблему.

dsimcha
источник
1
Я заметил, что одним из ваших изменений было изменение деления на битовый сдвиг. Разве это не должно делать компилятор?
GManNickG
3
@GMan: Да, если значение, на которое вы делите, известно во время компиляции. Нет, если значение известно только во время выполнения, что было в случае, когда я сделал эту оптимизацию.
dsimcha
@dsimcha: Хм. Я полагаю, если вы знаете, как это сделать, компилятор тоже сможет. Проблема качества реализации, или мне не хватает того, что необходимо выполнить какое-то условие, которое компилятор не может доказать, но вы знаете? (Сейчас я изучаю D, так что эти мелочи о компиляторе внезапно меня заинтересовали. :))
GManNickG
13
@GMan: Битовый сдвиг работает, только если число, на которое вы делите, является степенью двойки. Компилятор не может это доказать, если число известно только во время выполнения, а тестирование и переходы будут медленнее, чем просто использование инструкции div. Мой случай необычен, потому что значение известно только во время выполнения, но я знаю во время компиляции, что это будет некоторая степень двойки.
dsimcha
7
Обратите внимание, что программа, представленная в этом примере, не выполняет выделение ресурсов в трудоемкой части.
Владимир Пантелеев
27

Это очень поучительная ветка, спасибо за всю работу OP и помощникам.

Одно замечание - этот тест не оценивает общий вопрос о штрафах за абстракцию / функциональность или даже о качестве серверной части. Он ориентирован практически на одну оптимизацию (оптимизация цикла). Я думаю, будет справедливо сказать, что бэкэнд gcc несколько более усовершенствован, чем dmd, но было бы ошибкой предполагать, что разрыв между ними столь же велик для всех задач.

Андрей Александреску
источник
4
Я полностью согласен. Как добавлено позже, меня в основном интересует производительность численных вычислений, где оптимизация цикла, вероятно, является наиболее важной. Какие еще оптимизации, по вашему мнению, будут важны для численных вычислений? И какие вычисления будут их проверять? Мне было бы интересно дополнить свой тест и реализовать еще несколько тестов (если они примерно такие же простые). Но евтл. это отдельный вопрос?
Ларс
11
Как инженер, который хорошо разбирается в C ++, вы мой герой. Однако, с уважением, это должен быть комментарий, а не ответ.
Алан
14

Определенно кажется проблемой качества реализации.

Я провел несколько тестов с кодом OP и внес некоторые изменения. Я фактически заставил D работать быстрее для LDC / clang ++, работая в предположении, что массивы должны распределяться динамически ( xsи связанные скаляры). Ниже приведены некоторые цифры.

Вопросы к ОП

Является ли намеренно использование одного и того же начального числа для каждой итерации C ++, а не для D?

Настроить

Я изменил исходный код D (дублированный scalar.d), чтобы сделать его переносимым между платформами. Это включало только изменение типа чисел, используемых для доступа к массивам и изменения их размера.

После этого я внес следующие изменения:

  • Используется, uninitializedArrayчтобы избежать инициализации по умолчанию для скаляров в xs (вероятно, имело наибольшее значение). Это важно, потому что D обычно по умолчанию все инициализирует молча, чего не делает C ++.

  • Код печати исключен и заменен writeflnнаwriteln

  • Импорт изменен на выборочный
  • Используется оператор pow ( ^^) вместо ручного умножения на последнем этапе вычисления среднего
  • Удален size_typeи заменен соответствующим образом новым index_typeпсевдонимом

... что приводит к 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;
    }

После тестирования scalar2.d(который по приоритетам оптимизации скорости), из любопытства я заменил петлю в mainс foreachэквивалентами, и назвал его 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;
    }

Я скомпилировал каждый из этих тестов с использованием компилятора на основе LLVM, поскольку LDC кажется лучшим вариантом для компиляции D с точки зрения производительности. В моей установке x86_64 Arch Linux я использовал следующие пакеты:

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

Я использовал следующие команды для компиляции каждого:

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

Полученные результаты

Результаты ( снимок экрана необработанного вывода консоли ) для каждой версии исходного кода выглядят следующим образом:

  1. scalar.cpp (оригинальный C ++):

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

    C ++ устанавливает стандарт на 2582 мс .

  2. scalar.d (модифицированный источник 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 

    Это длилось ~ 2957 мс . Медленнее, чем реализация на C ++, но не намного.

  3. scalar2.d (изменение типа индекса / длины и оптимизация uninitializedArray):

    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

    Другими словами, ~ 1860 мс . Пока это лидирует.

  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 мс медленнее scalar2.d, но быстрее, чем версия C ++.

Вывод

При правильной оптимизации реализация D фактически пошла быстрее, чем ее эквивалентная реализация на C ++ с использованием доступных компиляторов на основе LLVM. Текущий разрыв между D и C ++ для большинства приложений, по-видимому, основан только на ограничениях текущих реализаций.

Эрих Габлер
источник
8

dmd - это эталонная реализация языка, и поэтому большая часть работы направлена ​​на исправление ошибок, а не на оптимизацию серверной части.

"in" в вашем случае быстрее, потому что вы используете динамические массивы, которые являются ссылочными типами. С помощью ref вы вводите другой уровень косвенности (который обычно используется для изменения самого массива, а не только его содержимого).

Векторы обычно реализуются с помощью структур, в которых const ref имеет смысл. См. « SmallptD против smallpt» для получения реального примера с множеством векторных операций и случайности.

Обратите внимание, что 64-битная версия также может иметь значение. Однажды я пропустил, что на x64 gcc компилирует 64-битный код, в то время как dmd по-прежнему имеет значение 32 (изменится, когда 64-битный кодогенератор созреет). Было замечательно ускорение с "dmd -m64 ...".

Trass3r
источник
7

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

Тем не менее, есть несколько случаев , когда D есть хорошие шансы в избиении C ++ для скорости. Главное, что приходит в голову, - это обработка строк. Благодаря возможностям нарезки массивов в D строки (и массивы в целом) могут обрабатываться намного быстрее, чем это можно сделать в C ++. Для D1 XML-процессор Tango работает чрезвычайно быстро , в первую очередь благодаря возможностям нарезки массива D (и, надеюсь, у D2 будет такой же быстрый XML-анализатор, как только будет завершен тот, над которым в настоящее время работают для Phobos). Итак, в конечном итоге, будет ли D или C ++ работать быстрее, будет очень зависеть от того, что вы делаете.

Теперь я буду удивлён , что вы видите такую разницу в скорости в данном конкретном случае, но это такое дело , что я бы ожидать улучшения , как DMD улучшается. Использование gdc может дать лучшие результаты и, вероятно, будет более близким сравнением самого языка (а не бэкэнда), учитывая, что он основан на gcc. Но меня совсем не удивит, если есть несколько вещей, которые можно сделать для ускорения кода, генерируемого dmd. Я не думаю, что есть много сомнений в том, что на данный момент gcc более зрелый, чем dmd. А оптимизация кода - один из главных плодов зрелости кода.

В конечном счете, важно то, насколько хорошо dmd работает для вашего конкретного приложения, но я согласен с тем, что было бы определенно неплохо узнать, насколько хорошо C ++ и D сравниваются в целом. Теоретически они должны быть примерно одинаковыми, но на самом деле это зависит от реализации. Я думаю, что потребуется исчерпывающий набор тестов, чтобы действительно проверить, насколько хорошо они сравниваются в настоящее время.

Джонатан М Дэвис
источник
4
Да, я был бы удивлен, если бы ввод / вывод был значительно быстрее на любом из языков или если бы чистая математика была значительно быстрее на любом из языков, но строковые операции, управление памятью и некоторые другие вещи могли бы легко позволить одному языку сиять.
Макс Либберт
1
Легко сделать лучше (быстрее), чем iostreams C ++. Но это в первую очередь проблема реализации библиотеки (во всех известных версиях от самых популярных производителей).
Бен Фойгт
4

Вы можете написать код C - это D, насколько он быстрее, это будет зависеть от многих вещей:

  • Какой компилятор вы используете
  • Какую функцию вы используете
  • насколько агрессивно вы оптимизируете

Различия в первом не справедливо перетаскивать. Второй может дать C ++ преимущество, поскольку он, во всяком случае, имеет меньше тяжелых функций. Третий - интересный: код в некотором смысле легче оптимизировать, потому что в целом его легче понять. Также он имеет возможность выполнять большую часть генеративного программирования, позволяя писать такие вещи, как подробный и повторяющийся, но быстрый код, в более коротких формах.

BCS
источник
3

Похоже на проблему качества реализации. Например, вот что я тестировал:

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

С ManualInlineопределением я получаю 28 секунд, но без 32. Таким образом, компилятор даже не встраивает эту простую функцию, что, как мне кажется, должно быть очевидно.

(Моя командная строка dmd -O -noboundscheck -inline -release ....)

GManNickG
источник
1
Ваши тайминги бессмысленны, если вы также не сравните свои тайминги с C ++.
deceleratedcaviar
3
@ Даниэль: Вы упускаете суть. Это было сделано для того, чтобы продемонстрировать изолированную оптимизацию D, а именно для вывода, который я сказал: «Значит, компилятор даже не встраивает эту простую функцию, что, как мне кажется, должно быть». Я даже пытаюсь сравнить его с C ++, как я ясно сказал в первом предложении: «Похоже, проблема качества реализации».
GManNickG
Ах правда, извините :). Вы также обнаружите, что компилятор DMD вообще не векторизует циклы.
deceleratedcaviar