Доброго дня коллеги!
Интересно, есть ли в .Net возможности (имею ввиду что-то готовое или близко к этому), обеспечивать параллелализм в алгоритмах
на основе техники упоминаемой в статье ?
суть техники — наличие примитива:
join( do_a, do_b )
Основной момент тут в том, что два замыкания потенциально могут выполниться параллельно: решение, использовать или нет параллельные потоки, принимается динамически, в зависимости от того, есть ли свободные ядра или нет. Идея в том, что вы можете с помощью join помечать в своей программе те места, где параллелизм может быть полезен, а затем позволить библиотеке во время выполнения решать, использовать ли его или нет.
Внутри join реализован с использованием техники, известной как перехват работы. Насколько мне известно, перехват работы был впервые представлен как часть проекта Cilk, и с тех пор стал довольно стандартной техникой (фактически название Rayon (англ. «вискоза», а «Cilk» аллюзия на «silk», т.е. «шёлк» — прим. перев.) — дань уважения Cilk).
Главная идея в том, что при каждом вызове join(a, b) мы определяем две задачи a и b, которые могут быть безопасно выполнены параллельно, но мы пока что не знаем, есть ли для этого свободные потоки. Всё, что делает текущий поток, это добавляет b в очередь «планируемой работы», а затем берёт, и немедленно выполняет a. В то же время существует пул других активных потоков (обычно по одному потоку на ядро ЦП, или что-то типа того). Как только какой-то из потоков освобождается, он идёт и копается в очередях «планируемой работы» других потоков: если там находится задача, свободный поток захватывает её и выполняет её сам. Так что в таком случае, пока первый поток занят выполнением a, другой поток может начать выполнение b.
Как только первый поток заканчивает a, он проверяет: начал ли кто-то другой выполнять b? Если нет, то он выполняет её сам. Если да, то ему нужно подождать, пока другой поток её закончит. Но пока первый поток ждёт, он может пойти и стащить работу у другого потока, тем самым способствуя завершению всего процесса работы в целом.
Первое что приходит в голову — создать для задачи b Task и дождаться его окончания, но в моём тесте — таск b всегда стартовал на другом потоке, и в итоге оверхид на синхронизацию (при условии относительно небольшой работы выполняемой в нём) будет заметен. это недостатки шедулинга тасков? или всегда таск стартует на другом потоке? или лучше такую технику реализовать как-то по другому?
MH>Первое что приходит в голову — создать для задачи b Task и дождаться его окончания, но в моём тесте — таск b всегда стартовал на другом потоке, и в итоге оверхид на синхронизацию (при условии относительно небольшой работы выполняемой в нём) будет заметен. это недостатки шедулинга тасков? или всегда таск стартует на другом потоке? или лучше такую технику реализовать как-то по другому?
У меня в одном из проектов свой Scheduler, который создаёт свой пул строго по числу ядер, и по ним раскидывает задачи. Этот же всемогутор отвечает за свои версии For/ForEach. Синхронизации при таком исполнении минимум — из-за того что точно знаешь максимальное число потоков и сами потоки, можно многие виды циклов сделать даже без interlocked счётчиков. Если есть небольшие объёмы задач которые надо быстро протолкнуть и ждать следующей пачки данных (совсем как у тебя) — то такой подход вполне рулит.
Здравствуйте, MadHuman, Вы писали:
MH>Доброго дня коллеги! MH>Интересно, есть ли в .Net возможности (имею ввиду что-то готовое или близко к этому), обеспечивать параллелализм в алгоритмах MH> на основе техники упоминаемой в статье ?
TPL, Parallel.For, PLINQ etc. Детальный ответ зависит от задачи, которую вы пытаетесь решить и от типа нагрузки (утыкаемся в процессор/память/IO).
P.S. В большинстве случаев попытка ускорить что-либо без повторяемых замеров до-после приводит к самым неожиданным результатам
Здравствуйте, Sinix, Вы писали:
S>TPL, Parallel.For, PLINQ etc. Детальный ответ зависит от задачи, которую вы пытаетесь решить и от типа нагрузки (утыкаемся в процессор/память/IO).
S>P.S. В большинстве случаев попытка ускорить что-либо без повторяемых замеров до-после приводит к самым неожиданным результатам
понравилась сама техника, когда обеспечивется динамическая параллелизация в зависимости от текущей нагрузки. конкретной задачи пока нет, но если будет понятно как обеспечить такую технику, то и места найдутся где применить. ну и думаю понятно что это для cpu типа нагрузки.
для примера можно взять пример из статьи (код на Rust, но думаю понятен), когда за счет простой его модификации алгоритм сортировки qsort на 4-х ядерной машине ускорился до 4-х раз.
fn quick_sort<T:PartialOrd+Send>(v: &mut [T]) {
if v.len() > 1 {
let mid = partition(v);
let (lo, hi) = v.split_at_mut(mid);
//было так quick_sort(lo); quick_sort(hi);
//таким простым изящным способом и обеспечивается параллелизация
rayon::join(|| quick_sort(lo),
|| quick_sort(hi));
}
}
fn partition<T:PartialOrd+Send>(v: &mut [T]) -> usize {
// см. https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
}
Осталось прикинуть распределение значений, как часто количество элементов будет больше 1k?
Подвох в том, что "распараллелил == ускорил" не работает. Точнее, работает не так, как ожидали: общая производительность системы может падать, причём из-за исчерпания ресурсов внезапно на порядки. Неоднократно узнавали сложным способом, последний был полгода назад. Из-за высокой нагрузки на CPU отпал низкоприоритетный поток, который неспешно разгребал заявки в фоне и дальше подвисла цепочка обработчиков, которые видели, что заявки в очереди есть и ожидала их через spin wait. Что, понятное дело, нагрузку на CPU не уменьшило
Повезло, что стабильно воспроизводилось, иначе не поймали бы никогда — "ускоренный код" был вообще в другой сборке.
MH>Интересно, есть ли в .Net возможности (имею ввиду что-то готовое или близко к этому), обеспечивать параллелализм в алгоритмах MH> на основе техники упоминаемой в статье ?
Здравствуйте, vaskir, Вы писали:
MH>>Интересно, есть ли в .Net возможности (имею ввиду что-то готовое или близко к этому), обеспечивать параллелализм в алгоритмах MH>> на основе техники упоминаемой в статье ?
V>https://github.com/Hopac/Hopac
А как именно при использовании этой библиотеки будет выглядеть аналог исходного join?
S>Подвох в том, что "распараллелил == ускорил" не работает. Точнее, работает не так, как ожидали: общая производительность системы может падать, причём из-за исчерпания ресурсов внезапно на порядки. Неоднократно узнавали сложным способом, последний был полгода назад. Из-за высокой нагрузки на CPU отпал низкоприоритетный поток, который неспешно разгребал заявки в фоне и дальше подвисла цепочка обработчиков, которые видели, что заявки в очереди есть и ожидала их через spin wait. Что, понятное дело, нагрузку на CPU не уменьшило
спасибо. интересный результат.
F# хорош, мне нравится
я пробовал также qsort на c#, результаты были такие (на 2млн массиве):
0.8сек — исходная реализация без попыток использования join
1.5сек — добавлен join(A,B) (с реализаций создания вначале Task-а для B, затем запуск A, затем ожидание завершения таска для B) и всегда передаётся флаг "не пытаться параллелить". то есть всегда A и B выполняются синхронно последовательно вызвавшим потоком. оверхид возник на заворачивание в Action-ы и их вызовы. неслабо так.
1.3сек — запуск join(A,B) с параллельным выполнением B. даже не обогнали исходную версию! wtf?.
интересно в чем дело? неэффективный шедулинг тасков в таком кэйсе?
и почему hopac даёт такое заметное ускорение? куда делся оверхид на создание job-ов, шедулинг работы в другой поток...
и самое интересное почему в исходной статье пример на rust-е при сортировке примерно 1млн массива ускорился аж почти в 4-ре раза?
неужели родной в .Net шедулинг тасков настолько уступает? ведь вроде они как раз оптимизированы под выполнение мелких cpu задач?
Вы, используете hopac в реальных проектах? как впечатления?
//аналог примитива join из rust rayonpublic static void join_(Action a, Action b, bool tryDoBParallel = true) {
Task t = null;
if (tryDoBParallel && a != null && b != null)
t = Task.Factory.StartNew(b);
if (a != null)
a();
if (t != null)
t.Wait();
else {
if (b != null)
b();
}
return;
}
Тут одно из двух — либо ты любишь синтаксис ML, либо ненавидишь
MH>интересно в чем дело? неэффективный шедулинг тасков в таком кэйсе? MH>и почему hopac даёт такое заметное ускорение? куда делся оверхид на создание job-ов, шедулинг работы в другой поток...
Используем. Впечатления двоякие. 1. Очень и очень мощная либа, ничего похожего даже отдаленно нет под .NET 2. Отлаживать код сложно, написать неверно работающий код — раз плюнуть. 3. Народ попроще, вроде тестеров, принципиально не врубается что это вообще такое и зачем нужно.
