?

Log in

No account? Create an account
Занимательный бег не спеша у _foreseer - Valse oubliée [entries|archive|friends|userinfo]
aruslan

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]
[ delicious | aruslan's delicious ]

Links
[Links:| Tags Profile Friends FG1 PP gamedev XNA FF Entries Comments Memories ]

Занимательный бег не спеша у _foreseer [Oct. 18th, 2008|09:50 am]
aruslan
[Tags|, , ]

Спешите видеть замечательное введение в 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.
LinkReply

Comments:
[User Picture]From: dieash
2008-10-19 05:17 pm (UTC)
каждому овощу свой фрукт! или давайте разделять проблемы :) я говорю о тех ошибках, что просто являются чьим-либо недосмотром, и исправляются, по-хорошему если, за 5 минут. по сути же, являются следствием (чего уж греха таить - ведь такое тоже бывает), низкого уровня квалификации исполнителя (в зависимости от типа). тут уж сколько не плати - выше головы не прыгнешь :)

ЗЫ
полагаю, сколько надо" нужно в контракте фиксировать, со всеми вытекающими. но это тема для отдельного разговора
(Reply) (Parent) (Thread)