Самый быстрый язык для ДЛЯ циклов

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

(def mylist ["i" "j" "i" "i" "j" "i"])
(map #(= "i" %) mylist)

результат

(истина ложь истина истина ложь истина)

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

Цитата @Rotsor:

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

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

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

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

APL.

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

Вот пример простоты работы с массивами в APL:

    A <- 2 3 4 5 6 8 10
    ((2|A)/A) <- 0
    A
2 0 4 0 6 8 10

Первая строка задает A вектор чисел. Вторая строка заменяет все нечетные числа в векторе нулями. Третья строка запрашивает новые значения A, а четвертая строка - результирующий вывод.

Обратите внимание, что явного цикла не требуется, так как скалярные операторы, такие как '|' (остаток), автоматически распространяются на массивы по мере необходимости. APL также имеет встроенные примитивы для поиска и сортировки, что, вероятно, будет быстрее, чем написание собственных циклов для этих операций.

В Википедии есть хорошая статья по APL, в которой также даны ссылки на поставщиков, таких как IBM и Dyalog.

Может, вам лучше всего подойдет ассемблерная вставка, написанная вручную? Если, конечно, вам не нужна переносимость.

Это и оптимизированный алгоритм должны помочь (и, возможно, реструктурировать данные?).

Вы также можете попробовать несколько алгоритмов и профилировать их.

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 работают очень быстро, вам просто нужно найти способы выразить свои алгоритмы непосредственно в терминах матричные операторы.

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

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

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

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

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

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

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

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

Как хранятся данные? На время выполнения, вероятно, больше влияет ввод-вывод (особенно диск или, что еще хуже, сеть), чем ваш язык.

Предполагая, что операции со строками ортогональны, я бы выбрал C # и использовал PLINQ , чтобы использовать весь возможный параллелизм.

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

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

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

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

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

void doit(){
  double sum = 0;
  for (int i = 0; i < 1000; i++){
    for (int j = 0; j < 16000000; j++){
      sum += j * 3.1415926;
    }
  }
}

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

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

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

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] Возможны некоторые микро -оптимизации, но они не дадут желаемых скоростей.

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