Параллельно на C ++ не так быстро, как C #

Question

У меня есть такой код на C #

private static Random random = new Random();
public static string RandomString(int length)
{
    const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    return new string(Enumerable.Repeat(chars, length)
      .Select(s => s[random.Next(s.Length)]).ToArray());
}
     Task.Factory.StartNew(() => {       
                 System.Threading.Tasks.Parallel.For(0L, 10000000, new ParallelOptions { MaxDegreeOfParallelism = Environment.ProcessorCount * 10 }, n =>
                 {
                 Console.WirteLine(RandomString(12));
                 });
                }

Добавьте к нему параллельный метод, он сможет запустить генерацию 10 миллионов случайных строк менее чем за 8 секунд и использовать всю мощность процессора

введите описание изображения здесь

Я попытался сделать это снова в C ++

string NonRepeatChar(int max_len)
{
    std::string valid_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(valid_chars.begin(), valid_chars.end(), g);
    std::string rand_str(valid_chars.begin(), valid_chars.begin() + max_len);
    return rand_str;
}

Применил код к рекомендованному параллельному методу C ++

void multiply()
{
for (size_t i = 0; i < 10; i++)
{
    for (size_t j = 0; j < 10; j++)
    {           
        for (int k = 0; k < 10; k++)
        {
            printf("%s\n",NonRepeatChar(10));
        }           
    }
}
}

class Foo {
public:
    Foo() : counter_(0) {}

    std::pair<string, std::future<void>> a_function(std::future<void>& f) {
        // Ensure that the background task from the previous iteration
        // has completed
        f.wait();

        // Set the task for the next iteration
        std::future<void> fut = std::async(std::launch::async, &Foo::background_task, this);

        // Do some work
        string value = NonRepeatChar(12);

        // Return the result and the future for the next iteration
        return std::make_pair(value.c_str(), std::move(fut));
    }

    void background_task() {
        ++counter_;
    }

private:
    std::atomic<int> counter_;
};

Запишите время запуска

int main()
{   
    clock_t tStart = clock();
    std::future<void> bleak = std::async(std::launch::deferred, []() {});

    Foo foo;

    for (size_t i = 0; i < 10000; ++i) {
        // Call the function
        std::pair<string, std::future<void>> result = foo.a_function(bleak);    
        bleak = std::move(result.second);   
        std::cout << result.first << "\n";
    }
    printf("Time taken: %.2fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);
    return 0;
    }

Вот мой результат:

10,98 с // нормальный цикл

8,76 с // умножить

8.88s // Foo

Очевидно, что код не имеет никакой разницы по сравнению с исходным циклом, генерирует только 10000 строк, и он даже не использует всю мощность процессора, такую ​​как C #. Что-то не так с параллельным методом? Как я могу оптимизировать это?

Answer 1

Это простой однопоточный пример того, что можно сделать с гибридным C / C ++ подход. Разработчики игр используют методы, которые являются гибридами «формального» кода C ++ и меньше похож на питона. Конечно, как и Marmite, вы любите это или ненавидите, но результаты говорят сами за себя.

Я прошу прощения, если это больше, чтобы узнать, что вы думали.

Этот конкретный пример генерирует 10M строк в 3.682 с в одном потоке на моей старой коробке AMD. Вы можете запустить небольшое количество асинхронных рабочих (

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

#include <stdint.h>
#include <stdio.h>

// This is typical of the random number generators used in professional games.
// It is less "correct" than mersenne twisters, for example, but much faster.
inline uint32_t fast_rand(int32_t &seed, uint32_t limit) {
  // Prevent infinite loops.
  //if (limit == 0) return 0;

  // Make a mask that has all 1s in the bottom few bits.
  // This reduces the number of iterations of the loop to ~1
  int leading_zeros = __builtin_clz(limit);
  int mask = 0xffffffff >> leading_zeros;

  // Loop until our result is in range using rotate and xor.
  do {
    seed = (seed << 1) ^ ((seed >> 31) & 0xa53a9be9);
  } while ((seed & mask) >= limit);

  return seed & mask;
}

int main() {
  // I'm using two seeds to prevent coupling.
  // On their own, their quantiles are pretty flat, but
  // in this example they couple, causing conditioning in the results.
  int32_t length_seed = (int32_t)0x95abcfad;
  int32_t swap_seed = (int32_t)0xba7235fab;

  for (int i = 0; i != 10000000; ++i) {
    // Note we don't use a std::string. These are very slow.
    char chars[] = 
      "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    auto num_chars = sizeof(chars) - 1;
    auto length = fast_rand(length_seed, num_chars-1) + 1;

    // Trim the string to the right length.
    chars[length] = 0;

    // Shuffle the characters.
    for (int j = 0; j != length; ++j) {
      int swapper = j + fast_rand(swap_seed, length - j);
      auto tmp = chars[j];
      chars[j] = chars[swapper];
      chars[swapper] = tmp;
    }

    // Print with puts (not iostreams).
    puts(chars);
  }
}

Для примеров «горячей петли», подобных этому, вы должны проверить свой результат на Godbolt или подобном.

clang с -O3 -mlzcnt дает следующий внутренний цикл.

.LBB0_4:                                #   Parent Loop BB0_1 Depth=1
    mov     rsi, rax
    sub     rsi, rdx
    lzcnt   ecx, esi
    mov     edi, -1
    shr     edi, cl
.LBB0_5:                                #   Parent Loop BB0_1 Depth=1
    lea     ecx, [rbx + rbx]
    sar     ebx, 31
    and     ebx, -1522885655
    xor     ebx, ecx
    mov     ecx, ebx
    and     ecx, edi
    cmp     rsi, rcx
    jbe     .LBB0_5
    add     ecx, edx
    mov     sil, byte ptr [rsp + rdx]
    movsxd  rdi, ecx
    mov     cl, byte ptr [rsp + rdi]
    mov     byte ptr [rsp + rdx], cl
    mov     byte ptr [rsp + rdi], sil
    add     rdx, 1
    cmp     rdx, rax
    jne     .LBB0_4

Answer 2

Ваш код C ++ вовсе не эквивалентен вашему C # one.

На стороне C # ,

Вы используете Parallel.For из пространства имен System.Threading.Tasks. Это высокоуровневая конструкция, которая позволяет выполнять итерации цикла параллельно, без необходимости управления потоками на низком уровне, поскольку задачи автоматически создаются для вас и распределяются по ядрам вашего процессора оптимальным образом для ваша система.

В случае вашего конкретного кода Parallel.For настроен на одновременное планирование максимум Environment.ProcessorCount * 10 рабочих потоков. Хотя это и не является гарантией (планировщики библиотеки будут иметь последнее слово), это должно обеспечить оптимальное использование процессорных ядер для представленной рабочей нагрузки, так как имеется достаточно задач, чтобы занять все ядра, и достаточно большая рабочая очередь, чтобы убедиться, что ядра не страдают от голода из-за отсутствия запланированных заранее работ.

На стороне C ++ ,

Вы используете async и future, которые являются конструкциями более низкого уровня, которые позволяют запускать фоновые задачи, но вы искусственно ограничиваете свой уровень параллелизма, вызывая синхронизацию на каждой итерации:

// Ensure that the background task from the previous iteration
// has completed
f.wait();

Самый простой (но непереносимый) способ, с помощью которого вы можете добиться поведения в C ++, похожего на ваш код C #, - это использовать Microsoft Parallel Patterns Library . Это обеспечивает функциональность, которая очень похожа на то, что System.Threading.Tasks.Parallel.For предоставляет на стороне C #, то есть concurrency::parallel_for.