Если вы часто пользуетесь variadic templates, то вы, скорее всего, настрадались с Prolog-подобным стилем работы со списками, где приходилось откусывать по одному элементу списка с начала или конца.
Видимо, кто-то из членов комитета спустя 15 лет после C++11, где variadic template появились, наконец-то воспользовался ими в полной мере и понял, что это не так удобно, как казалось. И снизошло озарение - индексы...
Вместе с индексированием мы получаем необычайно мощный инструмент для обобщённого программирования:
... который, судя по примеру, по мощности приближается к макросам.
В хорошем примере этот код был бы обложен ограничениями на типы аргументов функций foo и bar. Надеюсь, в тексте стандарта именно это и будет сделано, иначе все это превращается в макромагию
Точно так же - значение 65535 в такой интерпретации не является валидным для ushort_16.
Я понимаю, что где-то это удобно и пр. Но подобные assert'ы не способствуют пониманию для чего все это введено в стандарт, а наоборот - показывают, что писавший сам плохо понимает, для чего это употреблять не надо
Интересно, только у меня возникает впечатление, что комитет по стандартизации занимается во многом велосипедостроением, кое осуждается в обычной жизни?..
Разберем по порядку. Что подводит нас к новому атрибуту [[indeterminate]]. Если у нас есть неинициализированная переменная и есть функция, которая только пишет в переменную, то можно компилятору дать подсказку, что это не ошибочное поведение. Тогда значение из переменной не будут читать в функции
Тут следует продолжить так: "...и при развитии проекта, когда функция перед инициализацией этого аргумента будет проверять его значение, получим то же, что и было, но без ругани компилятора". Неужели не предусмотреть последствия своих действий сразу?..
мы в международной группе пришли к такой мысли: «А было бы неплохо выдавать произвольную диагностику и для =delete»
ИМХО, полезно,но является имитацией бурной деятельности комитета. То же самое можно написать в комментарии к строке, где может возникнуть ошибка, только еще более развернуто.
Эти методы при переполнениях операции возвращают максимальное/минимальное число, которое может содержать определённый тип данных. Проще всего понять на примере с unsigned short
Из этих примеров мне понятно одно: при таком вычитании значение 0 является невалидным для unsigned short. Кажется, в комитете сидят умные люди и должны понимать, что средствами диапазона [a, b] нельзя выразить признак, что значение X не входит в этот диапазон. То есть налицо новоприобретенный костыль, который будут выпиливать в C++29.
Свершилось! В C++26 добавили функции для работы с векторами и матрицами. Более того — новые функции работают с ExeсutionPolicy, так что можно заниматься многопоточными вычислениями функций линейной алгебры. Вся эта радость работает с std::mdspan и std::submdspan
Я вижу эту "радость" по-другому: вместо того, чтобы описывать матрицу, тензор и пр., мы описываем сначала как эта матрица хранится в памяти, а затем поверх этого нахлобучиваем view, как на это нужно смотреть. Странный способ... То есть мы намеренно выносим кишки (memory representation) наружу, хотя до этого комитет всячески убеждал нас не делать такого. ИМХО, эпический костыль...
Мне такой материал неизвестен. Есть многотомные описания для каждой модели процессора (не архитектуры, а фактически каждой модели), там есть всё, но в 10-ти томах
Спасибо за развернутый ответ, Евгений! Да, без dynamic allocation в C++ жизнь скушна, - без неё никуда. Поэтому изобретаешь свои велосипеды, но все std контейнеры сразу побоку (абстракция Allocator не работает хорошо). [На правах рекламы] Благо есть boost::intrusive, - по-моему, самая правильная идеологически библиотека контейнеров, она и спасает.
SObjectizer - очень интересный framework, слежу краем глаза лет 7 уже. Единственное, что я явно не увидел во всех пропагандистских (в хорошем смысле) статьях - что в нем насчет динамического распределения памяти?.. Для моей области применения это очень критично, - использование стандартных new/delete недопустимо (дает просадку перформанса до 20%, причем вне зависимости, что прикручиваешь в качестве системного аллокатора - tcmalloc, jemalloc и пр., разница только в незначительном различии процентов этой просадки). Поэтому либо преаллоцированные массивы, либо страничные thread-local субаллокаторы без блокировок (строго говоря, на fast path). Выпиливание new/delete из бибилиотек - вещь неблагодарная, зачастую невозможная (получится клон, новые версии применять невозможно). Предусмотрена ли в SObjectizer обертка над распределением памяти?..
Эмм… Мне помнится, эта ошибка уже была давно исправлена в статье, сейчас не вижу этого кода.
Вы точно уверены, что это привет из 2020 года, а не из 2013?.. ;-)
Да, согласен.
Иерархические hazard pointer'ы практически не поддерживаются, так как от строгой древовидной иерархии очень просто случайно перейти к циклическому графу, в котором уже никакие ухищрения не помогут (или помогут путем усложнения схемы HP и накладывания каких-то дополнительных требований на данные).
Внедрить иерархический HP, описываемый Вами, в принципе можно: сейчас есть classic_scan и inplace_scan, на выбор. Можно добавить hierarchical_scan, учитывающий Ваш случай и первым делом копирующий массив retired в локальный массив (видимо, new'ed, что в мире lock-free считается дурным тоном). Ну и раз уж у нас появится new, то достаточно move (подмена массивов, так как retired фактически thread local data) вместо copy полного массива.
Я просто поясню, что взрывает мозг — то, что в обоих случаях мы _пишем_ (и читаем) в top
Да, и не только у вас. RMW-операции могут обладать как acquire, так и release семантикой. К сожалению, стандарт довольно подробно описывает атомарные чтение/запись, и только вскользь — атомарные RMW, типа, «они могут обладать как acquire, так и release семантикой». А ведь это — самое главное, ИМХО: без RMW atomic'и довольно бесполезны. Мы сами наделяем RMW-операции нужной семантикой: одни становятся «операциями acquire-чтения», другие — «операциями release-записи», хотя на самом деле они операции и чтения, и записи.
С точки зрения записи в top, парой к release мог бы быть guard.protect( m_Top ), если бы он использовал acquire семантику (но это, вероятно, не так, и он использует relaxed).
Мог бы, но здесь как раз и проявляется семантика: операции с контейнером и с Hazard Pointer'ом — это разные семантические уровни (HP на уровень глубже и играет вспомогательную роль). На самом деле в глубине HP есть m_Top.load( acquire ). Но я не уверен, что этот acquire-load обеспечит нам синхронизацию push и pop.
Верно я понимаю, что рассматривая семантику мы как бы говорим, что если происходит push/pop, то менять их местами нельзя (ведь стек может быть пуст), а pop/push — пожалуйста (ну вытолкнем мы 2й элемент, а не 1й, ну бывает).
На самом деле, вопрос далеко не глупый. На него есть два ответа.
Первый — чисто технический: release/acquire всегда идут парами. Если в push() мы делаем release-CAS, то в pop — acquire-CAS.
Второй — точнее. Memory order задают семантику атомарных RMW-операций. Метод push() — это метод записи данных в стек, а раз запись — значит, из пары «acquire или release» мы можем выбрать только release. Метод pop() — это чтение данных из стека, а для чтения подходящим memory order является acquire.
Замечательная статья!
В защиту автора (хотя, мне кажется, он не нуждается в защите) выражу свое мнение: подход, основанный на истинных stackful сопрограммах, который на протяжении уже нескольких лет разрабатывает автор, мне кажется очень перспективным. И намного более глубоким и красивым, чем то, что предлагают ввести в стандарт C++. Стандарты всегда запаздывают, так как описывают вещи для всех уже привычные и тысячу раз испробованные.
Недостатками этого подхода мне видится две вещи:
1. Отдельный стек для каждой сопрограммы. На самом деле, это достоинство (все данные — на стеке, всегда под рукой, сколько бы нас не прерывали), но за которым надо внимательно следить, иначе при чрезмерном увлечении можно всю память сожрать. Быть может, стоит ограничить размер стека сопрограмм, но это уже детали.
2. Необычность. Этот «недостаток» лечится только опытом. Во-первых, надо попробовать все другие методы асинхронного/многопоточного программирования, начиная от тривиальных mutex/condvar, наплодить 100500 потоков на 4-ядерной машинке, удивиться «а чё оно так медленно работает и падает/лочится», затем пройти через callback hell, попробовать переписать callback на stackless сопрограммах, понять, что просто это не удастся, надо много переписывать. Во-вторых, надо научиться думать в терминах модели stackful сопрограмм; это бывает весьма нелегко, — заставить свой мозг работать по-другому, в терминах новой модели. Например, синхронизировать вовсе без примитивов синхронизации. Или: сделать многопоточную программу, в которой многопоточная логика не вылезает наверх, не затеняет логику самой программы, так что, читая код, вы видите, что делает программа, а не потроха взаимодействия потоков, future, callback и прочую машинерию, за которой леса не видно.
Вообще, трудность введения новых моделей взаимодействия компонентов программы всегда одна и та же: программу приходится переписывать практически с нуля. И вторая трудность — выбор правильной модели.
PS: сам я модель stackful сопрограмм не применял по причинам, описанным выше, — негде было. Но искренне завидую тем, кто это попробовал на реальных задачах.
Замечательные статьи, автору респект!
У меня вопрос: почему вы выбрали BronsonAVLTree и SkipList для сравнения? Только потому, что это стандартные map, не-hash map?..
Я спрашиваю потому, что ваша техника прямо ложится на простой hash-map: хеш-таблица, доступ к каждому элементу таблицы — под вашим легким shared mutex; у Shavit & Herlihy подобная техника называется striping. Не пробовали?..
ИМХО, подход надо развивать, попробовать на каких-то lock-based конкурентных алгоритмах — тот же cuckoo-hashing, hopscotch hashing и пр.
Спасибо за ценный совет! Накопление способов использования очень важно для нас.
В принципе, это возможно сделать. Но здесь может быть другая засада — некоторые радиусы не имеют возможности различать источник запроса — отвечают на любой Access-Request как будто он приходит из одного места (хм… получилось как-то двусмысленно, но в данном контексте даже хорошо ;). В этом случае такой радиус может послать циске такое, что она долго будет плеваться…
Можно также сделать на стороне fastDPI настраиваемый vendor-specific атрибут, в котором должна находиться строка определенного формата, и выкусывать из этой строки regexp'ами то, что нам нужно.
assert Вам ничего не говорит?..
я продолжу...
Видимо, кто-то из членов комитета спустя 15 лет после C++11, где variadic template появились, наконец-то воспользовался ими в полной мере и понял, что это не так удобно, как казалось. И снизошло озарение - индексы...
... который, судя по примеру, по мощности приближается к макросам.
В хорошем примере этот код был бы обложен ограничениями на типы аргументов функций
fooиbar. Надеюсь, в тексте стандарта именно это и будет сделано, иначе все это превращается в макромагиюИз примера, очевидно:
Точно так же - значение 65535 в такой интерпретации не является валидным для
ushort_16.Я понимаю, что где-то это удобно и пр. Но подобные assert'ы не способствуют пониманию для чего все это введено в стандарт, а наоборот - показывают, что
писавший сам плохо понимает, для чегоэто употреблять не надоИнтересно, только у меня возникает впечатление, что комитет по стандартизации занимается во многом велосипедостроением, кое осуждается в обычной жизни?..
Разберем по порядку.
Что подводит нас к новому атрибуту [[indeterminate]]. Если у нас есть неинициализированная переменная и есть функция, которая только пишет в переменную, то можно компилятору дать подсказку, что это не ошибочное поведение. Тогда значение из переменной не будут читать в функцииТут следует продолжить так: "...и при развитии проекта, когда функция перед инициализацией этого аргумента будет проверять его значение, получим то же, что и было, но без ругани компилятора". Неужели не предусмотреть последствия своих действий сразу?..
мы в международной группе пришли к такой мысли: «А было бы неплохо выдавать произвольную диагностику и для =delete»ИМХО, полезно,но является имитацией бурной деятельности комитета.
То же самое можно написать в комментарии к строке, где может возникнуть ошибка, только еще более развернуто.
Эти методы при переполнениях операции возвращаютмаксимальное/минимальное число, которое может содержать определённый тип
данных. Проще всего понять на примере с unsigned short
Из этих примеров мне понятно одно: при таком вычитании значение 0 является невалидным для unsigned short. Кажется, в комитете сидят умные люди и должны понимать, что средствами диапазона [a, b] нельзя выразить признак, что значение X не входит в этот диапазон. То есть налицо новоприобретенный костыль, который будут выпиливать в C++29.
Свершилось! В C++26 добавили функции для работы с векторами и матрицами.Более того — новые функции работают с ExeсutionPolicy, так что можно
заниматься многопоточными вычислениями функций линейной алгебры. Вся эта
радость работает с std::mdspan и std::submdspan
Я вижу эту "радость" по-другому: вместо того, чтобы описывать матрицу, тензор и пр., мы описываем сначала как эта матрица хранится в памяти, а затем поверх этого нахлобучиваем view, как на это нужно смотреть. Странный способ... То есть мы намеренно выносим кишки (memory representation) наружу, хотя до этого комитет всячески убеждал нас не делать такого. ИМХО, эпический костыль...
del
Мне такой материал неизвестен.
Есть многотомные описания для каждой модели процессора (не архитектуры, а фактически каждой модели), там есть всё, но в 10-ти томах
Спасибо за развернутый ответ, Евгений!
Да, без dynamic allocation в C++ жизнь скушна, - без неё никуда.
Поэтому изобретаешь свои велосипеды, но все std контейнеры сразу побоку (абстракция
Allocatorне работает хорошо). [На правах рекламы] Благо естьboost::intrusive, - по-моему, самая правильная идеологически библиотека контейнеров, она и спасает.SObjectizer - очень интересный framework, слежу краем глаза лет 7 уже.
Единственное, что я явно не увидел во всех пропагандистских (в хорошем смысле) статьях - что в нем насчет динамического распределения памяти?.. Для моей области применения это очень критично, - использование стандартных new/delete недопустимо (дает просадку перформанса до 20%, причем вне зависимости, что прикручиваешь в качестве системного аллокатора - tcmalloc, jemalloc и пр., разница только в незначительном различии процентов этой просадки). Поэтому либо преаллоцированные массивы, либо страничные thread-local субаллокаторы без блокировок (строго говоря, на fast path).
Выпиливание new/delete из бибилиотек - вещь неблагодарная, зачастую невозможная (получится клон, новые версии применять невозможно). Предусмотрена ли в SObjectizer обертка над распределением памяти?..
Да, согласен, — поправил, спасибо!
Эмм… Мне помнится, эта ошибка уже была давно исправлена в статье, сейчас не вижу этого кода.
Вы точно уверены, что это привет из 2020 года, а не из 2013?.. ;-)
Да, согласен.
Иерархические hazard pointer'ы практически не поддерживаются, так как от строгой древовидной иерархии очень просто случайно перейти к циклическому графу, в котором уже никакие ухищрения не помогут (или помогут путем усложнения схемы HP и накладывания каких-то дополнительных требований на данные).
Внедрить иерархический HP, описываемый Вами, в принципе можно: сейчас есть
classic_scanиinplace_scan, на выбор. Можно добавитьhierarchical_scan, учитывающий Ваш случай и первым делом копирующий массивretiredв локальный массив (видимо, new'ed, что в мире lock-free считается дурным тоном). Ну и раз уж у нас появитсяnew, то достаточно move (подмена массивов, так какretiredфактически thread local data) вместо copy полного массива.Да, и не только у вас. RMW-операции могут обладать как acquire, так и release семантикой. К сожалению, стандарт довольно подробно описывает атомарные чтение/запись, и только вскользь — атомарные RMW, типа, «они могут обладать как acquire, так и release семантикой». А ведь это — самое главное, ИМХО: без RMW atomic'и довольно бесполезны. Мы сами наделяем RMW-операции нужной семантикой: одни становятся «операциями acquire-чтения», другие — «операциями release-записи», хотя на самом деле они операции и чтения, и записи.
Мог бы, но здесь как раз и проявляется семантика: операции с контейнером и с Hazard Pointer'ом — это разные семантические уровни (HP на уровень глубже и играет вспомогательную роль). На самом деле в глубине HP есть m_Top.load( acquire ). Но я не уверен, что этот acquire-load обеспечит нам синхронизацию push и pop.
Да, можно сказать и так.
Первый — чисто технический: release/acquire всегда идут парами. Если в push() мы делаем release-CAS, то в pop — acquire-CAS.
Второй — точнее. Memory order задают семантику атомарных RMW-операций. Метод push() — это метод записи данных в стек, а раз запись — значит, из пары «acquire или release» мы можем выбрать только release. Метод pop() — это чтение данных из стека, а для чтения подходящим memory order является acquire.
В защиту автора (хотя, мне кажется, он не нуждается в защите) выражу свое мнение: подход, основанный на истинных stackful сопрограммах, который на протяжении уже нескольких лет разрабатывает автор, мне кажется очень перспективным. И намного более глубоким и красивым, чем то, что предлагают ввести в стандарт C++. Стандарты всегда запаздывают, так как описывают вещи для всех уже привычные и тысячу раз испробованные.
Недостатками этого подхода мне видится две вещи:
1. Отдельный стек для каждой сопрограммы. На самом деле, это достоинство (все данные — на стеке, всегда под рукой, сколько бы нас не прерывали), но за которым надо внимательно следить, иначе при чрезмерном увлечении можно всю память сожрать. Быть может, стоит ограничить размер стека сопрограмм, но это уже детали.
2. Необычность. Этот «недостаток» лечится только опытом. Во-первых, надо попробовать все другие методы асинхронного/многопоточного программирования, начиная от тривиальных mutex/condvar, наплодить 100500 потоков на 4-ядерной машинке, удивиться «а чё оно так медленно работает и падает/лочится», затем пройти через callback hell, попробовать переписать callback на stackless сопрограммах, понять, что просто это не удастся, надо много переписывать. Во-вторых, надо научиться думать в терминах модели stackful сопрограмм; это бывает весьма нелегко, — заставить свой мозг работать по-другому, в терминах новой модели. Например, синхронизировать вовсе без примитивов синхронизации. Или: сделать многопоточную программу, в которой многопоточная логика не вылезает наверх, не затеняет логику самой программы, так что, читая код, вы видите, что делает программа, а не потроха взаимодействия потоков, future, callback и прочую машинерию, за которой леса не видно.
Вообще, трудность введения новых моделей взаимодействия компонентов программы всегда одна и та же: программу приходится переписывать практически с нуля. И вторая трудность — выбор правильной модели.
PS: сам я модель stackful сопрограмм не применял по причинам, описанным выше, — негде было. Но искренне завидую тем, кто это попробовал на реальных задачах.
У меня вопрос: почему вы выбрали BronsonAVLTree и SkipList для сравнения? Только потому, что это стандартные map, не-hash map?..
Я спрашиваю потому, что ваша техника прямо ложится на простой hash-map: хеш-таблица, доступ к каждому элементу таблицы — под вашим легким shared mutex; у Shavit & Herlihy подобная техника называется striping. Не пробовали?..
ИМХО, подход надо развивать, попробовать на каких-то lock-based конкурентных алгоритмах — тот же cuckoo-hashing, hopscotch hashing и пр.
В принципе, это возможно сделать. Но здесь может быть другая засада — некоторые радиусы не имеют возможности различать источник запроса — отвечают на любой Access-Request как будто он приходит из одного места (хм… получилось как-то двусмысленно, но в данном контексте даже хорошо ;). В этом случае такой радиус может послать циске такое, что она долго будет плеваться…
Можно также сделать на стороне fastDPI настраиваемый vendor-specific атрибут, в котором должна находиться строка определенного формата, и выкусывать из этой строки regexp'ами то, что нам нужно.
Народ, расчехляем загашники!