Комментарии 117
Как всегда 90% времени занимает эпическая битва с борроучекером))
Ох, дофига всего комментировать, но то, что сходу бросается в глаза:
Если вы представите, что WakerSlot содержит ссылку на WakerList, то никогда не сможете создать &mut WakerList где-либо ещё, поскольку основное правило времени жизни в Rust гласит, что у вас может быть либо одна мутабельная ссылка, либо множество иммутабельных, но не то и другое одновременно.
Надеюсь, что такое всё же возможно, и кто-нибудь напишет об этом в комментариях.
Это же в точности std::marker::PhantomData?
use std::marker::PhantomData;
#[derive(Debug)]
struct WakerList;
struct WakerSlot<'a> {
_phantom: PhantomData<&'a mut WakerList>,
}
impl<'a> WakerSlot<'a> {
fn new(_reference: &'a mut WakerList) -> Self {
WakerSlot { _phantom: PhantomData }
}
}
fn main() {
let mut data = WakerList{};
let slot = WakerSlot::new(&mut data);
let another_ref = &mut data;
println!("{:?}", another_ref);
}
С чего бы оно phantom-то?
PhantomData не позволяет как-то сделать множество мутабельных ссылок. В main() важна только сигнатура new(), которая гласит «захватывает мутабельную ссылку и возвращает объект с временем жизни не больше чем эта ссылка». Ну и ссылка будет захвачена до тех пор, пока живёт этот объект. Сам объект или функция new() тут уже никак не анализируется.
Пример работает потому что первая ссылка (slot) из-за non lexical lifetimes уничтожается раньше конца блока, чтобы не допустить нарушения правила. Если попытаться её всё-таки заставить существовать одновременно с another_ref, то всё рассыпается: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=e10d0e0640175ff2f74aace396915ecd
Просто для протокола
void foo(int* p, const int* q) {Ключевое слово
constздесь «бессмысленно» в том плане, что не препятствует возможному изменению указателя, поэтому компилятор не может произвести на основе этого оптимизацию.
ну так тогда надо
void foo(int* p, const int* const q) {пожалуйста, постоянный указатель на постоянные данные.
Мне не нравится термин "постоянные данные". const запрещает их менять через этот указатель. Но их могут в любой момент поменять через другой.
так данные тут и не должны быть постоянные, неизменяемый тут только указатель на данные, т.е. адрес
Ну тогда постоянные данные могут быть только в ROM.
Это если этот другой смогут создать. Если бы язык запрещал создавать изменяемые указатели на постоянные данные, то этому указателю взяться было бы неоткуда. Но С не запрещает...
Вообще, в сигнатурах функций традиционно есть некоторая двойственность, какие гарантии дают типы. Это гарантии для вызывающего кода или вызываемого? Исторически сложилось, что и для тех и тех, на когда компиляторы стали работать не по наитию, а более формально, внезапно выяснилось, что гарантии нужны разные. В данном примере * const это гарантия вызывающему коду, что функция не собирается менять данные по указателю.
. В данном примере
* constэто гарантия вызывающему коду, что функция не собирается менять данные по указателю.
это не гарантия, а соглашение,
так-то код внутри может почти что угодно с этим указателем сделать. Просто мы предполагаем что автор либы с функцией такой сигнатуры делать этого не будет :)
Это стандарт языка, на который полагается компилятор при оптимизациях.
А если следовать вашей логике - и AI32 architecture тоже соглашение (вдруг космические лучи создадут наводку в транзисторе?). Извращённая логика получается.
если писать простой код - то все всегда норм.
а если писать сложный код, много кода и много лет, то чего только не повидаешь - и баги библиотек и баги компилятора и баги железа (и откровенное вредительство некоторых авторов). И космические лучи (или наводки от всяких излучателей).
На практике нас крайне интересуют две вещи:
- модульность (позволяет сосредоточиться на своей части работы не делая чужую, позволяет использовать "бинарный поиск" для нахождения ошибок);
- частота ошибок (позволяет искать ошибки эффективно - в первую очередь там, где они более вероятны).
И ваш подход "снандарт языка - это соглашение" - ухудшает работу, т.к. затрудняет использование плюсов обоих этих вещей.
Для примера - сколько раз в жизни вы на практике сталкивались с ошибками в stable-version gcc \ clang \ icc (приведите любую из них)?
непонятно - что ва так возбудило? против чего вы негодуете?
1) в стабильных версиях чего-угодно - практически нет багов. (только known issues) А во всяких пре-релизах - только так. На поддержке старого - вы будете спокойно писать код.
А если вы игродел и вам дали коробочку "это инженерный вариант следующего ифона" - то там чего только не отломают.
2) просто помните: если у вас все написано средствами языка - то там будет как написано в декларации. А вот если у вас FFI или вставки ассемблера (растовский unsafe) - то обязательно напишите тест, который сломается если что-то пойдет не так.
Или вы не любите тесты а любите параноить, принудительно обкладывая все подозрительные места на переполнения, изменения констант и прочие исключительные случаи ?
Моё утверждение - очень полезно понимать, вот эти вот гарантии, какой статус они имеют, и насколько велика вероятность что они сломаны (тобой или не тобой).
В ваших краевых случаях - стандарт всё равно остаётся стандартом, но вероятность, что он будет сломан, существенно повышается.
непонятно - что ва так возбудило(1)? против чего вы негодуете?
Или вы не любите тесты а любите параноить(2), принудительно обкладывая все подозрительные места на переполнения
Пожалуйста не переходите на личности(1) и не используйте демагогический приём соломенное чучело (2) - в технической дискуссии это некрасиво.
И зачем второй коммент подряд вы пытаетесь без приглашения меряться длиной и толщиной опыта? (доводилось писать и компилятор и симулятор под разрабатываемую архитектуру и модели многопоточности).
И во всех случаях было крайне полезно отличать стандарт от соглашений, а также модель(и ошибки модели) от имплементации модели (и ошибок имплементации).
Теперь по вашим примерам - кажется, что вы смешали сильно разные случаи в одну кучу:
- Ниженерный вариант смартфона - corner case;
- Rust unsafe - довольно edge case: как для core-team(судя по старым ошибкам с зацикливанием владения при инициализации) так и для пользователей;
- Асм-вставки - стандартный инструмент при низкоуровневой разработке и ожидать, что скажем в gcc он будет сломан дольше пары недель крайне странно;
- FFI (хотя непосредственно с ним работать не доводилось) - либо при наличии OBI стандарт либо если всё держится на честном слове вендора обкладывается тестами;
странно, я опытом и не пытался меряться, если мои воспоминания кого-то угнетают - можете не переживать, я ко всем отношусь одинаково "на вы" вне зависимости их возраста.
И тем более я не считаю себя непогрешимым светочем :D , я работал с людьми которые гораздо умнее меня.
Это стандарт языка, на который полагается компилятор при оптимизациях.
1) возможно что это не было понятно, но - я абсолютно согласен с утверждением выше.
2) на этот стандарт полагается и человек. Просто человек должен быть умнее компилятора - если "вдруг что-то пошло не так", то чтобы помнить об этом всём (и ценить OSS :D а не готовые бинарники)
1) возможно что это не было понятно, но - я абсолютно согласен с утверждением выше.
Ну так проблема в том, что изначальная фраза "стандарт это не гарантия, а соглашение" - куда больше вредит, чем помогает.
Это стандарт языка, на который полагается компилятор при оптимизациях.
стандарт это не гарантия, а соглашение
оба этих утверждения истинны
куда больше вредит, чем помогает.
знание того, что оба утверждения сверху истинны - могут "повредить" некоторым людям при написании кода, но помогают при отладке и поиске багов, не так ли ?
Содержательно - нет.
Corner case (а все ваши примеры в той или иной мере corner case ) - следует описывать только после того, как основной случай описан и понят достаточно хорошо.
Наша цель - построить конечную модель бесконечного количества знаний.
Для этого более важные утверждения должны попасть в модель раньше менее важных.
Поэтому приведённая вами модель - плохая она куда больше сбивает с толку, чем помогает.
Это стандарт языка, на который полагается компилятор при оптимизациях.
стандарт это не гарантия, а соглашение
Хорошая модель (из 2 фраз) была что-то типа:
Это стандарт языка, на который полагается компилятор при оптимизациях.
Стандарт - это гарантия, пока нет явных оснований считать по-другому.
Мне не нравится термин "постоянные данные". const запрещает их менять через этот указатель.
Так это и есть соглашение для С. Постоянный указатель на постоянные данные означает лишь, что значение указателя и данные на которые он указывает на будут меняться через этот указатель, ни более, но и не менее.
В итоге получилось быстрее и надежнее, чем если бы было написано на том же C#? Ну или в сравнении с простым C?
Примечание: это мог быть баг MIRI, или с тех пор правила были смягчены
Это совершенно точно баг в MIRI, потому что Rust разрешает заимствовать &mut-ссылку как разделяемую, а значит и через указатель делать то же самое вполне допустимо.
Эта статья - наглядная иллюстрация того, почему весь софт на расте либо переписан с Си, либо имеет кучу сишных зависимостей, которые и выполняют основную работу.
Собственно как и на любом другом ЯП включая С.
В этом и есть киллер фича rust совместимость с C.
Одна из двух.
1) контроль ссылочной целостности без использования сборщика мусора на этапе компиляции;
2) компилируемый код совместимый с С настолько, что в проекте могут быть куски кода на C.
Смелое утверждение: "весь софт на расте" = "100% софта на расте" = "для любого софта на расте верно". Но это, разумеется не правда. Правда, это утверждение "существует софт на расте, для которого верно". Но оно не такое красочное получается)
Очень смелое утверждение. За 2 года программирования на Rust такое встречал только с библиотеками к БД.
А ведь можно было сделать wait-free очередь безо всяких самореферентных структур, мьютексов, CAS-ов и прочих сложностей.. Нужны лишь барьеры памяти.
не-не-не, это слишком просто.
Какие же будут описания героической борьбы с растом, преодоление и эпическое свершение?
И что эта картинка означает? Вы привели ее под вашим утверждением, но я не вижу, каким образом она его иллюстрирует.
верхний ряд - это как сделать из очереди 1-к-1, очередь много-к-много.
нижний ряд, слева - это скорее всего логическое описание АПИ очереди как буфера в памяти (тут я могу ошибаться, я не автор картинки :) )
нижний ряд, справа "простой советский" кольцевой буфер как пример "очереди 1-к-1",
В нем отправитель и получатель оперируют фиксированным (обычно кратное степени 2) куском памяти и двумя индексами.
Никаких локов, только атомарное чтение/запись (или простой volatile если индекс вмещается в регистр) и барьер (чтобы оптимизатор чтение/запись в индексы не трогал).
Если у вас фиксированный известный размер данных - то их можно прямо в этом буфере размещать (чтобы не париться менеджером памяти вообще). Если нефиксированный - то передавайте указатели. Владение указателем и данными - на самом буфере (если это не так - то проще честно скопировать и отдать в очередь указатель на копию), так что время жизни данных понять легко что с растом, что без.
Ну, только с кольцевым буфером что-то понятно, остальное все равно туманно. Почему в Input стрелки заходят, а из Output выходят? Что стрелки вообще значат? Явно не поток данных, иначе было бы наоборот.
сделать из очереди 1-к-1, очередь много-к-много.
При этой на картинке оба конца "много" смотрят во внутрь структуры, т.е. это что-то, спрятанное внутри? А наружу торчат конца "1"? При этом внутри "1-to-1", значит, мы на ее основе получили что-то, что тоже "1-к-1"? Что вообще значит "очередь много-к-много"? Очередь с несколькими головами и несколькими хвостами? Так вообще бывает (если и бывает, разве это очередь?)?
1) стрелки обозначают поток данных - от писателя к читателю.
Почему в Input стрелки заходят, а из Output выходят?
потому что "внутренний потребитель" - это внешний чей-то Input, мы ему в его Input отправляем наши данные
(а "внутренний производитель" - это внешний Output, т.е. мы у кого-то из его Output к себе забираем данные).
2) у очереди может быть те, кто в нее пишут, и те кто из нее читают.
Или если не в терминах "пассивной очереди", а в терминах "активной очереди-актора", очередь может забрать данные у писателя и отдать читателю.
ПРИМЕР
можно представить себе очередь как ассистента книжной лавки, который принимает книжку у человека-писателя и потом отдает ее человеку-читателю.
Т.к. он активный, то это не просто полка (или там конвейер), он может делать какие-то дополнительные действия во время получения/выдачи каждой книжки или прихода/ухода читателей и писателей.
Что вообще значит "очередь много-к-много"?
это когда есть много писателей и читателей у этой конкретной очереди.
ПРИМЕР1: для очереди 1-к-многим
вы писатель и ваши книжки хочет читать множество читателей,
вы им говорите "ходите в эту книжную лавку - я потдаю все мои книжки туда".
Они добавляют себя в эту лавку как читатели, и каждый раз когда вы даете новую книжку в книжную лавку, ассистент смотрит в свой список читателей, и потом
* может посылать им всем сигнал "есть книжка! приходите!"
* каждому пришедшему делает копию вашей книжки.
ЗАМЕТЬТЕ, что писатель не знает списка читателей и не парится им вообще, он только отдает книжу и всё. Добавление/удаление читателей, их оповещение и т.д. - это забота книжной лавки (то есть очереди).
ПРИМЕР2: для очереди многие-к-многим
вас таких писателей много, и вы все в принципе пишете об одном и том же. Поэтому вы все записываетесь в писатели одной книжной лавки, чтобы все могли вас читать в одном месте.
ЗАМЕТЬТЕ, что читатели не знают списка писателей, они только читают все книжки из этой лавки.
остальные примеры (много-к-1, вырожденные случаи "когда нет читателей/писателей", блокировки, переполнение, гарантирование доставки и т.д. - это уже можно дальше самостоятельно)
3)
Так вообще бывает (если и бывает, разве это очередь?)?
например очередь сообщений об ошибках.
Все туда пишут (вот прямо вообще все, без разбору), и вы назначаете ей три читателя: один читатель, который пишет все в файл, второй - перекидывает на удаленный сервер, а третий читатель выводин на консоль.
Удобно же?
Все туда пишут (вот прямо вообще все, без разбору), и вы назначаете ей три читателя: один читатель, который пишет все в файл, второй - перекидывает на удаленный сервер, а третий читатель выводин на консоль.
Только это broadcast очередь, а не mpmc. Если будет mpmc, то часть ошибок будет только в консоле, часть ошибок только в файле и часть ошибок только на сервере.
По сути своей, mpmc имеет смысл только для равноправных читателей (которые делают одно и то же). Поэтому весьма редкий зверь.
Почти, только внизу слева показаны потоки данных, а справа пример состояния курсоров, на основе которых каждый участник понимает сколько может прочитать/записать.
Output выходной канал, в него пишут. Input - входной, из него читают.
Размер очереди имеет смысл задавать кратным странице памяти, чтобы минимизировать фрагментацию. А курсоры располагать в разных кеш линиях, чтобы одновременные записи двух ядер не мешали друг другу.
Атомарная запись тут не требуется - достаточно барьерами упорядочить операции с буфером и с курсом. При записи сначала пишем в свободный слот, потом смещаем курсор писателя. При чтении читаем данные, потом смещаем курсор читателя. Чтение курсоров упорядочивать тоже нет необходимости.
Каждый канал хранит список таких вот очередей с которыми работает по какой либо стратегии: раунд Робин, по приоритету, по наполненности.
Тут есть пример кода.
Атомарная запись тут не требуется -
обычно не требуется, т.к. всё помещается в 1 регистр и пишется за 1 такт.
Но если не помещается (или не пишется), то могут быть случаи, что читатель видит только половину обновления (и кто-то увидит после ffff не 0000, а ff00 или 00ff, что грустновато).
А то что это будут нечастые случаи - это будет дополнительное волшебство.
---
в остальном абсолютно согласен👍
(разве что если начинается тема с "линейками кеша", то уже надо тогда привязываться к процессору и его ядрам, это уже совсем низкоуровнево ИМХО)
Совсем не требуется, ибо изменение курсора всегда атомарно, а данные из буфера не читаются пока курсор не сдвинут.
А пример кода тут.
Присваивание атомарно только на x86-64, но на ARM-е все сложнее. Вот здесь хороший обзор: https://marabos.nl/atomics/hardware.html
Даже на арме запись машинного слова в память атомарна. А по ссылке речь про атомарность транзакций из нескольких инструкций.
non-temporal store инструкции обычно даже не генерируются компиляторами, так что про "прямую" запись в память я даже не говорю. Разговор про запись в кэш процессора и его инвалидацию, и чтение данных другими ядрами процессора (а еще есть совместные кэши в hyperthreading, а NUMA nodes это вообще туши свет). Для согласования всего этого безобразия и нужны полноценные атомарные операции.
Ну вот читатель сдвинул курсор в заполненном кольцевом буфере, но еще не забрал сообщение. Тут приходит писатель, видит, что место свободно (читатель уже сдвинул курсор) и пишет туда новое сообщение. Чем тут помогает атомарность изменения курсора?
Тут помогают барьеры памяти. Видимо, я забыл упомянуть о них в первом же сообщении.
Все равно, непонятно, чем поможет барьер. Куда его вставить? По вашему описанию можно предположить:
читатель меняет курсор
барьер
читатель читает ячейку, на которую раньше указывал курсор
Чем это мешает писателю? Что мешает ему переписать данные в ячейке до того, как читатель прочитает их? Вот если бы читатель сначала читал ячейку, а потом двигал курсор, писатель бы видел, что ячейка еще занята и писать туда нельзя. Но в этом случае другие читатели могут успеть сдвинуть курсор и первый читатель прочитает не те данные, на которые курсор указывал. А в худшем случае писатель уже будет видеть эту ячейку, как свободную и что-то туда запишет.
Output выходной канал, в него пишут. Input - входной, из него читают.
Тогда, если на всех диаграммах, кроме кольцевого буфера (внизу справа), стрелки -- это потоки данных, то:
верхняя картинка противоречит этому утверждению
внизу слева вообще непонятно, стрелки двунаправленные
Не противоречит. Вас же не смущает, что в терминал данные поступают из cout потока, а из терминала приходят в cin?
Что не понятного в двустороннем обмене данными?
Смущает. Если мы рассматриваем картину с точки зрения программы, то очень даже бы смущало, если бы мы читали из потока вывода. Насчет терминала -- никогда не слышал, чтобы говорили "поступает в терминал". Обычно говорят "выводится на терминал" и "вводится с терминала", "поступает с терминала". "Выводится" -- "
cout", "вводится" -- "cin", все логично.Зачем тогда их называть Input и Output, если и то, и то выступает и как вход, и как выход? Почему вы назвали одно Input, а другое Output, если работают они одинаково? В чем отличие? Если уж назвали по разному, значит хотели этим что-то подчеркнуть? Что?
В общем, чтобы не гадать, напишите уже, что означают описанные картинки и как они доказывают отсутствие необходимости в мьютексах, CAS-ах и прочих сложностях.
https://habr.com/ru/companies/ruvds/articles/858246/#comment_27562096
вот тут я расписал про верхний ряд рисунка.
более подробное пояснение:
1) вот у нас 1 насос, у него есть вход и выход
2) если мы соединим 2 насоса, то видно что выход одного - это вход другого (привет многоножка!):
теперь, если эти два насоса положим в коробку, то получится, что у нас 1 большой насос,
и его выход которого можно соединить в входом чего-то другого
или его вход можно сосединить с чьим-то выходом.
а стрелочки все время показывают - куда течет вода.
вот так и с очередями (только вместо воды - данные)
2) их правильно назвали, просто неявно обозначили.
Напишите "очередь_А" , "очередь_B" "очередь_C" и тогда можно будет понять что
A-> Output_A ->connect-> Input_B ->B -> Output_B ->connect-> Input_C -> C
верхний ряд - это как сделать из очереди 1-к-1, очередь много-к-много.
И сразу нет.
Это как сделать из очередей 1:M + M:1 - очередь M:M.
Но проблема в том, что она вообще никак не избавляет от необходимости множественного mut-владения \ mut-ссылок.
если у вас есть очередь 1-к-1
то очередь 1-к-М делается при помощи назначения каждому потребителю своей отдельной очереди 1-к-1,
а очередь М-к-1 делается при помощи назначения каждому писателю своей очереди 1-к-1.
вот так из очереди 1-к-1 можно сделать и очередь М-к-М, просто таких очередей 1-к-1 будет не одна штука %)
если у вас есть очередь 1-к-1
то очередь 1-к-М делается при помощи назначения каждому потребителю своей отдельной очереди 1-к-1,
На рисунке (1) 2 очереди 1-1
На рисунке (2) очерещь 2-1.
Вы утверждаете, что из рисунка (1) можете сделать рисунок(2) без дополнительных фокусо? Как?
1) почему "mut-владения \ mut-ссылок" не может быть назначено очереди?
Т.е. писатель создает свою "mut-ссылку", посылает ее в очередь и тем самым передает владение ей? А потом читатель при чтении из очереди - полчает владение "mut-ссылки" себе?
2) по рисунку:
а) если нет отдельного потока для м-к-1-очереди, чтение делается на потоке читателя: тогда при каждом приходе читателя за данными, функция чтения-из-м-к-1-очереди, внутри проходит по 1-к-1-очередям писателей и перекладывает все их сообщения в 1-к-1-очередь читателя, после чего возвращает читателю либо следующее сообщение из его 1-к-1-очереди, либо "ничего нет"
б) если есть отдельный поток для м-к-1-очереди, то м-к-1-очередь на своем потоке ходит по 1-к-1-очередям писателей и перекладывает в 1-к-1-очередь читателя, а потом функция чтения-из-м-к-1-очереди, возвращает читателю либо следующее сообщение из его 1-к-1-очереди, либо "ничего нет" .
Если у вас чтение с блокировкой, то у 1-к-1-очередей писателей будут [Waker/callback/Promise и тд способы выполнения кода на нужном потоке], которые они будут дергать при записи в свои 1-к-1-осереди, после чего это будет вызывать логику а) или б) выше.
(заметим, что в случае б - у 1-к-1-очереди читателя будет свой [Waker/callback/Promise и тд] только если читатель заблокировался на пустой 1-к-1-очереди. Если в его 1-к-1-очереди уже есть данные - то потоку м-к-1-очереди достаточно просто дописывать новые данные в 1-к-1-очередь)
В изначальных картинках (nin-jin) очередь 1:1 помогает примерно как топор в сказке "каша из топора".
Т.е. что синхронизацию поверх M:M писать что превращать (1:1) - (1:M) - (M:1) - (1:1) - примерно одного уровня проблемы. Как я понял вы явно стали защищать позицию "1:1" очень полезный примитив - ИМХО нет.
=================================================
Разумеется такую очередь lock-free построить можно (на ll-sc прям влёт, на CAS ну запакуем два 32-битных значения в 64-битное).
Однако она встаёт против BorrowChecker, который слишком консервативен.
В итоге у вас получается либо Lock, либо Waker либо unsafe. И тут наличие 1:1 очереди крайне мало помогает.
ну, я вообще не растовод, я страдания с BorrowChecker-ом читаю с попокрном в руках.
ИМХО "простая + работающая в многопоточности очередь 1:1" - этот как кирпичик лего. Она сокращает время написания и отладки всего остального.
Как там будет всё остальное у М:М (или М:1) - это уже надо смотреть на архитектуру и ограничения, универсальная такая очередь - это будет "и жнец и швец и на дуде игрец"
Вы бы хоть почитали чем wait-free от lock-free отличается прежде чем причендалами меряться..
Вы бы хоть почитали чем wait-free от lock-free отличается прежде чем причендалами меряться..
Если есть что сказать на техническом уровне - говорите.
Если единственное ваше утверждение "вы бы хоть сделал Х" - лучше вообще молчать.
да ну, если люди делают через мутекс с ожиданием на нем - то какая уже разница искать такие отличия wait-free от lock-free? типа "чтобы знать тонкости теоретического счастья которого у них нет" ?
И что же ваша чудеснеая очередь будет делать-то при попытке прочитать из пустой очереди? Заблокироваться нельзя - она же wait-free. Усыпить сопрограмму нельзя - для этого требуется самореференсная структура...
Так не читайте из пустой очереди, займитесь чем то более осмысленным.
Это вообще как?
if( empty ) yield;
То есть если приложению ну вот совсем нет работы, оно будет грузить все ядра на 100% просто переключаясь между сопрограммами в цикле? Ну просто отличный план! (нет, не отличный)
Это решает планировщик задач. Можно сделать несколько циклов вхолостую, а потом уснуть не на долго или заблокироваться до наступления события или даже прибить воркер. Но во многих типах приложений всегда есть чем заняться.
Можно сделать несколько циклов вхолостую, а потом уснуть не на долго или заблокироваться до наступления события или даже прибить воркер.
Ну и как вы собрались блокироваться не используя Waker и не ведя список ожидающих разблокировки читателей?
Но во многих типах приложений всегда есть чем заняться.
Да, и чтобы не отбирать ресурсы у тех задач, которым есть чем заняться - те задачи, которым заняться нечем, должны быть заблокированы.
Вы не поверите, создаётся мьютекс, отсылается в очередь управляющего потока, после чего текущий воркер останавливается.
Это верно для многопоточного кода, автор же использует сопрограммы.
Странная дихотомия. А вы чего доказать-то пытаетесь?
даже многопоточный код не может запретить программисту сохранить указатель на коллбек, и потом вызывать его каждый раз, когда очередь непустая, на нужном потоке.
Это же можно делать и сопрограммами и без, и даже в однопоточном коде на других языках - я проверял, работает.
кстати, а расте же есть коллбеки ?
(а то вдруг я предлагаю нерабочие варианты ...)
даже многопоточный код не может запретить программисту сохранить указатель на коллбек
И архитектура сразу же усложняется.
Там, где был простой цикл чтения из очереди в сопрограмме до отмены, появился колбек, который должен породить сопрограмму, которая будет читать в цикле пока очередь не опустеет. И всё лишь потому, что nin-jin не понравились некоторые сложности реализации.
Я считаю, что перекладывать сложность с библиотечного кода (очереди) на вызывающий код - неправильно.
кстати, а расте же есть коллбеки ?
Есть, есть. Но код на async/await проще кода на колбеках, пусть и библиотечный код оказывается сложнее.
ну, не все уперлось в колбеки,
(они - альтернатива sleep / вариант реализации wakeup )
можно и без колбеков - если возвращать async и там пускай читатель опустошает уже с доступной скоростью.
...но ведь именно это автор и сделал? А ему тут говорят: "вот взяли бы wait-free очередь, не нужно было бы ничего делать"...
непонятно как одно отменяет другое
можно очередь сделать и с wait-free и с коллбеками, а можно без обоих.
Вопрос в скорости разработки / скорости работы.
Вот именно про это я и пишу. Непонятно как одно отменяет другое.
посмотрел в начало треда,
наверно у нас разное понимание фразы "не нужно ничего делать"
я хотел написать, что если делать через мутекс - то оно конечно безопасно, но расточительно вообще-то - создали поток (а ешл дескриптор небесплатный!), и он стоит тупит, ничего не делает.
А вот если сделать через "wait-free и с коллбеками (или аналогами)", то поток будет свободный и сможет сделать чего-то полезного, пока там читать нечего. (собственно для того их в пуле и держат)
Это ж сопрограммы. Нет никакого потока, который бы стоял и ничего не делал. Нет никакого системного дескриптора. Есть только Waker в списке WakerList. Который и является той самореференсной структурой, с которой боролся автор.
А вот если сделать через "wait-free и с коллбеками (или аналогами)", то поток будет свободный и сможет сделать чего-то полезного, пока там читать нечего. (собственно для того их в пуле и держат)
Вот именно так решение автора и работает - поток свободен и может сделать что-то полезное. Но чтобы он стал свободен - сопрограмма должна уснуть, а её Waker - быть добавлен в WakerList ожидающих сопрограмм.
Раста не знаю, поэтому всю статью осилить не смог. Но вопрос появился: откуда такое желание избежать аллокаций? Я не знаю, как в расте устроен внутренне вектор, но не думаю, что там аллокация происходит при каждом добавлении. Скорее всего используется типичный алгоритм - при исчерпании выделяется двойной объем от уже исчерпанного. Для большинства применений это очень даже не плохо. Если ваша библиотека позиционируется как "общего применения", то неплохо бы сравнить, чем ваша реализация реально лучше банальной на векторах ? Если же вы хотите обеспечить предсказуемость работы по времени, т е всегда одинаковое время добавления нового элемента в очередь, то боюсь это сложнее, чем описано в статье и действительно, лучше смотреть на лок-фри структуры, т к в них не будет зависимости от ОС и не будет переменной задержки. А просто заменять динамический массив на такой же динамический список - ну я видимо идеи не понял...
Ну и что, что он не будет перемешаться в памяти - Сейчас процессоры с этой задачей справляются весьма быстро. Я к тому, а то ли вы оптимизируете, что приносит максимум проблем?
Если беда в медленности аллокатора от ОС, так всегда можно заранее попросить выделить кусок памяти, что бы в ближайшие миллисекунду или в ближайший час к этому аллокатору не обращаться. Понятно, что сколько выделить, знает только конечный потребитель библиотеки. В этом случае ему нужно дать соответствующий рычаг.
Или это всë же задача ради "смотрите, а оно оказывается вот так может"? Из статьи не очень понятно, как ее воспринимать.
Или это всë же задача ради "смотрите, а оно оказывается вот так может"? Из статьи не очень понятно, как ее воспринимать.
я там в самом начале текста увидел "К сожалению, ни один из них не отвечает полноценно моим потребностям, поэтому я решил написать собственный канал мечты. "
и поэтому для меня этот код, это авторское "смотрите как я могу" :)
Здесь это не критично, но вообще аллоцирование очень мешает распараллеливанию. Начинают использоваться барьеры, мутексы и прочие дорогие вещи
Выделение памяти может вызвать syscall (зависит от менеджера памяти, но по умолчанию jemalloc встроенный в Rust его делает, если в существующих таблицах не хватает места), а это переключение контекста, которое достаточно долгое. Естественно, это заметно только в масштабах миллионов операций в секунду, или на слабых процессорах. Более того, учитывая что автор упомянул no-std, программа возможно вообще работает без ОС, тогда либо нужен либо свой менеджер памяти, либо отказаться от её выделения вообще.
Проблема с использованием вектора в том, что он уничтожается при пробуждении вектора (mem::take заберёт вектор, а взамен поставит пустой). Поэтому в рабочем режиме будут постоянно происходить аллокации вектора (каждый раз заново). Рассуждения про удвоение размера в таком случае неприменимы.
Это можно починить, если использовать метод drain. В таком случае, из вектора будут забраны все элементы, но оставлена сама аллокация памяти. Это предотвратит походы в аллокатор памяти в рабочем режиме. Тем не менее, данная схема страдает от утечек: если один раз у нас образовалась большая очередь, то память мы никогда уже не вернём. Такие утечки в канале общего назначения могут быть неприемлемы.
Собственно решение предложенное в статье, позволяет избежать аллокаций, а также избежать утечек в описанном выше смысле.
P.S. На мой вкус, выбор решения в статье не до конца обоснован. Выглядит так, будто просто взяли решение, которое использует tokio, без оглядки на то, почему.
Какие средства предохранени для небезопасного rust? :)
Получается, что в случае примитивной реализации мы будем раз за разом аллоцировать и освобождать память при отправке и получении в стабильном режиме, а это весьма приличный объём.
Это просто не так. Память будет выделяться при росте capacity, экспоненциально, и быстро выйдет на плато. Если известно разумное capacity с которого стоит начать, можно выделить под него сразу.
Более того, память из-под вектора не освобождается никогда, если специально не вызывать shrink_to_fit(), например.
Так что причина для всех остальных приключений выглядит надуманной.
Там же вроде объясняют, что выделенная память из вектора забирается (вот весь выделенный capacity), оставляя в нем capacity=0. Не вектор очищается путем установки length в 0, а весь указатель на storage отдается другому объекту. И когда нужно опять добавить данные в вектор, нужно создать новый storage
Речь про этот код?
fn send<T>(channel: &mut Channel<T>, value: T) {
channel.q.push_back(value);
let wakers = mem::take(&mut channel.waiting_for_elements);
// Примечание: здесь мьютексы освобождаются, перед пробуждением задач.
// Если не предусмотреть какой-то способ фильтрации, то придётся пробудить все промисы (futures), так как мы не знаем, какой из них попытается произвести очередной опрос, и есть ли вообще такой.
for waker in wakers {
waker.wake();
}
}
а там нет варианта делать двойной буфер?
т.е. пока один опустошается, второй заполняется, а потом просто меняются местами
(как рендеринг в графике)
Не вариант для multi-producer очереди.
почему же ?
В случае multi-producer очереди - каждый producer пишет в свой буфер, а у каждого consumer есть свой чистый буфер (ибо если он непустой - то пускай сначала его дочитает, а потом уже бегает в очередь).
так что если приходит consumer - то очередь свапает эти буфера у producer-a местами.
Скрытый текст
Это кстати решает вопрос с динамической длиной буфера - очередь может выступать псевдо-consumer-ом, и держать пул буферов, который можно использовать, если consumer еще не пришел, а данные терять не хочется.
ну, а если память ограничена - то значит просто брать из пула самый старый "полный" буфер и перетирать его новыми данными.
Вы запутались в потребителях и поставщиках, конкретно из этого буфера producer читает. Но да, схема выглядит рабочей... если забыть про необходимость отмены задач. Без отмены задач банальное чтение с тайм-аутом в цикле из пустой очереди будет приводить к утечке памяти, что не хорошо.
если забыть про необходимость отмены задач.
а чьих задач? писателя или читателя ?
Если читателя - то какая разница с какой скоростью он обрабатывает свой буфер сообщений.
Если писателя - то тут сложнее. Разве что добавить флаги
"писатель_начал_писать" (выставляется писателем)
и "сюда писать запрещено" (выставляется очередью/читателем)
если есть первый флаг - то читателю придется либо дожидаться последнего сообщения, либо отбрасывать его
а если еесть второй флаг - то писателю надо перестартовать запись. по идее - заметить такой флаг он может только в момент когда "обмен буферами" (простой CAS индекса) начался но незавершился, т.е. достаточно очень редко.
чтение с тайм-аутом в цикле из пустой очереди будет приводить к утечке памяти, что не хорошо.
непонятно как чтение из пустой очереди будет приводить к утечкам памяти.
Обмен пустыми буферами - никакой утечки памяти, чтение из собственного пустого буфера - тоже не должно быть учтечки памяти ...
Вообще-то любых, то тут речь о задачах-читателях, ждущих на пустой очереди.
Если читателя - то какая разница с какой скоростью он обрабатывает свой буфер сообщений.
Так он его не обрабатывает, он ждёт. И вот это ожидание может быть отменено по разным причинам. Кстати, вот вам ещё одна из них - читатель читает сразу из нескольких очередей (как на одной из картинок в комментариях выше), и в параллельной очереди пришло сообщение.
непонятно как чтение из пустой очереди будет приводить к утечкам памяти.
Что непонятного-то? Чтение из пустой очереди приводит к регистрации Waker в коллекции ожидающих читателей. Если отмена чтения не будет приводить к удалению из этой коллекции - коллекция пухнуть, а память - утекать.
Чтение из пустой очереди приводит к регистрации Waker в коллекции ожидающих читателей. Если отмена чтения не будет приводить к удалению из этой коллекции - коллекция пухнуть, а память - утекать.
хм, обычно есть подписка и отписка от получения сообщений.
Т.е. логика такая же как и с открытием/закрытием файла или какого-то ресурса - освободить перед вызовом деструктора (если это не было сделано раньше). Конечно очередь может отписать читателей сама (и удалить их Waker), но тогда нужно понять - когда сделать это(по таймауту?).
вот примерная схема, того что я предлагал выше по треду:
Скрытый текст
тут все буферы - это кольцевые лок-вейт-фри буферы.
буферы слева - на 2 сообщения (там лежат индексы буферов в пуле - куда писать producer-у)
буферы справа и по центру - это буферы для данных, они все одинакового размера.
читатели и писатели обозначены разным цветом:
бордовый - это пул буферов
синий - это писатели в очередь
зеленый - это сама очередь
бирюзовый - это читатели из очереди.
--
на данной диаграмме:
1) producer1 пишет в bufA,
если bufA заполнится, то он считает следующий индекс - и будет писать туда (т.е. в bufB, который сейчас пустой). В то время пока producer1 туда пишет, очередь зашлет индекс нового пустого буфера.
Таким образом - producer всегда будет иметь возможность писать свои данные.
2) если есть читатели (а их тут 2), то очередь может
а) перекладывать им данные в их буферы по одному
б) обменивать буферы (заполненный из пула - на внутренний читательский). При этом никакая память не выделяется и не освобождается.
Обратите внимание - что у каждого читателя единственный буфер.
Очередь обходит писателей и проч. логика, а вот читатель - читает только 1 свой буфер. Когда дочитал - то пусть вызывает очередь за данными.
Очередь сидит в своем потоке, у её Waker просыпается при вызове записи из любого писателя.
хм, обычно есть подписка и отписка от получения сообщений.
Ну да, а я о чём говорю? Есть отписка, которая случается регулярно. При отписке нужно удалить Waker из коллекции.
Из какой коллекции удаление дешевле (при правильной реализации, естественно) - из вектора или из двусвязного списка?
Конечно очередь может отписать читателей сама (и удалить их Waker), но тогда нужно понять - когда сделать это(по таймауту?).
Нет, в асинхронном Rust всё однозначно - отписка читателя происходит при отмене задачи чтения. А отмена задачи чтения происходит в деструкторе задачи.
В принципе, ничто не мешает взять и всё усложнить, но зачем?
Очередь сидит в своем потоке, у её Waker просыпается при вызове записи из любого писателя.
Создавать по потоку на очередь? Кто из нас тут всё переусложняет?
Вы всё ещё почему-то сосредоточены на реализации очереди, в то время как тема статьи - реализация WakerList.
Из какой коллекции удаление дешевле (при правильной реализации, естественно) - из вектора или из двусвязного списка?
если у вас нет приоритетов, этот список небольшой или у вас один поток владеет этим списком - то из вектора проще (перетереть удалямый элемент последним элементом, а потом уменьшить size),
но если вы хотите приоритеты, этот список длинный, и вы хотите чтобы его могли модифицировать параллельно куча потоков - тогда двусвязный лучше (при правильной реализации блокировок! :) )
если операции "внезапного удаления" редкие (а обычно просто удаляется элемент с какого-то конца) - то можно даже односвязный список использовать.
Создавать по потоку на очередь? Кто из нас тут всё переусложняет?
если очередь привязана к одному читателю или к писателю - тогда нет смысла делать отдельный поток (операции с ней можно делать в том же потоке, что и этот единственный читатель/писатель).
Но если это "общая шина данных", то логично сделать ее "актором" и выделить ей отдельный поток из пула.
Вы всё ещё почему-то сосредоточены на реализации очереди, в то время как тема статьи - реализация WakerList.
Так ведь реализация WakerList зависит от реализации очереди. Но ОК.
перетереть удалямый элемент последним элементом, а потом уменьшить size
Для этого его нужно сначала найти, а это операция с неконстантным временем.
если операции "внезапного удаления" редкие
Не настолько редкие как хотелось бы - банальное чтение из нескольких очередей (ради которого в том же go уж целый оператор сделали!) приводит к тому, что операции чтения отменяются постоянно.
Так ведь реализация WakerList зависит от реализации очереди. Но ОК.
А в чём зависимость? Нет, ну понятно что иногда коллекция вообще не нужна и достаточно Optional<Waker>. Но во всех остальных случаях архитектура сопрограмм накладывает на реализацию коллекции схожие требования.
Для этого его нужно сначала найти, а это операция с неконстантным временем.
хм, а рвзве у вас нет возможности сделать наследник от Waker (или обертку, чтобы ее передавать наружу при подписке), чтобы он хранил в себе ссылку на элемент коллекции (индекс вектора или ссылку на узел списка) ?
потому что если искать каждый раз заново - тогда это превращается в дерево (или подобные структуры).
ДА, еще вариант - помечать подписчиков по дате подписки + держать отдельный "список отписавшихся" и при выборе следующего читателя (т.е. "кого сейчас будем пробуждать") / периодически - удалять из списка подписки "всех старых и дохлых". Так что они конечно не сразу удалятся, но и утечек память не будет.
А в чём зависимость?
если на каждое сообщение снова вызывать Waker и передавать чтение по 1 элементу туда, а после завершения чтения - помещать Waker в обратно очередь ожидания, тогда да, зависимости от архитектуры очереди данных нет.
Нет, от Waker наследоваться нельзя, это ж токен планировщика сопрограмм, он не создаётся очередью. Однако, сделать обёртку вокруг него и правда можно - и автор сделал WakerSlot именно для этой цели.
В принципе, подход с хранением индекса элемента внутри WakerSlot будет работать, но зачем? Вам всё равно придётся хранить разделяемые ссылки на запиненный WakerSlot (иначе вы не сможете обновить индекс при перемещении элемента), и вы тем самым получите снова самореференсную структуру. Двусвязный список проще.
ДА, еще вариант - помечать подписчиков [...]
Вы сейчас назвали нечто на порядок более сложное, чем двусвязный список.
и вы тем самым получите снова самореференсную структуру
ну, это без вариантов.
Даже двусвязный список будет самореференсным - потому что он будет хранить ссылку на WakerSlot, которая хранит ссылку на узел двусвязного списка %)
Двусвязный список проще.
чтобы из двусвязного списка удалять элементы потоковобезопасно - там нужно будет потрудиться.
Небезопасный Rust сложнее C