Почему этот алгоритм в Ruby работает быстрее, чем в Parallel'd С#?

Следующий код ruby ​​работает в ~ 15 секунд. Он почти не использует процессор/память (около 25% от одного процессора):

def collatz(num)
   num.even? ? num/2 : 3*num + 1
end

start_time = Time.now
max_chain_count = 0
max_starter_num = 0
(1..1000000).each do |i|
    count = 0
    current = i
    current = collatz(current) and count += 1 until (current == 1)
    max_chain_count = count and max_starter_num = i if (count > max_chain_count)
end

puts "Max starter num: #{max_starter_num} -> chain of #{max_chain_count} elements. Found in: #{Time.now - start_time}s"

И следующий TPL С# помещает все мои 4 ядра в 100% использование и на несколько порядков медленнее, чем рубиновая версия:

static void Euler14Test()
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    int max_chain_count = 0;
    int max_starter_num = 0;
    object locker = new object();
    Parallel.For(1, 1000000, i =>
    {
        int count = 0;
        int current = i;
        while (current != 1)
        {
            current = collatz(current);
            count++;
        }
        if (count > max_chain_count)
        {
            lock (locker)
            {
                max_chain_count = count;
                max_starter_num = i;
            }
        }
        if (i % 1000 == 0)
            Console.WriteLine(i);
    });
    sw.Stop();
    Console.WriteLine("Max starter i: {0} -> chain of {1} elements. Found in: {2}s", max_starter_num, max_chain_count, sw.Elapsed.ToString());
}

static int collatz(int num)
{
    return num % 2 == 0 ? num / 2 : 3 * num + 1;
}

Почему ruby ​​работает быстрее, чем С#? Мне сказали, что Рубин медленный. Это не так, если речь идет о алгоритмах?

Perf ПОСЛЕ коррекции:

  • Ruby (Non parallel): 14.62s
  • С# (непараллельно): 2.22s
  • С# (с TPL): 0.64s

Ответы

Ответ 1

Собственно, ошибка довольно тонкая и не имеет ничего общего с потоками. Причина, по которой ваша версия С# занимает настолько много времени, состоит в том, что промежуточные значения, вычисленные методом collatz, в конечном итоге начинают переполнять тип int, что приводит к отрицательным числам, которые могут затем уходить в возрасте, чтобы сходиться.

Это происходит, когда i составляет 134 379, для которого термин 129 th (при условии подсчета на основе одного) равен 2,482,111,348. Это превышает максимальное значение 2,147,483,647 и поэтому хранится как -1,812,855,948.

Чтобы получить хорошую производительность (и правильные результаты) в версии С#, просто измените:

int current = i;

... в:

long current = i;

... и:

static int collatz(int num)

... в:

static long collatz(long num)

Это снизит вашу производительность до респектабельных 1,5 секунд.

Изменить: CodesInChaos поднимает очень правильную точку в вопросе включения проверки переполнения при отладке приложений, ориентированных на математику. Это позволило бы сразу определить ошибку, поскольку среда выполнения создала бы OverflowException.

Overflow checking

OverflowException

Ответ 2

Должно быть:

Parallel.For(1L, 1000000L, i =>
    {

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

Ответ 3

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

Есть альтернатива для этого: вы можете получить, сколько у вас ядер процессора, и чем использовать цикл parallelism с тем же количеством итераций, которые у вас есть ядра, каждый цикл будет оценивать часть требуемого цикла, он сделанный путем создания внутреннего цикла цикла, который зависит от параллельного цикла.

РЕДАКТИРОВАТЬ: ПРИМЕР

int start = 1, end = 1000000;
Parallel.For(0, N_CORES, n =>
{
    int s = start + (end - start) * n / N_CORES;
    int e = n == N_CORES - 1 ? end : start + (end - start) * (n + 1) / N_CORES;
    for (int i = s; i < e; i++)
    {
        // Your code
    }
});

Вы должны попробовать этот код, я уверен, что это сделает работу быстрее.

EDIT: ELUCIDATION

Ну, довольно давно я ответил на этот вопрос, но снова столкнулся с проблемой и, наконец, понял, что происходит.

Я использую реализацию AForge цикла Parallel for, и кажется, что он запускает поток для каждой итерации цикла, поэтому, если цикл занимает относительно небольшое количество времени для выполнения, вы заканчиваете с неэффективным parallelism.

Итак, как некоторые из вас указали, методы System.Threading.Tasks.Parallel основаны на Tasks, которые являются более высоким уровнем абстракции потока:

"За кулисами задачи поставлены в очередь на ThreadPool, которые были расширены с помощью алгоритмов, которые определяют и корректируют количество потоков и обеспечивают балансировку нагрузки для максимальной пропускной способности. Это делает задачи относительно легкими, и вы можете создавать множество из них для обеспечения мелкозернистого parallelism.

Итак, если вы используете библиотечную реализацию по умолчанию, вам не нужно будет использовать этот "фиктивный".