Игровой тур Всесибирской Олимпиады 2012

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
10	nor	152

О том, насколько было неожиданно и... Сохранил ли кто-нибудь инфраструктуру для запуска решений I номинации?
Итак, хорошая мысль приходит опосля. Начну с того, что о многопоточной структуре я узнал за час до контеста. После обеда пробный тур уже был совсем закрыт, так что с задачей и системой тестирования я знакомился уже на контесте. А так как представление о работе многих потоков хотя бы теоретическое в команде имел только я, пришлось мне одному большую часть и делать.
Уже в поезде пришли в голову несколько идей. Во-первых, "почти наверняка" компилятор С++ уоптимизирует декремент и проверку на ноль до атомарной операции (как скорее всего и ((a-=13)==0)). А это позволяет после небольших раздумий получить синхронизацию, причём ОЧЕНЬ быструю. Во-вторых, ассемблерные вставки. Я как-то уже забыл, что они существуют, а запретов я не видел, особенно если учесть, что это не АСМ тур. Поэтому хотелось бы попробовать написать и посмотреть, будет ли адекватно работать.
Но так получилось, что у меня осталась инфраструктура только для Java. Может кто-нибудь выложить?

Комментарии (19)

Написать комментарий?

andreyv

12 лет назад, # |

← Rev. 2 →

Ага, как же. Во-первых, "почти наверняка" не считается. Во-вторых, допустим, что это действительно так. Тогда возможно такое:

Сначала ресурс свободен (в оперативной памяти, скажем, a = 1).
Поток на процессоре 1 делает ((a-=1)==0), видит, что ресурс был свободен, начинает с ним работать. Значение a = 0 записывается в кеш процессора 1 (но ещё не в оперативную память).
Поток на процессоре 2 делает ((a-=1)==0), считывает из памяти оставшееся там a = 1, видит, что ресурс был свободен, начинает с ним работать.
Fail

Вместо ассемблерных вставок можно использовать встроенные функции компилятора, такие, как http://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html. Это уже будет работать.

→ Ответить

WhiteCrow

12 лет назад, # ^ |

-18

Очень интересно!
Во-первых, "почти наверняка" не зря в кавычках, это термин из теории вероятностей. Например, почти наверняка процессор не глюканёт во время выполнения одной из указанных вами функций. Скажем так, я не представляю, какими должны быть обстоятельства, чтобы компилятор решил сделать лишнюю проверку на равенство нулю. Ну, при условии, что он оптимизирует код.
Во-вторых, вы не поверите, кэш синхронизирован. Ключевое слово для поиска — MESIF. А как по-вашему реализованы те функции, о которых вы говорили?
В-третьих, интересно то, что по поводу ассемблерных вставок вы не стали спорить. Но ведь при выполнении первого пункта они могут не больше, чем указанный код на C++, не так ли?
Ну и наконец... Про то, что я был не очень готов к работе с многопоточностью я сказал. По сути я знал только про synchronized и Thread в Java. Так что встроенные функции использовать не удалось бы.

Хорошо, но это всего лишь одно из слабых мест. Основная проблема в том, что при использовании обычных инструкций мы никаким образом а) не гарантируем атомарность их выполнения (в ++a есть две под-операции: чтение и запись) и б) не ограничиваем "критическую секцию". Из-за а) синхронизация может просто не работать так, как задумывалось, а из-за б) может оказаться, что программа использует общую память до/после блокировки самодельных мьютексов — потому что компилятор и процессор могут переставлять инструкции по желанию, если это явно не запрещено.

Какими долны быть обстоятельства, чтобы это не скомпилировалось в одну инструкцию? Разные, к примеру, компилятор недостаточно умный, или же процессор не имеет подходящей инструкции (да, такие тоже есть). Да и даже если это одна инструкция, то она необязательно выполнится атомарно по отношению к другим процессорам. В общем-то, важно лишь то, что искомое утверждение ничем не гарантировано, и на него нельзя полагаться.

Как реализованы встроенные функции из GCC/функции из библиотек типа pthreads? Они решают проблему а) с помощью специальных атомарных инструкций/операций (например, CMPXCHG) и проблему б) с помощью memory barriers (см. http://en.wikipedia.org/wiki/Memory_barrier ).

В общем, лучше не париться и просто использовать pthread_mutex_lock и pthread_mutex_unlock, чем в 1 раз из 100 словить глюк на самописном коде.

nk.karpov

есть стандартные и более низкие вещи чем mutex

RodionGork

(страшно сказать, на одном из собеседований требовали написать софтварную синхронизацию, т.е. вообще на volatile-ах)

-19

а) ++a будет скомпилирована в инструкцию инкремента. Она не менее атомарна, чем CMPXCHG.
б) Компилятор и процессор могут переставить инструкции при условии, что не портится логика. if(--a){ ... }. ... будет выполняться только после того, как процессор будет уверен, что в результате декремента получился ноль. Строго говоря, он начнёт выполнять раньше, пытаясь предугадать возможное развитие последствий, но результат будет записан только после того, как будет ноль.
Компилятор достаточно умный, чтобы проверять такие вещи, потому что они часто используются. Да, спасибо, я знаю, что такие процессоры есть, но спецификация задачи явно указывает процессор, который имеет инструкцию декремента.
Искомое утверждение не гарантировано. Цель была собственно проверить, насколько всё это было бы работоспособно, об этом я вроде как сказал. Про CMPXCHG и другие функции я уже тоже сказал.

agul

В NSUTS (новосибирской системе тестирования), если я не ошибаюсь, стоит noasm, который проверяет на наличие ассемблерных вставок все посылки, так что, скорее всего, посылку бы срезали.

droptable

Типа игра "угадай на какой платформе/ОС" мы тестируем? И кстати data execution protection вроде есть на многих современных платформах... %)

И главное неужели так велика уверенность что переписав таким образом часть кода можно страшно увеличить производительность изобретаемой конкуррентной хэшмэпы?

По-моему вставки такого рода имеют только академический интерес (в духе, "получится ли у нас ребутнуть judge-а)

package.zaic

Инфраструктура. Вроде именно та, которая давалась участникам на контесте.

Prestige

А что за задание?

Видимо вот это

А точное условие задачи сохранилось у кого-нибудь. Или кто-то максимально точно вспомнить может? Хотя наверное по executor-у можно восстановить попытаться. Интересуют подробности определения "производительности"...

Tinkturianec

точнее этого ничего, вроде, не было

mr146

Не только ты имел представление — у Миши Рубинчика был целый семестр курса по этой штуке, и он по нему получил автоматом 5. ;)

-12

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

Он распараллелил Флойда, можешь спросить у Бахтерева. Так что то, что он ничего не делал на контесте кроме перечисленного тобой — наверняка просто нежелание заниматься неинтересной для него задачей, желание потроллить тебя как следует и просто твое неумение убеждать и общаться с Мишей.

Я помню, что он спрашивал у меня как-то, как можно параллелить Флойда. Я ему рассказал. Так что можешь не выдавать за его идеи=)
По поводу неумения общаться с Мишей, а так же с тем, что он пытался потроллить, я согласен. Впрочем, ты меня тоже сейчас пытаешься троллить, зачем-то наехал. Непонятно, что я такого обидного для тебя успел сказать?

Да я не попытался наехать, просто сказал, что ты не один хоть что-то знаешь о многопоточности в команде.

Блог пользователя WhiteCrow