Самый быстрый язык для циклов FOR - PullRequest
6 голосов
/ 07 июля 2010

Я пытаюсь найти лучший язык программирования для аналитической модели, которую я строю. Основное внимание уделяется скорости, с которой он будет запускать циклы FOR.

Некоторая деталь:

  • Модель должна выполнять многочисленные (~ 30 на запись, более 12 циклов) операции с набором элементов из массива - в массиве ~ 300 тыс. Строк и ~ 150 столбцов. Большинство из этих операций являются логическими по своему характеру, например, если place (i) = 1, то j (i) = 2.
  • Я построил более раннюю версию этой модели с использованием Octave - для запуска требуется около 55 часов на экземпляре Amazon EC2 m2.xlarge (и он использует ~ 10 ГБ памяти, но я совершенно счастлив бросить больше памяти на это). Octave / Matlab не будет выполнять поэлементные логические операции, поэтому необходимо большое количество циклов for - я относительно уверен, что я максимально векторизовал - оставшиеся циклы необходимы. Я получил многоядерные октавы для работы с этим кодом, что дает некоторое улучшение (снижение скорости ~ 30%, когда я запускаю его на 8 ядрах EC2), но в итоге получается нестабильным с блокировкой файлов и т. Д. + Я действительно ищу пошаговое изменение во время выполнения - я знаю, что на самом деле использование Matlab может принести мне улучшение на 50%, если смотреть на некоторые тесты, но это непомерно дорого. Первоначальный план при запуске программы заключался в том, чтобы фактически запустить Монте-Карло с этим, но при 55-часовом пробеге это совершенно нецелесообразно.
  • Следующая версия этого проекта будет полностью перестроена с нуля (по причинам, связанным с IP, я не буду вдаваться в подробности), поэтому я полностью открыта для любого языка программирования. Я наиболее знаком с Octave / Matlab, но баловался R, C, C ++, Java. Я также опытен с SQL, если решение предполагает хранение данных в базе данных. Я выучу любой язык для этого - это не сложная функциональность, которую мы ищем, не взаимодействие с другими программами и т. Д., Поэтому не слишком озабочен кривой обучения.

Итак, со всем вышесказанным, какой самый быстрый язык программирования специально для циклов FOR? От поиска SO и Google, Fortran и C пузыря к вершине, но ищите еще несколько советов, прежде чем погрузиться в к одному или другому.

Спасибо!

Ответы [ 14 ]

6 голосов
/ 07 июля 2010

Этот цикл for выглядит не более сложным, чем этот, когда он попадает в CPU:

for(int i = 0; i != 1024; i++) переводится как

mov r0, 0           ;;start the counter    
top:

;;some processing

add r0, r0, 1       ;;increment the counter by 1
jne top: r0, 1024   ;;jump to the loop top if we havn't hit the top of the for loop (1024 elements)

;;continue on

Как вы можете сказать, это достаточно просто, вы не можете оптимизировать его очень хорошо [1] ... Перефокусироваться на уровень алгоритма.

Первое, что нужно сделать, это посмотреть на локальность кэша. Посмотрите на классический пример умножения матриц и замены индексов i и j.

edit: В качестве второго варианта я бы предложил оценить алгоритм зависимости данных между итерациями и зависимости данных между местностями в вашей «матрице» данных. Это может быть хорошим кандидатом для распараллеливания.

[1] Возможны некоторые микро -оптимизации, но они не приведут к быстродействию, которое вы ищете.

5 голосов
/ 09 июля 2010

Как сказал @Rotsor, 16G операций / 55 часов - это около 80 000 операций в секунду, или одна операция каждые 12,5 микросекунд.Это очень много времени на операцию.

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

Если вам нужна скорость, вам сначала нужно быть на скомпилированном языке.Затем вам нужно выполнить настройку производительности (или профилирование) или просто выполнить один шаг в отладчике на уровне команд.Это скажет вам, что он на самом деле делает в своем сердце сердец.Как только вы дойдете до того, чтобы не тратить впустую циклы, более изящное оборудование, ядра, CUDA и т. Д. Ускорят параллелизм.Но делать это глупо, если ваш код занимает слишком много циклов. (Вот пример настройки производительности - 43-кратное ускорение только путем обрезки жира).

Я не могу поверить, что респонденты говорят о matlab, APL и других векторизованных языках.Это переводчики.Они дают вам краткий исходный код , который совсем не - это то же самое, что быстрое выполнение .Когда дело доходит до чистого металла, они застряли на том же оборудовании, что и любой другой язык.


Добавлено: чтобы показать, что я имею в виду, я просто запустил этот код C ++, который выполняет операции 16Gна этом заплесневелом старом ноутбуке, и это заняло 94 секунды, или около 6 нс за итерацию.(Я не могу поверить, что ты сидел с этой штукой целых два дня.)

void doit(){
  double sum = 0;
  for (int i = 0; i < 1000; i++){
    for (int j = 0; j < 16000000; j++){
      sum += j * 3.1415926;
    }
  }
}
5 голосов
/ 07 июля 2010

~300k * ~150 * ~30 * ~12 = ~16G итераций, верно?Это количество примитивных операций должно завершиться за считанные минуты (если не секунды) на любом скомпилированном языке на любом приличном процессоре.Fortran, C / C ++ должен делать это почти одинаково хорошо.Даже управляемые языки, такие как Java и C #, будут отставать лишь с небольшим отрывом (если вообще будут).

Если у вас есть проблема с ~ 16G итераций, выполняющих 55 часов, это означает, что они оченьот того, чтобы быть примитивным (80k в секунду? это смешно), так что, возможно, мы должны знать больше.(как уже предлагалось, ограничивает ли доступ к диску производительность? Доступ к сети?)

3 голосов
/ 07 июля 2010

Любой скомпилированный язык должен выполнять сам цикл примерно на равных условиях.

Если вы можете сформулировать свою проблему в ее терминах, вы, возможно, захотите взглянуть на CUDA или OpenCL и запустить свой матричный код на GPU - хотя это не очень хорошо для кода с большим количеством условных выражений.

Если вы хотите остаться на обычных процессорах, вы можете сформулировать свою проблему в терминах SSE-операций разброса / сбора и битовой маски.

3 голосов
/ 07 июля 2010

Для того, что вы обсуждаете, Фортран, вероятно, ваш первый выбор.Ближайшее второе место - , вероятно C ++.Некоторые библиотеки C ++ используют «шаблоны выражений», чтобы получить некоторую скорость по сравнению с C для такого рода задач.Не совсем ясно, что они принесут вам пользу, но C ++ может быть, по крайней мере, так же быстро, как C, и, возможно, несколько быстрее.

По крайней мере, теоретически, нет причин, по которым Ада также не могла быть конкурентоспособной,но с тех пор, как я использовал его для чего-то подобного, я не решался его рекомендовать - не потому, что это плохо, а потому, что я не достаточно хорошо отслеживал текущие компиляторы Ada, чтобы разумно комментировать их.

3 голосов
/ 07 июля 2010

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

Edit - обычно вы увидите гораздо лучшую производительность с любым видом зацикливания или разветвления (например,Если операторы) кодируются скомпилированным языком, а не интерпретируемым языком.

Например, в недавнем проекте, над которым я работал, размеры данных и операции составляли примерно 3/4 размера того, что вы 'мы говорим здесь, но, как и ваш код, у него было очень мало места для векторизации, и он требовал значительных циклов.После преобразования кода из matlab в C ++ время выполнения сократилось с 16-18 часов до примерно 25 минут.

2 голосов
/ 09 июля 2010

Вероятно, язык ассемблера для любой вашей платформы.Но компиляторы (особенно специализированные, специально предназначенные для одной платформы (например, Analog Devices или TI DSP)) часто так же хороши, как и люди.Кроме того, компиляторы часто знают о хитростях, которых вы не знаете.Например, вышеупомянутые DSP поддерживают циклы с нулевыми издержками, и компилятор будет знать, как оптимизировать код для использования этих циклов.

1 голос
/ 09 июля 2010

C ++ не быстро при выполнении матричных операций с циклами for.С, на самом деле, особенно плохо в этом.См. хорошая математика плохая математика .

Я слышал, что у C99 есть __strict указатели, которые помогают, но я не знаю много об этом.

Фортран по-прежнему является языком перехода длячисленные вычисления.

1 голос
/ 09 июля 2010

Matlab будет выполнять поэлементные логические операции, и они, как правило, довольно быстрые.

Вот небольшой пример на моем компьютере (AMD Athalon 2,3 ГГц с 3 ГБ):

d=rand(300000,150);
d=floor(d*10);

>> numel(d(d==1))
ans =
     4501524

>> tic;d(d==1)=10;toc;
Elapsed time is 0.754711 seconds.

>> numel(d(d==1))
ans =
     0
>> numel(d(d==10))
ans =
     4501524

В общем, я обнаружил, что операторы Matlab очень быстры, вам просто нужно найтиспособы выразить ваши алгоритмы напрямую через матричные операторы.

0 голосов
/ 09 июля 2010

Любой современный скомпилированный или JITted-язык будет отображаться практически в одном и том же коде машинного языка, предоставляя издержки цикла 10 nano секунд или меньше на одну итерацию на современных процессорах.

Цитирование @Rotsor:

Если у вас есть проблема с ~ 16G итераций, выполняющих 55 часов, это означает, что они очень далеки от примитивности (80 Кбит / с? Это смешно), поэтому, возможно, нам следует знать больше.

80 000 операций в секунду - это около 12,5 микросекунд каждая - в 1000 раз больше, чем можно ожидать из-за издержек цикла.

Предполагая, что ваша 55-часовая среда выполнения однопоточная, и если ваши операции с каждым элементом настолько просты, как это было предложено, вы сможете (консервативно) добиться ускорения в 100 раз и очень легко сократить его до менее часа.

Если вы хотите по-прежнему работать быстрее, вам стоит взглянуть на написание многопоточного решения, и в этом случае будет необходим язык, который обеспечивает хорошую поддержку. Я бы склонялся к PLINQ и C # 4.0, но это потому, что я уже знаю C # - YMMV.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...