Занимательный бег не спеша у _foreseer |
[Oct. 18th, 2008|09:50 am]
aruslan
|
Спешите видеть замечательное введение в lock free стеки у _foreseer: Running lock free.
Там просто и внятно изложена базовая идея и есть хорошие ссылки на почитать. Ну а уж презентация Elimination-Backoff Stack просто жжёт термоядом - спасибо за ссылку, Андрей!
В геймдеве lock-free структуры данных используют повсеместно, но о них ничего не пишут. Видимо, умные очень, и через это боятся публиковать свой удивительный код.
"Как стек running free у нас" - ABA брутально через CAS2. Но чаще не столько CAS, сколько классическое комбо Load-Link/Store-Conditional. А именно lwarx/lwsync/stwcx/GETLLAR/PUTLLC, и дальше вариации на тему очень быстрой vs очень устойчивой синхронизации (ну и на обход багов в отдельно взятых процессорах).
Важно помнить про тот самый exponential backoff. Ну и вообще, важно думать. Если думать, то и lock-free структуры не понадобятся :) Ну а если не думать, то они скорее всё испортят, чем помогут.
Вот не далее чем на прошлой неделе загадочно и очень каскадно протухла память. И - что вы думаете? - выяснилось, что зажгла самопальная реализация lock-free очереди. Автору кода было интереснее реализовывать lock free очередь нежели свои таски. И хотя тема протеста "маленького человека" против обезличенной корпоративной машины мне в целом понятна, это таки не повод не читать википедию.
Я по-прежнему считаю, что геймдев конторы обязаны предоставлять публичный доступ к исходникам. Чтобы термины "exponential backoff", "memory barrier" и "lock-line reservation" из абстрактных превратились в конкретные, благодаря помощи зала. Принцип Керкхоффа вполне применим к геймдеву, ибо смысл соревнований - в умении создавать и шипить игры.
Через это ссылки на почитать дальше про lock free и вообще: 1. Lock-Free Code: A False Sense of Security Хебра нашего Саттера. 2. Insomniac’s SPU Best Practices (PPT) Майка нашего Эктона. 3. Obstruction-Free Synchronization (PDF) того самого Мориса Херлихуя (ц) _foreseer. |
|