Здравствуйте, Кодт, Вы писали:
К>Высокоуровневая — потому, что цена за межпотоковое взаимодействие не должна превысить выгоды распараллеливания. К>То есть, матрицы 10*10 перемножать на нескольких ядрах — смысла нет, а вот матрицы 10000*10000 — уже есть.
Матрицы перемножать надо на GPU. Они для этого предназначены.
И вообще, такие вещи должны делать библиотеки. Не должен каждый писать свой вариант перемножения матриц.
В общем, пример из пальца высосан.
В реальности речь почти всегда идет о сложных задачах с кучей ветвлений и сложных данных. И вот в этих условиях распараллеливание цикла ничего не дает. Все существенно сложнее.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Khimik, Вы писали:
EP>>Запустится несколько потоков и будет произведена параллельная редукция — проблемы нет, так как операция умножения ассоциативна: EP>>
EP>> #pragma omp parallel for reduction(*:result)
EP>> for(T i = 1; i <= N; ++i)
EP>> result *= i;
EP>>
K>Сорри за профанство, но я не понимаю как этот код работает. Речь шла о том, что вычисление факториала как раз нельзя распараллелить. Или в этом коде оно паралеллится частично, типа цифры с 2 до 5 перемножаются в одном процессе, с 6 по 9 в другом, потом два результата перемножаются и получается факториал девяти?
Да, именно так. Параллельная редукция это одна из базисных операций для параллельных алгоритмов, причём как для multi-core, для multi-node (а-ля MPI_Reduce), так и для GPGPU.
То есть нужно вычислить:
a * b * c * d
где a,b,c,d — произвольные данные, а * — произвольная ассоциативная бинарная операция. За счёт ассоциативности имеем возможность расставить скобки как нам требуется (что по сути уменьшает зависимости между данными):
(a * b) * (c * d)
И соответственно вычислять операции в скобках параллельно.
На самом деле это подходит и для операций с плавающей точкой, несмотря на то что они неассоциативные. Главное понимать что результат может зависеть от порядка вычислений, и часто эти различия допустимы (в случае floating point).
Здравствуйте, Khimik, Вы писали:
K>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные.
Это такой детский, дилетантский взгляд. Он преобладал в 90-е. Тогда думали, что если сделать расширение императивных языков, то все срузу ускорится во столько раз, сколько у тебя есть процессоров.
В реальности, это самообман.
Параллелить вычисления на уровне циклов чуть менее чем бесполезно.
В реальном мире есть задачи которые хорошо параллелятся и те что параллелятся плохо.
У большинства вычислений есть четкая последовательность. Чтобы вычислить Б нужно сначала вычислить А, и т.д.
Параллелить можно "в большом". Простой пример. Вот есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто.
На мой взгляд от языков программирования следующего поклонения нужно требовать не автоматического распараллеливания, а обеспечения гарантий корректности ручного распараллеливания.
Ну не может эффективно распараллеливать вычисления автомат (программа). А человек — может.
Значит нужно ему помочь.
Я считаю, что следующим шагом в развитии человечества будет обеспечение локальности данных и повышение эффективности изменения и "копирования" локальных данных.
Возвращаемся к тем же файлам. Вот отпарсили мы файл в отдельном потоке. Теперь надо сделать так, чтобы я мог обработать полученные данные ( а их очень много) параллельно с остальными данными (из других файлов) и при этом не иметь проблем с блокировками и не копировать все данные.
Для того нужно чтобы программист оперировал некими областями памяти которые можно изменят только из одного потока управления. И предоставить программисту дешевый способ передачи "замороженного слепа информации" из одного потока в другой.
Иными словами нужно сделать так, чтобы потоки не имели общих изменяемых данных, а передача данных из одного потока в другой была прозрачной и дешевой.
У меня есть масса мыслей по этому поводу. Но это требует разработки нового языка программирования. И нового рантайма для него.
Правильные мысли есть в Расте. Но там все слишком сложно для того чтобы это могло войти в мэйнстрим. Нужно научить языки манипулировать кучами. Научить передавать эти кучи между "виртуальными процессами" (в стиле Эрланг).
Для этого нужно создавать новые языки программирования.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Параллелить вычисления на уровне циклов чуть менее чем бесполезно.
Не факт.
Параллелизм — это высокоуровневая векторизация.
Высокоуровневая — потому, что цена за межпотоковое взаимодействие не должна превысить выгоды распараллеливания.
То есть, матрицы 10*10 перемножать на нескольких ядрах — смысла нет, а вот матрицы 10000*10000 — уже есть.
Здравствуйте, Khimik, Вы писали:
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм?
Языки 4-го поколения например sql. Где компилятор сам синтезирует и распаралеливает алгоритм.
K>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
В таких языках циклов не нужно. Просто другие примитивы — выборки, свёртки и т.п.
Здравствуйте, Sharov, Вы писали:
S>Если везде и всюду использовать типы из ConcurrentCollections, то зуб дам.
А если в эту коллекцию положить изменяемый объект? Ты можешь гарантировать что на этот объект не будет ссылок из разных потоков?
Ты такими темпами без зубов останешься.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Khimik, Вы писали:
EP>>Для C++ ещё есть OpenMP — там вообще параллелятся самые обыкновенные циклы, посредством добавления #pragma. Но библиотеки типа TBB всё же лучше. K>А что будет, если в этом распараллеленном обычном цикле попробовать посчитать факториал?
Запустится несколько потоков и будет произведена параллельная редукция — проблемы нет, так как операция умножения ассоциативна:
template<typename T>
T factorial(T N)
{
T result = 1;
#pragma omp parallel for reduction(*:result)for(T i = 1; i <= N; ++i)
result *= i;
return result;
}
Но, опять таки, я вместо OpenMP предпочитаю библиотеки типа TBB, либо C++17 STL. При наличии лямбд, повсеместного вывода типов и т.п. трюки с прагмами не нужны.
Здравствуйте, Khimik, Вы писали:
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм?
Существует как минимум два разных класса задач. Про векторизацию (параллельные циклы) и соответствующие библиотеки уже несколько раз упомянули, параллельные коллекции есть практически везде.
Второй тип задач упоминал VladD2. Это более высокоуровневые (и более динамические) задачи. У него парсинг и обработка данных. В вебе может быть загрузка конфигов и потом дополнительных ресурсов из нескольких сервисов с разными зависимостями (пойти по конфигу в один сервис, потом по его ссылке в другой и т.п.). Для этой задачи тоже есть решения. Это Futures/Promises (еще deferred из той же серии). Называются по-разному в разных языках. Удобство зависит от конкретного API в конкретном языке. В языках с поддержкой монад вообще все прекрасно. Монадное/аппликативное API с функцией слева (в haskell-style fn :> v1 :> v2 :>> v3 и аналогичные) тоже нормально. А вот если разработчики осилили только функтор (aka map), то там больно. Пример — javascript. Без нормальных оберток (одной функции Async.apply(fn, arg1, arg2, ....)) что-либо нетривиальное на родных Promise делать очень неудобно (обертка делается легко, но почему не в стандарте то???).
Вот буквально вчера делал:
def deleteRecursive(path : Path) : Future[Unit] =
deleteNode(path) recoverWith {
/* Already deleted. */
case NoNodeException ⇒ Future.successfull(())
case NotEmptyException ⇒
val op = for {
children ← getChildren(path)
childOperations = children.map(child ⇒ deleteRecursive(path + child))
_ ← Future.sequence(childOperations)
_ ← deleteNode(path)
} yield ()
op recoverWith {
case NoNodeException ⇒ Future.successfull(())
}
}
Future.sequence делатет черную магию по преобразованию Seq[Future[Unit]] в Future[Seq[Unit]].
По сути аналогично deleteChildren отсюда. Пока оригинал дожидается ответа от сервера, мой отправляет стопку команд и потом потихоньку разгребает результат. На самом деле там не "многопоточность", а "асинхронность" (один поток обмена данными), но в использовании API этого факта просто не видно.
Здравствуйте, VladD2, Вы писали:
EP>>Если ты не все циклы циклами называешь, а лишь те которые не параллелятся, то видимо да. А если без терминологической эквилибристики — то вполне имеет, отсюда и видим в параллельных библиотеках (что multi-thread, что multi-process, что multi-node) примитивы "параллельных циклов" типа parallel map/transform, reduce, а иногда и сплавленные mapreduce. VD>Эти библиотеки точно так же бесполезны. Они не более чем костыли не решающие проблему, а только лишь незначательно их облегчающие.
Полезны, решают вполне реальные инженерные и научные задачи, причём успешно. Именно эти библиотеки и нагружают все вычислительные кластеры.
Ещё раз, речь про parallel computing, научные вычисления и инженерные расчёты. Ты же вещаешь больше про concurrency — это другая тема.
VD>В плане языковых средств и библиотек можно выделить такие либы как Rx и ReactiveUI. Это более полезные костыли. И там нет никаких циклов. VD>Но даже эти продвинутые костыли не решают проблему конкурентного изменения данных.
Во-во, о том и речь — это всё concurrency, и к сабжу имеет лишь опосредованное отношение
EP>>Это только для подмножества тех задач, в которых требуется передача данных между параллельными процессами. Многие же задачи выражаются через mapreduce, где внутри процессов нет никакого взаимодействия с другими. VD>Это 100% задач. Все задачи требуют работы с данными.
Да, с данными, но далеко не все с разделяемыми данными.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Sharov, Вы писали:
S>>Вот lock-free структуры данных эту проблему решают. Голова о синхронизации не болит. WH>Зуб дашь что у тебя в коде нигде нет доступа из разных потоков к данным которые к этому не готовы? WH>Чтобы можно было ответить да для кода из 1000+ строк нужен язык, который это контролирует.
Если везде и всюду использовать типы из ConcurrentCollections, то зуб дам.
Здравствуйте, Khimik, Вы писали:
K>Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм? Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
Существует много всего. В своем комментарии ты описал OpenMP (расширение для С++). OpenMP позволяет решать такие задачи (это называется data parallel — когда каждый поток работает со своей независимой памятью, а потом все объединяется), но помимо этого, он позволяет задействовать task parallelism (это когда вычисление может быть представлено как ациклический направленный граф задач, т.е. стартует первая задача, порождает несколько новых, те порождают еще ряд задач и тд., расчет факториала или параллельный quicksort это как раз оно).
Помимо этого, есть еще такое расширение языка как Cilk (https://www.cilkplus.org/). Это тоже task level parallelism. Еще MIT недавно представили Milk (этот призван исправлять data access patterns в параллельных приложениях).
В принципе, все это можно делать на уровне библиотек (кроме того что делает Milk). Существуют высокоуровневые тулкиты, вроде Intel TBB, которые позволяют описывать топологию вычислений и запускать их. Futures/promises это по сути просто удобный интерфейс для реализации task parallelism-а. Для task level подхода достаточно иметь хорошую реализацию task pool-а (work stealing например). Вообще, одна из серьезных проблем обоих подходов (data parallel и task parallel — балансировка нагрузки, наивный подохд — разделить заранее все между потоками, работает только в простых случаях).
Еще можно посмотреть в сторону dataflow языков программирования, например StreamIt (на MIT open courseware есть серия лекций по параллельному программированию, в которых про него рассказывают). Примерно того же самого пытаются добиться с помощью библиотек, пример — http://www.raftlib.io/
Принцип, лежащий в основе dataflow подхода похож на task level подход. У нас тут тоже есть ациклический направленный граф каких-нибудь задач, вот только топология не incidential а строится заранее. Пример: мы пишем скан для СУБД, (упрощенно) скан перебирает блоки Б+дерева хранящиеся на диске, каждый блок должен быть прочитан, распакован, данные должны быть десериализованы, потом идет фильтрация (т.к. у нас есть where clause в запрсое), далее оно должно быть преобразовано в соответствии с projection в немного другую форму.
Data parallel подход тут работать не будет, так как scan должен обрабатывать данные в определенном порядке.
Task parallel как-то очень сложно и криво выглядит для этого случая.
Казалось бы тут нет параллелизма, но если все это реализовать с помощью RaftLib, то оно будет выполняться параллельно, будет построен конвейер, блоки будут читаться в буфер в одном потоке, второй поток будет брать блоки по очереди, распаковывать и передавать на десериализацию во второй поток (можно буферизовать данные между потоками, опять же), далее данные будут фильрроваться в еще одном потоке и тд. Количество потоков и распределение задач по потокам будет определяться библиотекой, например, если filter выполняется очень быстро то он не будет выноситься в отдельный поток а будет выполняться в том же потоке что и deserialization step для балансировки нагрузки.
Можно сделать то же самое для merge join-а двух деревьев:
Тут scan каждого дерева (таблицы) может быть распараллелен через конвейерную обработку, плюс возможно выполнять параллельное сканирование двух таблиц, плюс конвейерная обработка (сканирование) -> (kway merge) -> (output).
Здравствуйте, VladD2, Вы писали:
EP>>Циклы бывают не только на низком уровне, но и на высоком. Ты же сам дальше и приводишь пример: VD>>>Параллелить можно "в большом". Простой пример. В от есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто. EP>>Вот как раз параллельный разбор отдельных файлов, это и есть цикл по файлам на высоком уровне — parallel transform/map, и может ещё и parallel reduce после, в зависимости от задачи. VD>Это уже не циклы. Это уже структура программы.
А выражается эта СТРУКТУРА каким образом? Не циклами ли случайно?
VD>Паралеленье циклов чуть менее чем полностью бесполезно.
Если ты не все циклы циклами называешь, а лишь те которые не параллелятся, то видимо да. А если без терминологической эквилибристики — то вполне имеет, отсюда и видим в параллельных библиотеках (что multi-thread, что multi-process, что multi-node) примитивы "параллельных циклов" типа parallel map/transform, reduce, а иногда и сплавленные mapreduce.
VD>А для повышения эффективности и безопасности предоставить ему механизмы контроля передачи данных между параллельными процессам (или иными единицами параллельного выполнения).
Это только для подмножества тех задач, в которых требуется передача данных между параллельными процессами. Многие же задачи выражаются через mapreduce, где внутри процессов нет никакого взаимодействия с другими.
Те же задачи в которых имеется постоянное взаимодействие между процессами обычно относятся не к parallel computing, а к concurrent.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Не обязательно язык, и даже необязательно компилятор. Достаточно внешнего верификатора.
В коде всё равно понадобятся аннотации.
Так что получаем язык с компилятором вид с боку.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
EP>>Не обязательно язык, и даже необязательно компилятор. Достаточно внешнего верификатора. WH>В коде всё равно понадобятся аннотации.
Необязательно. Например верификатор может ограничить всё глобальное взаимодействие до одного объекта очереди сообщений.
Да и аннотации уже есть во многих языках, если же нет — то можно для этой цели использовать типы.
Здравствуйте, chaotic-kotik, Вы писали:
CK>Пока вы это только обсуждаете, в С++ уже есть thread sanitizer а в Go — race detector.
Зуб дашь что я их не сломаю?
CK>Проблема race-ов это конечно проблема, но она стоит не так остро, как некоторые другие проблемы параллельного программирования, которые вы тут с Владом даже не начинали обсуждать.
Если эта проблема не решена решать остальные не имеет смысла просто по тому что программа не работает.
CK>Thread safety это конечно критично, но это простая проблема, которую можно решить на уровне архитектуры.
Зуб дашь что после очередного изменения ссылка на изменяемый объект не зацепится за два потока?
CK>Помимо этого есть еще проблема композиции. В многопоточном программировании, если твоя программа состоит из thread-safe элементов (все коллекции и объекты используют мьютексы например), это не значит что программа является корректной и потокобезопасной.
Корректность программы понятие неопределённое.
А вот то что программа не меняет объект из двух потоков доказать можно.
Существует несколько систем типов которые это делают.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Khimik, Вы писали:
K>Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>>Запустится несколько потоков и будет произведена параллельная редукция — проблемы нет, так как операция умножения ассоциативна: EP>>
EP>>template<typename T>
EP>>T factorial(T N)
EP>>{
EP>> T result = 1;
EP>> #pragma omp parallel for reduction(*:result)
EP>> for(T i = 1; i <= N; ++i)
EP>> result *= i;
EP>> return result;
EP>>}
EP>>
А во что это в итоге скомпилируется? Оно не получится медленнее чем однопоточный варинант? Не превысят ли накладные расходы на распараллеливание выигрыш от самого распараллеливания?
Всё сказанное выше — личное мнение, если не указано обратное.
Здравствуйте, WolfHound, Вы писали:
V>>А если нам эти гонки принципиально нужны для lock-free алгоритмов? WH>Язык и стандартная библиотека с большим запасом покроют потребности примерно 100% пользователей. WH>А те пара человек, которым не хватит используют unsafe. WH>И это если не вспоминать о том, что примерно 99% программистов lock-free структуру данных написать не смогут.
Ну, простейшим lock-free как раз 99% программистов пользуются регулярно.
Через т.н. "relaxing memory order":
Т.е., даже если заменить bool на некий библиотечный atomic<bool>::store/load (где происходящее в точности аналогично в случае memory_order_relaxed) — все-равно у нас торчит ссылка на расшаренный объект в двух потоках.
Да, я помню про твои "каналы".
Но это ж из пушки по воробьям. ))
Здравствуйте, WolfHound, Вы писали:
WH>>>2)Большая часть программистов даже не поймёт, что тут написано. V>>Эээ... не там ты работал и работаешь... )) WH>Ты представления не имеешь где я работал и работаю.
Да тут половина КЫВТ прекрасно об этом в курсе. ))
И по прошлому и по недавнему настоящему.
V>>Я думаю, тут надо спускаться на самый низ и давать тупо базу, а всякие cancellation token пусть будет сугубо библиотечной приблудой, написанной честным образом прямо в языке. WH>Перестающем работать при переносе на другую железку.
Если железка не поддерживает какую-то одну из 4-х базовых операций, то эта железка не для многоядерности. На такой железке многопоточность у нас будет работать на одном физическом ядре, а указанные примитивы реализуются через запрет прерываний, выполнение "атомарного" кода и разрешение прерываний.
V>>Достаточно взять ровно четыре минимальных базовых примитивов для многопоточности: WH>Не нужен этот ад при прикладной разработке.
В прикладной разработке будут прикладные библиотеки.
Цимус в том, что произвольные прикладные библиотеки становится возможным разрабатывать ср-вами безопасного языка, а не вкладывать их в некую магическую "поставку".
V>>Теперь твои "каналы", "cancellation tokens" и вообще любые желаемые вещи можно выразить прямо ср-вами языка. WH> Только никакого контроля со стороны компилятора не будет.
Я дал для случая uniqueness-типов.
Куда уж больший контроль-то?
Здравствуйте, WolfHound, Вы писали:
V>>Цимус в том, что произвольные прикладные библиотеки становится возможным разрабатывать ср-вами безопасного языка, а не вкладывать их в некую магическую "поставку". WH>Хватит пороть чушь. Ей больно. WH>Никаких гарантий со стороны компилятора на этих примитивах ты не получишь.
Со стороны компилятора нам требуется строгая типизация и uniqueness-семантика.
Cо стороны железки требуется атомарность этих операций.
Вот и всех делов. А то опять развели обсуждения не в ту степь. ))
Каждый процесс (поток) пусть владеет своим типобезопасным экземпляром Atomic, каждый из которых "унутре" пусть ссылается на одну и ту же структуру в памяти. Atomic должен быть встроенным opaque-типом, навроде встроенных integer.
Сейчас вроде рост производительности процессоров остановился, значит будущее за распараллеливанием – много ядер, много процессоров в одном компьютере. Существуют ли ЯП, позволяющие удобно распараллелить алгоритм? Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика. В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Khimik, Вы писали:
K>В этих параллельных циклах некоторые задачи будет невозможно реализовать – например, расчёт факториала. Но в целом, когда нужно будет в один присест обработать большой массив, они будут нормально работать.
Для "параллельных циклов" отдельные языки не нужны, достаточно библиотек. Например Intel TBB, Microsoft PPL, а начиная с C++17 — вообще в STL.
Там как раз те самые параллельные циклы, даже название соответствующее — parallel_for.
Здравствуйте, Khimik, Вы писали:
K>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика.
Для C++ ещё есть OpenMP — там вообще параллелятся самые обыкновенные циклы, посредством добавления #pragma. Но библиотеки типа TBB всё же лучше.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Здравствуйте, Khimik, Вы писали:
K>>Я это представляю так: в таких ЯП должны быть два типа циклов – обычные и параллельные. В обычных циклах есть какой-то счётчик, который увеличивается каждую итерацию, а в параллельных система должна сразу запустить много потоков, каждый из которых обрабатывает свой участок памяти и имеет на входе своё число – аналог счётчика.
EP>Для C++ ещё есть OpenMP — там вообще параллелятся самые обыкновенные циклы, посредством добавления #pragma. Но библиотеки типа TBB всё же лучше.
А что будет, если в этом распараллеленном обычном цикле попробовать посчитать факториал?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Запустится несколько потоков и будет произведена параллельная редукция — проблемы нет, так как операция умножения ассоциативна: EP>
EP>template<typename T>
EP>T factorial(T N)
EP>{
EP> T result = 1;
EP> #pragma omp parallel for reduction(*:result)
EP> for(T i = 1; i <= N; ++i)
EP> result *= i;
EP> return result;
EP>}
EP>
EP>Но, опять таки, я вместо OpenMP предпочитаю библиотеки типа TBB, либо C++17 STL. При наличии лямбд, повсеместного вывода типов и т.п. трюки с прагмами не нужны.
Сорри за профанство, но я не понимаю как этот код работает. Речь шла о том, что вычисление факториала как раз нельзя распараллелить. Или в этом коде оно паралеллится частично, типа цифры с 2 до 5 перемножаются в одном процессе, с 6 по 9 в другом, потом два результата перемножаются и получается факториал девяти?
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, VladD2, Вы писали:
VD>В реальности, это самообман. VD>Параллелить вычисления на уровне циклов чуть менее чем бесполезно.
Циклы бывают не только на низком уровне, но и на высоком. Ты же сам дальше и приводишь пример:
VD>Параллелить можно "в большом". Простой пример. В от есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто.
Вот как раз параллельный разбор отдельных файлов, это и есть цикл по файлам на высоком уровне — parallel transform/map, и может ещё и parallel reduce после, в зависимости от задачи.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Циклы бывают не только на низком уровне, но и на высоком. Ты же сам дальше и приводишь пример:
VD>>Параллелить можно "в большом". Простой пример. В от есть у нас проект который мы разрабатываем. В нем 100500 файлов. Паралелить разбор одно фала практически бесполезно (очень сложно и мало толку). Но распараллелить разбор отдельных файлов можно довольно просто.
EP>Вот как раз параллельный разбор отдельных файлов, это и есть цикл по файлам на высоком уровне — parallel transform/map, и может ещё и parallel reduce после, в зависимости от задачи.
Это уже не циклы. Это уже структура программы.
Паралеленье циклов чуть менее чем полностью бесполезно.
Параллелить можно только сущности реально способные обрабатываться независимо. На сегодня, решить что можно параллелить может только лишь человек.
По сему от языка требуется позволять человеку определять что и как параллелить. А для повышения эффективности и безопасности предоставить ему механизмы контроля передачи данных между параллельными процессам (или иными единицами параллельного выполнения).
Грубо говоря нужны языки обеспечивающие дешевые паралельные процессы. И дешевую передачу данных между ними. Для этого нужны:
1. Гарантией неизменности данных разных "процессах".
2. Дешевизна передачи данных (заморозка графа объектов в одном процессе и передачи его в другой).
3. Средства контроля последовательности вычислений. Чтобы человек мог созерцать как расчеты распараллеливаются и возвращаются обратно к синхронным.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>А выражается эта СТРУКТУРА каким образом? Не циклами ли случайно?
Нет. Но это не главное.
Главное то, что основная задача не распаралелить, а сделать так, чтобы распаралеленные вычисления не мешали друг другу (были изолированными). И в том как объединять результаты вычислений.
EP>Если ты не все циклы циклами называешь, а лишь те которые не параллелятся, то видимо да. А если без терминологической эквилибристики — то вполне имеет, отсюда и видим в параллельных библиотеках (что multi-thread, что multi-process, что multi-node) примитивы "параллельных циклов" типа parallel map/transform, reduce, а иногда и сплавленные mapreduce.
Эти библиотеки точно так же бесполезны. Они не более чем костыли не решающие проблему, а только лишь незначательно их облегчающие.
В плане языковых средств и библиотек можно выделить такие либы как Rx и ReactiveUI. Это более полезные костыли. И там нет никаких циклов.
Но даже эти продвинутые костыли не решают проблему конкурентного изменения данных.
Для решения этой проблемы нужно делать новые языки и новые рантаймы к ним.
EP>Это только для подмножества тех задач, в которых требуется передача данных между параллельными процессами. Многие же задачи выражаются через mapreduce, где внутри процессов нет никакого взаимодействия с другими.
Это 100% задач. Все задачи требуют работы с данными. Мап-редью — не более чем алгоритм для определенных задач. Гарантий он никаких не дает. А для безопасного и производительного программирования нужны гарантии и контроль.
EP>Те же задачи в которых имеется постоянное взаимодействие между процессами обычно относятся не к parallel computing, а к concurrent.
Да ты можешь хоть к черту лысому что хочешь относить. Это ничего не меняет. Основная проблема параллельных вычислений в том что нужно контролировать изменение данных. Если бы это было не так, то проблемы решали бы банальные функции.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Возвращаемся к тем же файлам. Вот отпарсили мы файл в отдельном потоке. Теперь надо сделать так, чтобы я мог обработать полученные данные (а их очень много) параллельно с остальными данными (из других файлов) и при этом не иметь проблем с блокировками и не копировать все данные.
Звучит как типичная задача для futures + immutable структур данных. Причем числодробильные части (вроде парсера считанного файла и прочих строго алгоритмических замкнутых шагов) про Futures ничего знать не будут, это будет во внешнем (координирующем) коде.
VD>Для того нужно чтобы программист оперировал некими областями памяти которые можно изменят только из одного потока управления.
Локальные переменные
VD>И предоставить программисту дешевый способ передачи "замороженного слепа информации" из одного потока в другой.
Immutable типы.
VD>Иными словами нужно сделать так, чтобы потоки не имели общих данных, а передача данных из одного потока в другой была прозрачной и дешевой.
Не имели общих изменяемых данных. Не вижу никаких проблем в неизменяемых данных, разделяемых многими потоками. Передача незименяемых данных — простая и прозрачная. Чистота API (immutable in, immutable out) достигается ревью кода. Внутри методов — пусть изменяемые структуры используют, не жалко.
VD>Нужно научить языки манипулировать кучами. Научить передавать эти кучи между "виртуальными процессами" (в стиле Эрланг).
И программистов тоже этому учить? А сколько там выиграть планируется по сравнению с futures+immutable structures? Я ради двух-трех раз в разнице производительности вряд ли буду учить новый язык и кучу вручную на области размечать. За immutable плата есть, но относительно небольшая (чуть менее оптимальные структуры, лишний lookup вместо циклов). Если припрет, я скорее будут смотреть на кластер по компиляции. Потому что в чистых функциях и ациклических графах выносить отдельные операции на кластер можно легко и просто. Почти ничего не поменяется. Было Future, вычисляющееся в потоке. Будет Future, получающее данные из сети. Можно еще всякие shared fs + caches посмотреть и т.п. Но это вряд ли скоро понадобится.
Здравствуйте, Khimik, Вы писали:
K>Здравствуйте, kov_serg, Вы писали:
_>>Языки 4-го поколения например sql. Где компилятор сам синтезирует и распаралеливает алгоритм.
K>На SQL Doom не напишешь...
"Как мыло вы знаете про добрых фей". На js написали же.
Сори за задержку с ответом. Заметил ответ только сейчас.
VD>>Возвращаемся к тем же файлам. Вот отпарсили мы файл в отдельном потоке. Теперь надо сделать так, чтобы я мог обработать полученные данные (а их очень много) параллельно с остальными данными (из других файлов) и при этом не иметь проблем с блокировками и не копировать все данные.
M>Звучит как типичная задача для futures + immutable структур данных.
Использование неизменяемых структур — это паттерн программирования. Проблема любого паттерна в том, что его можно легко нарушить. А контроля нет!
Если язык не "чисто функциональный" (по сути таких и не бывает), то нет возможности гарантировать, что чужая локальная память не изменяется.
Кроме того далеко не все алгоритмы можно эффективно реализовать на базе неизменяемых структур данных. Зачастую императивное решение гораздо эффективнее или проще (при той же эффективности).
Ну, и последнее — нельзя заставить мэйстрим программировать чисто функциоально.
M>Причем числодробильные части (вроде парсера считанного файла и прочих строго алгоритмических замкнутых шагов) про Futures ничего знать не будут, это будет во внешнем (координирующем) коде.
Все так. Но числодробильные части — это обычно суровый императив. Возвращаясь к парсингу — быстрый парсер невозможен без оптимизаций вроде конечных автоматов с состоянием или таблиц мемоизации. Это все императив.
И от языка поддерживающего распараллеливание вычислений требуются гарантии, того что этот императив не станет причиной трудно уловимого бага.
Все что ты говоришь правильно и я это знаю. Но на практике, на большом проекте сделать хорошо распараллельненый код да еще и без блокировок крайне не просто. Ошибки все равно вылезают.
Людям свойственно ошибаться!
Задача языка — уберечь людей от ошибок или (хотя бы) сделать так, чтобы ошибки было легко выявить. Возможно поменять память из разных потоков — это гарантия, что ошибки будут.
Паттернами и библиотеками можно сократить их число. Но нельзя гарантировать их отсутствие или облегчить их выявление.
M>Локальные переменные
1. Зачастую дорого, так как приходится копировать тучу данных.
2. Опять же не гарантирует, что все изменения локальны. Локальная переменнамя может указывать на область памяти в которой будет изменяемое поле. И вот уже программист тратит неделю на поиск простейшего бага. А то и баг живет в продакшене много лет.
M>Immutable типы.
Опять же:
1. Дорого.
2. Это паттерн который легко нарушить и трудно найти его нарушение.
При этом мьютабельность в рамках одного потока совершенно безвредна.
VD>>Иными словами нужно сделать так, чтобы потоки не имели общих данных, а передача данных из одного потока в другой была прозрачной и дешевой. M>Не имели общих изменяемых данных.
Да. Сори. Исправил в своем сообщении.
M>Не вижу никаких проблем в неизменяемых данных, разделяемых многими потоками.
Проблема в неизменяемых данных одна — они не столь же универсальны как изменяемые. Нельзя сделать быструю сортировку или хэш-таблицу на неизменяемых данных. Хоть байт, но придется изменить. Плюс это зачастую дороже.
И чем больше объем данных, тем труднее удержать их неизменяемыми.
Ну, и повторюсь — это паттерн. А создать язык где все неизменяемо нельзя. Даже в Хаскеле есть лазейки. Плюс Хаскель дико не удобен в отладке и не все его могут использовать.
M>Передача незименяемых данных — простая и прозрачная.
Да. Но нет гарантии, что передаются только неизменяемые данные. Плюс дороговизна "изменения" неизменяемых структур (по сути их надо пересоздавать, хотя и возможно с и использованием большей части старых данных).
M>Чистота API (immutable in, immutable out) достигается ревью кода.
Ну тогда можно смело писать на С. Реьвю кода там доступен!
Такие вещи должны проверять компиляторы языков.
Если будет дешевое императивное изменение кучи данных и фича в языке позволяющее сказать, что отныне эти данных "заморожены", то проверять, что мы передали куда-то изменяемые данные просто не придется.
M>Внутри методов — пусть изменяемые структуры используют, не жалко.
А кто гарантирует, что где-то не осталось ссылочки на тот же объект и по ней параллельно что-то не будет изменено?
VD>>Нужно научить языки манипулировать кучами. Научить передавать эти кучи между "виртуальными процессами" (в стиле Эрланг). M>И программистов тоже этому учить?
Для программиста нужны простые и понятные конструкции вроде заморозки разморозки. А уж компилятор должен проверять, что потоку передаются замороженные данные и гарантировать, что два потока не получат возможность менять одну ячейку памяти.
На самом деле языки и сейчас оперируют весьма сложными вещами вроде GC, но программисты об этом и не думают. Вызвал new и получил объект. Точно так же и тут.
Возможно придется добавить какие-то дополнительные аннотации, но в целом это не должно быть сложно. Скажем нечто вроде оператора new с дополнительным параметром — кучей. В общем, как это оформить — надо думать. Ясно только что надо сделать.
M>А сколько там выиграть планируется по сравнению с futures+immutable structures?
Выиграть планируется — надежность.
А скорость будет обеспечиваться за счет выбора более производительных алгоритмов.
Скажем конечный автомат с доп памятью или мемоизация ускоряют парсинг нелинейно (устраняя возможную экспоненту). Ни один любитель ФП не вздумает писать быстрый парсер на неизменяемых структурах данных. Какой-нибудь Парсек сольет LR-автомату или Packrat-парсеру на первой же нетривиальной грамматике.
M>Я ради двух-трех раз в разнице производительности вряд ли буду учить новый язык и кучу вручную на области размечать.
Основное это надежность, как я уже говорил. Производительность она просто вытекает из надежности. Если ты гарантирован от ошибок, то можешь себе позволить по оптимизировать код. Если же сложность уже на грани, то ты вряд ли на это отчаешься.
M>За immutable плата есть, но относительно небольшая
Все зависит от задач. Скажем неизменяемое дерево и хэш-таблица имеют просто разную алгоритмическую сложность. По сему и решение на их основе будет отличаться по скорости. В парсерах я уже примеры приводил. В одном случае это будут оптимизированные алгоритмы, в другом будет приводить к экспоненте в некоторых случаях. Какие тут разы? Тут уже речь о непригодности.
M>(чуть менее оптимальные структуры, лишний lookup вместо циклов). Если припрет, я скорее будут смотреть на кластер по компиляции. Потому что в чистых функциях и ациклических графах выносить отдельные операции на кластер можно легко и просто.
Чистые функции и так параллелить нет проблем. Но вот писать только в чистых функйия на практике не выходит. Ну, или можно писать только некоторый класс задач.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Возможно придется добавить какие-то дополнительные аннотации, но в целом это не должно быть сложно. Скажем нечто вроде оператора new с дополнительным параметром — кучей. В общем, как это оформить — надо думать. Ясно только что надо сделать.
Давно всё придумано: Re: Мысли о эффективном автоматическом управлении памятью
VD>Все зависит от задач. Скажем неизменяемое дерево и хэш-таблица имеют просто разную алгоритмическую сложность. По сему и решение на их основе будет отличаться по скорости. В парсерах я уже примеры приводил. В одном случае это будут оптимизированные алгоритмы, в другом будет приводить к экспоненте в некоторых случаях. Какие тут разы? Тут уже речь о непригодности.
Тут всё не так плохо, как ты говоришь. Будет не экспонента, а умножение на Log(N) (возможно несколько раз) и большую константу.
Но всё равно результат обычно не укладывается в требования по производительности.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Я тебе уже отвечал, что это "придумано" на уровне того анекдота про переворачивающиеся на границе самолете. В реальности это не хилая инженерная задача, которая в процессе реализации почти наверняка даст совершенно не похожий на твои замысли результат. Точно так же как наши рассуждения о том какая должна быть Нитра 4 года назад мало напоминают то, что получилось в реальности.
Когда решаются технические проблемы всегда бывает легко и ясно когда ты к ним не приступил, и второе, когда ты закончил.
Твои "все давно придумано" это легкость и ясность "когда ты еще не приступал к решению задачи".
Вот на практике ты ведь знаешь, что надо в парсере поправить, чтобы он отступные грмматике парсил и одинаковые префиксы/постфиксы в правилах отслеживал. Скоро будет два года как ты это знаешь. И что? Почему ничего так и не реализовано?
WH>Тут всё не так плохо, как ты говоришь. Будет не экспонента, а умножение на Log(N) (возможно несколько раз) и большую константу.
Это если хотя бы дерево вместо хэш-таблицы использовать. Но по жизни в функциональном стиле пишут комбинаторные парсеры. Они очень красиво пишутся на разных Хаскелях. Но они в экспоненту выливаются. С таблицей мемоизации на базе дерева — да, экспоненты не будут. Будут просто тормоза. Но для практики и это не приемлемо.
Плюс опять же вопрос — как гарантировать, что все чисто функционально и неизменяемо? Еще на Хаскеле это можно обеспечить, но на мэйстрим-языках — нет.
WH>Но всё равно результат обычно не укладывается в требования по производительности.
+1
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Я тебе уже отвечал, что это "придумано" на уровне того анекдота про переворачивающиеся на границе самолете.
На уровне этого анегдота твоё:
Возможно придется добавить какие-то дополнительные аннотации, но в целом это не должно быть сложно. Скажем нечто вроде оператора new с дополнительным параметром — кучей. В общем, как это оформить — надо думать. Ясно только что надо сделать.
А там описан конкретный механизм.
С конкретной математикой.
Но ты его даже не пытался понять.
VD>Вот на практике ты ведь знаешь, что надо в парсере поправить, чтобы он отступные грмматике парсил и одинаковые префиксы/постфиксы в правилах отслеживал. Скоро будет два года как ты это знаешь. И что? Почему ничего так и не реализовано?
По тому что я эту задачу решать даже не начинал.
И тут это оффтопик.
VD>Это если хотя бы дерево вместо хэш-таблицы использовать. Но по жизни в функциональном стиле пишут комбинаторные парсеры. Они очень красиво пишутся на разных Хаскелях. Но они в экспоненту выливаются.
Это зависит от реализации. При желании на комбинаторах можно пакрат сделать.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>А там описан конкретный механизм.
А я тебе могу еще раз сказать, что все что там написано — это знание перед тем как сделать — т.е. ни о чем.
WH>С конкретной математикой.
Там треп, а не математика. Начнешь делать, сразу упрешься в реальность. Вся твоя математика пойдет в лес. Останутся только общие идеи.
WH>Но ты его даже не пытался понять.
Там понимать не чего. Там общие слова.
WH>По тому что я эту задачу решать даже не начинал.
Ну, да. Зато знаешь в деталях, как решать во много более сложные.
WH>И тут это оффтопик.
Ну, вот ты реши эту простую и конкретную задачу, в которой (казалось бы) известно как все делать. А потом рассказывай, обсудим что-то более сложное и отдаленное. А то то что нужно еще вчера и вроде как тоже ясно как решать у нас годами не делается, но мы обсуждаем как в деталях решать будущие задачи.
WH>Это зависит от реализации. При желании на комбинаторах можно пакрат сделать.
Может и можно, но не делают. В том же pappy, как я понимаю нормальную грамматику сделали, а комбинаторы в лес послали.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Там треп, а не математика. Начнешь делать, сразу упрешься в реальность. Вся твоя математика пойдет в лес. Останутся только общие идеи.
Трёп это у тебя. А там всё сводится к нескольким очень простым операциям.
WH>>По тому что я эту задачу решать даже не начинал. VD>Ну, да. Зато знаешь в деталях, как решать во много более сложные.
Намного более сложные задачи чем контроль графов объектов на этапе компиляции я уже успешно решал.
Восстановление после ошибок в нитре намного сложнее.
VD>Ну, вот ты реши эту простую и конкретную задачу, в которой (казалось бы) известно как все делать. А потом рассказывай, обсудим что-то более сложное и отдаленное. А то то что нужно еще вчера и вроде как тоже ясно как решать у нас годами не делается, но мы обсуждаем как в деталях решать будущие задачи.
Такие приёмы на мне даже в детском саду не работали.
Если тебе от меня что-то нужно попроси по нормальному.
VD>Может и можно, но не делают. В том же pappy, как я понимаю нормальную грамматику сделали, а комбинаторы в лес послали.
Вот например GLL'ные комбинаторы. https://github.com/djspiewak/gll-combinators/blob/master/examples/src/lambdacalc/LambdaCalcParser.scala
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Трёп это у тебя. А там всё сводится к нескольким очень простым операциям.
А, ну, тогда все ОК. Садись сделай.
WH>Намного более сложные задачи чем контроль графов объектов на этапе компиляции я уже успешно решал.
Ты когда начнешь решать, то поймешь, что это тоже сложная задача, а ты просто деталей не видел при взгляде из далека.
WH>Восстановление после ошибок в нитре намного сложнее.
Это ты после того как все трудности ощутил говоришь. А 3 года назад ни ты, ни я особых проблем не видели.
VD>>Ну, вот ты реши эту простую и конкретную задачу, в которой (казалось бы) известно как все делать. А потом рассказывай, обсудим что-то более сложное и отдаленное. А то то что нужно еще вчера и вроде как тоже ясно как решать у нас годами не делается, но мы обсуждаем как в деталях решать будущие задачи. WH>Такие приёмы на мне даже в детском саду не работали.
Какие приемы? Это факт. Реальная сложность задачи становится понятной только когда подходишь к реализации деталей. Вдруг оказывается масса внутренних противоречий и проблем. Но в теории, глядя на задачу абстрактно — все выглядит просто.
Вот только качественных реализаций ЖЦ можно по пальцам пересчитать.
WH>Если тебе от меня что-то нужно попроси по нормальному.
Я тебе 1.5 года назад сказал, что нам нужно. И уж если это сложно сделать, то шлушать как легко решать вселенские задачи создания эффективных и безопасных многопоточных языков мне уж совсем слушать смешно.
Если ты хочешь чтобы я тебе еще раз попросил, то ОК. Я гордый.
У нас в парсинге не сделаны следующие задачи:
1. Передача параметров в правила (с мемоизаций их значений). Это позволило бы решить следующие проблемы:
* Парсинг отступных грамматик (аля Хаскель).
* Парсинг правил с одинаковым префиксами и суфиксами (литералы С++, Раста, ХМЛ и т.п.).
2. Инкрементальный парсиг. Ты его почти сделал, но не доделал. А для качественной работы в редакторе это было бы очень желательно.
Если ты реально можешь это сделать, то сделай пожалуйста. Я полностью погряз в IDE-плагине. Да код этот твой. Ты в нем все знаешь.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
WH>>Трёп это у тебя. А там всё сводится к нескольким очень простым операциям. VD>А, ну, тогда все ОК. Садись сделай.
Когда решу сделать язык обязательно сделаю.
VD>Ты когда начнешь решать, то поймешь, что это тоже сложная задача, а ты просто деталей не видел при взгляде из далека.
Нет там никаких деталей.
Всё что нужно это пометить каждый объект кучей, в которой он лежит.
После чего проконтролировать что ссылка на одну кучу не попала в объект другой кучи.
Тут справится тайпчекер каждого первого статически типизированного языка с генериками.
Сами кучи описываются через уникальные переменные.
Далее параметризируем типы переменными кучи и позволяем читать/писать только если соответствующая переменная жива.
Всё.
Подробности смотри по ссылкам. Я это всё между прочим для тебя написал.
Это всё мне очень напоминает историю с тем как ты мне доказывал, что у меня вставка в приоритетную очередь линейная. При этом даже не попытавшись понять алгоритм.
WH>>Такие приёмы на мне даже в детском саду не работали. VD>Какие приемы?
Взять на слабо.
Короче заканчивай с оффтопиком. Хочешь поговорить про нитру делай это в другом месте.
Тут обсуждается управление памятью.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
EP>>Это только для подмножества тех задач, в которых требуется передача данных между параллельными процессами. Многие же задачи выражаются через mapreduce, где внутри процессов нет никакого взаимодействия с другими.
VD>Это 100% задач. Все задачи требуют работы с данными. Мап-редью — не более чем алгоритм для определенных задач. Гарантий он никаких не дает. А для безопасного и производительного программирования нужны гарантии и контроль.
С помощью MapReduce считают page-rank например, ну и алгоритмы на графах тоже запускают как MapReduce задачи.
Про гарантии не очень понятно, гарантии отсутствия race conditions это хорошо, но это не гарантирует корректность параллельного алгоритма. Или ты хочешь научить компилятор доказывать корректность параллельных алгоритмов? Это похвально, желаю удачи (на самом деле), но не представляю как это может быть сделано. И еще такой момент, КМК ты не учитываешь одну вещь, помимо safety и correctness есть еще performance. Многие параллельные алгоритмы работают на одном ядре быстрее чем на двух или четырех и даже если это не так, там либо прирост проиходительности сублинеен, либо она начинает проседать когда мы запускаем это все на мультипроцессорной машине (внезапно, tradeoffs другие). Поэтому нужно учитывать не только thread safety но и memory access patterns и contention. Если все потоки юзают одну и ту же память на запись, то алгоритм перестает быть параллельным, так как исполнение сериализуется. В общем, не представляю как это все можно верифицировать автоматически.
Здравствуйте, VladD2, Вы писали:
VD>Эти библиотеки точно так же бесполезны. Они не более чем костыли не решающие проблему, а только лишь незначательно их облегчающие.
VD>В плане языковых средств и библиотек можно выделить такие либы как Rx и ReactiveUI. Это более полезные костыли. И там нет никаких циклов.
VD>Но даже эти продвинутые костыли не решают проблему конкурентного изменения данных.
VD>Для решения этой проблемы нужно делать новые языки и новые рантаймы к ним.
K>Сорри за профанство, но я не понимаю как этот код работает. Речь шла о том, что вычисление факториала как раз нельзя распараллелить.
Можно.
Разделяй и властвуй.
Один ицикл накопления факториала можно разбить на 2:
от 1 до n/2
от n/2 до n
Вот тебе и два треда...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Sharov, Вы писали:
S>Вот lock-free структуры данных эту проблему решают. Голова о синхронизации не болит.
Зуб дашь что у тебя в коде нигде нет доступа из разных потоков к данным которые к этому не готовы?
Чтобы можно было ответить да для кода из 1000+ строк нужен язык, который это контролирует.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
S>>Вот lock-free структуры данных эту проблему решают. Голова о синхронизации не болит. WH>Зуб дашь что у тебя в коде нигде нет доступа из разных потоков к данным которые к этому не готовы? WH>Чтобы можно было ответить да для кода из 1000+ строк нужен язык, который это контролирует.
Не обязательно язык, и даже необязательно компилятор. Достаточно внешнего верификатора.
Здравствуйте, Sharov, Вы писали:
S>Вот lock-free структуры данных эту проблему решают. Голова о синхронизации не болит.
В общем случае ничего они не решают. Надо тебе две такие структуры изменить и гарантировать, что они синхронны в любой момент времени и ты приплы.
Я вот, кстати, недавно был вынужден заменить две лок-фри структуры на две доступных только для чтения и их заполнение под блокировкой. Это как бы совсем не в какие ворота.
Плюс повторяю еще раз, в надежде, что мысль дойдет. Главное, что нет никаких гарантий! Если среди гигабайта кода ты один раз ошибешься и воспользуеся не той структурой, не сделаешь блокировку или сделаешь ее не правильно, то компилятор тебя не остановит. Ошибку эту ты будешь ловит в рантайме и сделать это будет крайне не просто.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Sharov, Вы писали:
S>>Если везде и всюду использовать типы из ConcurrentCollections, то зуб дам. WH>А если в эту коллекцию положить изменяемый объект? Ты можешь гарантировать что на этот объект не будет ссылок из разных потоков? WH>Ты такими темпами без зубов останешься.
Имелись ввиду простейшие операции над коллекциями: добавить, удалить, вставить... Для более-менее приемлемого решения в общем виде надо использовать immutable ds.
Здравствуйте, Sharov, Вы писали:
S>Имелись ввиду простейшие операции над коллекциями: добавить, удалить, вставить... Для более-менее приемлемого решения в общем виде надо использовать immutable ds.
Не обязательно. Есть способы передавать произвольные изменяемые графы между потоками гарантируя что ссылок в старом потоке не останется.
Я уже писал как: Re: Мысли о эффективном автоматическом управлении памятью
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Необязательно. Например верификатор может ограничить всё глобальное взаимодействие до одного объекта очереди сообщений.
Слишком сильное ограничение.
EP>Да и аннотации уже есть во многих языках, если же нет — то можно для этой цели использовать типы.
Так это и получается язык с компилятором, но через зад автогеном.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Не обязательно язык, и даже необязательно компилятор. Достаточно внешнего верификатора.
Это равносиельно языку. Ну, и не факт что достаточно. Для это "верификации" нужна модель. Плюс нужна поддержка в рантайме.
Короче, если бы все был так просто, то проблему эту уже давно решили. Но что-то решения не видно не смотря на монструозные коллективы работающие над этим в Майкрософт, Гугле и Оракле.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Зуб дашь что у тебя в коде нигде нет доступа из разных потоков к данным которые к этому не готовы? WH>Чтобы можно было ответить да для кода из 1000+ строк нужен язык, который это контролирует.
Пока вы это только обсуждаете, в С++ уже есть thread sanitizer а в Go — race detector. Проблема race-ов это конечно проблема, но она стоит не так остро, как некоторые другие проблемы параллельного программирования, которые вы тут с Владом даже не начинали обсуждать. Thread safety это конечно критично, но это простая проблема, которую можно решить на уровне архитектуры. Язык, который не позволит мне написать не thread-safe программу это довольно сомнительно, IMO.
Помимо этого есть еще проблема композиции. В многопоточном программировании, если твоя программа состоит из thread-safe элементов (все коллекции и объекты используют мьютексы например), это не значит что программа является корректной и потокобезопасной.
Здравствуйте, chaotic-kotik, Вы писали:
CK>Здравствуйте, Sharov, Вы писали:
S>>Вот lock-free структуры данных эту проблему решают. Голова о синхронизации не болит.
CK>
CK>ты эти lock-free структуры данных сам писать то пробовал?
К чему этот вопрос? Я в курсе про дикую сложность их написания и отладки, особенно для ConcurrentDictionary. Но как это влияет на их полезность и применимость?
Здравствуйте, VladD2, Вы писали:
WH>>В коде всё равно понадобятся аннотации. WH>>Так что получаем язык с компилятором вид с боку. VD>+ еще, наверняка, потребуется рантайм менять.
Зависит от того что делать.
Например, мою систему можно натянуть на любой рантайм с ГЦ.
Повышение производительности, которое можно получить, зная особенности этой системы типов конечно не будет, но гарантии того что объект не будут менять из разных потоков останутся.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, chaotic-kotik, Вы писали:
CK>>Пока вы это только обсуждаете, в С++ уже есть thread sanitizer а в Go — race detector. WH>Зуб дашь что я их не сломаю?
Что значит "сломаю"?
WH>Если эта проблема не решена решать остальные не имеет смысла просто по тому что программа не работает.
Т.е. многопоточные программы не работают?
CK>>Thread safety это конечно критично, но это простая проблема, которую можно решить на уровне архитектуры. WH>Зуб дашь что после очередного изменения ссылка на изменяемый объект не зацепится за два потока?
Я это отловлю в тестовом окружении с вероятностью 99.9%.
WH>Корректность программы понятие неопределённое. WH>А вот то что программа не меняет объект из двух потоков доказать можно. WH>Существует несколько систем типов которые это делают.
Это всего навсего одни класс ошибок. Некоторые ошибки многопоточности вообще к падениям не приводят (starvation, false shearing)но тем не менее являются ошибками. Основная сложность это вообще не это, а всякие performance related штуки. Типа, нужен нам счетчик, который бы инкрементировался из разных потоков, можно на атомиках сделать, но это медленно, т.к. contention, а можно сделать счетчик как folly.
Как поможет написать счетчик a-la folly твоя идея я хз.
Здравствуйте, chaotic-kotik, Вы писали:
CK>>>Пока вы это только обсуждаете, в С++ уже есть thread sanitizer а в Go — race detector. WH>>Зуб дашь что я их не сломаю? CK>Что значит "сломаю"?
Сделаю гонку, которую они не поймают.
WH>>Если эта проблема не решена решать остальные не имеет смысла просто по тому что программа не работает. CK>Т.е. многопоточные программы не работают?
Сложные обычно не работают.
Они начинают работать только после очень долгой отладки. И то не факт.
WH>>Зуб дашь что после очередного изменения ссылка на изменяемый объект не зацепится за два потока? CK>Я это отловлю в тестовом окружении с вероятностью 99.9%.
Ещё один адепт секты "тесты гарантируют корректность программы".
CK>Это всего навсего одни класс ошибок.
Но очень гадкий класс ошибок. Примерно, как порча памяти.
Он может приводить к молчаливой порче данных которую никакими тестами не отловить.
Порча данных может быть использована как дыра в безопасности.
CK>Некоторые ошибки многопоточности вообще к падениям не приводят (starvation, false shearing)но тем не менее являются ошибками. Основная сложность это вообще не это, а всякие performance related штуки. Типа, нужен нам счетчик, который бы инкрементировался из разных потоков, можно на атомиках сделать, но это медленно, т.к. contention, а можно сделать счетчик как folly. CK>Как поможет написать счетчик a-la folly твоя идея я хз.
Это примерно, как говорить, что статическая типизация не нужна по тому что она не мешает написать квадратичный алгоритм вместо линейного.
То, о чем ты говоришь это другой класс проблем. И решать его нужно другими методами.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
CK>>Что значит "сломаю"? WH>Сделаю гонку, которую они не поймают.
Good luck with that.
WH>Сложные обычно не работают.
Чойта?
WH>Они начинают работать только после очень долгой отладки. И то не факт.
Все приложения требуют тестирования и любой код может потенциально содержать баги.
WH>Ещё один адепт секты "тесты гарантируют корректность программы".
Добро пожаловать в реальный мир, вот вам вести от сохи: сегодня тесты принято собирать с опцией -fsanitize=thread и -fsanitize=address.
WH>Но очень гадкий класс ошибок. Примерно, как порча памяти.
Если код не трогает одну и ту же память одновременно из разных потоков, это еще не означает, что он потокобезопасен.
WH>Он может приводить к молчаливой порче данных которую никакими тестами не отловить.
-fsanitize=thread
WH>Порча данных может быть использована как дыра в безопасности.
Есть класс дыр в безопасности, т.н. double fetch vulnerabilities вызванных именно race-ами, но ты едва ли сможешь избавиться от них с помощью системы типов. Ну и проявляются они в основном в старых С-style API, где размер буфера передается через указатель (он используется как in/out параметр), поэтому вредоносный код может его заэксплотировать, но это в API вызовах, а обычный RC в приложении как правило нельзя использовать.
WH>Это примерно, как говорить, что статическая типизация не нужна по тому что она не мешает написать квадратичный алгоритм вместо линейного. WH>То, о чем ты говоришь это другой класс проблем. И решать его нужно другими методами.
Я же не говорю что это не нужно, только то, что это не очень полезно, так как thread safety и liveliness не гарантирует.
Здравствуйте, chaotic-kotik, Вы писали:
WH>>Сделаю гонку, которую они не поймают. CK>Good luck with that. https://github.com/google/sanitizers/issues/621
Зубы на полку.
WH>>Сложные обычно не работают. CK>Чойта?
Жизнь такая.
CK>Все приложения требуют тестирования и любой код может потенциально содержать баги.
Только стоимость отладки разных типов багов отличается в разы если не на порядки.
CK>Если код не трогает одну и ту же память одновременно из разных потоков, это еще не означает, что он потокобезопасен.
Рассказывай дальше. Что там такое может произойти?
CK>Есть класс дыр в безопасности, т.н. double fetch vulnerabilities вызванных именно race-ами, но ты едва ли сможешь избавиться от них с помощью системы типов.
Есть несколько разных систем типов которые убивают гонки с 100%ной гарантией.
CK>Я же не говорю что это не нужно, только то, что это не очень полезно, так как thread safety и liveliness не гарантирует.
Ты не крути. Ты расскажи, что может произойти если гонок нет от слова совсем.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Ладно, уел. (хотя я не припомню data-race-ов на глобальных переменных (не используем) или стековых переменных в своей практике)
CK>>Чойта? WH>Жизнь такая.
Я бы сказал что это чрезмерное обобщение. За ним обязательно должна следовать ссылка на что-нибудь, подтверждающее твои слова. Если я напишу "системы типов не уменьшают число багов" просто так, заклюете же.
CK>>Все приложения требуют тестирования и любой код может потенциально содержать баги. WH>Только стоимость отладки разных типов багов отличается в разы если не на порядки.
Еще одно спорное утверждение. Пересобрал с tsan-ом, воспроизвел и все. Можно еще под helgrind-ом запустить.
CK>>Если код не трогает одну и ту же память одновременно из разных потоков, это еще не означает, что он потокобезопасен. WH>Рассказывай дальше. Что там такое может произойти?
Race condition же, или ты считаешь что data race это единственная разновидность race condition? Что нибудь в духе:
if (queue.empty()) { // lock-free queue
connection.close(); // здесь queue.empty() уже равно false
}
или такое тоже можно отловить?
CK>>Есть класс дыр в безопасности, т.н. double fetch vulnerabilities вызванных именно race-ами, но ты едва ли сможешь избавиться от них с помощью системы типов. WH>Есть несколько разных систем типов которые убивают гонки с 100%ной гарантией.
Например?
CK>>Я же не говорю что это не нужно, только то, что это не очень полезно, так как thread safety и liveliness не гарантирует. WH>Ты не крути. Ты расскажи, что может произойти если гонок нет от слова совсем.
Starvation/priority inversion, thundering herd, deadlock, livelock, lock contention (крайние проявления по крайней мере).
Здравствуйте, WolfHound, Вы писали:
EP>>Необязательно. Например верификатор может ограничить всё глобальное взаимодействие до одного объекта очереди сообщений. WH>Слишком сильное ограничение.
Во-первых, это лишь простейший пример для демонстрации идеи, причём рабочий. В реальности верификатор может разрешать более сложный сценарии.
Во-вторых, в штуках типа Erlang на подобных очередях сообщений всё и построено
EP>>Да и аннотации уже есть во многих языках, если же нет — то можно для этой цели использовать типы. WH>Так это и получается язык с компилятором, но через зад автогеном.
Здравствуйте, VladD2, Вы писали:
EP>>Не обязательно язык, и даже необязательно компилятор. Достаточно внешнего верификатора. VD>Это равносиельно языку.
Нет. По-твоему какой-нибудь Lint'ер, Resharper, предупреждатор превращает язык в другой?
Но это уже вопрос терминологии, и не особо интересно.
VD>Ну, и не факт что достаточно.
Достаточно для чего? Например в Erlang всё на очердях сообщений и построено.
VD>Для это "верификации" нужна модель.
Модель чего? Ясное дело что будет некоторая спецификация — верификатор лишь будет её форсировать.
VD>Плюс нужна поддержка в рантайме.
Это может быть обычной библиотекой.
VD>Короче, если бы все был так просто, то проблему эту уже давно решили.
А я не говорю что это супер просто. Это вполне возможно, и отдельный язык для этого не нужен.
Проблемы с очередями сообщений и подобным — например в производительности. На локах, а тем более atomics, нужно лисапедить когда недостаточно отработанных решений типа очередней сообщений, акторов, CSP и прочего.
VD>Но что-то решения не видно не смотря на монструозные коллективы работающие над этим в Майкрософт, Гугле и Оракле.
Решения чего? Кривых рук которые сломя голову хватаются за низкоуровневые примитивы синхронизации в тех случаях когда достаточно высокоуровневых, и вполне закономерно бегают по граблям?
Здравствуйте, chaotic-kotik, Вы писали:
CK>Помимо этого есть еще проблема композиции. В многопоточном программировании, если твоя программа состоит из thread-safe элементов (все коллекции и объекты используют мьютексы например), это не значит что программа является корректной и потокобезопасной.
Отчасти эту проблему пытаются решить посредством STM — software transactional memory.
Здравствуйте, Философ, Вы писали:
Ф>А во что это в итоге скомпилируется?
В параллельную редукцию. Например каждому потоку, число M которых соответствует числу вычислительных единиц, дадут задание в собственном под-диапазоне, что возможно за счёт ассоциативности.
Потом эти M результатов свернут в один, в соответствии с операцией. Если M достаточно большое — то эти M значений опять могут разбить на параллельные под-диапазоны.
Конкретные детали зависят от реализации OpenMP. Но думаю вопрос не в этих деталях, так как аналогичная техника реализуется и без расширений языка, посредством ФВП — например Intel TBB, или Microsoft PPL.
Ф>Оно не получится медленнее чем однопоточный варинант? Не превысят ли накладные расходы на распараллеливание выигрыш от самого распараллеливания?
Очевидно зависит от стоимости ассоциативной операции и входного N, так как накладные расходы от них практически не зависят.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Во-вторых, в штуках типа Erlang на подобных очередях сообщений всё и построено
Разговаривал я с реальными ерлангистами. Рассказывали они как оно работает в реальности, а не в маркетинговых статьях.
Короче очень плохо оно работает.
И что самое смешное рассказывали примерно те же самые жутики что я предсказал, изучив модель эрланга.
WH>>Так это и получается язык с компилятором, но через зад автогеном. EP>Верификатор это не компилятор.
Добавление аннотаций == изменение языка.
Верификатор == компилятор — генерация кода.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, chaotic-kotik, Вы писали:
CK>Ладно, уел. (хотя я не припомню data-race-ов на глобальных переменных (не используем) или стековых переменных в своей практике)
Смысл в том что решение не имеет под собой точной математической модели, а значит не может обеспечить гарантий.
И кто знает сколько там ещё false negative по углам прячется.
Ибо false positive находятся довольно легко, а false negative только если программист сам откопал.
CK>Я бы сказал что это чрезмерное обобщение. За ним обязательно должна следовать ссылка на что-нибудь, подтверждающее твои слова.
Насмотрелся я на разные попытки писать многопоточные программы.
Пока есть железная дисциплина и код придерживается некоторой модели исполнения то они чаще работают чем нет. Но шаг в сторону и начинается...
CK>Если я напишу "системы типов не уменьшают число багов" просто так, заклюете же.
Обязательно. Ибо системы типов исключают целые классы ошибок.
CK>Еще одно спорное утверждение. Пересобрал с tsan-ом, воспроизвел и все. Можно еще под helgrind-ом запустить.
Про tsan мы уже выяснили.
CK>Race condition же, или ты считаешь что data race это единственная разновидность race condition?
Нет. Но остальные в нормальных языках прописываются явно. Те в коде ты одновременно ожидаешь событие из нескольких источников.
CK>Что нибудь в духе: CK>
CK>if (queue.empty()) { // lock-free queue
CK> connection.close(); // здесь queue.empty() уже равно false
CK>}
CK>
CK>или такое тоже можно отловить?
1)Метод empty в очереди сообщений мягко говоря сомнителен.
При нормальном дизайне там должен быть метод isClosed означающий что сообщений больше не будет.
2)Доставка сообщений с гарантией — это отдельный большой вопрос.
WH>>Есть несколько разных систем типов которые убивают гонки с 100%ной гарантией. CK>Например?
Раз: Re[13]: Языки для распараллеленных вычислений
Два: http://www.ponylang.org/
CK>Starvation/priority inversion, thundering herd, deadlock, livelock, lock contention (крайние проявления по крайней мере).
Ещё раз. Это всё равно что заявлять, что статическая типизация не нужна, ибо позволяет написать вместо линейного алгоритма квадратичный.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
EP>>Во-вторых, в штуках типа Erlang на подобных очередях сообщений всё и построено WH>Разговаривал я с реальными ерлангистами. Рассказывали они как оно работает в реальности, а не в маркетинговых статьях. WH>Короче очень плохо оно работает. WH>И что самое смешное рассказывали примерно те же самые жутики что я предсказал, изучив модель эрланга.
Это всё здорово, и у модели Erlang есть действительно определённые недостатки/проблемы.
Вот только не надо уходить в сторону от исходного обсуждения, а именно от того насколько трудно гарантировать отсутствие одновременного доступа из нескольких потоков к данным которые к этому не готовы — в обсуждаемом примере с верификатором эта задача решается ограничением глобального доступа только к одной потокобезопасной очереди
WH>>>Так это и получается язык с компилятором, но через зад автогеном. EP>>Верификатор это не компилятор. WH>Добавление аннотаций == изменение языка.
1. Механизм аннотаций описан в рамках самого языка.
2. Да и в обсуждаемом случае они особо не нужны, достаточно нормальной системы типов.
WH>Верификатор == компилятор — генерация кода.
Не обязательно. Например в верификатор может быть заложена куда более простая модель языка нежели чем в компилятор. Например очевидно что верификатор гарантирующий отсутствие одного из ключевых слов в коде — намного проще того что есть в "компилятор — генератор"
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Вот только не надо уходить в сторону от исходного обсуждения, а именно от того насколько трудно гарантировать отсутствие одновременного доступа из нескольких потоков к данным которые к этому не готовы — в обсуждаемом примере с верификатором эта задача решается ограничением глобального доступа только к одной потокобезопасной очереди
Ты себя послушай... "глобального доступа только к одной потокобезопасной очереди" == ограничение возможностей языка == другой язык.
Одна из основных задач компилятора — определение того принадлежит ли текст программы к языку.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Ты себя послушай... "глобального доступа только к одной потокобезопасной очереди" == ограничение возможностей языка == другой язык.
По-твоему какой-нибудь Lint'ер, Resharper, предупреждатор превращает язык в другой?
ОК, возможно, но это уже вопрос терминологии, и не особо интересно
Здравствуйте, WolfHound, Вы писали:
CK>>Если я напишу "системы типов не уменьшают число багов" просто так, заклюете же. WH>Обязательно. Ибо системы типов исключают целые классы ошибок.
Вопрос не об этом был.
CK>>Еще одно спорное утверждение. Пересобрал с tsan-ом, воспроизвел и все. Можно еще под helgrind-ом запустить. WH>Про tsan мы уже выяснили.
Ничего мы про него еще не выяснили. Если крайне полезный инструмент с небольшой вероятностью может дать false negative, то это не значит что он бесполезен. Ну и что что нет "гарантии". Гарантии никогда нет, ее не может быть в принципе, до тех пор, пока весь код не будет верифицирован. Там же могут еще быть всякие милые сердцу вещи вроде FFI и всяких callback-ов из native потоков. В общем, до момента, пока великая система типов все верифицирует можно не дожить, а TSan есть уже сейчас.
CK>>Race condition же, или ты считаешь что data race это единственная разновидность race condition? WH>Нет. Но остальные в нормальных языках прописываются явно. Те в коде ты одновременно ожидаешь событие из нескольких источников.
Define "нормальные языки". Пока получается такая цепочка рассуждений — data race очень опасная штука, потому что очень сложно найти источник проблемы, а race condition in general — нет, так как в "нормальных языках" (тм) ...
WH>1)Метод empty в очереди сообщений мягко говоря сомнителен. WH>При нормальном дизайне там должен быть метод isClosed означающий что сообщений больше не будет. WH>2)Доставка сообщений с гарантией — это отдельный большой вопрос.
Ну вот видишь, получается что просто нормальным дизайном можно избавиться от проблемы. Подумать явно о том что в фоне может что-то с очередью происходить и все. Тем не менее, если программист пишет межпоточную очередь с метдом empty, как ты его остановишь? Какая система типов запретит делать херню?
WH>>>Есть несколько разных систем типов которые убивают гонки с 100%ной гарантией. CK>>Например? WH>Раз: Re[13]: Языки для распараллеленных вычислений
А как же накладные расходы на копирование/сериализацию/десериализацию?
CK>>Starvation/priority inversion, thundering herd, deadlock, livelock, lock contention (крайние проявления по крайней мере). WH>Ещё раз. Это всё равно что заявлять, что статическая типизация не нужна, ибо позволяет написать вместо линейного алгоритма квадратичный.
Если ты предлагаешь какую-то модель вычислений в качестве решения проблемы, она должна решать не только эту проблему. Это мое IMO конечно, но то что ты предлагаешь (разделить кучи) это как раз такое вот решение, которое решает одну проблему и закрывает глаза на другие.
Здравствуйте, chaotic-kotik, Вы писали:
CK>Ничего мы про него еще не выяснили.
Выяснили что ничего он не гарантирует.
CK>Define "нормальные языки". Пока получается такая цепочка рассуждений — data race очень опасная штука, потому что очень сложно найти источник проблемы, а race condition in general — нет, так как в "нормальных языках" (тм) ...
Если единственный способ получить гонку написать:
GetMessage(mailbox1, mailbox2, mailbox3...)
то проблем нет.
CK>Ну вот видишь, получается что просто нормальным дизайном можно избавиться от проблемы.
Только мы тут о других проблемах говорим.
И нормальный дизайн от ошибок по невнимательности не защищает.
А система типов именно это и делает. Причем гарантированно.
CK>Подумать явно о том что в фоне может что-то с очередью происходить и все. Тем не менее, если программист пишет межпоточную очередь с метдом empty, как ты его остановишь? Какая система типов запретит делать херню?
1)Никакая. Точно так же как никакая система типов не запретит вместо линейного алгоритма написать квадратичный.
2)Очередь должна быть в стандарной библиотеке. Так что 99.999% программистов её писать не будут.
WH>>Раз: Re[13]: Языки для распараллеленных вычислений
CK>А как же накладные расходы на копирование/сериализацию/десериализацию?
Их нет. В пределах одного адресного пространства передача графа объектов из одного потока в другой на машинном уровне всегда сводится к передаче одного указателя.
Вся эта пляска с системами типов для этого и задумывалась.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
CK>>Есть класс дыр в безопасности, т.н. double fetch vulnerabilities вызванных именно race-ами, но ты едва ли сможешь избавиться от них с помощью системы типов. WH>Есть несколько разных систем типов которые убивают гонки с 100%ной гарантией.
А если нам эти гонки принципиально нужны для lock-free алгоритмов?
Здравствуйте, VladD2, Вы писали:
VD>На мой взгляд от языков программирования следующего поклонения нужно требовать не автоматического распараллеливания, а обеспечения гарантий корректности ручного распараллеливания.
Может ты и прав, но по-моему, основная проблема в том, что человек не очень умеет распараллеливать свои алгоритмы. Так что может все же будущее за автоматическим распараллеливанием. В языке при этом было бы полезно иметь какие-то средства, позволяющие объяснить компилятору, что от чего на самом деле зависит, а что зависит только случайно.
VD>Правильные мысли есть в Расте. Но там все слишком сложно для того чтобы это могло войти в мэйнстрим. Нужно научить языки манипулировать кучами. Научить передавать эти кучи между "виртуальными процессами" (в стиле Эрланг).
Раст, на мой (очень поверхностный) взгляд черезчур детальный. Слишком много слов надо сказать компилятору, чтобы выразить мысль. То, что многие из этих слов обозначаются двухбуквенными сокращениями, особо не помогает
Здравствуйте, VladD2, Вы писали:
VD>Параллелить можно только сущности реально способные обрабатываться независимо. На сегодня, решить что можно параллелить может только лишь человек.
Мне кажется, конечное решение, что параллелить, а что нет, можно принять только в рантайме. Человек должен иметь возможность выразить, что можно параллелить, но вот будет оно фактически распараллелено или нет, можно определить только в процессе исполнения.
VD>Грубо говоря нужны языки обеспечивающие дешевые паралельные процессы. И дешевую передачу данных между ними. Для этого нужны: VD>1. Гарантией неизменности данных разных "процессах".
Функциональное программирование без побочных эффектов?
VD>2. Дешевизна передачи данных (заморозка графа объектов в одном процессе и передачи его в другой).
Заметим, что если данные не могут меняться, то передача их довольно дешевая. Но есть естественное ограничение, если данные передаются между кешами разных процессорных ядер, это не бесплатно на аппаратном уровне.
Здравствуйте, Pzz, Вы писали:
Pzz>Может ты и прав, но по-моему, основная проблема в том, что человек не очень умеет распараллеливать свои алгоритмы.
Многие и написать то их не в состоянии. Зачем равняться на идиотов? У меня как-то само распараллеливание проблем не вызывает. Человек отлично понимает где имеет смысл вводить параллелизм. В отличии от компьютера он понимает и держит в голове модель всего приложения и представляет какими данными человек манипулирует.
У компьютера же 100500 вариантов и выбрать оптимальный — неразрешимая, для него, задача.
Pzz>Так что может все же будущее за автоматическим распараллеливанием. В языке при этом было бы полезно иметь какие-то средства, позволяющие объяснить компилятору, что от чего на самом деле зависит, а что зависит только случайно.
"Рассказать" может и можно, но пока нет ИИ решить где надо параллелизм компьютер не сможет.
Он сможет выявить участки кода которые нельзя параллелить (т.е. должны выполняться последовательно). Но таких участков будет море. И еще не факт, что нужно весь этот участок параллелить, а не его часть.
Параллелить любую возможную последовательность бессмысленно. Просто перенос вычислений в отдельный поток занятие довольно дорогое. Издержки могут превысить выигрыш.
Pzz>Раст, на мой (очень поверхностный) взгляд черезчур детальный. Слишком много слов надо сказать компилятору, чтобы выразить мысль. То, что многие из этих слов обозначаются двухбуквенными сокращениями, особо не помогает
В Расте отказались от ЖЦ чем усложнили программирование. Но в целом там есть правильные идеи. Лучше пока что ничего нет.
Pzz>Зачем нужно передавать кучи?
Для эффективности. Довольно распространенным паттерном является: формирование некоторого набора данных и передача его на обработку в другой поток/процесс (возможно даже удаленный).
Pzz>Странно, что ты не упомянул go.
Это тупейший язык не имеющий ничего интересного в области распараллеливания кода (если они ничего нового не придумали).
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Pzz, Вы писали:
Pzz>Мне кажется, конечное решение, что параллелить, а что нет, можно принять только в рантайме.
Из чего это вытекает? Я вот как-то без проблем параллелью код в во время проектирования.
Более того не очень ясно что делать в рантайме. Код то уже скомпилирован. В рантайме можно лишь решить в скольких потоках выполнять ту или иную функцию (в одном или в нескольких). Но сам код распараллеливания уже должен быть написан и распараллеливание функция должна быть выбрана. Или весь код будет каким-тол жутким интерпретатором.
Pzz>Человек должен иметь возможность выразить, что можно параллелить, но вот будет оно фактически распараллелено или нет, можно определить только в процессе исполнения.
Все с точностью до наоборот. На практике я точно знаю какие части программы имеет смысл распараллелить. А компьютер (компилятор, рантайм и т.п.) и понятия не имеет. Он туп.
Вот берем конкретный пример компилятора. Я точно знаю, что параллельно можно парсить. И мне нужен лишь контроль со стороны компилятора и рантайма, который поможет мне избежать ошибок. Когда я пишу код парсинга мне нужно проконтролировать, что разные парцедуры парсинга не начнут менять какие-то общие данные. А общие данные таки могут быть. Например, для повышения эффективности может производиться какое-то там кэширование правил, которые в дальнейшем могут использоваться в параллельных процедурах. Причем формировать эти кэши желательно императивно, а использовать в рейд-онли режиме. Все это можно обеспечить и проконтролировать врунчую, но это черевато ошибками. И проблема в том, что внутри сложной программы невозможно быть уверенным, что таких ошибок нет. А поиск таких ошибок может быть очень болезненным.
По сему мне нужно иметь языковые средства которые бы разделяли работу с данными на два этапа:
1. Формирование.
2. Использование.
А компилятор должен помочь мне четко разделить эти этапы. На этапе формирования я могу императивно манипулировать данными, но исключительно из одного потока. На этапе использования я могу использовать данные из любого числа потоков, но менять их я уже не могу. Она для меня должны быть эдаким слепком.
Естественно, что в какой-то момент я должен иметь возможно снова перевести данные в режим формирования, но это формирование опять таки должно осуществляться в рамках одного потока (т.е. изменения не должны быть видны другим потокам).
В принципе аналогичных результатов можно добиться используя неизменяемые структуры данных и чисто функциональный стиль программирования. Но это:
1. Не всегда эффективно. Точнее — зачастую не эффективно.
2. Все равно есть необходимость подмены неизменяемых структур в разных потоках, а стало быть есть место для ошибки.
Pzz>Функциональное программирование без побочных эффектов?
Нельзя все сделать функционально. Это не эффективно. И это не всегда удобно. Плюс есть еще и внешние источники данных, а так же необходимость взаимодействия с внешними клиентами.
Классические задачи не ложащиеся на ФП:
1. Изменение баз данных.
2. Интерактивный UI.
3. Синхронизация действий внешних агентов (например, пользователей).
Pzz>Заметим, что если данные не могут меняться, то передача их довольно дешевая. Но есть естественное ограничение, если данные передаются между кешами разных процессорных ядер, это не бесплатно на аппаратном уровне.
Если данные не изменяются, то их можно и совместно в разных потоках использовать. Более того, можно создавать версии этих данных, которые используются как часть более новых версий данных Классический односвязный список — отличный пример такой версионности. Но, если в языке есть изменяемые структуры данных, то рано или поздно программист накосячит.
Более того при формировании данных куда эффективнее и удобнее использовать не только неизменяемые структуры, но и "обычные" изменяемые. Например, хэш-таблицу. Но передавать такие данные опасно. Графы же объектов, которые надо передавать, могут быть очень сложными. И вручную проконтролировать, что их части не изменяются случайно в другом потоке невозможно.
Можно конечно тупо клонировать весь граф объектов, но это дорого для многих применений.
Дешевле условно разбить процесс на два:
1. Формирование данных.
2. Использование.
Если заставить компилятор и рантайм контролировать:
1. Отсутствие параллельного доступа на этапе 1 (формирования).
2. Невозможность изменять данные на этапе 2 (использования).
То можно создать очень эффективную и удобную модель для написания параллельных программ.
Такие блоки данных можно помещать в отдельные кучи. А в язык можно добавить средствам манипуляции целыми кучами. За одно это решило бы и проблему не эффективности GC. Так как GC мог бы манипулировать не всеми данными в процессе, а отдельными кучами. За одно было бы проще решать и проблему утечки памяти. Ведь человек может четка определить, что в такой то момент времени ссылок на некоторую кучу быть не должно. И если они есть — это ошибка. Остается только разобраться что не так.
Переключать режимы Формирование/Использование в куче будет очень удобно и просто.
Но для такого подхода нужна поддержка в языке и рантайме. По объекту нужно иметь возможность определить из какой кучи выделен объект и в каком состоянии находится эта куча. В типах указателей так же должна быть информация о режиме в котором находится объект (куча). Нечто похожее на C++-ый const.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, vdimas, Вы писали:
WH>>Есть несколько разных систем типов которые убивают гонки с 100%ной гарантией. V>А если нам эти гонки принципиально нужны для lock-free алгоритмов?
Язык и стандартная библиотека с большим запасом покроют потребности примерно 100% пользователей.
А те пара человек, которым не хватит используют unsafe.
И это если не вспоминать о том, что примерно 99% программистов lock-free структуру данных написать не смогут.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Более того не очень ясно что делать в рантайме. Код то уже скомпилирован. В рантайме можно лишь решить в скольких потоках выполнять ту или иную функцию (в одном или в нескольких). Но сам код распараллеливания уже должен быть написан и распараллеливание функция должна быть выбрана. Или весь код будет каким-тол жутким интерпретатором.
Не обязательно. Можно перекомпилировать код в рантайме как это делают некоторые реализации явы.
VD>Все с точностью до наоборот. На практике я точно знаю какие части программы имеет смысл распараллелить. А компьютер (компилятор, рантайм и т.п.) и понятия не имеет. Он туп.
Лет 10-15 назад говорили, что руками на ассемблере код получится быстрее чем у компилятора.
Сейчас только упоротые пытаются соревноваться с лучшими компиляторами.
Что получится с автоматическим распараллеливанием будем посмотреть, но от категоричных высказываний лучше воздержаться.
VD>А компилятор должен помочь мне четко разделить эти этапы. На этапе формирования я могу императивно манипулировать данными, но исключительно из одного потока. На этапе использования я могу использовать данные из любого числа потоков, но менять их я уже не могу. Она для меня должны быть эдаким слепком.
Система типов о которой я говорю именно это и делает.
После это строки ссылки на изменяемые структуры данных oldP1, oldP2,... становятся не доступны.
p1, p2,... и всё на что они ссылаются можно использовать имея гарантию что они никогда не будут изменены.
В случае с нитрой идеально подходит для композитных грамматик.
VD>Естественно, что в какой-то момент я должен иметь возможно снова перевести данные в режим формирования, но это формирование опять таки должно осуществляться в рамках одного потока (т.е. изменения не должны быть видны другим потокам).
Тут придётся немного усложнить систему типов и использование таких структур будет создавать шум в виде read lock/write lock и некоторые другие ограничения. Но тоже возможно.
lp1, lp2,... контейнеры содержащие ссылку на примитив синхронизации и указатель на данные. Сами контейнеры являются неизменяемыми для того чтобы можно было положить их в неизменяемую структуру данных.
read lock (p1 = lp1)
{
//тут можно читать содержимое структуры данных
}
//тут все ссылки полученные из структуры станут недоступны
тоже самое с write lock но структуру данных можно ещё и изменять.
В случае с нитрой можно использовать для АСТа, деклараций итп.
VD>Если заставить компилятор и рантайм контролировать: VD>1. Отсутствие параллельного доступа на этапе 1 (формирования). VD>2. Невозможность изменять данные на этапе 2 (использования).
Достаточно компилятора.
VD>Такие блоки данных можно помещать в отдельные кучи. А в язык можно добавить средствам манипуляции целыми кучами. За одно это решило бы и проблему не эффективности GC. Так как GC мог бы манипулировать не всеми данными в процессе, а отдельными кучами.
О чем я тебе уже сколько лет говорю?
VD>Переключать режимы Формирование/Использование в куче будет очень удобно и просто.
формирование -> заморозка
Действительно удобно и просто.
формирование -> использование -> изменение -> использование -> изменение -> ...
Неизбежно потребует дополнительных приседаний.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, vdimas, Вы писали:
V>Ну, простейшим lock-free как раз 99% программистов пользуются регулярно. V>Через т.н. "relaxing memory order":
1)Я сказал написать, а не пользоваться.
2)Большая часть программистов даже не поймёт, что тут написано.
3)Это тупая и не переносимая реализация cancellation token.
Естественно cancellation token как и многие другие примитивы будут в поставке.
V>Да, я помню про твои "каналы". V>Но это ж из пушки по воробьям. ))
Каналы — это ещё один очень полезный инструмент.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, VladD2, Вы писали:
VD>Я не знаю зачем ты мне что-то говоришь. Я объяснял человеку общие идеи и развеивал его сомнения.
То, что ты тут пересказываешь.
VD>Меня за советскую власть агитировать не надо.
С тобой всегда так. Сначала "чё за чушь", через пару лет "я всегда так говорил".
Просто ты ещё сам не до конца понял, что реализовать можно, а что нет.
Вот я тебе и пояснил где ты заблуждаешься.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>2)Большая часть программистов даже не поймёт, что тут написано.
Эээ... не там ты работал и работаешь... ))
WH>3)Это тупая и не переносимая реализация cancellation token. WH>Естественно cancellation token как и многие другие примитивы будут в поставке.
Ну, тут мой ответ и за 10 лет не поменялся:
я вижу слабость таких рассуждений в заведомой зависимости от содержимого "изкаробки", получая резко меньшие возможности для маневра/экспериментов, т.е. для построения своих примитивов.
Я думаю, тут надо спускаться на самый низ и давать тупо базу, а всякие cancellation token пусть будет сугубо библиотечной приблудой, написанной честным образом прямо в языке.
Достаточно взять ровно четыре минимальных базовых примитивов для многопоточности:
— атомарное чтение слова
— атомарная запись слова
— безусловный обмен
— условный обмен
По желанию можно добавить еще операции (если процессор поддерживает):
— атомарные инкремент/декремент
— или даже атомарное прибавление/вычитание
В любом случае, эти последние выражаются через первые, даже если проц не умеет их прямо.
Рисуем "системную" базу:
(некий псевдо-язык, в котором все типы уникальные)
type Atomic { /* тут указатель на машинное слово, в языке не представимо */};
Atomic dup(Atomic); // копия указателя
Word read(Atomic);
void write(Atomic, Word);
Word exchange(Atomic, Word);
Word compare_exchange(Atomic, Word, Word);
Ну и всё.
Теперь твои "каналы", "cancellation tokens" и вообще любые желаемые вещи можно выразить прямо ср-вами языка.
===========
Будет ли там GC или подсчет ссылок для расшаренного машинного слова — не принципиально.
Здравствуйте, vdimas, Вы писали:
WH>>2)Большая часть программистов даже не поймёт, что тут написано. V>Эээ... не там ты работал и работаешь... ))
Ты представления не имеешь где я работал и работаю.
V>Я думаю, тут надо спускаться на самый низ и давать тупо базу, а всякие cancellation token пусть будет сугубо библиотечной приблудой, написанной честным образом прямо в языке.
Перестающем работать при переносе на другую железку.
V>Достаточно взять ровно четыре минимальных базовых примитивов для многопоточности:
Не нужен этот ад при прикладной разработке.
V>Теперь твои "каналы", "cancellation tokens" и вообще любые желаемые вещи можно выразить прямо ср-вами языка. Только никакого контроля со стороны компилятора не будет.
А значит можно оставаться на С++.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, vdimas, Вы писали:
V>Цимус в том, что произвольные прикладные библиотеки становится возможным разрабатывать ср-вами безопасного языка, а не вкладывать их в некую магическую "поставку".
Хватит пороть чушь. Ей больно.
Никаких гарантий со стороны компилятора на этих примитивах ты не получишь.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Перекуём баги на фичи!
