[recovery mode] Parallel или в один поток? Внезапные результаты

Исходные данные: Есть простой алгоритм для генерации комбинаций.

Задача: Заставить работать быстрее с минимумом программист\часов

Решение: Parallel, Claster, Thread\Tasks

статья может быть дописана

• исходный алгоритм
  

  
  for( int i1cards=0; i1cards< cards.Count(); i1cards++ ) {
          for( int i2cards=0; i2cards< cards.Count(); i2cards++ ) {
            Card[] _cards = new Card[] { cards[i1cards], cards[i2cards] };
            if( result.Exists( pair => pair.Contains(_cards[0]) && pair.Contains(_cards[1]) ) )
              continue;
            result.Add( _cards );
          }
        }
  
  

  
  if( result.Exists( pair => pair.Contains(_cards[0]) && pair.Contains(_cards[1]) ) ) — так мы исключаем из результирующего списка сгенеренную комбинацию. (Далее это вынесено за пределы цикла для «чистого тестирования циклов» и соответствующим образом изменено)


• первое улучшение
  

  
  foreach( Card card1 in cards ) {
          foreach( Card card2 in cards ) {
            foreach( Card card3 in cards ) {
              result.Add( new Card[]{card1,card2,card3} );
            }
          }
        }
  
  



• второе улучшение
  

  
  Parallel.ForEach( cards, ( card1 ) =>
          Parallel.ForEach( cards, ( card2 ) => {
              result.Add( new Card[] { card1, card2 } );
          } ) );
  
  

  
  Загрузило процессор на 100% на несколько минут и свыше 10 потоков (число потоков изменялось на протяжении генерации). recult.Count = разные больше 100,000.


• Добавил в начало функции:
  

  
  ParallelOptions po= new ParallelOptions() {
          MaxDegreeOfParallelism = 8,
        };
  
  

  
  Это так сказать глобальные настройки для работы Parallel. MaxDegreeOfParallelism — ограничивает максимально допустимым числом потоков (в нашем случае ограничили 8 потоками)
  
  Загрузка процессора все те же 100% и 10 потоков (с последующим увеличением числа потоков) и отработка около секунды.


• 
  

  
  Partitioner.Create( cards, true ).AsParallel().ForAll( ( card1 ) =>
          Partitioner.Create( cards, true ).AsParallel().ForAll( ( card2 ) =>
            Partitioner.Create( cards, true ).AsParallel().ForAll( ( card3 ) =>
              result.Add( new Card[3] { card1, card2, card3 } )
          ) ));
  
  

  
  Partitioner.Create( cards, true ) — заставляет разбивать на блоки. Т.е. если обычный foreach выполняет по одному вхождению в потоке, то в этом случае будет сразу несколько итераций взято в одном потоке.
  
  Загрузка процессора меньше 5% и потоков выше 50. recult.Count = 113698, 114976. Иногда выскакивает исключилка: «Длина результирующего массива недостаточна» или «Индекс находился вне границ массива.».


• 
  

  
  Partitioner.Create( cards, true ).AsParallel().WithMergeOptions( ParallelMergeOptions.FullyBuffered ).ForAll( ( card1 ) =>
          Partitioner.Create( cards, true ).AsParallel().WithMergeOptions( ParallelMergeOptions.FullyBuffered ).ForAll( ( card2 ) =>
            Partitioner.Create( cards, true ).AsParallel().WithMergeOptions( ParallelMergeOptions.FullyBuffered ).ForAll( ( card3 ) =>
              result.Add( new Card[3] { card1, card2, card3 } )
          ) ));
  
  

  
  WithMergeOptions( ParallelMergeOptions.FullyBuffered ) — заставляет при распараллеливании использовать настройку объединения и в нашем случае с режимом FullyBuffered, т.е. полностью буферизовать.
  
  Число потоков свыше 50, загрузка процессора меньше 5%. recult.Count = 114988, 133495.


• 
  

  
  cards.ForEach( ( card1 ) =>
          cards.ForEach( ( card2 ) =>
            cards.ForEach( ( card3 ) =>
              result.Add( new Card[] { card1, card2, card3 } )
              ) ) );
  
  

  
  Отработка мгновенная. Не успел увидеть изменения числа потоков. recult.Count = 140608.
  
  По идее, должно само распараллеливать вычисления (сейчас уже не могу вспомнить где, но определенные операции вида, Select, Where,… другие запросы разработаны microsoft так, что оно само раскидывает на потоки, а использование AsParallel явно указывает распараллеливать.


• 
  

  
  cards.AsParallel().ForAll( ( card1 ) =>
          cards.AsParallel().ForAll( ( card2 ) =>
            cards.AsParallel().ForAll( ( card3 ) =>
              result.Add( new Card[] { card1, card2, card3 } )
              ) ) );
  
  

  
  Процессор меньше 5% и потоков выше 50. recult.Count = 136339, 135416. Иногда выскакивает исключилка: «Длина результирующего массива недостаточна» или «Индекс находился вне границ массива.» (под час частота появления этих ошибок бывает изумительно большая).

Изобретаем свое

будем использовать Thread, Task, WCF (мультипроцесс сеть (бот-нет)… нужно?..

Изюм

Мне, как рядовому программисту, не очень понятно по какому же алгоритму работают эти механизмы от разработчиков microsoft. Там где оно должно работать предсказуемо и просто — работает с какой-то магией.

Все что я вычитал из справки к этим классам не содержит информации о том, что обычный for по конечному числу элементов будет выдавать разные результаты, подчас «Очень» разные, возможно, я нарвался на недокументированные возможности, которые можно использовать как «Генератор случайных чисел».

Я «где-то» читал, что Parallel и PLINQ должны сами рассчитывать оптимальное число потоков в зависимости от ресурсов и ресурсоемкости распараллеливаемого алгоритма, но иногда вычисления занимают через чур много времени, а систему даже не загружают и на 5%.

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

Проблема с исключением из результата

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

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.