- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
static Singleton * g_pInstance = NULL;
Singleton* Singleton::sharedInstance()
{
if (g_pInstance)
return g_pInstance;
else {
g_pInstance = new Singleton();
if (g_pInstance->init()) {
return g_pInstance;
} else {
delete g_pInstance;
g_pInstance = NULL;
}
return g_pInstance;
}
}
Deacon 08.10.2013 17:53 # +1
bormand 08.10.2013 17:59 # +2
3.14159265 08.10.2013 19:11 # +2
И 90% попыток написать double checked locking - говно.
Да и это касается синглтонов в целом.
bormand 08.10.2013 19:31 # +1
3.14159265 08.10.2013 19:38 # 0
В с++11 вроде как что-то делали для многопоточности.
bormand 08.10.2013 19:45 # +1
Stertor 09.10.2013 10:27 # −3
Вывод: все кодили на Delphi.
bormand 08.10.2013 20:21 # +3
В общем, если верить статьям, то и модель памяти с хеппенс бефор есть, и набор атомиков, и набор более высокоуровневых классов, и tls, и статикам внутри функций поведение стандартизировали... Но я могу заблуждаться, т.к. пока кресто11потоки не юзал, и стандарт не раскуривал...
3.14159265 08.10.2013 21:17 # +1
bormand 08.10.2013 21:43 # +3
Ересь виндузячья! По стандарту volatile не имеет отношения к тредам (т.к. тредов нет). И поэтому может сделать только хуже. А то, что MS прикрутил к volatile aquire-release семантику - это их персональное извращение.
P.S. volatile вроде как предназначался только для отображенных в память портов ввода-вывода.
bormand 08.10.2013 21:52 # +1
http://msdn.microsoft.com/en-us/library/ee418650%28v=VS.85%29.aspx
Короче это даже в вижуалке работает далеко не везде и не всегда.
Dummy00001 09.10.2013 13:29 # 0
"[...] the compiler does not insert any instructions to prevent the CPU from reordering reads and writes."
что к слову не есть конфликт, т.к. CPU знает про io-mmap и обращения туда сам не оптимизирует.
laMer007 10.10.2013 11:31 # 0
DMA, Memory Mapped IO, Interrupts, борьба с оптимизацией в "синтетических" тестах.
bormand 10.10.2013 12:28 # +1
Ну и юниксовые сигналы еще тогда. Но в любом случае не для тредов.
3.14159265 10.10.2013 12:43 # 0
> в любом случае не для тредов.
А как по-вашему оно (thread switch context) сделан внутри ОС?
Или линуксовый планировщик не использует прерывания?
bormand 10.10.2013 13:13 # +1
Для межъядерного общения volatile неюзабелен чуть более чем полностью... Те же атомарные интринсики подавляют оптимизации намного аккуратней (всего лишь убирая перескоки через барьер), и вставляют необходимые на данной архитектуре барьеры и/или команды. volatile же глушит оптимизацию на переменной полностью, и ничего не понимает в барьерах (перверсии майкрософта в расчет не принимаем)... Я вот даже сомневаюсь, можно ли его юзать volatile переменные для общения с обработчиками прерываний на двух и более ядрах...
3.14159265 10.10.2013 14:09 # 0
>Для межъядерного общения volatile неюзабелен чуть более чем полностью...
Нет. Отчасти.
>Те же атомарные интринсики подавляют оптимизации намного аккуратней (всего лишь убирая перескоки через барьер)
Они не всегда гарантируют что компилкр не закешит переменную в регистре или не оптимизнет каким-либо образом.
Другое дело что сишкоблядский стандарт позволяет вообще ложить на volatile: "What constitutes an access to an object that has volatile-qualified type is implementation-defined".
И я где-то читал что популярные компилеры собственно и ложат на это и потому баги при реализации volatile - тот же GCC на О2 не всегда работает как надо.
bormand 10.10.2013 15:13 # 0
Ну собственно в этом и их плюс по сравнению с volatile. Они подавляют только те оптимизации, которые будут мешать правильному переходу через границу. Остальные то зачем трогать? Это ж не MMIO, где важен каждый load/store, и, емнип, даже зоны памяти размечают как некешируемые...
> И я где-то читал что популярные компилеры собственно и ложат на это и потому баги при реализации volatile
http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
this?
3.14159265 10.10.2013 16:07 # 0
Объясняю. Зачем нужны volatile при трейдинге. volatile, как известно, означает отключение оптимизаций, и готовность к тому что переменная ВНЕЗАПНО изменится, неожиданным образом.
Вот есть умный крестобляский компилер.
Он видит ситуацию:
Он подумает stop в коде не меняется - можно такое оптимизнуть оставив безусловный переход, не проверяя stop.
Откуда компилер узнает что переменная меняется из другого треда, пусть даже атомарно?
>this?
yeah
bormand 10.10.2013 19:07 # +2
Блин, вот интересный пример на самом деле. В отличие от других примеров, здесь data race не страшный: флаг переключается только в одну сторону, тред после выхода из цикла просто завершает работу...
С одной стороны, насколько я понимаю, volatile не имеет никакого воздействия на кеши. И одно ядро какой-нибудь SMP системы, не умеющей в когерентность кешей будет вечно дрочить stop в цикле и никогда не узнает о том, что другое ядро туда положило true...
С другой же стороны в многозадачной оси потоки постоянно переключаются, и рано или поздно кеши все равно сбросятся, и оно этот флаг увидит...
И еще меня смущает тот факт, что почти на всех архитектурах atomic_read/atomic_set в линуксе запилены как каст в volatile int *, но на power pc они по какой-то причине реализованы через ассемблерную вставку.
3.14159265 10.10.2013 19:44 # +1
Причем жизненный. Я не далее чем джва часа назад писал в проекте такое :)
>в линуксе запилены как каст в volatile int
Ну так не зря это. Я ж и говорю что volatile нужен для многозадачности - он отключает такие оптимизации компилера, чтоб не он выпилил лишнего.
Потому что если будет где-то меняться атомиком, этого недостаточно - запросто оптимизнется в бесконечный цикл.
bormand 10.10.2013 19:59 # +1
Менять атомиком недостаточно. Надо еще и читать атомиком ;) И этого будет вполне достаточно. Ибо каст в volatile будет заныкан в макросе, либо там будет volatile асмовая вставка, либо это вообще будет встроенная "функция", о которой компилятор и так знает все. Так зачем тащить в свой код эту деталь реализации атомика?
На переменных, которые читаются\пишутся\CAS'ятся только атомарными операциями volatile писать не нужно (и даже вредно). Или есть опровержение? :)
P.S. Небольшой вбросец: https://www.kernel.org/doc/Documentation/volatile-considered-harmful.txt
3.14159265 10.10.2013 20:35 # +1
Ну всё-равно то оптимизация где-то должна быть отключена. То есть категорически утверждать, что volatile совсем не нужен для многопоточных сред я бы не стал.
Линк - хороший.
LispGovno 10.10.2013 20:44 # +1
Ничего интересного. Это вечный цикл.
А вот если бы переменная была:
1) ссылка полученная неизвестно откуда
2) глобальная переменная
3) от этой переменной взяли ссылку или указатель и отправили в а)глобальную область видимости б)или передавали в неанализируемую функцию (функцию в скомпилированном объектнике или DLL) с)или отправили в данные, полученные по указателю\по ссылке (тут тоже возможен анализ и в некоторых случаях компилятор оставит бесконечный цикл при выполнении 3)с) ).
То при выполнении любого условия из списка выше компилятор пишет цикл с постоянной проверкой этой переменной. По крайней мере так делают обычно в нормальном компиляторе. Стандарт до 11 этого правда не оговаривает, а в новый я не смотрел по этому поводу. Там могло появится.
bormand 10.10.2013 21:08 # 0
Ну я предполагал, что она глобальна ;)
> Ничего интересного.
Пример интересен тем, что до него трудно доебаться. Если бы флаг назывался не stop, а как-то еще, можно было бы упомянуть про переупорядочивание, и обозвать код говном...
LispGovno 10.10.2013 20:50 # 0
А такие бывают? Не слышал.
LispGovno 10.10.2013 20:25 # 0
>Нет. Отчасти.
Ну в джаве то конечно...
А вот если нужно, чтобы в крестах, то там перед\после обращения к переменной барьер лучше вставь. Ну или если нужно повторно зачитать переменную с гарантией обращения к памяти, то опять же между ними барьерчик.
3.14159265 10.10.2013 20:37 # 0
Там тоже не всё гладко. Вот в 8-ю предлагают запилить:
http://openjdk.java.net/jeps/171
anonimb84a2f6fd141 10.10.2013 20:39 # 0
>jeps
Пародия на pep?
bormand 10.10.2013 21:14 # 0
Да этих *EP горы... Хрен бы знал кто начал первым. Скорее всего и правда питонисты.
3.14159265 11.10.2013 21:05 # 0
Ведь улыбка - это флаг корабля.
Само собой. Хотя бы тем что в сишке implementation-defined, а в жабе везде одинаковый. Это выше по треду указано кстати.
anonimb84a2f6fd141 11.10.2013 21:54 # 0
guest8 03.11.2018 17:55 # −999
roman-kashitsyn 08.10.2013 23:06 # +2
Dummy00001 09.10.2013 13:41 # 0
буст доделает. главное что есть атомики, которые в некоторых случаях позволяют без структур обходится.
> и тредпулов нет :(
с std::function'ом я могу и сам налепить без проблем.
как по мне, std::function есть одно из самых важных дополнений в 11ом.
roman-kashitsyn 09.10.2013 14:06 # +1
Ты имел в виду с std::packaged_task. Простой тредпул запилить в 11 плюсах действительно несложно. А вот work-stealing уже не хочется самому писать.
> буст доделает
> std::function есть одно из самых важных дополнений
Ну тогда boost::function тоже давно есть
> есть атомики, которые в некоторых случаях позволяют без структур обходится
Атомики могут помочь избежать мутексов, но уж никак не структур данных. Заменить блокирующую очередь атомарным интом не получится. Конечно, оаписать простую медленную очередь - плёвое дело для тех, кто это уже делал. А вот новички могут все грабли собрать. Грамотно выбрать интерфейс многопоточной очереди, например, не каждый с первого раза сможет.
3.14159265 09.10.2013 14:13 # 0
А разве от него серъезный профит?
>оаписать простую медленную очередь - плёвое дело
Смотря как писать. Если через мьютексы - то несложно, там только надо подумать хорошо над waitForSingleObject и notify.
А вот если на спин-локах, там на порядок сложнее.
В любом случае алгоритмы известны.
roman-kashitsyn 09.10.2013 14:28 # 0
Зависит от специфики задач. Я думаю, многим хватит и простого пула с одной очередью. Но если для уменьшения оверхеда сделать по очереди на поток, то вполне может сложиться, что треду-неудачнику достанется несколько тяжёлых задач, а остальные треды будут сделают простые таски и будут бездействовать.
3.14159265 09.10.2013 14:43 # 0
Причем сильно. Если задания больше тратят на I/O, то work-stealing не сильно поможет.
Это скорее отпимизация, над которой надо думать когда уже найдено узкое место.
roman-kashitsyn 09.10.2013 14:47 # 0
Abbath 09.10.2013 16:21 # 0
roman-kashitsyn 09.10.2013 16:25 # +4
Мне кажется, что люди просто кидают такие статьи в "избранное", где они пыляться как непрочитанные вкладки.
Бложик, статью из которого "перевели" на хабре (в 33 линии на хаскеле? wut?), кстати, очень даже годен, всем советую.
3.14159265 09.10.2013 16:50 # +2
laMer007 09.10.2013 17:42 # +3
LispGovno 09.10.2013 20:00 # 0
LispGovno 09.10.2013 21:11 # 0
roman-kashitsyn 09.10.2013 21:15 # 0
forkIO, Control.Concurrent.Async
anonimb84a2f6fd141 09.10.2013 21:17 # 0
LispGovno 09.10.2013 21:21 # 0
LispGovno 09.10.2013 21:22 # 0
roman-kashitsyn 09.10.2013 21:30 # 0
> форкио делает новый поток
Это ты не в теме как работает forkIO
LispGovno 09.10.2013 21:39 # 0
bormand 09.10.2013 21:49 # 0
forkIO треды плавают между тредами операционки, поэтому ни о каком тред локал состоянии не может быть и речи... Если нужно привязать гринтред к одному потоку операционки - юзай forkOS.
LispGovno 09.10.2013 22:00 # 0
LispGovno 09.10.2013 21:25 # 0
wvxvw 10.10.2013 09:53 # 0
> done команда не имеет детей, так что компилятор выводит, что она имеет полиморфное возвращаемое значение (т.е. r), это означает, что оно никогда не завершится
Хороший водитель, но иногда педали путает.
laMer007 10.10.2013 11:32 # 0
LispGovno 21.01.2015 22:37 # 0
defecate-plusplus 21.01.2015 23:15 # +1
а сам объект в куче ты уж синхронизируй как тебе надо
bormand 21.01.2015 23:19 # +1
LispGovno 21.01.2015 23:21 # 0
bormand 21.01.2015 23:23 # 0
А чем не нравится мутекс + шаред птр? Производительность реально проседает на этом месте?
LispGovno 21.01.2015 23:28 # 0
http://ideone.com/OzLFib
bormand 21.01.2015 23:31 # 0
LispGovno 21.01.2015 23:46 # 0
bormand 21.01.2015 23:50 # 0
LispGovno 21.01.2015 23:52 # 0
bormand 21.01.2015 23:57 # +1
In addition, std::atomic may be instantiated with any TriviallyCopyable type T. А std::shared_ptr<> не особо похож на тривиально копируемый...
LispGovno 22.01.2015 00:20 # 0
bormand 21.01.2015 23:52 # +1
LispGovno 22.01.2015 00:21 # 0
defecate-plusplus 22.01.2015 00:10 # 0
шаред птр как бы на то и _шаред_ птр
это указатель на объект, который собирается _использовать_ несколько тредов, не думая о том, сколько владельцев в данный момент
если живой шаред птр один из тредов собирается менять, то что-то странное, что-то пошло не так в датском королевстве
вангую, что в данном случае подойдет вариант с одним реальным властелином + n-1 weak_ptr?
ну... или shared lock + upgrade lock вокруг чтения и модификации этого шаред птра
LispGovno 22.01.2015 00:18 # 0
defecate-plusplus 22.01.2015 00:21 # 0
http://ru.cppreference.com/w/cpp/memory/shared_ptr/swap
LispGovno 22.01.2015 00:25 # 0
с чего ты взял что свап атомический при использовании одного смарта в разных потоках? никогда не слышал. вот атомик эксчендж или атомик стор как следует из названия явно атомический
defecate-plusplus 22.01.2015 00:34 # 0
из памяти, когда в прошлой жизни читал сорцы буст шаред птр
LispGovno 22.01.2015 00:37 # 0
пс буст это не стд и полагаться на это нельзя
defecate-plusplus 22.01.2015 00:52 # +2
теперь же отвечаю за всякую поебень вселенского масштаба на глиняных ногах, и студию не запускал очень давно
bormand 22.01.2015 00:26 # +1
Нет, т.к. без atomic_load'а у тебя не будет happens before. Хотя на интеле и проканает (но на нём и atomic_load бесплатный, и ничего не делает, емнип, так что ты ничего не теряешь заюзав его).
bormand 22.01.2015 00:26 # +1
Т.е. shared_ptr + std::atomic_load на чтении + std::atomic_store на модификации. Ну или shared_ptr + r/w lock или мутекс, да.
LispGovno 22.01.2015 00:35 # 0
пс ты все верно понял. разве что дорабатывать со старыми задания не обязательно, а можно и новые заюзать параметры
bormand 22.01.2015 00:37 # 0
Там настолько мелкие задания, что это влияет?
LispGovno 22.01.2015 00:38 # 0
был бы pair мьютекса и объекта, который можно разьименовывать и мьютекс будет сам блокироваться
bormand 22.01.2015 00:41 # +1
lispgovno::locked_ptr<>
LispGovno 22.01.2015 00:43 # 0
и лучше уж тогда
если на то пошло (2 типа)
bormand 22.01.2015 00:45 # +1
Abbath 22.01.2015 11:30 # 0
laMer007 22.01.2015 13:54 # 0
Abbath 22.01.2015 14:01 # 0
laMer007 22.01.2015 14:46 # 0
LispGovno 22.01.2015 00:47 # 0
>> рвлоки будут и дешевле
> Там настолько мелкие задания, что это влияет?
bormand 22.01.2015 00:49 # +1
Я в Qt его юзал, там он давным-давно. Ну и boost::shared_mutex, который советовал d++.
> да и не удобный он
Апгрейда с R на W нету поди?
LispGovno 22.01.2015 00:57 # 0
bormand 22.01.2015 00:57 # +1
Наоборот же. Поработал на уровне апгрейд лока, понял, что пора что-то менять, апгрейднул до эксклюзивного, записал, снял локи. Вот в Qt upgrade_lock'а не было. А без него хуёво.
LispGovno 22.01.2015 01:00 # 0
Или в окно выйти
defecate-plusplus 22.01.2015 01:07 # 0
и нахуй тут локи?
нужен объект конфиг-холдер
в котором и хранится этот исходный эталонный шаред птр
захотел сменить конфиг - говори этому конфиг холдеру "на тебе новый шаред птр, в нем новый конфиг"
тот берет и делает .swap
.swap потокобезопасный, атомарный и няшный вообще nothrow
все старые потоки доработают со старым конфигом, просто в их шаред птре будет уже счетчик на 1 меньше, и он с последним заданием просто подохнет
все новые задания должны взять себе копию шаред птра из холдера
и пусть с ней работают сколько влезет, пока тоже не сдохнут
bormand 22.01.2015 01:12 # 0
defecate-plusplus 22.01.2015 01:19 # 0
у всех своя собственная копия shared_ptr
внутри которого есть shared_count
вот он как раз потокобезопасный, увеличивается на копировании, уменьшается на деструкторе
раз у тебя есть валидный объект shared_ptr, то он твой валидный объект, и каунт в нем больше нуля, значит и объект по этому шаред птр тоже в порядке (если ты не выстрелил сам себе в ногу и не затер эту область памяти смищными картинками с гоатсе)
bormand 22.01.2015 01:25 # 0
Один поток делал свап, а второй попросил прочитать. Есть ли гарантия, что он всегда получит непобитый шаредптр (либо старый, либо новый). И будет ли гарантирована видимость - увидит ли читающий тред в конфиге то, что туда засунул пишущий?
Почему я и предлагал атомиклоад и атомист ор вместо свапа и чтения (у них есть перегрузки для шаредптр).
defecate-plusplus 22.01.2015 01:30 # 0
что значит попросить прочитать
он может только попросить сделать себе копию, которую будет потом использовать сколько захочет
делание копии потокобезопасно, и развязано со swap, т.к. это всё атомарные операции над shared_count
bormand 22.01.2015 01:40 # 0
А у арма подляна есть - weak order. Т.е. Читающий тред может увидеть новый указатель, но старые данные (мусор) по нему, т.к. чтение шло без барьера. Ну и кровь-кишки.
Жалко, что сотик одноядерный, потестить неначем.
defecate-plusplus 22.01.2015 01:51 # 0
тут всё написано, что говорили борманд и лиспговно
http://www.boost.org/doc/libs/1_57_0/libs/smart_ptr/shared_ptr.htm#ThreadSafety
eco-terrorists win
LispGovno 22.01.2015 01:56 # 0
LispGovno 22.01.2015 01:41 # −1
LispGovno 22.01.2015 01:50 # 0
По сути указатель скопировали во втором потоке, затем в первом мы убили старый и заменили на новый и вот у нас дохлый в скопированным в треде2
defecate-plusplus 22.01.2015 02:03 # 0
я уже выше предоставил ссылку, что одновременная запись и чтение одного шаред птр может приводить к говну при удачном стечении обстоятельств - можно создать новый шаред птр со старым указателем и новым каунтером, и потом в будущем наткнуться на освобожденную память, либо дважды освободить её (т.к. сама по себе операция swap и операция = в бусте сделана оптимистично)
но в твоем примере, если представить, что операции swap и операции = атомарны, ты либо будешь читать хороший, годный int(1), либо хороший, годный int(2) - т.к. захватишь себе либо старую копию, либо уже новую
потенциально дохлый int(1) с каунтером от int(2) ты получишь только при действительно (не)удачных обстоятельствах
LispGovno 22.01.2015 02:10 # +2
Ты мне предлагаешь ПРЕДСТАВИТЬ что операции атомарны и после этого с чувством уверенности писать падающую прогу? У меня уже бомбит
bormand 22.01.2015 07:22 # 0
Горький опыт подсказывает, что с потоками лучше не представлять... Вот такой код же имелся в виду? A shared_ptr instance can be "read" (accessed using only const operations) simultaneously by multiple threads. Different shared_ptr instances can be "written to" (accessed using mutable operations such as operator= or reset) simultaneously by multiple threads (even when these instances are copies, and share the same reference count underneath.)
Any other simultaneous accesses result in undefined behavior.
У нас как раз any other (один тред пишет в swap'е, второй читает в конструкторе копирования). На интеле будет работать из-за его strong ordering'а. А вот на ARM'ах, с их достаточно вольным обращением с кешами, я что-то очкую, от реализации конструктора копирования в boost::shared_ptr очень сильно зависит: если там сразу идет инкремент и барьер, то, скорее всего, работать будет, если какое-то неатомарное чтение из управляющего блока - кровь-кишки.
bormand 21.01.2015 23:16 # 0
LispGovno 22.01.2015 00:44 # 0
Dummy00001 09.10.2013 14:33 # 0
> Ну тогда boost::function тоже давно есть
сорри. имел в виду std::bind, результат которого кастится в std::function<void(void)>:
http://stackoverflow.com/questions/13108663/storing-functions-call-and-list-of-parameters-to-invoke-later
> Заменить блокирующую очередь атомарным интом не получится.
не ну про блокировку ни кто и не говорит. блокировка требует дергания ОСи/скедулера, и относительно медленна как ни крути.
самая простая структура на атомиках это stack/LIFO. circular buffer (фиксированого размера) тоже как бы не сильно сложна. знаю народ еще как-то singly-linked list делает, но я еще не догадался как (т.к. я не могу себе представить как они случай пустой очереди обрабатывают.)
> А вот новички могут все грабли собрать.
Новички везде с легкостью могут грабли найти. По себя еще помню...
roman-kashitsyn 09.10.2013 14:40 # 0
Это гарантируется только для std::atomic_flag.
По поводу lock-free: даже то, что рализовано, к примеру, в расширениях гнутых библиотек, часто подходит только для специфичных случаев (типа один писатель, один читатель), надо очень внимательно читать доки. Корректно написатать самому такие вещи крайне сложно.
Dummy00001 09.10.2013 15:27 # 0
Если ты доходишь до уровня таких оптимизаций, то принцип разработки меняется с "мне нужна такая-то структура для увдолетворения требований" на "у меня есть в распоряжении такие-то структуры, вопрос как на них оптимально замапить требования." Другими словами, ты "специфичные случаи" создаются преднамерено в дезайне, а не случайно.
"Корректно написатать самому такие вещи крайне сложно."
True. Граблей очень много.
Хотя сейчас стало легче, потому что на какой 16 процессорно-корной системе можно достаточно хорошо протестировать. Раньше, даже на двух процах, такое тестировать было почти невозможно.
3.14159265 09.10.2013 16:55 # 0
Профита от lock-free тогда нету. Грубо говоря вешаем мьютекс на чтение, мьютекс на запись. Теперь и чтение и запись синхронизированы по одному потоку.
А вот lock-free алгоритмы для очередей тот же классический Michael & Scott они могут обслуживать несколько потоков потребителей и производителей и они умудряются меньше мешать друг другу.
Суть в том что увидев ноду в промежуточном состоянии, другой поток помогает выпилить/связать её. А у первого потока CAS просто выдает false.
Работы делается чуть больше, да. Но она не идёт последовательно как в мьютексе. Плюс нет захвата/освобождения лочки.
Dummy00001 09.10.2013 17:39 # 0
не видел. линк в студию.
"Профита от lock-free тогда нету."
есть. мутексы не бесплатны. по моей метрике, лок/анлок аналогичен "memset(buf,0,128)". в то время как атомики по производительности почти не отличаются от обычных переменных.
3.14159265 09.10.2013 18:43 # 0
Да, согласен.
> в то время как атомики по производительности почти не отличаются от обычных
Нет. Даже volatile считается дорого, если уж быть щепетильным.
mutex>atomic>volatile>usual
3.14159265 09.10.2013 18:46 # 0
http://g.zeos.in/?q=michael%20scott%20lockfree%20queue
Dummy00001 09.10.2013 19:05 # 0
3.14159265 09.10.2013 20:44 # 0
Вот в сжатом виде (чистый код, никаких abstract, описаний, доказательств и бенчей) джва самых известных алгоритма для очередей.
Даже по объему кода видно насколько lock-free сложнее.
Там же видно превосходство мьютексного кода "The two-lock concurrent queue algorithm performs well on under high contention".
Dummy00001 09.10.2013 22:55 # 0
"Даже по объему кода видно насколько lock-free сложнее."
оно не сложнее. просто синхронизационные примитивы в открытую кодируются, потому что стандартные не подходят.
> "The two-lock concurrent queue algorithm performs well on under high contention".
Ты опустил: "Useful for multiprocessors without a universal atomic primitive."
не забывай, этот псевдо код еще с тех времен когда cache coherency была еще эксперементальным хай-эндом и многие из атомарных операций в лоб сбрасывали кэш проца. а локам нужно было сбрасывать кэш как мининмум два раза. вообщем это были страшные времена.
anonimb84a2f6fd141 10.10.2013 02:37 # 0
А сейчас нет?
LispGovno 10.10.2013 06:42 # +1
anonimb84a2f6fd141 10.10.2013 19:35 # 0
И на хуй86 тоже?
LispGovno 10.10.2013 20:05 # 0
anonimb84a2f6fd141 11.10.2013 00:35 # 0
3.14159265 10.10.2013 16:57 # +2
Они сложнее, потому что к ним предъявляются особые требования.
Тривиальный CAS-алгоритм может очутится в такой ситуации что треды мешают друг другу и никто не может выполнить до конца свою операцию, потому что второй (или последний) CAS обламывается, происходит клинч, он же лайвлок. В отличии от дедлока движение не замирает, оно происходит, но это хаотическое движение ни к чему ни приводит.
Примерно такую же патовую ситуацию можно наблюдать в московском метро или банке набитой огурцами - все мешают друг, другу.
В первом случае происходит конкуренция, а нужен качественно другой подход - кооперация, треды помогают друг дружке завершить начатую операцию. Это сильно усложняет дело.
В отличие от мьютексного "кто первый встал тому и тапки", сортир занят - все ждут своей очереди.
И так гарантированно, подчеркиваю _гарантированно_ осуществляется движение вперед.
Вышеупомянутый work-stealing кстати это именно дальнейшее развитие идей кооперации.
С эстетической точки зрения такие алгоритмы невероятно круты и являются произведениями искусства.
Но при реализации на практике, они выглядят крайне непонятно и даже чтоб прочитать и вникнуть требуется немало умственных затрат. В отличие от более тривиального - попробовал захватить лок, не получилось, впал в спячку, пришло уведомление, захватил, поработал, освободил лок.
Dummy00001 10.10.2013 17:54 # +1
Live-lock может происходить на доморощеных реализациях CAS. И факт что в одном потоке CAS обломался означает что один из потоков на самом деле сделал прогресс и что-то записал.
Последний раз когда я занимался этим в плотную, Intel/x86 и PPC32 платформы гарантировали отсутствие live-lock'ов, за счет тривиального тайминга прерываний и доступа к памяти. В случае PPC32, где CAS реализуется несколькими инструкциями и есть реальный шанс live-Lock'а, с официальной реализацией CAS гарантируется что live-lock не случается.
Простой пример. Возвращаясь к ситуации когда один из потоков что-то сумел записать и в других потоках CAS обламался. Это будет значить что в других потоках/на других процах кэш данных для данной ячейки памяти был сброшен и процы должны перечитать ячейку из памяти. Только один проц может читать из ячейки память, что значит что процы выстроятся в очередь пытаясь читать память и вернутся в CAS цикл в разное время.
И самое главное. Если у тебя часто обламывается CAS, то у тебя что-то неправильно реализовано на логическом уровне. Синхронизация, какой бы легковесной она не была, остается "тяжелой" и меньше программа ей пользуется, лучше.
"Вышеупомянутый work-stealing кстати это именно дальнейшее развитие идей кооперации."
Я читал как-то HP'шные документы по HPC оптимизациям (HPC: high performance computing) и честно говоря у меня сложилось впечатление что из-за cache coherency народ такого избегает, потому что тогда "ownership" ячеек памяти постоянно меняется с одного проца на другой.
"[...] и даже чтоб прочитать и вникнуть требуется немало умственных затрат"
Это приходит с опытом. По умственным усилиям не сильно отличается от чтения асма.
LispGovno 10.10.2013 20:16 # 0
Также есть облом касов в лайвлок части потоков в высоконагруженной среде при сильно разном времени выполнении транзакций. У тяжелых есть вероятность уйти в долгий лайвлок, пока нагрузка не спадет, или размеры транзакций не сравняются.
3.14159265 10.10.2013 20:29 # 0
В этом случае дохера данных попусту гоняется всё-равно процесс идёт.
Это как перемещение войск строем хоть и выглядит на первый взгяд тупо, но при большом количестве народу - это есть вынужденная необходимость рационального использования дороги.
И колоннами люди передвигаются быстрее, и компактнее чем врассыпную.
LispGovno 10.10.2013 20:55 # 0
Процесс идет у мелкозернистых транзакций, а у крупных стоит колом и может стоять очень долго, если нагрузка или средняя зернистость не сменится.
Dummy00001 10.10.2013 23:11 # 0
Что такое "фолс шаринг"? http://en.wikipedia.org/wiki/False_sharing ?
Про проблему слышал, но сам по граблям не ходил. Видел в системщине народ по простой целую страницу жертвует что бы избежать проблемы.
"Питухи из стандарта крестов об этом молчат и никакую возможность вычислить размер линии кеша стандартными средствами не дают."
А ее в принципе узнать портабельными средствами невозможно и она даже на внешне одинаковых системах может отличатся. Если на самом деле надо, то делай как системщики: выделяй страницу и ложи туда все что будет доступатся только из одного потока. Выделение страницы дело простое:
posix_memalign( ... sysconf(_SC_PAGESIZE ) ... );
3.14159265 09.10.2013 17:00 # +2
Многопоточный код не "тестируют". Его невозможно тестировать.
Можно только выявить некорректность, но невозможно "тестированием" доказать корректность. Можыд на хасвеле оно будет заебись, а на другой машине с другой памятью, процом оно может поломаться.
А при правильной фазе Луны, когда оно будет в продакшене - может поломаться и на исходной машине.
Это уже не сфера программирования - ололо у меня есть тесты, они проходят и мой код корректен, это сфера математики и теории.
Корректность lock-free алгоритма доказывается нетривиальными математическими рассуждениями. Это вам не assParallel писать.
TarasB 09.10.2013 17:20 # +3
3.14159265 09.10.2013 17:39 # +4
И уж лучше использовать высокоуровневые чужие обёртки, чем самому из примитивов конструировать #12413 велосипеды.
anonimb84a2f6fd141 09.10.2013 19:51 # 0
guest 08.10.2013 19:34 # −2
bormand 08.10.2013 19:35 # +3
Ваш кэп.
P.S. Надо запилить третью кнопку "не говно", чтобы народ наконец-то перестал думать, что заминусованный код кошерен.
guest 08.10.2013 20:49 # −3
bormand 08.10.2013 22:11 # +4
Это повод ее постить? Нет. Ибо код, в котором нет ничего интересного и нового читать скучно. Отсюда и пачки минусов.
3.14159265 09.10.2013 17:32 # +6
Вот они под впечатлением и постят.
Odin 03.11.2018 17:38 # 0
Ты кого говном небезопасным назвал?
guest 11.10.2013 14:37 # −14
guest 11.10.2013 14:40 # −14
guest 11.10.2013 14:40 # −14
PragramistOtBoga 08.10.2013 22:10 # −6
PragramistOtBoga 09.10.2013 03:51 # −7
Stertor 09.10.2013 10:22 # −2
Это типа я тебя витаминами угостил (в школе часто с собой приносили)
)
Stertor 09.10.2013 10:28 # −3
TarasB 09.10.2013 10:28 # +80
Stertor 09.10.2013 10:30 # −2
Stertor 09.10.2013 20:07 # −3
bormand 09.10.2013 20:37 # +1
3.14159265 10.10.2013 13:11 # +1
Stertor 10.10.2013 17:33 # −2
anonimb84a2f6fd141 10.10.2013 18:54 # −2
guest 11.10.2013 13:05 # +2
>anonimb84a2f6fd141
показательно что на пост про долбоёбов ответила только эта парочка.
guest 11.10.2013 14:05 # −1
guest 11.10.2013 14:37 # −13
guest 11.10.2013 14:40 # −12
Dummy00001 09.10.2013 13:03 # 0
ты меня обогнал на день обогнал! я уже собрался постить аналог из моего проекта.
и говно не в количестве return'ов.
после двух дней отладки я наконец понял почему у меня все сообщения об ошибках инициализации синглтона появляются на экране три раза. потому что после первого эксепшена из getInstance() (из init()), в ходе "обработки" ошибок он еще дополнительно два раза вызывается.
чудеса да и только.
guest 11.10.2013 14:38 # −14
guest 15.04.2017 02:26 # 0
Мы коллектив студенток города Москва, продаем наши обнаженные фото 1шт-15р.
Первые 3 фото с твоим именем бесплатно
Сразу после опроса-регистрации можно выбрать свой институт
с нами 967 девушек :)
<a href=http://gelanc.ml/>gelanc.ml</a>