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

Автор WhiteCrow, 12 лет назад, По-русски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • Сначала ресурс свободен (в оперативной памяти, скажем, 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. Это уже будет работать.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -19 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    .

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -12 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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