aruslan: (Default)
[personal profile] aruslan
Спешите видеть замечательное введение в lock free стеки у [livejournal.com profile] _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.

Date: Oct. 18th, 2008 19:57 (UTC)
From: [identity profile] dieash.livejournal.com
геймдев конторы обязаны предоставлять публичный доступ к исходникам
да хрен с ними, с исходниками, пусть они хотя бы все ошибки, обнаруженные QA-отделом, исправляют перед непосредственным выходом в продажу :)

сон смерти не помеха

Date: Oct. 19th, 2008 16:25 (UTC)
From: [personal profile] alll
Между двумя этими практиками есть несомненная связь.

Re: сон смерти не помеха

Date: Oct. 19th, 2008 19:03 (UTC)
From: [identity profile] aruslan.livejournal.com
Безусловно.
В первую очередь несомненен романтический флер обеих практик :)

Re: сон смерти не помеха

Date: Oct. 19th, 2008 21:19 (UTC)
From: [identity profile] dieash.livejournal.com
дык понятно, но зачем в сырцы лезть, если всё и так на поверхности валяется :)
(deleted comment)

Date: Oct. 19th, 2008 21:17 (UTC)
From: [identity profile] dieash.livejournal.com
каждому овощу свой фрукт! или давайте разделять проблемы :) я говорю о тех ошибках, что просто являются чьим-либо недосмотром, и исправляются, по-хорошему если, за 5 минут. по сути же, являются следствием (чего уж греха таить - ведь такое тоже бывает), низкого уровня квалификации исполнителя (в зависимости от типа). тут уж сколько не плати - выше головы не прыгнешь :)

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

Date: Oct. 19th, 2008 04:04 (UTC)
From: [identity profile] http://users.livejournal.com/_zerg/
ссылка на Insomniac’s SPU Best Practices не работает.

Date: Oct. 19th, 2008 18:55 (UTC)
From: [identity profile] aruslan.livejournal.com
Спасибо, поправил.

Date: Oct. 19th, 2008 07:51 (UTC)
From: [identity profile] neteraser.livejournal.com
не для блондинок, херлихуя!

Date: Oct. 19th, 2008 11:55 (UTC)
From: [identity profile] neteraser.livejournal.com
я не со зла :)

Date: Oct. 19th, 2008 16:47 (UTC)
From: [identity profile] helvegr.livejournal.com
херлихуй прикольный:
http://groups.google.com/group/hopscotch-hashing

In a series of benchmarks on a state-of-the-art 64-way Niagara II multi-
core machine, a concurrent version of hopscotch proves to be highly scal-
able, delivering in some cases 2 or even 3 times the throughput of today’s
most efficient concurrent hash algorithm, Lea’s ConcurrentHashMap from
java.concurr.util. Moreover, in tests on both Intel and Sun uni-processor
machines, a sequential version of hopscotch consistently outperforms the
most effective sequential hash table algorithms including cuckoo hashing
and bounded linear probing
.

Date: Oct. 19th, 2008 17:53 (UTC)
From: [identity profile] neteraser.livejournal.com
> И хотя тема протеста "маленького человека" против обезличенной корпоративной машины мне в целом понятна, это таки не повод не читать википедию.
Ребус был сложен, ничего не значил и что самое удивительное привозразить было не к чему. :) И кто-то делал за интересно, а кто-то применял за деньги принцип применимости применения чего угодно к чему угодно...

Date: Oct. 19th, 2008 19:07 (UTC)
From: [identity profile] aruslan.livejournal.com
Ибо постмодерн.

Date: Oct. 19th, 2008 18:15 (UTC)
From: (Anonymous)
>Я по-прежнему считаю, что геймдев конторы обязаны предоставлять публичный доступ к исходникам.
Ага, начинаем :-D
  //
  //  Весь этот пиздец должен быть перехуячен.
  //  Чему быть, того не миновать.
  //


Рад видеть, что ты в добром здравии, хотя и жжешь глаголом злобно.

Date: Oct. 19th, 2008 18:58 (UTC)
From: [identity profile] aruslan.livejournal.com
Ох, злобный ты! :)
Хоть комментарий и правдив вполне для юности горящих глаз.

Рад видеть и тебя, я в гуглетоке есть, ты присоединяйся!
Edited Date: Oct. 19th, 2008 19:04 (UTC)

Date: Oct. 21st, 2008 07:54 (UTC)
From: [identity profile] neteraser.livejournal.com
> Хоть комментарий и правдив вполне для юности горящих глаз.
Признак успеха :)))

Profile

aruslan: (Default)
aruslan

January 2014

S M T W T F S
   1234
56789 1011
12131415161718
19202122232425
262728293031 

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jul. 20th, 2017 14:51
Powered by Dreamwidth Studios