О том, насколько было неожиданно и... Сохранил ли кто-нибудь инфраструктуру для запуска решений I номинации?
Итак, хорошая мысль приходит опосля. Начну с того, что о многопоточной структуре я узнал за час до контеста. После обеда пробный тур уже был совсем закрыт, так что с задачей и системой тестирования я знакомился уже на контесте. А так как представление о работе многих потоков хотя бы теоретическое в команде имел только я, пришлось мне одному большую часть и делать.
Уже в поезде пришли в голову несколько идей. Во-первых, "почти наверняка" компилятор С++ уоптимизирует декремент и проверку на ноль до атомарной операции (как скорее всего и ((a-=13)==0)). А это позволяет после небольших раздумий получить синхронизацию, причём ОЧЕНЬ быструю. Во-вторых, ассемблерные вставки. Я как-то уже забыл, что они существуют, а запретов я не видел, особенно если учесть, что это не АСМ тур. Поэтому хотелось бы попробовать написать и посмотреть, будет ли адекватно работать.
Но так получилось, что у меня осталась инфраструктура только для Java. Может кто-нибудь выложить?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | Petr | 145 |
| 9 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.05.2024 21:21:27 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Ага, как же. Во-первых, "почти наверняка" не считается. Во-вторых, допустим, что это действительно так. Тогда возможно такое:
((a-=1)==0), видит, что ресурс был свободен, начинает с ним работать. Значение a = 0 записывается в кеш процессора 1 (но ещё не в оперативную память).((a-=1)==0), считывает из памяти оставшееся там a = 1, видит, что ресурс был свободен, начинает с ним работать.Вместо ассемблерных вставок можно использовать встроенные функции компилятора, такие, как http://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html. Это уже будет работать.
Очень интересно!
Во-первых, "почти наверняка" не зря в кавычках, это термин из теории вероятностей. Например, почти наверняка процессор не глюканёт во время выполнения одной из указанных вами функций. Скажем так, я не представляю, какими должны быть обстоятельства, чтобы компилятор решил сделать лишнюю проверку на равенство нулю. Ну, при условии, что он оптимизирует код.
Во-вторых, вы не поверите, кэш синхронизирован. Ключевое слово для поиска — 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 словить глюк на самописном коде.есть стандартные и более низкие вещи чем mutex
(страшно сказать, на одном из собеседований требовали написать софтварную синхронизацию, т.е. вообще на volatile-ах)
а)
++aбудет скомпилирована в инструкцию инкремента. Она не менее атомарна, чемCMPXCHG.б) Компилятор и процессор могут переставить инструкции при условии, что не портится логика.
if(--a){ ... }....будет выполняться только после того, как процессор будет уверен, что в результате декремента получился ноль. Строго говоря, он начнёт выполнять раньше, пытаясь предугадать возможное развитие последствий, но результат будет записан только после того, как будет ноль.Компилятор достаточно умный, чтобы проверять такие вещи, потому что они часто используются. Да, спасибо, я знаю, что такие процессоры есть, но спецификация задачи явно указывает процессор, который имеет инструкцию декремента.
Искомое утверждение не гарантировано. Цель была собственно проверить, насколько всё это было бы работоспособно, об этом я вроде как сказал. Про
CMPXCHGи другие функции я уже тоже сказал.В NSUTS (новосибирской системе тестирования), если я не ошибаюсь, стоит
noasm, который проверяет на наличие ассемблерных вставок все посылки, так что, скорее всего, посылку бы срезали..
Типа игра "угадай на какой платформе/ОС" мы тестируем? И кстати data execution protection вроде есть на многих современных платформах... %)
И главное неужели так велика уверенность что переписав таким образом часть кода можно страшно увеличить производительность изобретаемой конкуррентной хэшмэпы?
По-моему вставки такого рода имеют только академический интерес (в духе, "получится ли у нас ребутнуть judge-а)
Инфраструктура. Вроде именно та, которая давалась участникам на контесте.
А что за задание?
Видимо вот это
А точное условие задачи сохранилось у кого-нибудь. Или кто-то максимально точно вспомнить может? Хотя наверное по executor-у можно восстановить попытаться. Интересуют подробности определения "производительности"...
точнее этого ничего, вроде, не было
Не только ты имел представление — у Миши Рубинчика был целый семестр курса по этой штуке, и он по нему получил автоматом 5. ;)
Что-то ты не то говоришь, потому что он мне абсолютно отчётливо сказал, что не разбирается в этом совсем. Это было причиной, по которой от него не было почти никакой пользы, кроме вычитывания исходника и поиска логических ошибок.
Он распараллелил Флойда, можешь спросить у Бахтерева. Так что то, что он ничего не делал на контесте кроме перечисленного тобой — наверняка просто нежелание заниматься неинтересной для него задачей, желание потроллить тебя как следует и просто твое неумение убеждать и общаться с Мишей.
Я помню, что он спрашивал у меня как-то, как можно параллелить Флойда. Я ему рассказал. Так что можешь не выдавать за его идеи=)
По поводу неумения общаться с Мишей, а так же с тем, что он пытался потроллить, я согласен. Впрочем, ты меня тоже сейчас пытаешься троллить, зачем-то наехал. Непонятно, что я такого обидного для тебя успел сказать?
Да я не попытался наехать, просто сказал, что ты не один хоть что-то знаешь о многопоточности в команде.