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

Подход прост:

Создайте массив целых чисел и обнулите его. (Я использую 2001 целых чисел)Повторно рассчитать индексы в этом массиве и индексировать эту запись в массиве, следующим образомЦикл или 999 или 1000 раз. На каждой итерации:Заполнить индекс массива центральным значением (1000)Генерация случайного числа = + 1 / -1. и добавить его в индекс массивав конце цикла увеличьте значение на рассчитанный индекс массива.

Поскольку случайные значения 0/1 имеют тенденцию встречаться примерно так же часто, конечное значение индекса из внутреннего цикла выше имеет тенденцию оставаться близко к центральному значению. Значения индекса, намного большие / меньшие, чем начальное значение, становятся все более необычными.

После большого количества повторений значения в массиве принимают форму кривой распределения нормального распределения. Однако высококачественная случайная функция arc4random_uniform (), которую я использую, довольно медленная, и для создания гладкой кривой требуется МНОЖЕСТВО итераций.

Я хотел построить 1 000 000 000 (один миллиард) очков. Работа в основном потоке занимает около 16 часов.

Я решил переписать код расчета для использования dispatch_async и запустить его на моем 8-ядерном Mac Pro.

В итоге я использовал dispatch_group_async () для отправки 8 блоков, а dispatch_group_notify () - для уведомления программы о завершении обработки всех блоков.

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

В любом случае, я реорганизовал код для использования dispatch_group_async () и вычислил 1/8 от общего значения в каждом блоке, и отключил мой код для запуска. К моему полному замешательству, параллельный код, в то время как он максимально использует все ядра на моем Mac, работаетМНОГО медленнее, чем однопоточный код.

При запуске в одном потоке, я получаю около 17 800 точек в секунду. При запуске с использованием dispatch_group_async производительность падает примерно до 665 точек в секунду, илипримерно 1/26 как быстро, Я изменил количество блоков, которые я отправляю - 2, 4 или 8, это не имеет значения. Производительность ужасная. Я также попытался просто отправить все 8 блоков, используя dispatch_async без dispatch_group. Это тоже не важно.

Там в настоящее время нет блокировки / блокировки: все блоки работают на полной скорости. Я совершенно не понимаю, почему параллельный код работает медленнее.

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

Вот код, который выполняет вычисления:

randCount = 2;
#define K_USE_ASYNC 1

#if K_USE_ASYNC
    dispatch_queue_t highQ = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0);
    //dispatch_group_async

    dispatch_group_t aGroup = dispatch_group_create();
    int totalJobs = 8;
    for (int i = 0; i<totalJobs; i++)
    {
      dispatch_group_async(aGroup,
                           highQ,
                           ^{
                             [self calculateNArrayPoints: KNumberOfEntries /totalJobs
                                          usingRandCount: randCount];
                           });
    }


    dispatch_group_notify(aGroup,
                          dispatch_get_main_queue(),
                          allTasksDoneBlock
                          );
#else
    [self calculateNArrayPoints: KNumberOfEntries
                 usingRandCount: randCount];
    allTasksDoneBlock();
#endif

И общий метод расчета, который используется как однопоточным, так и параллельным вариантом:

+ (void) calculateNArrayPoints: (NSInteger) pointCount usingRandCount: (int) randCount;
{
  int entry;
  int random_index;

  for (entry =0; entry<pointCount; entry++)
  {
    static int processed = 0;
    if (entry != 0 && entry%100000 == 0)
    {
      [self addTotTotalProcessed: processed];
      processed = 0;
    }

    //Start with a value of 1000 (center value)
    int value = 0;

    //For each entry, add +/- 1 to the value 1000 times.
    int limit  = KPinCount;
    if (randCount==2)
      if (arc4random_uniform(2) !=0)
        limit--;
    for (random_index = 0; random_index<limit; random_index++)
    {
      int random_value = arc4random_uniform(randCount);
      /*
       if 0, value--
       if 1, no change
       if 2, value++
       */
      if (random_value == 0)
        value--;
      else if (random_value == randCount-1)
        value++;
    }
    value += 1000;
    _bellCurveData[value] += 1;
    //printf("\n\nfinal value = %d\n", value);
    processed++;
  }
}

Это быстрый и грязный учебный проект. Он работает как на Mac, так и на iOS, поэтому использует класс общих утилит. Класс утилит - это не что иное, как методы класса. Не существует экземпляра созданного метода утилит. У него смущающее количество глобальных переменных. Если я в конечном итоге сделаю что-нибудь полезное с кодом, я реорганизую его, чтобы создать синглтон утилит и преобразовать все глобальные переменные в переменные экземпляра на синглтоне.

Пока это работает, и отвратительное использование глобалов не влияет на результат, поэтому я оставляю это.

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

Я в тупике Я написал достаточное количество параллельного кода, и эта задача "смущающе параллельно"проблема, поэтому нет никаких причин, по которым он не должен работать с полным наклоном на всех доступных ядрах.

Кто-нибудь еще видит что-нибудь, что может вызвать это, или может предложить какие-то другие идеи?