Здравствуйте, neFormal, Вы писали:

НС>>Но ведь С++ то не единственная альтернатива. Java или дотнет и компилируются секунды, и прекрасно позволяют перезагружать классы/сборки на ходу.
F>дотнет на серваках держать не хочется

Твои фобии, уж извини, не аргумент ни разу.

F>а у жавы проблемы с распределённостью.

А если распределенность не нужна?

F> только akka вроде дала нужные плюшки

Ага, значит все таки нерешимых проблем нет.

F>но это уже половина эрланга.

И что?

Здравствуйте, Ночной Смотрящий, Вы писали:

V>>О том, о чем написано. При вызове из тела Task другого асинхронного метода через await происходит переключение логических потоков по принципам кооперативной многозадачности.
НС>Мдя. Ничего там не происходит. По await метод просто режется

Что значит "режется"? ))
Происходит прерывание текущего логического потока (в твоей терминологии — в том самом месте "нарезки"), т.е. поток OS (worker из пула потоков) запускает следующую задачу из той самой СОБСТВЕННОЙ очереди. Т.е. тело асинхронного метода можно рассматривать как некий логический поток, у которого срабатывает механизм кооперативной многозадачности в месте await (и то не всегда), т.е. в местах await текущий логический поток вычислений может быть прерван и вместо него будет запущен другой.

Бенефит work stealing именно в том, что каждый worker не лезет в IOCP за следующей задачей, а обрабатывает свою очередь до тех пор, пока она не пуста, потом пытается обработать очередь другого случайного потока, если она тоже не пуста. Т.е. только когда личные очереди потоков будут пусты, worker начинает слушать IOCP.

НС>и неважно, в теле другого таска или где то еще. Но к зависимостям задач это отношения не имеет. Хуже того, await вобщем то никак на Task не завязан, ему нужен только awaiter. И уж точно никакого переключающего вызова API тут нет, это чисто статическая штука. Ты же сам писал про то что yield и await это близнецы-братья.

Боюсь, что выделенное — это спор о терминологии. Если awater не готов еще, то происходит возврат из асинхронного метода. В случае Task происходит возврат worker-у из пула, то бишь запускается механизм шедуллинга (выполняется алгоритм work-stealing тем самым worker-ом).


НС>>>И при чем тут work stealing? Work stealing дотнет применяет вовсе не для ожидания другой задачи
V>>Вообще-то тот шедуллер, идущий в поставке, который сидит на пуле потоков, он с версии 4.0 стал work-stealing. Более того — lock-free, более того, теперь он наиболее дешев в режиме LIFO (из-за оссобенностей конструкции lock-free очереди, которая представляет из себя стек, скорее).
НС>Я в курсе. Я его код почти весь прочел. Поэтому и говорю, что work stealing никакого отношения к ожиданию IO не имеет.

Ну я прочел код нейтивного PPL, который вышел одновременно с .Net 4, TPL и одновременно с VS 2010. В случае, когда все личные очереди worker-ов пусты, они сидят на IOCP. Более того, они устанавливают специальный флаг, говорящий о том, что они перешли в режим "ядерного" ожидания задач, т.е. следующая задача, которую надо выполнить в worker-е, будет поставлена не ему в личную очередь, а в IOCP и будет обработана первым же проснувшимся на IOCP потоком.

Т.е., вся дешевизна work stealing проявляется ровно в одном сценарии — когда новые задачи поступают на обработку, но очереди задач еще не пусты, т.е. в сценарии, который можно назвать "нагруженным". Только тогда операция постановки задачи в очередь выполняется со "скоростью света", потому что при этом не дергаются ядерные вызовы.


НС>>>(для этого там есть такая штука как зависимость задач).
V>>Это при ожидании некоего task, а при порождении новой задачи?
НС>Зависимость создается автоматически. И это по прежнему никакого отношения к work stealing не имеет.

Там происходят две вещи (в случае некоего await SomeAsyncMethod()):
1. запуск новой задачи (с сигнатурой Task<> SomeAsyncMethod());
2. создание зависимости от возвращенного Task;
Причем, если на момент шага (2) случилось так, что Task, порожденный вызовом SomeAsyncMethod уже успел перейти в состояние resolved (ну мало ли как карты легли из-за низлежащей вытесняющей многозадачности ОС), то зависимость не создаётся, а метод продолжает выполняться. Т.е. на шаге (2) создаётся зависимость и происходит возврат из асинхронного метода (в моей терминологии — "переключение логического потока") только если задача, порожденная шагом (1) не успела выполнится на момент шага (2).

V>>В общем, там намного больше тонкостей и намного больше любопытных эффектов, чем можно описать в одном посте.
НС>Какие уж тут тонкости, если ты какие то ожидания приплел. С work stealing нет никаких суперсложностей. В дизайн-документе TPL на все описание хватило пары абзацев ЕМНИП. Да и в исходниках тоже все довольно тривиально. Открываешь ConcurrentBag.cs и читаешь.

Ага, посмотрел ConcurrentBag.cs, спс.

В общем, в нейтивном варианте аналогичной либы PPL/task чуть другой механизм, там очередь обслуживает только через lock-free, а в ConcurrentBag.cs — через Monitor.Enter/Exit и через спин-ожидание на поле list.m_currentOp (т.е. таки разновидность блокирующего мьютекса, только вместо ядерного примитива — просто спин).

Алгоритм вышел чуть другой в итоге, попроще.


V>> К тому же, ты вводишь людей в заблуждение — уже активированные задачи (поставленные в очередь) лучше всего шедуллятся через round robin
НС>Уж не знаю лучше или хуже, но вот TPL использует для этого очереди, привязанные к потокам + work stealing.

V>>То бишь, work stealing хорошо умеет только одно — дешево ставить задачу в очередь.
НС>Вот только в TPL этого нет.

В ConcurrentBag.cs очереди ThreadLocalList из Node.
Это оно и есть.


V>> В нейтивном варианте постановка в ту очередь на PPL занимает несколько десятков ns всего.
НС>В TPL тоже все сравнительно быстро. Но при чем здесь ожидание задач?

После того, как текущий async-метод прервется на await task, кто-то должен выполнить этот task. И это зависит уже от того, что происходит при порождении ожидаемого task. Если там асинхронный ввод-вывод на IOCP или просто некое действие, выполняемое по таймеру, привязанному к IOCP, то "кто-то" должен слушать IOCP.

The default scheduler for Task Parallel Library and PLINQ uses the .NET Framework ThreadPool to queue and execute work. In the .NET Framework 4, the ThreadPool uses the information that is provided by the System.Threading.Tasks.Task type to efficiently support the fine-grained parallelism (short-lived units of work) that parallel tasks and queries often represent.

ThreadPool Global Queue vs. Local Queues

As in earlier versions of the .NET Framework, the ThreadPool maintains a global FIFO (first-in, first-out) work queue for threads in each application domain. Whenever a program calls QueueUserWorkItem (or UnsafeQueueUserWorkItem), the work is put on this shared queue and eventually de-queued onto the next thread that becomes available. In the .NET Framework 4, this queue has been improved to use a lock-free algorithm that resembles the ConcurrentQueue<T> class. By using this lock-free implementation, the ThreadPool spends less time when it queues and de-queues work items. This performance benefit is available to all programs that use the ThreadPool.

Top-level tasks, which are tasks that are not created in the context of another task, are put on the global queue just like any other work item. However, nested or child tasks, which are created in the context of another task, are handled quite differently. A child or nested task is put on a local queue that is specific to the thread on which the parent task is executing. The parent task may be a top-level task or it also may be the child of another task.

Собсно, в нейтивном PPL аналогично, только еще чуть заковырестее. Не обязательно быть в контексте выполнения task, чтобы дочерний порожденный task отправить в очередь задешево (т.е. отправить в локальную lock-free очередь, а не глобальную поверх IOCP).


НС>>>Там все совершенно банально и никакого отношения к async автоматам не имеет.
V>>Э, нет. Не банально. Очередь специфическая, решает проблему ABA весьма остроумным способом. Скажу так, на этом сайте, когда шло активное обсуждение lock-free алгоритмов, этот способ никем не упоминался.

НС>Какой способ? Локализация данных по потокам с целью уменьшения блокировок? Довольно стандартный прием.

Речь об ABA-проблеме в случае lock-free стека. Описана здесь.

Решается вот так:
\Program Files (x86)\Microsoft Visual Studio 10.0\VC\crt\src\collections.h

    //
    // An implementation of interlocked SLIST that does not support Pop. This
    // avoids the ABA problem. The reason for this data structure is to get
    // to the top node (Windows SLIST does not provide this functionality
    // without FirstSListEntry).
    // Type T is required to have an intrusive SLIST_ENTRY m_slNext.
    //
    template <class T>
    class LockFreePushStack

Скажу честно, обнаружив это с выходом VS2010 малость обрадовался, т.к. своё аналогичное решение было полностью умозрительным и нигде я его обсуждений не видел. Т.е. был уверен в нем, скажем, на 99.5%, не более. ))

НС>ConcurrentBag вообще сравнительно простой.

Слишком простой и НЕ является полностью lock-free.

V>>И тут не всё так просто. Возможна ситуация, когда все потоки из пула загружены тасками, порождающими другие асинхронные таски безо-всякого ввода-вывода.
НС>Возможна. Именно для этого там очереди. Какая связь с тем кто кого порождает непонятно.

Ну вот я привел вырезку из доки MSDN. В дотнете связь идёт по тому, в какую очередь будет поставлена задача — в локальную задешево или в глобальную задорого.


V>> Не заглядывая в доку предположи — кто и как слушает IOCP при этом и слушает ли? ))
НС>Ничего не понял. IOCP вообще не дело TPL.

IOCP — это такой механизм, на котором сидит стандартный дотнетный пул потоков. IOCP необязательно связан с вводом-выводом, это просто системная очередь (в случае дотнета — глобальная, т.е. одна на домен), которой можно послать некий тикет и разбудить им случайный поток, который в БЛОКИРУЮЩЕМ режиме слушает эту очередь.

НС>Это особенность реализации конкретных методов конкретного асинхронного API. Если у тебя задача чисто вычислительная, то и IOCP не нужен.

Ну так ты посмотри, как шедуллятся Task-и в TPL. ))
Как раз на глобальном пуле потоков, т.е. как раз Task-и верхнего уровня идут прямиком в IOCP.


НС>Но ты то там задвигал про ожидание IO.

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


НС>>>А если внутри задачи ждать, то это как раз таки быстро поставит конвеер TPL раком, и work stealing только поспособствует тому, чтобы раком встало как можно больше аппаратных потоков.
V>>Речь шла о логическом потоке. В любом случае, логический поток всегда ждет выполнения другой задачи, т.е. блокирован.
НС>В рамках TPL это крайне плохая практика, ставящая, как я уже писал, TPL раком. Суть fork/join состоит в том, чтобы нарезать задачу на куски, которые ничего не ждут и связать их зависимостями. А уж сделано это вручную или при помощи написания в нужных местах await — никакой роли не имеет.

Да я уже понял, что это "столкновение" терминологий.
Конечно, я не имел ввиду блокирующие ожидания "физического" (ядерного) потока. Повторюсь, я рассматриваю асинхронные методы как логические потоки.

Напомню, что дискуссия шла изначально о корутинах в C++, так вот, серьезной разницы с т.з. С++ кода м/у stackless и stackful корутинами нет и не будет. Но, как я вижу, одни коллеги готовы рассматривать stackful-корутину как логический вычислительный процесс, а stackless — нет. )) В дотнете async-методы — это stackless корутина, которую можно рассматривать как "линейный" вычислительный процесс. Ну а то, что там унутре автомат с состояниями или связь task-ов, порождающая граф вычислений — это уже дело десятое. ))


НС>И опять это совсем другая тема, к work stealing отношения не имеющая.

Да я просто хотел обратить внимание коллеги, что work stealing хорошо работает только тогда, когда имеем большой трафик маленьких задач. Тогда происходит серьезная экономия ресурсов за счет работы через локальные очереди, вместо глобальной-системной.


V>> Используя пул потоков мы лишь убегаем от ядерного переключения логических потоков
НС>При чем тут пул потоков?

ы?

Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Я подробностей сейчас не помню, но там возникает логическая связь между очередями, которую при помощи CAS или заведения массива флажков не разрулишь.

В нейтиве достоверно lock-free. Но с той особенностью, что у другого потока за раз отбирается ВСЯ его очередь на момент обращения к ней.
Вот тут:
\Program Files (x86)\Microsoft Visual Studio 10.0\VC\crt\src\collections.h

См. метод:

// Flush all the elements in the stack
T * Flush()

Т.е., схема такая:
— некий поток из пула порождает task-и и складывает их к себе в очередь;
— остальные свободные потоки отбирают у него всё содержимое очереди на момент обращения к ней (просто вызов Flush());
— текущий поток из пула, после окончания выполнения текущего task (порождающего другие task-и), заберет себе на стек всё содержимое своей локальной очереди в стековую переменную, затем, если эта очередь не пуста, изымет из неё один task (владея ей единолично, т.е. без всяких ABA-проблем) и опять вернет хвост очереди самому себе;
— если своя очередь пуста, то поток попытается отобрать задачи у другого случайного потока, потом следующего и т.д.;
— если все локальные очереди потоков окажутся пусты, то поток становится в блокирующее ожидание на глобальной IOCP-очереди.

Локальные очереди там LIFO, т.е. просто стеки. Первым выполняются задачи, поставленные в очередь последними. Что тоже гут с т.ч. актуальности кеша проца.

Глобальная очередь — FIFO.

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>>>Если "попросить" — то это work requesting.
НС>>А если грохнуть шедулер, у которого мы попросили, то это work robbing?

EP>А вообще я серьёзно, work-stealing и work-requesting — это разные механизмы. remark вот тут резюмировал.

Ну он там так рассуждает:

There are also 2 problems with work-stealing due to it's asynchronous nature. First, it inherently incurs some observable per-task overhead, because every pop operation from a thread's work deque must be synchronized with a potential asynchronous steal operation from another thread. Stealing is rare, but one still has to pay that price on every pop operation. The price is at least a single store-load style memory fence (MFENCE instruction for x86 architecture), or a single atomic RMW operation (LOCK prefixed instruction on x86). Here is an illustration of the problem:

Нашел исходник:
http://www.1024cores.net/home/parallel-computing/concurrent-skip-list/work-stealing-vs-work-requesting

Спорно, что один безусловный атомарный exchange стоил того, чтобы отказаться от work stealing в пользу work requesting. Это надо на конкретных боевых задачах мерить, т.е. даже не на прототипах.

Здравствуйте, Evgeny.Panasyuk, Вы писали:


EP>Никакое не ЧТД
EP>Что мешает вот это:
EP>

EP>future<void> coroutine()
EP>{
EP>    int x = await foo;
EP>    char y = await bar;
EP>    cout << x << " " << y << endl;
EP>}
EP>

Преобразовать вот в это:
EP>

EP>struct coroutine : asio::coroutine
EP>{
EP>    int x;
EP>    char y;

EP>    void operator()()
EP>    {
EP>        reenter(*this)
EP>        {
EP>            await(x, foo); // x = await foo;
EP>            await(y, bar); // y = await bar;
EP>            cout << x << " " << y << endl;
EP>        }
EP>    };
EP>};
EP>

?

То, что future<void> — это value-type, который владеет через shared над future_shared_state.


EP>Более того, в C# именно подобное преобразование и происходит.

Конечно именно так. Но там TaskAwaiter — это value-type, просто фасад над Task. Зато сам Task создаётся в куче. И поданное ему continuation — это делегат, лямбда для которого тоже создаётся в куче.


V>>Так вот, если уши торчат, как в твоём примере, то нафига это тянуть в стандарт?
EP>Я не предлагаю в стандарт тянуть эмуляцию на макросах. Ещё раз, я показываю как оно может быть устроенно внутри.

Я прекрасно понимаю, как оно устроено изнутри. Но я, хоть убей, не могу понять, как ты собрался реализовать свои желания с т.з. системы типов C++?

Вот у нас есть тип std::future, который устроен примерно так:

template<class T>
class future {
...
  shared_ptr<shared_state> shared_state_;
}

Т.е. внутри него всего одно поле и sizeof(future<>) скорее всего совпадет с sizeof(shared_state_).
Где ты предлагаешь разместить аналог своего asio::coroutine в future<>? Я бы его разместил в объекте-наследнике того самого shared_state, который, в свою очередь, создаётся на куче.

Другое дело:

iterator<T> generate() resumable {
  yield return 1;
  yield return 2;
};

Т.к. тип iterator<> еще не специфирован, вполне возможно, что у него будет некое зарезервированное поле, в котором можно поместить целочисленную переменную — состояние автомата-корутины.

НО! Это всё еще не так просто. Посмотри по твоей же ссылке на поле private object <>t__stack.
Если твоя легковесная корутина будет содержать в себе другие корутины, то нужно эмулировать стек для их правильного обхода. И тут уже, извини, но без выделения памяти в куче — никак.

Здравствуйте, vdimas, Вы писали:

Вдогонку. Что насчет локальных переменных корутины? Где их хранить?

В примерах буста они хранятся в структуре-наследнике asio::coroutine.
А как будет выглядеть аналогичный объект с т.з. системы типов С++ в случае:

iterator<T> generate() resumable {
  int tmp = 1;
  yield return rand()*tmp++;
  yield return rand()*tmp++;
};

Где будет хранится локальная переменная tmp в твоём случае, т.е. когда iterator<> — это полностью value-type объект?

Здравствуйте, Ikemefula, Вы писали:

I>"Недетерминированный порядок исполнения двух задач"
I>Если непонятно — можешь рассматривать код выше как небольшой фрагмент применения зеленых потоков. Разницы абсолютно никакой. Все проблемы абсолютно одинаковы.

Опять двадцать пять.

V>>Например, даже любимый твой Майкрософт в доках пишет, что кооперативная многозадачность позволяется избегать лишних гонок и лишних же блокировок. Но у тебя как был затык в понимании "гонок", так и не рассосался до сих пор. И ведь не страшно же тебе на весь интернет так подставляться, не? )) С работы не уволят, случаем? ))

I>Микрософт говорит совсем про другое. См пример выше. Этот код задачи, таких в джаваскрипте можно запустить хоть тысячу за раз. Все они будут работать в одном потоке по правилам кооперативной многозадачности. Собтсвенно, ровно ничем не отличается от зеленых потоков.
I>Отсюда получаем тот самый "недетерминированый порядок"

Я вот уже близок, чтобы повторить тебе всё то, что было в той эпической дискуссии, на которую ты, на свою беду, постоянно ссылаешься. ))


I>Именно. Если твой объект используется из разных задач, что будет ? Если класс инкапсулирует всего лишь указатель на разделяемый ресурс ?
I>Инкапсуляция — во весь рост, изоляции — ноль.

Тем не менее, нам нужна лишь изоляция от конкурирующего доступа, т.е. изоляция от тех самых гонок. Если гонок нет, то "изоляция" соблюдается или нет?


I>Это не разрезание, а связывание. Задача состоит из кусков, которые, возможно, выполняются в разных потоках, или, например, задача прибита к эвентлупу.

Это лишь точка зрения на происходящее.
Понимаешь, в вытесняющей многозадачности АБСОЛЮТНО так же. Потому что все юзверские потоки — это логические потоки. Физические потоки — это процессоры/ядра/потоки_в_многопоточных_ядрах.

ОС может вытеснить твой логический поток, затем продолжить его выполнение из ДРУГОГО физического потока, так? Но при этом, хотя логический поток переползет на другой физический поток, ОС предоставляет нам гарантии, что никакой участок кода логического потока не будет будет выполнен одновременно. Чтобы одновременно выполнять некий участок кода, нам надо будет явным образом создать еще один логический поток уровня ОС. ))

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

Мне повторять пример из той давней дискуссии про то, как в случае такой кооперативной многозадачности мы порой можем обходиться без обкладывания кода критическими секциями? Или ты уже догадался, когда такое возможно?

Ну вот включи воображение, представь, что у тебя есть два пользовательских потока (назовём их корутины), которые обслуживаются только одним потоком ОС. Эти две корутины делят м/у собой некую очередь, одна корутина что-то кладет в очередь и вызывает yield, вторая корутина забирает что-то из очереди и, когда очередь пуста, тоже вызывает yield. Нужно ли нам для этого сценария защищать такую очередь с помощью критической секции или нет?

(сорри, но если опять не осилишь... ну ты понял)


V>>И все это с единственной целью — уйти от вытесняющей ядерной многозадачности в сторону кооперативной юзверской.
I>У тебя должен быть хороший ответ — как 1000 зеленых потоков смогут корректно работать с глобальным состоянием.

Зачем это мне? Это нужно твоему жабаскрипту, а так же Lisp, Scheme и вообще всем тем языкам, которые оперируют "контекстом".
Т.е., в твоём жабаскрипте на любой вызов любой ф-ии или лямбды всегда неявно протаскивается некий "контекст". Эти контексты связаны друг с другом по цепочке вызовов и образуют т.н. связанную "область видимости" глобальных переменных и ф-ий (которые в жабаскрипте и в лиспе — тоже лишь "переменные", хранящие указатель на тело ф-ии). Т.е. фиг с ними, с переменными, но, блин, когда ф-ия представлена переменной — тот тут надо быть оч осторожным, не? ))

Собсно, чем мне не нравится жабасрипт — это тем, что без навыков отслеживать цепочку хотя бы из 3-х контекстов ты эффективно программировать не будешь. Именно поэтому жабаскрипт пестрит вот таким высмеянным сто раз синтаксисом:

    })
   })
  })
 })

Что это всё попытка "обрезать" зависимости от вышестоящего контекста.
И именно поэтому в жабаскрипте принято такое правило хорошего тона, что код библиотек, по возможности, вообще не определяет никаких глобальных ф-ий, все ф-ии (т.е. указатели на безымянные ф-ии) принято складывать в некий объект, который служит как АПИ библиотеки.

Потому что когда скрипт выполняет код, даже просто ОБЪЯВЛЯЮЩИЙ некую глобальную ф-ию, то он выделяет в том самом контексте-словаре ячейку для её хранения. Ну конечно, если несколько потоков будут оперировать одним и тем же контекстом, как же все они, несчастные, будут выделять одну и ту же ячейку для хранения адреса только что пережёванной интерпретатором ф-ии? ))

В С++ с этим проще, контекстом можно управлять явно (вызов метода объекта) или не использовать вовсе. Запросто можно отказаться от глобальных переменных, потому что глобальные ф-ии — это именно ф-ии, а не переменные, хранящие адрес ф-ии с возможностью этот адрес перезаписать.

Конечно, в многопоточных С++ программах глобальный контекст или не используют вовсе, или он представлен такими объектами, которые безопасны для конкурентного доступа из разных потоков. Это азы многопоточного программирования, собсно.

И конечно, многократно порицаемый оператор const позволяет сделать так, чтобы некий глобальный объект, безопасный для многопоточного использования, нельзя было перезаписать (как минимум без помощи хаков), потому что сама операция перезаписи разделяемой переменной не является потокобезопасной.

Здравствуйте, Ночной Смотрящий, Вы писали:

F>>дотнет на серваках держать не хочется
НС>Твои фобии, уж извини, не аргумент ни разу.

главное, поскипал причины, а теперь говорит о фобиях.

НС>А если распределенность не нужна?
НС>Ага, значит все таки нерешимых проблем нет.
НС>И что?

короче, хочешь заниматься демагогией — найди кого-нибудь другого.
иначе доставай линейку, договоримся о критериях и по-нормальному сравним.
дискуссия в стиле шеридан-мамут мне нахрен не упёрлась. я не поклонник "шоколадных удовольствий".

Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Но даже и в рамках concurrency у Erlang куча ограничений. Про проблемы с GUI, к примеру, Ikemefula уже писал.
НС>Так что, когда Мамут пытается тут нам рассказать, что ничего круче Ерланга нет, не указывая область применимости, то он, мягко говоря, не совсем прав. И главная проблема Ерланга именно что в весьма узкой области его применимости, а не в тонкостях работы VM.

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

Здравствуйте, vdimas, Вы писали:

V>Что значит "режется"? ))

То и значит. Кусок метода выделяется с возможностью его отдельного исполнения.

V>Происходит прерывание текущего логического потока

Не происходит никакого прерывания. И никакого логического потока тоже нет. Все происходит чисто статически, на этапе компиляции.

V>т.е. поток OS (worker из пула потоков) запускает следующую задачу из той самой СОБСТВЕННОЙ очереди.

Это совершенно необязательно. Даже в рамках TaskAwaiter и дефолтного шедулера. Посмотри, к примеру, на Task.Run или, на 5 с плюсом, на Task.Yield и подумай для чего они понадобились.

V> Т.е. тело асинхронного метода можно рассматривать как некий логический поток

Зачем его так рассмаривать?
Видишь ли, рассматривать его можно кучей разных способов. Например как continuation monad. Вопрос в том, что ты этими рассматриваниями хочешь получить.
Если же речь о сути происходящего, то никаких логических потоков и вызовов специального передающего управление API в коде async методов нет. А есть конструирование автомата.

V>Бенефит work stealing именно в том, что каждый worker не лезет в IOCP за следующей задачей

Господи, какая каша. IOCP вообще имеет отношение только ко вводу/выводу. Для очередей задач никакие IOCP не нужны вообще, в принципе. Что ты мешаешь все в одну кучу?
Work stealing нужен для ускорения работы в ситуации, когда у нас куча вычислительных fine grained задач и затраты на перекладывание задач по очередям начинают становиться заметны.
Если сделать общую очередь задач, то мы будем заметно терять на блокировках, так как полностью lock free для такой очереди не сделать (простой очереди, для которой lock free реализация имеется, недостаточно). Да и сам lock free отнюдь не бесплатен, даже с fast path алгоритмами и эвристиками — прокручивание цикла CAS на коллизиях это тоже работа, да и сам CAS опять же ощутимо дороже обычного свапа (особенно на на мультикоре) — memory barrier и все такое. Хуже того, чтобы обеспечить корректную работу на мультикоре и синглкоре, приходится еще и SpinWait.SpinOnce в цикл втыкать.
Поэтому TPL заводит по отдельной очереди на поток (по факту даже не заводит, очереди автоматично заводятся при добавлении, см. все тот же ConcurrentBag.cs), и покуда воркер кормится из этой очереди, то вероятность коллизии минимальна и алгоритмы быстро проскакивают по fast path.
Но наличие кучи очередей добавляет другую проблему — когда невыполненные задачи подходят к концу, то, из-за ошибок выравнивания (а такие ошибки всегда будут, коль скоро мы не можем предсказать общее количество и длительность исполнения задач) получается, что вот этот хвост выполнения будет плохо распараллелен. Поэтому, чтобы не допускать такого, простаивающие воркеры, пусть и с блокировками, начинают тырить задачи из чужих очередей с другого конца, освобождая перегруженные воркеры от лишней работы.
Так вот в какое место этой картины ты пытаешься впихнуть IO, IOCP и свои логические потоки — мне абсолютно неясно.
V>, а обрабатывает свою очередь до тех пор, пока она не пуста, потом пытается обработать очередь другого случайного потока, если она тоже не пуста. Т.е. только когда личные очереди потоков будут пусты, worker начинает слушать IOCP.

Нет там вообще никакого IOCP. На пустой очереди воркер висит используя Monitor. Внутри которого спинлоки и мьютексы. Но это мелкая деталь реализации. Притащив ее сюда, ты только еще больше все запутываешь.

НС>>Зависимость создается автоматически. И это по прежнему никакого отношения к work stealing не имеет.
V>Там происходят две вещи (в случае некоего await SomeAsyncMethod()):
V>1. запуск новой задачи (с сигнатурой Task<> SomeAsyncMethod());
V>2. создание зависимости от возвращенного Task;

Неа. Там все несколько запутаннее. Можно, к примеру, написать такой код (при наличии соотв. эвейтера) var data = await "Foo". И никаких Task тут нет. await использует свою собственную схему. А Task туда встраивается при помощи специального класса-адаптера — TaskAwaiter.

V>Причем, если на момент шага (2) случилось так, что Task, порожденный вызовом SomeAsyncMethod уже успел перейти в состояние resolved

Нет такого состояния.

V>В общем, в нейтивном варианте аналогичной либы PPL/task чуть другой механизм, там очередь обслуживает только через lock-free, а в ConcurrentBag.cs — через Monitor.Enter/Exit

Нет. Monitor.Enter/Exit используется только при work stealing. В остальных ситуациях там lock free.

V> и через спин-ожидание на поле list.m_currentOp (т.е. таки разновидность блокирующего мьютекса, только вместо ядерного примитива — просто спин).

Monitor тоже внутри на спинлоках построен.

НС>>В TPL тоже все сравнительно быстро. Но при чем здесь ожидание задач?
V>После того, как текущий async-метод прервется на await task, кто-то должен выполнить этот task. И это зависит уже от того, что происходит при порождении ожидаемого task. Если там асинхронный ввод-вывод на IOCP или просто некое действие, выполняемое по таймеру, привязанному к IOCP, то "кто-то" должен слушать IOCP.

Если кто то должен слушать IOCP, то Task практически сразу же завершится. И все это пройдет мимо системной механики TPL.

V>>>Э, нет. Не банально. Очередь специфическая, решает проблему ABA весьма остроумным способом. Скажу так, на этом сайте, когда шло активное обсуждение lock-free алгоритмов, этот способ никем не упоминался.
НС>>Какой способ? Локализация данных по потокам с целью уменьшения блокировок? Довольно стандартный прием.
V>Речь об ABA-проблеме в случае lock-free стека.

Нет такой проблемы в случае managed рантайма. Потому что нельзя получить другую ноду по идентичному указателю. Так что это персональный трах неуправляемого С++.

НС>>Это особенность реализации конкретных методов конкретного асинхронного API. Если у тебя задача чисто вычислительная, то и IOCP не нужен.
V>Ну так ты посмотри, как шедуллятся Task-и в TPL. ))

Я тебе уже сказал — через Monitor.

V>Как раз на глобальном пуле потоков, т.е. как раз Task-и верхнего уровня идут прямиком в IOCP.

Использование пула потоков не означает использования IOCP для собственной логики. Ты еще вспомни про свап-файл, он тоже внутри IOCP использует.

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

В TPL тоже можно. Пишешь свой шедулер и наслаждаешься.

V>Напомню, что дискуссия шла изначально о корутинах в C++, так вот, серьезной разницы с т.з. С++ кода м/у stackless и stackful корутинами нет и не будет.

Все зависит от степени абстракции. На каком то уровне и между дедушкой и бабушкой разницы нет. Только к чему эта софистика?

V> Но, как я вижу, одни коллеги готовы рассматривать stackful-корутину как логический вычислительный процесс, а stackless — нет. )) В дотнете async-методы — это stackless корутина, которую можно рассматривать как "линейный" вычислительный процесс. Ну а то, что там унутре автомат с состояниями или связь task-ов, порождающая граф вычислений — это уже дело десятое. ))

Я уже говорит — точно так же это можно рассматривать как continuation monad, и тоже много интересных теорий понапридумывать. Только это все полезно на этапе индукции. А вот когда речь идет о дедукции, то попытки жонглированием моделей что то обосновать становятся грубейшей демагогией.

V>Да я просто хотел обратить внимание коллеги, что work stealing хорошо работает только тогда, когда имеем большой трафик маленьких задач.

Да пофик на work stealing, что ты тут его так усиленно муссируешь? Просто один прием параллельного программирования. Там еще с десяток таких же накопать можно. не менее важных. Например локализацию блокировок по содержимому данных или использование массива флажков для разруливания в lock free гонок сразу по двум переменным. Разобрался с этим — молодец, но к данному обсуждению это никакого отношения не имеет.

Здравствуйте, neFormal, Вы писали:

F>короче, хочешь заниматься демагогией — найди кого-нибудь другого.

Демагогия, дорогой мой, это когда выдают что то типа этого:

у жавы проблемы с распределённостью. только akka вроде дала нужные плюшки. но это уже половина эрланга

Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Да тут дело даже не в лучшести. Для parallel computing Erlang просто не годится. А раз так, то то что пишет vdimas вообще не в тему, так как все эти work stealing и lock free важны строго для parallel computing.

Строго говоря, есть области, где требования к стоимости переключений "потоков" такие же, как в parallel computing. Т.е. есть задачи, работающие с low-latency IO (я упоминал специальные сетевые картейки и драйвера к ним, дающие порядка 2us медианы latency на пакет), но при этом же выполняющие обсчет сурьёзного входного трафика пакетов (а не просто их диспетчеризацию).

В этих областях практически невозможно провести четкую грань м/у "parallel computing" и "обычный concurrency", т.к. практически все требования к различным стадиям обработки данных являются идентичными.

Здравствуйте, vdimas, Вы писали:

V>Строго говоря, есть области, где требования к стоимости переключений "потоков" такие же, как в parallel computing. Т.е. есть задачи, работающие с low-latency IO (я упоминал специальные сетевые картейки и драйвера к ним, дающие порядка 2us медианы latency на пакет), но при этом же выполняющие обсчет сурьёзного входного трафика пакетов (а не просто их диспетчеризацию).

Неважно. Главное что Ерланг в этих областях вообще не применим.

Здравствуйте, vdimas, Вы писали:

I>>Если непонятно — можешь рассматривать код выше как небольшой фрагмент применения зеленых потоков. Разницы абсолютно никакой. Все проблемы абсолютно одинаковы.

V>Опять двадцать пять.

Нет аргумента.

Подумай еще над таким вариантом

Вот аналог бесконечного цикла, но асинхронного

logicalTask() {
    setTimeout(logicalTask, 5*1000);
   
    console.log('infinite loop is in progress...');
}

logicalTask();
logicalTask();
...
logicalTask();

// опаньки - однопоточный JS крутит N бесконечных задач одновременно

Надо ли объяснять, что ты можешь запустить хоть тысячу таких тасков и они будут работать по правилам кооперативной многозадачности ? Это ровно то же, что и зеленые потоки

Теперь сложнее, вводим глобальное состояние

logicalTask() {
    var i = yield readFile();
    var newI = yield modify(i);
        yield readFile(newI);
        async(logicalTask); // бесконечный цыкл, как и раньше
}
async(logicalTask);
async(logicalTask);
...
async(logicalTask);

//опаньки - порядок доступа к глобальному состоянию __недетерминирован__

Вот тебе и монады и проблемы с глобальным состоянием в однопоточном и, внимание, МНОГОЗАДАЧНОМ коде.

I>>Отсюда получаем тот самый "недетерминированый порядок"

V>Я вот уже близок, чтобы повторить тебе всё то, что было в той эпической дискуссии, на которую ты, на свою беду, постоянно ссылаешься. ))

Нет аргумента. Если есть чего сказать — скажи это кодом.

I>>Именно. Если твой объект используется из разных задач, что будет ? Если класс инкапсулирует всего лишь указатель на разделяемый ресурс ?
I>>Инкапсуляция — во весь рост, изоляции — ноль.

V>Тем не менее, нам нужна лишь изоляция от конкурирующего доступа, т.е. изоляция от тех самых гонок. Если гонок нет, то "изоляция" соблюдается или нет?

Ты получил ответ, что же такое гонки ?
Ты согласен с формулировкой ?
Ты видишь потенциальные гонки в моем коде ?

I>>Это не разрезание, а связывание. Задача состоит из кусков, которые, возможно, выполняются в разных потоках, или, например, задача прибита к эвентлупу.

V>Это лишь точка зрения на происходящее.

Покажи, как 'разрезать' задачу, которая есть N некоторых событий от пользователя. По моему — эвенты надо связывать.

V>Чтобы одновременно выполнять некий участок кода, нам надо будет явным образом создать еще один логический поток уровня ОС. ))

Неверно. ОС ничего не знает про зеленые потоки, а они, между прочим, выполняются по правилам кооперативной многозадачности. Логически — одновременно.

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

После того, как задача разделена на части, её нужно правильно связать, для обеспечения корректного control flow.

V>Мне повторять пример из той давней дискуссии про то, как в случае такой кооперативной многозадачности мы порой можем обходиться без обкладывания кода критическими секциями? Или ты уже догадался, когда такое возможно?

Ключевое слово — 'порой'. Я привел пример, где это невозможно.

V>Ну вот включи воображение, представь, что у тебя

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

V>Т.е., в твоём жабаскрипте на любой вызов любой ф-ии или лямбды всегда неявно протаскивается некий "контекст". Эти контексты связаны друг с другом по цепочке вызовов и образуют т.н. связанную "область видимости" глобальных переменных и ф-ий (которые в жабаскрипте и в лиспе — тоже лишь "переменные", хранящие указатель на тело ф-ии). Т.е. фиг с ними, с переменными, но, блин, когда ф-ия представлена переменной — тот тут надо быть оч осторожным, не? ))

Не имеет значения, функция, переменная или база данных. Главное что есть недетерминированый порядок выполнения.

V>Собсно, чем мне не нравится жабасрипт — это тем, что без навыков отслеживать цепочку хотя бы из 3-х контекстов ты эффективно программировать не будешь. Именно поэтому жабаскрипт пестрит вот таким высмеянным сто раз синтаксисом:
V>

V>    })
V>   })
V>  })
V> })
V>

Смотри внимательно мои примеры кода — это, внимание, асинхронный JS ! И там нет того, о чем ты говоришь.

V>Что это всё попытка "обрезать" зависимости от вышестоящего контекста.

Ты ушел в сторону. От тебя не было ответов про недетерминированый порядок выполнения.

V>Потому что когда скрипт выполняет код, даже просто ОБЪЯВЛЯЮЩИЙ некую глобальную ф-ию

Давай представим, для простоты, что глобальный ресурс это файл.

Вобщем, все что не по теме, я скипнул.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>собственно, для этого достаточно все обращения к ОС заменять на обёртки, которые умеют кооперироваться с ВМ/рантаймом. преркасно реализуется что в C++ (как раз Asynca это и делает), что в ghc из коробки

Сорри, а можно ссылку на Asynca?..
а то в гугле несколько страниц нерелеванта выпадает на запрос.

Здравствуйте, BulatZiganshin, Вы писали:

BZ>ты похоже видишь единственный вариант решения этой проблемы — разбить работу на мноджество небольших задач. а можно сделать горажо проще — исользовать короутины, вставить yield в тех же самых местах и при этом сохранить состояние стека.

Это да. Только без поддержки языка это сложновато. ))
Если корутина не вложена в другую, еще куда ни шло, можно выкрутиться, но когда они вызывают друг друга, то лучше со всем этим пусть компилятор разгребается.

Здравствуйте, Ночной Смотрящий, Вы писали:

F>>короче, хочешь заниматься демагогией — найди кого-нибудь другого.
НС>Демагогия, дорогой мой

короче, дорогой, ты готов определить критерии сравнения и определить профиты разных технологий в согласованном списке задач?
если хочешь поупражняться в словесности, то я тебя развлекать не готов.
мне лично глубоко насрать на то, кто/что победит. меня волнуют только факты. в особенности по тем технологиям, которые я не трогал.

Здравствуйте, vdimas, Вы писали:

BZ>>ты похоже видишь единственный вариант решения этой проблемы — разбить работу на мноджество небольших задач. а можно сделать горажо проще — исользовать короутины, вставить yield в тех же самых местах и при этом сохранить состояние стека.

V>Это да. Только без поддержки языка это сложновато. ))
V>Если корутина не вложена в другую, еще куда ни шло, можно выкрутиться, но когда они вызывают друг друга, то лучше со всем этим пусть компилятор разгребается.

Ужос, а еще недавно ты говорил "Но уже есть готовые реализации. Дело в их популяризации." А теперь уже "пусть компилятор разгребается"

Здравствуйте, vdimas, Вы писали:

BZ>>собственно, для этого достаточно все обращения к ОС заменять на обёртки, которые умеют кооперироваться с ВМ/рантаймом. преркасно реализуется что в C++ (как раз Asynca это и делает), что в ghc из коробки

V>Сорри, а можно ссылку на Asynca?..

Вероятно, речь идет о Synca, разрабатывает которую спец из Яндекса, Григорий Демченко.
Об этой разработке было две большие статьи на Хабре: Асинхронность: назад в будущее и Асинхронность 2: телепортация сквозь порталы.

Здравствуйте, neFormal, Вы писали:

F>короче, дорогой, ты готов определить критерии сравнения и определить профиты разных технологий в согласованном списке задач?

Я? Не я этот спор завел. Это ты должен сделать, если хочешь предметно спорить.

F>меня волнуют только факты. в особенности по тем технологиям, которые я не трогал.

Чего то не очень заметно, если честно.