LINUX.ORG.RU

cpp_stm_free: монадическая STM библиотека для параллельного программирования

 , ,


0

7

Привет,

Меня зовут Александр Гранин, и я рад представить вам свою библиотеку для Software Transactional Memory.

Software Transactional Memory (STM, программная транзакционная память) - подход к программированию многопоточных приложений с конкурентно изменяемой моделью данных. STM значительно облегчает создание многопоточного кода, так как не нужно (почти) ломать голову над синхронизацией, data races и валидностью данных. Также STM снижает риск наступить на типичные проблемы параллельного программирования: блокировки, голодание, нетривиальные многопоточные баги. STM позволяет создать две модели: безопасную конкурентную модель данных и транзакционную модель изменения этих данных.

Для С++ существует несколько STM разной степени годности: Wyatt-STM (хорошая), пропозал TS 19841:2015 (плохой), и вот теперь я создал свою библиотеку, которая называется cpp_stm_free.

Библиотека построена на продвинутых идеях из мира ФП (Free-монады, алгебраические типы данных, и др.), и имеет монадический интерфейс. Иными словами, используя эту библиотеку, вы будете писать ФП-код. Библиотека повторяет интерфейс таковой STM в Haskell: транзакции - это монадические комбинаторы в монаде STML, работающие над транзакционными переменными (TVar).

Библиотека может быть полезна в разных сценариях.

  • В серверных приложениях, обрабатывающих входящие и исходящие сообщения.
  • В soft-realtime многопоточных играх.
  • Для моделирования асинхронных вычислений.

Текущая версия библиотеки - v0.5.5. Требует GCC 7.2 и C++17 (и qmake; вскоре заменю на cmake или что-нибудь другое).

Буквально на днях я провел первый раунд оптимизаций и рефакторинга, увеличив производительность изначальной версии на 200% и добавив большое количество комбинаторов.

Для библиотеки имеется два движка, оба построены на Free монадах. Первый - Scott encoded Free monad (медленный), второй - Church encoded Free monad (быстрый). Для понимания: элементарные транзакции над простой моделью выполняются за <0.01 ms, сложные транзакции <0.1 ms, сложные транзакции в многопоточной среде <1 ms.

Более подробно с библиотекой можно ознакомиться в следующих материалах:

В качестве демонстрационного приложения я решил задачу «обедающих философов» (код здесь), и она работает хорошо. Пример транзакций для взятия ложек:

stm::STML<Unit> takeFork(const TFork& tFork) {
    return stm::withTVar<Fork, stm::Unit>(tFork, [=](const Fork& fork) {
       if (fork.state == ForkState::Free) {
           return stm::modifyTVar<Fork>(tFork, setForkTaken);
       }
       else {
           return stm::retry<stm::Unit>();
       }
    });
}

stm::STML<stm::Unit> takeForks(const TForkPair& forks) {
    stm::STML<stm::Unit> lm = takeFork(forks.left);
    stm::STML<stm::Unit> rm = takeFork(forks.right);
    return stm::sequence(lm, rm);
}

Продолжаю развивать библиотеку, на очереди - еще один раунд оптимизаций и добавление новых фич.

Буду рад ответить на вопросы.



Последнее исправление: GraninAS (всего исправлений: 5)

Но зачем это в языке, где нет do-нотации и удобного синтаксиса для лямбд? Стекать этот stm::bind, судя по всему, не то чтобы сильно удобно или выразительно.

Softwayer ★★
()
Ответ на: комментарий от anonymous

Эта штука, насколько я вижу, лишь продвинутый аналог std::atomic. STM куда интереснее за счет явной модели транзакций и одного маленького, но очень важного комбинатора - retry. С его помощью можно обозначать нежелательные состояния модели данных, что очень сильно упрощает программирование и понимание кода. Например, в коде выше состояние, когда вилка занята кем-то еще, недопустимо. Транзакция просто будет остановлена, и движок дождется, когда нужные вилки (TVar) станут свободны.

GraninAS
() автор топика
Ответ на: комментарий от anonymous

в расте это тоже через пень в колоду доп внешними либами

anonymous
()
Ответ на: комментарий от Softwayer

Это проблема, да, но она решаема. Я пока еще думаю, как do-нотацию лучше имитировать, и где-то находил, что люди на бустовом препроцессоре это делали.

GraninAS
() автор топика
Ответ на: комментарий от GraninAS

Можете поподробнее рассказать: чем занимаетесь, что за компания? Хочу связать свою жизнь с ФП и формальными методами, но пока выбор мест работы не очень велик.

anonymous
()
Ответ на: комментарий от anonymous

Компания называется Restaumatic, Польша. Пишем сервисы для ресторанов: заказ еды, системы скидок, сайты, вот это вот все. Обычный web, CRUD, фронтенд на PureScript, бэкенд на Haskell. На самом деле, переписываем потихоньку эту функциональность с RoR и добавляем новую. Формальных методов у нас не очень много, но ребята сильно шарят в метапрограммировании на типах.

GraninAS
() автор топика

Прикольно, но чем именно хорош haskell, так это тем, что в рамках транзакции нельзя выполнить IO. Действие IO можно вернуть, но выполнить нельзя. Поэтому есть некоторые гарантии. Выходит, программист сам должен в случае других языков следить за тем, что у него нет никакого IO в транзакциях, а иначе такая каша получится при всех эти откатах и повторах! Это во мне хаскельный максимализм говорит. Тем не менее, круто! Ну, что же, удачи!

dave ★★★★★
()
Ответ на: комментарий от dave

У меня тоже так. Если программист не начнет явным образом протаскивать контекст в транзакцию (объект класса Context), то и не сможет выполнить транзакцию в транзакции (stm::atomically). Да и эффекты в транзакциях запрещены административно. Хотя да, их запрет не энфорсится типами.

Context ctx;
auto result = stm::atomically(ctx, someTrans);

Конечно, есть вопрос, как поведет себя atomically внутри другого atomically, я еще не проверял, но есть ощущение, что все будет хорошо.

GraninAS
() автор топика

Выглядит прикольно, но вся соль STM в том же хаскеле гарантировала отсутствие сайд-эффектов (в виде IO) при выполнении экшнов.

Если тут в коде вдруг сходить на диск или в интернет (т.е. обратиться к мутабельному ресурсу - плюсы ж не запрещают), а потом будет ретрай, то вся задумка превращается в тыкву?

Кстати, а где тут монады? stm::sequence() это оно?

yoghurt ★★★★★
()
Ответ на: комментарий от anonymous

Хочу связать свою жизнь с ФП и формальными методами

Светлые желания обычно разбиваются о суровый продакшен, так что чтобы ФП и формальные методы тебе не насточертели, наверное, надо в какой-нибудь МС ресёрч идти, а не в продуктовую контору :)

yoghurt ★★★★★
()

Главный вопрос: зачем эту библиотеку кому-то использовать, если ее не использует в продакшене даже сам автор (а ведь автор даже на C++ сейчас не пишет)?

Т.е. в ракурсе «я вот сделал, посмотрите» все понятно, никаких вопросов. Но вот практическая применимость...

eao197 ★★★★★
()
Ответ на: комментарий от yoghurt

в какой-нибудь МС ресёрч идти, а не в продуктовую контору

Так и задумано (ну почти): сначала получить MSc, а потом уехать делать PhD в UPenn или CSIRO/Data61 (не уверен, правда, что они позволяют делать PhD, а не берут сразу готовых).

Но хочется набраться какого-нибудь прикладного опыта, т.к. пока его у меня мало.

anonymous
()
Ответ на: комментарий от yoghurt

Да, если делать эффекты в транзакциях, можно все превратить в тыкву.

Монада здесь в том, как связываются транзакции. STML - монадический тип. Все функции, которые его возвращают, являются монадическими функциями. stm::sequence - в том числе. Название, кстати, не очень удачное именно для этой функции. Надо бы переименовать.

GraninAS
() автор топика
Ответ на: комментарий от eao197

1) Чтобы было; 2) Wyatt-STM используется в продакшене, следовательно, спрос есть; 3) Я бы хотел использовать ее в продакшене. Сейчас делаю pet project на ней; 4) Хаскельная STM используется в продакшене. Почему бы и в плюсах не быть такой же?

GraninAS
() автор топика
Ответ на: комментарий от GraninAS

1) Чтобы было;

Это понятно.

2) Wyatt-STM используется в продакшене, следовательно, спрос есть;

И это понятно.

3) Я бы хотел использовать ее в продакшене. Сейчас делаю pet project на ней;

Это уже ближе к ответу на вопрос. На самом деле, когда для какого-то проекта выбирается библиотека, то оценивается соотношение выгод (что именно дает библиотека, какой ценой это достигается) и рисков. Тут очевидные риски в том, что:

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

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

Поэтому интересно узнать о практических ее применениях, пусть даже это собственные pet-project-ы.

4) Хаскельная STM используется в продакшене. Почему бы и в плюсах не быть такой же?

Например, потому, что не всегда идиомы и best practicies из одного языка хорошо ложатся в другой язык. Например, неоднократно доводилось наблюдать как люди с опытом Java за плечами, оказавшись в C++, начинали использовать shared_ptr направо и налево. Потому, что им так было проще, а какие с этим связаны расходы их не интересовало.

eao197 ★★★★★
()
Ответ на: комментарий от GraninAS

Да, если делать эффекты в транзакциях, можно все превратить в тыкву.

Тохда видимо нужен некий чистый DSL для описания транзакций, без возможности инжектить фри-форм код? Возможно, как https://en.wikipedia.org/wiki/Expression_templates

yoghurt ★★★★★
()
Ответ на: комментарий от yoghurt

Если тут в коде вдруг сходить на диск или в интернет (т.е. обратиться к мутабельному ресурсу - плюсы ж не запрещают), а потом будет ретрай, то вся задумка превращается в тыкву?

А можно мьютекс залочить и вдруг не отпустить.
Вся идея мьютексов превратилась в тыкву!

anonymous
()
Ответ на: комментарий от eao197

Например, потому, что не всегда идиомы и best practicies из одного языка хорошо ложатся в другой язык.

Ну, в 2К18 этот довод уже звучит совсем неубедительно. Помнится, лет 7 назад плюсовики активно сопротивлялись ФП и ФПшным фичам в языке, но поколение сменилось, и сейчас я наблюдаю неподдельный интерес к этой теме.

А то, что кто-то там неправильно использует некоторые фичи, никак не ставит крест на заимствовании этих фич из других парадигм.

P.S. Не беспокойтесь, STM не конкурирует с SObjectizer, у них разное предназначение. ;)

GraninAS
() автор топика
Ответ на: комментарий от yoghurt

Компайл-тайм описание транзакций бы помогло, конечно. Но это очень много мороки. Приходится ограничиваться административным запрещением, такое уж оно, ФП в С++.

GraninAS
() автор топика
Ответ на: комментарий от anonymous

Для этого-то хотя бы автоматика есть в виде RAII

yoghurt ★★★★★
()
Ответ на: комментарий от GraninAS

но поколение сменилось

Как-то незаметно, если честно. Слишком часто слышен плач тех, кто пугается, увидев лямбды в коде.

Но речь про другое. Фичи можно копировать и платить за это, например, большими накладными расходами. Либо адаптировать, но тогда сами фичи могут видоизменяться. Но это уже философствования, хотелось бы вернуться ближе к исходному вопросу.

Не беспокойтесь, STM не конкурирует с SObjectizer, у них разное предназначение.

Дело не в этом. Вот вы выкатили библиотеку. Как эта библиотека позиционируется: как эксперимент или как практичный инструмент?

Если как практичный инструмент, то почему некий Вася Пупкин, который решил использовать STM в своем плюсовом коде, может сделать выбор в пользу вашей библиотеки? А не взять что-то другое, или написать что-то самостоятельно.

eao197 ★★★★★
()
Ответ на: комментарий от GraninAS

P.S. Не беспокойтесь, STM не конкурирует с ...(то что нельзя называть), у них разное предназначение. ;)

Зря ты это слово написал. Он занимается саморекламой. Индекс цитирования - такой индекс цитирования.

anonymous
()
Ответ на: комментарий от eao197

Как-то незаметно, если честно. Слишком часто слышен плач тех, кто пугается, увидев лямбды в коде.

Очень заметно. Мои ФП-доклады на C++ Russia собирают полные залы, масса вопросов и разговоров. Книжки всякие от Иванов выходят, мастер-классы; ведущие плюсовики про ФП рассказывают и то и дело Haskell упоминают, Eric Niebler свою библиотеку пилит, на r/cpp сколько об этом разговоров.

Вы, может, не с теми общаетесь просто. В России еще полно разработчиков «старой школы».

Как эта библиотека позиционируется: как эксперимент или как практичный инструмент?

И то, и другое. Должен ли Вася ее использовать, он сам решит, если у него на плечах есть голова. А мое дело - рассказать, как использовать и что это даст. Об этом можно в приаттаченных материалах почитать / посмотреть. Если создам другие дополнительные материалы или showcase-проекты, тоже приаттачу.

GraninAS
() автор топика
Ответ на: комментарий от GraninAS

Очень заметно. Мои ФП-доклады на C++ Russia собирают полные залы, масса вопросов и разговоров.

Опрос в Интернете показал, что Интернетом пользуются 100% опрашиваемых.

В России еще полно разработчиков «старой школы».

Не только в России.

И то, и другое.

Если «и другое» подразумевает использование в продакшене, то какой опыт, какие уроки были получены, какие косяки были найдены и исправлены?

eao197 ★★★★★
()
Ответ на: комментарий от eao197

Второй движок не просто так появился. Монадическое связывание на Scott encoded Free монады имеет квадратичную сложность, поэтому я заменил ее на Church encoded Free монаду. Производительность сразу же подскочила в 10 раз. Потом еще избавился от глупого GUID в пользу целочисленного. Производительность снова подскочила в 10 раз. А до этого, еще когда готовил версию 0.4, исправил конкурентный баг, который приводил к излишним перезапускам транзакций (но все же не портил верные результаты). Сейчас известно, что STM порождает большой memory-трафик, и происходят множественные копирования данных, которые вы помещаете в TVar, но это так даже в Wyatt-STM, которой уже несколько лет. Такая уж особенность, и соответственно применимость. На ГитХабе есть ряд known issues, которые необходимо решить, прежде чем объявлять релиз.

Но вы поймите одну простую вещь. Если ФПшное что-то, сделанное по всем правилам ФП, начинает работать, то багов там будет минимум. Я понимаю, что всякие SObjectizer'ы нужно было сильно отлаживать, ведь там такой ад в имплементации с этими локами, синхронизациями... Но когда мы говорим о ФП, работают совсем другие принципы. Я, конечно, не исключаю, что в библиотеке есть какие-нибудь не очень хорошие баги, - вероятность имеется. Но не то, чтобы высокая. Модельные приложения вроде тех же обедающих философов и мои бенчмарки, которые я запускал и в качестве стресс-тестов, показывают, что если баги и есть, то они не про надежность кода (она очень высокая), а про тонкий тюнинг. Там подкрутить, здесь улучшить, вот это сделать оптимальнее... Но это обычная работа, и она будет делаться постепенно.

GraninAS
() автор топика
Ответ на: комментарий от GraninAS

Второй движок не просто так появился. Монадическое связывание на Scott encoded Free монады имеет квадратичную сложность, поэтому я заменил ее на Church encoded Free монаду. Производительность сразу же подскочила в 10 раз. Потом еще избавился от глупого GUID в пользу целочисленного. Производительность снова подскочила в 10 раз. А до этого, еще когда готовил версию 0.4, исправил конкурентный баг, который приводил к излишним перезапускам транзакций (но все же не портил верные результаты).

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

Собственно, в этом-то и риск: если вы сами не используете свою разработку в реальных задачах, то кто знает, что там еще может боком вылезти. А когда вылезет, то насколько вы готовы будете с этим разбираться.

Я понимаю

Не думаю, что вы понимаете о чем я вас спрашиваю. Раз уж упомянули наш проект, то из опыта его эксплуатации. Один из моментов, который практически сразу же всплывает: «А как посмотреть, что у вас происходит внутри?» Т.е. когда ты вроде делаешь все по документации, а оно почему-то не работает, то как узнать, что и где прервалось.

Второй момент — отмена таймеров. Таймер можно отменить, но если это примерно совпадает со временем срабатывания таймера, то таймерное событие до вас все-таки может дойти. Это не очевидно для пользователей, но этому есть объяснение.

И мы объясняем пользователям вещи, с которыми при эксплуатации кто-то да сталкивается.

Собственно, если вы позиционируете cpp_stm_free как практичный инструмент, то можете ли вы рассказать о том, на что нужно обращать внимание при его использовании? Скажем, вы говорите «Сейчас известно, что STM порождает большой memory-трафик, и происходят множественные копирования данных, которые вы помещаете в TVar», а мониторить это как-то можно? Статистику какую-то снимать в каком-то виде?

eao197 ★★★★★
()
Последнее исправление: eao197 (всего исправлений: 1)
Ответ на: комментарий от eao197

а мониторить это как-то можно?

можно. монадой.

Статистику какую-то снимать в каком-то виде?

можно. монадой. в каком виде нужно, ту монаду и используй.

anonymous
()
Ответ на: комментарий от eao197

Вы же уже выяснили состояние библиотеки на данный момент. Требовать что-то, чего еще нет, и вы об этом знаете, - ну это просто наезд ради наезда. Мол, как же так, у нас все есть, а у вас тут только огрызок... Но давайте вспомним, сколько вы со своим SObjectizer'ом возитесь. Десяток лет, полагаю?

Если фича нужна, откройте гитхаб и сделайте фичереквест, как делают все люди, которым это действительно надо, а не на форуме покритиковать. Все, что библиотека умеет сейчас, описано в приаттаченных материалах. Узнаю больше, - расскажу больше. Будут интересоваться с целью применить, - пойдет иной разговор.

GraninAS
() автор топика
Ответ на: комментарий от GraninAS

Требовать что-то, чего еще нет, и вы об этом знаете, - ну это просто наезд ради наезда.

Разве непонятно ещё, что eao - это гений C++? :-)

Если фича нужна, откройте гитхаб и сделайте фичереквест, как делают все люди, которым это действительно надо, а не на форуме покритиковать.

А Вы не хотели бы выступить на какой-нибудь конференции C++ на предмет Вашей библиотеки? :-) Скоро вот будет конференция в Питере :-)

azelipupenko
()
Ответ на: комментарий от GraninAS

Вы же уже выяснили состояние библиотеки на данный момент.

Да, в результате наводящих вопросов.

Только вот вы как-то близко к сердцу воспринимаете вопросы из категории «а это готово для продакшена?» и «это где-то используется?»

Между тем вопросы обычные для такого рода анонсов.

eao197 ★★★★★
()

Для библиотеки имеется два движка, оба построены на Free монадах. Первый - Scott encoded Free monad (медленный), второй - Church encoded Free monad (быстрый). Для понимания: элементарные транзакции над простой моделью выполняются за <0.01 ms, сложные транзакции <0.1 ms, сложные транзакции в многопоточной среде <1 ms.

Насколько всё-таки получилось быстрее, чем в хаскеле?

Crocodoom ★★★★★
()
Ответ на: комментарий от azelipupenko

Так я уже выступал, в Питере, на C++ Russia в минувшем апреле. Ссылку на видео в пост тоже приаттачил.

Но, в принципе, рассказывать там есть еще на пару докладов. О какой конференции вы говорите?

GraninAS
() автор топика
Ответ на: комментарий от Crocodoom

Это интересный вопрос.

Нативная хаскельная либа, поддержанная компилятором, быстрее моей хаскельной реализации в 6 раз. При этом последняя работает в диапазоне до микросекунды.

Реализация на С++ работает в миллисекундном диапазоне. Выходит, она медленнее в тысячу раз.

Я полагаю, это из-за внутреннего мьютекса, взятие которого, видимо, очень затратное. Для сравнения: взятие MVar требует порядка двадцати наносекунд в Haskell.

GraninAS
() автор топика
Ответ на: комментарий от Crocodoom

Однако, я могу сильно ошибаться, так как не помню, тестил на одной машине или на разных, с оптимизациями или без.

GraninAS
() автор топика

Мне не понятно вот что :-) Зачем Вам, работающему с таким приличным языком программирования, как Haskell, понадобилось реализовывать библиотеку на цепепе? :-) Бытует мнение, что цепепе уже подошёл к точке «плато», и что сегодня в нём особого смысла нет вообще :-)

azelipupenko
()
Ответ на: комментарий от azelipupenko

Я поддерживаю это мнение, хотя до полного развоплощения плюсам, конечно, далеко.

А понадобилось мне это для того, чтобы выступить с докладом на C++ Russia 2018, продолжая цикл докладов о ФП в С++. Такой был план изначально. А если спросите, зачем я такие доклады делаю, это уже другая история. Нравится. Ну и конфы у Платонова всегда ламповые.

GraninAS
() автор топика
Ответ на: комментарий от azelipupenko

наверное потому что хаскель язык хоть и хороший и даже иногда применяется, но все еще остается уделом академических интересов. А кушать хоцца прям сейчас, а не через 100 лет, когда плюсы вымрут

anonymous
()

пропозал TS 19841:2015

Пропозал?

Status : Published

anonymous
()
Ответ на: комментарий от GraninAS

А если спросите, зачем я такие доклады делаю, это уже другая история. Нравится.

Я спрошу зачем Вам доклады на конференциях по цепепе? :-) Неужели нет конференций по Хаскелю? :-) Или Вам просто нравится работать на сложных языках и говорить о них публично? :-)

azelipupenko
()
Ответ на: комментарий от azelipupenko

Конфа по хаскелю намечается на август, правда, я не подал заявку на доклад. Может, посещу как участник.

А доклады по ФП на С++ - это возможность прокачать: скил в ФП; скил выступления; скил объяснения нетривиальных вещей людям, от этого далеким; скил С++, хотя мне это особо не удается. А еще это популяризация ФП и личный челендж. Я начинаю готовить доклад месяца за три. Например, заявив тему об STM, я вообще сомневался, что смогу сделать демо. Как запасной, рассматривал вариант, что возьму стороннюю либу и сделаю обзорный доклад. Но это вдвое менее интересно для меня и аудитории, чем специально написанный для конфы код. Мне снова повещло: я смог реализовать STM, причем очень просто. Раньше считалось, что STM - крайне сложная для имплементации концепция, посмотрите хотя бы Wyatt STM внутри. И это правда; но я нашел способ сделать более простую имплементацию, пусть даже с жертвованием некоторых характеристик (мой подход априори менее производителен, чем традиционные). Однако в легковестности тоже есть польза, и кому-то может подойти.

GraninAS
() автор топика
Ответ на: комментарий от GraninAS

Ну круто :-) Из всего того малого, что Вы сказали и показали, можно сделать вывод, что у Вас есть всё для успеха :-) Вроде бы есть и способности, и харизма, и страсть к публичным выступлениям :-) Дерзайте, успехов Вам :-)

azelipupenko
()

Классический вопрос автору. Как вы думаете, верно ли утверждение, что если многопоточный код изначально писать правильно (с использованием средств стандартной библиотеки), то:

1. «Ломать голову над синхронизацией, data races и валидностью данных» особо-то и не нужно.

2. «Риск наступить на типичные проблемы параллельного программирования: блокировки, голодание, нетривиальные многопоточные баги» почти минимален.

3. Накладных расходов на выполнение «безопасной конкурентной модели данных и транзакционной модели изменения этих данных» и вовсе нет.

4. STM получается-то и не нужен.

romp01
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.