Компания
172,35
рейтинг
25 апреля 2014 в 08:50

Разработка → Потоки — это Goto параллельного программирования

Сразу раскрою мысль, вынесенную в заголовок. Использование потоков (также именуемых нити, треды, англ. threads) и средств прямой манипуляции ими (создание, уничтожение, синхронизация) для написания параллельных приложений оказывает столь же пагубное влияние на сложность алгоритмов, качество кода и скорость его отладки, какое вносило использование оператора Goto в последовательных программах.
Как когда-то программисты отказались от неструктурированных переходов, нам необходимо отказаться от прямого использования потоков сейчас и в будущем. И так же, как каждый из нас использует структурные блоки вместо Goto, вместо потоков должны использоваться структуры, построенные поверх них. Благо, все инструменты для этого появились во вполне традиционных языках.
Автор фото: Rainer Zenz


Сперва — немного истории и отсылок с уже состоявшимся обсуждениям.

Goto considered harmful


Наверное, самый авторитетный гвоздь в гроб несчастного оператора в своё время вбил Эдсгер Дейкстра в своей пятистраничной статье 1968 года «A Case against the GO TO Statement», также известной как «Go-to statement considered harmful».

На Хабре тема использования/изгнания Goto из программ на языках высокого уровня поднималась неоднократно:
habrahabr.ru/post/114211
habrahabr.ru/post/114470
habrahabr.ru/post/114326
Несомненно, существование Goto — источник нескончаемого холивара. Однако современные языки «общего назначения», приблизительно начиная с Java, не включают в свой синтаксис Goto, по крайней мере в его первозданном виде.

Где Goto ещё в ходу

Отмечу одно часто применяемое, но ещё не упомянутое применение операции прыжка по метке, которое лично меня касается достаточно сильно: языки ассемблера и машинные коды. Практически все архитектуры микропроцессоров имеют инструкции условных и безусловных переходов. Более того, я не припомню ассемблера, в котором аппаратно сделан оператор for или while. В результате программисты, работающие на этом уровне абстракции, вынуждены разбираться со всей мешаниной нелокальных переходов. У Дейкстры по этому поводу есть замечание: "...goto должен быть изгнан из всех высокоуровневых языков (т.е. отовсюду, кроме — может быть — простого машинного кода)" [в оригинале: «everything except —perhaps— plain machine code»].

Опущу описание всех известных аргументов против Goto; желающие могут найти их по ссылкам выше. Напишу сразу вывод, как его понимаю я: использование Goto значительно понижает «высокоуровневость» кода, пряча алгоритм в деталях последовательной реализации. Перейдём лучше к потокам.

В чём заключается проблема потоков


Для формулировки того, где ожидать проблем от тредов, обратимся к статье Edward A. Lee «The Problem with Threads». Её автор попытался привести некоторый формализм (по-моему, излишний) для объяснения следующего факта. Прямое использование потоков требует анализа всех возможных чередований базовых операций, составляющих отдельные нити исполнения. Число таких комбинаций растёт лавинообразно при увеличении размера приложения и быстро превосходит возможности человеческого восприятия и инструментов анализа. Т.е. полностью отладить такую параллельную программу становится невозможно, не говоря уж о формальных доказательствах корректности.
Кроме этого важнейшего аспекта, программирование на потоках (например, на Pthreads) неоптимально просто с точки зрения производительности как программиста, так и результирующего приложения.
  1. Отсутствие свойства композиции. Вызывая из потока некоторую библиотечную функцию, без анализа её кода нельзя сказать, не породит ли она ещё несколько параллельных нитей исполнения и тем самым превысит возможности аппаратуры (т.н. oversubscription).
  2. Параллелизм на потоках невозможно сделать необязательным. Он всегда присутствует и жёстко зашит в логику программы несмотря на то, что в реальности два связанных процесса не всегда должны работать одновременно; часто решение должно приниматься динамически с учётом текущей обстановки и наличия ресурсов.
  3. Сложность обеспечения механизмов балансировки. Даже небольшой перекос в скоростях работы разных потоков может существенно ухудшить производительность всего приложения («караван идёт со скоростью самого медленного верблюда»). Все заботы о том, чтобы аппаратура была равномерно нагружена, перекладываются на прикладного программиста, у которого может и не быть достаточно информации об обстановке в системе. Да и не его это дело, в общем-то — он должен решить прикладную задачу.


Вывод почти дословно повторяет тот, что был сделан чуть выше: использование потоков значительно понижает «высокоуровневость» кода, пряча алгоритм в деталях параллельной реализации. «Ручное управление» потоками в программе, написанной на языке высокого уровня, обнажает многие детали нижележащей аппаратуры, которые при этом видеть не хочется.

Что же, если не потоки?


Как же использовать возможности многоядерной аппаратуры, не прибегая к потокам? Конечно же, есть различные языки программирования, изначально спроектированные с расчётом на эффективное написание параллельных программ. Тут и Erlang, и функциональные языки. Если нужна экстремальная масштабируемость решения, следует искать ответ в них и предлагаемых ими механизмах. Но что делать программистам, использующим более традиционные языки, например, Си++, и/или работающих с уже существующим кодом?

OpenMP — хорошо, да не то

Довольно долго ни в С, ни в C++ (в отличие от, например, более «молодой» Java) наличие параллелизма в программах никак не было отражено, т.е. фактически было отдано на откуп «сторонним» библиотекам вроде Pthread. Довольно давно известен OpenMP, вносящий структурированный fork-join параллелизм в эти языки, а также в Fortran. По моему мнению, этот стандарт не приносит решений, связанных указанными выше проблемами потоков. Т.е. OpenMP — всё ещё слишком низкоуровневый механизм. Последняя ревизия стандарта не предложила повышения уровня абстракции, а добавила возможностей (и сложностей) тем, кто хочет с помощью OpenMP пускать коды на гетерогенных системах (подробнее про версию 4.0 писали на Хабре).

Расширения и библиотеки

Между новыми языками, изначально пытающимися поддержать параллелизм, и традиционными языками, полностью его игнорирующими, лежат расширения — попытки добавить необходимые абстракции и закрепить их в синтаксисе, — и библиотеки — завёрнутые в уже существующие концепции языка (такие как вызов подпрограмм) решения проблем. Расширения языков теоретически позволяют добиться лучших результатов, чем библиотеки, ведь с их помощью мы вырываемся из ограничений исходного языка, создавая новый. Но очень нечасто такие расширения завоёвывают популярность у широкой аудитории пользователей. Признание зачастую приходит только после стандартизации такого расширения как части языка.

Расширениями языков и библиотеками, в том числе для параллельного программирования, занимаются многие компании, университеты и комбинации оных. У Intel, есть, конечно же, много раз упоминавшиеся на Хабре варианты и первого, и второго: Intel Cilk Plus, Intel Threading Building Blocks. Выражу своё мнение, что Cilk (Plus) более интересен как средство повышения уровня абстракции параллелизма чем TBB. Радует наличие поддержки его в GCC.

C++11

В последних стандартах С++ параллельная природа современных вычислений наконец-то получила признание; возможность кода исполняться одновременно с чем-то ещё учитывается при описании многих языковых конструкций и стандартных классов. Причём на выбор программисту даётся широкий диапазон уровней абстракций: от прямого манипулирования потоками через std::thread, через асинхронный вызов std::packaged_task до асинхронного/ленивого вызова std::async. Большая работа по обеспечению исправной работы всей этой машинерии сдвигается со сторонних библиотек на стандартную, поставляемую с компилятором, реализующим возможности нового стандарта. Открытым (по крайней мере для меня) вопросом является следующий: существуют ли уже реализации C++11, обеспечивающие все три свойства высокоуровневого параллелизма: композицию, необязательность и балансировку, и тем самым освобождающие от этих забот прикладного программиста.

Что ещё почитать


Напоследок хочу поделиться одной книгой. Главная её идея для меня заключается в том, что необходимо внесение понимания о существовании структуры у параллельных приложений в процесс их проектирования. Более того, необходимо обучать этому студентов максимально рано, примерно в то же время, когда им объясняют, почему«goto — это плохо».

Michael McCool, Arch Robison, James Reinders. Structured Parallel Programming — 2012 — parallelbook.com.

В книге, в частности, показаны решения одних и тех же задач с использованием нескольких библиотек/языков параллельного программирования: Intel Cilk Plus, OpenMP, Intel TBB, OpenCL и Intel ArBB. Это позволяет сравнить выразительность и эффективность указанных подходов в различных условиях практических задач.

Спасибо за внимание!
Автор: @Atakua
Intel
рейтинг 172,35

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

  • +6
    Linux: Using goto In Kernel Code
    archive.today/9LWN
    kerneltrap.org/node/553
    • +2
      Да в C коде его постоянно используют за неимением альтернатив
      • 0
        А какие альтернативы имеются в виду? Я считал, что код на C99 (и, возможно на более раннем, с потерей производительности) с goto — можно переписать структурно…
        • +2
          Ну традиционный пример: выход из глубоко вложенных циклов и условий (актуально, скажем, при отсутствии исключений в качестве альтернативы).
          Переписать структурно-то можно, но код будет медленнее и дико запутанным.
          • 0
            Полностью согласен, сам считал goto плохим стилем до того момента, пока не начал программировать на C. Иногда с его помощью получается куда более читабельный код. Да и не зря некоторые называют C макроассемблером.

            Но в моем мире на C++, например, уже распространяется правило, что goto это не есть хорошо, хотя бы потому, что там RAII. Да и вообще больше возможностей написать код лучше.
          • 0
            Ну традиционный пример: выход из глубоко вложенных циклов и условий

            Циклы заворачиваются в функцию; вместо goto вызывается return.
            • +3
              Параметров передаётся при этом 20, конечно, но зато return вместо goto.
              • 0
                Как говорится у функции может быть 0 параметров, 1 параметров, 2 параметра, 3 параметра, слишком много параметров. Если имеется 20 параметров, то вы явно делаете что-то не так. все это заворачивается в структуру и передается одна структура.
                • +1
                  Угу. Заворачиваем всё в объекты (или эмулируем их структурами). Иначе говоря, уходим всё выше и выше, объём кода необходимого для поддержания «структурности» всё больше и больше. На выходе — Java, когда на одну строчку кода может приходиться до 40 строк всего остального.
                  Оттуда и появляются IDE, которые генерят эти самые 40 строк…
                  • –2
                    Структуру передать ничем не медленнее, чем 2 параметра. И да, goto не поругается только на уровне ассемблера. С уже достаточно высокоуровневый язык, чтобы на нем писать читабельные программы, не теряющие от этого в скорости…
                    • 0
                      Сложно сказать, что читабельнее — goto cleanup, или функция на каждый уровень вложения объектов

                      int main()
                      {
                        context ctx;
                        foo* = createFoo();
                        do_something_with_foo(&ctx, foo);
                        free(foo);
                      }
                      
                      void do_something_with_foo(context* ctx, foo* foo)
                      {
                        if (foo_is_bad(foo)) return;
                        char* bar = malloc(100);
                        ctx.foo = foo;
                        do_something_with_bar(ctx, bar);
                        free(bar);
                      }
                      
                      void do_something_with_bar(context* ctx, bar* bar)
                      {
                        for (int i = 0; i < 100; i++) if (rand() & 3) return;
                        printf("bar is a winner!\n");
                        win(ctx.foo, bar);
                      }
                      
                      
        • 0
          RAII в C++, scoped в D

          Некоторые компиляторы даже extension сделали чтобы реализовать подобный функционал в C stackoverflow.com/a/368731/61505
  • +10
    Хм… На тему аппаратных циклов — DJNZ у 8051, LOOP у 80x86, REP* префисы у 80x86.
    • +1
      А еще REPEAT и DO на архитектуре PIC24 и dsPIC33. Удобство написания циклов этими инструкциями не повышается, но зато не тратятся такты на исполнение заголовка цикла! Тем самым отпадает необходимость в «разматывании циклов» там, где требуется высокое быстродействие.
      • +1
        Как всегда — на уровне машинного кода жертвуем удобством ради скорости :-).
    • +4
      Про DJNZ и LOOP. Логика у них одинаковая: уменьшить регистр на единицу и, если он не ноль, прыгнуть по смещению, Т.е. это всё-таки «условие плюс goto». Это не привносит структуры в программу на машинном коде. Задача слежения за ней всё ещё остаётся на плечах программиста. Я всё ещё могу написать так:

      label1:

      label2:

      loop label1:

      loop label2:

      Т.е. «циклы» будут пересекаться. Никакой структуры.

      Про REP*. Так как префиксы позволяют зациклить только единственную инструкцию, то они не создают свойства композиционности (возможность цикла в цикле). Вообще строковые команды — это некий архаизм, а на REP префиксы ныне активно навешивают новые смыслы (например, для HLE они превратились в XACQUIRE и XRELEASE).

      Мне кажется, что, если бы язык Brainfuck имел аппаратную реализацию, то инструкции, соответствующие его операторам [ и ], как раз служили бы задаче обеспечения циклов со структурой на машинном уровне.
      • +1
        Кстати, еще у TriCore очень вкусные реализации циклов:
        Four special versions of conditional jump instructions are intended for efficient
        implementation of loops: JNEI, JNED, LOOP and LOOPU. These are described in this
        section.

        Если говорить про языки — то у Forth вроде были очень приятные циклы, и они есть в аппаратной реализации.

        На тему пересечения циклов… На одних repeat {} until(true); + break можно нагородить кашу не меньше, чем из JMPов.

        Так что давай те будем честными — аппаратные циклы есть в процессорах. А то, что на них можно понаделать — это уже второй вопрос.
        • +1
          Если говорить про языки — то у Forth вроде были очень приятные циклы, и они есть в аппаратной реализации.

          Forth — это вообще для меня яркий просвет во тьме недоразумений машинных языков. Элегантный и мощный.
          • +1
            Жаль, что его возможностей по эффективной реализации недостаточно для топа.
            Зато он идеален для многих встраиваемых решений.

            Жаль, не взлетел.
    • –2
      Автор писал про циклы с пред-условием (for или while), а эти примеры — с пост-условием (repeat...until).
      • 0
        собственно, CJNE у 8051 прекрасно для пред-условий подходят:
        CLEARBUF:
        ; for(
        MOV R0, #BufBegin; void *i=buf;
        LoopFor:
        CJNE R0, #10, LoopBody; i<=buf+10;
        RET
        LoopBody:
        MOV @R0, #0; *buf =0;
        INC R0; i++)
        SJMP LoopFor

        Впрочем, я согласен, что структурированность уже не очень, исходный посыл последовательности _НАПИСАНИЯ_ действий разрушен. а вот последовательность ИСПОЛНЕНИЯ — как раз чиста и пыщпыщна.
  • +3
    Спасибо за книгу! Вот ещё пара отличных:

    Ссылки с сайтов издателей, цены там завышены. Обычно можно найти дисконт или магазин, где подешевле.

    На lektorium есть курс по параллельному программированию от Евгения Калишенко, там тоже объясняется, почему использовать потоки напрямую сложно и редко нужно.
    • +1
      Офигенный курс! Спасибо за ссылку.
    • +2
      Вот ещё одна интересная пишущаяся в данный момент книга:Seven Concurrency Models in Seven Weeks.
      • 0
        Спасибо за ссылку, посмотрю!
  • +6
    Между новыми языками, изначально пытающимися поддержать параллелизм
    А вот в Go всё относительно просто Go Parallel, Go Parallel 2, Go Parallel 3. Кроме того, в Go встроен гугловский Thread Sanitizer Go Race Detector, который отлавливает большинство ошибок, каких мог наляпать начинающий любитель goto и обращений к одним участкам памяти из разных потоков.
    • +1
      Плюсую. А ещё, когда привыкаете к подходу Go share memory by communicating, его же можно применять и на других языках, и ваши многонитевые алгоритмы становятся мягкими и шелковистыми.
    • 0
      Есть некоторая ирония в том, что в Go не только есть goto, но и иногда через него проще всего реализовать такие структурные блоки, как например в перл*:
      for {
      ...
      } continue {
      ...
      }
      
      * блок continue выполняется после каждой итерации for, даже если она была прервана посредине оператором next, очень удобно для циклов где возможно прерывание итерации (но не цикла) вследствии ошибки
      • +2
        В Go goto имеет меньше прав, чем в C, с goto нельзя прыгнуть за пределы variable scope, поэтому с ним наговнокодить гораздо сложнее.
  • +2
    Вот начитаются такого программисты и пишут потом bruteforce в один тред! :-D

    На самом деле НЕ ВСЕ задачи порождают излишнюю сложность при многопотоковости, не во всех задачах нужна синхронизация сложнее bool stop = false и т.д. И не во всех задачах нужен параллелизм, IMHO впихивать его туда где он не нужен — примерно такое же зло.
  • +8
    При разработке на си — goto вполне себе стандартный паттерн нетривиального досрочного завершения функций. А высказывание в заголовке — бред, т. к. оператор языка и механизм операционной системы сравнивать не корректно.
    goto -> циклы довольно простой переход. В большинстве случаев программисту нужен не goto а именно цикл, поэтому такой переход очевидный и в большинстве случаев всё сильно упрощает.
    Ручное управление потоками и синхранизацией нельзя заменить на единый и подходящий в 99% более простой механизм. Существует огромное количество паттернов многопоточности и в зависимости от задачи может быть необходимо как простое распараллеливание циклов, так и многопоточная очередь, producer->consumer и т. п. А ещё из всего этого нужно как-то работать с ассинхронным вводом / выводом.
    • –5
      | себе стандартный паттерн нетривиального досрочного завершения функций.
      return?
      • +10
        Во время работы функции инициализируются разного рода структуры другими функциями. и в конце функции есть метка (:fail или :error) в которой происходит очистка этих структур в случае сбоя. Был бы это С++ — всё сделали бы деструкторы. А в C приходилось так вот заморачиваться, чтобы не повторять нарастающий, как снежный ком, список функций освобождения ресурсов после вызова каждой функции, в которой что-то может пойти не так.
        • 0
          Поторопился я выше писать, Вы уже изложили мою идею =\
      • +4
        Сишный goto-defensive-programming во всей красе проявляется в модулях ядра, когда в процессе создания устройства (например) что-то может отвалиться и в таком случае нужно откатить все внесённые изменения, но не более, хвосты у функций инициализации обычно выглядят так:
        	out_devcreate: destroy_created_devices(created_num, poums_class);
        	out_devinit: deinit_poums_devices(init_num);
        	out_class: class_destroy(poums_class);
        	out_reg: unregister_chrdev_region(first, num);
        
        	return err;
        

        И в зависимости от того, на каком этапе произошла ошибка, в ту часть этого хвоста и попадаем.
    • +1
      Ручное управление потоками и синхранизацией нельзя заменить на единый и подходящий в 99% более простой механизм.
      То, что пока такой механизм не придумали, не означает, что его нельзя придумать. Скажем, транзакционная память способна избавить от многих проблем параллельного программирования.
      • 0
        Про транзакционную память и её «обещания об избавлении» я также хочу как-нибудь написать статью для Хабра. Пока что есть серия постов на IDZ про её аппаратные воплощения: 1, 2, 3, 4.
  • 0
    Я бы воздержался от категоричных высказываний по поводу потоков. Есть 2 типа приложений, надо которыми я работаю.
    Первый тип занимается обработкой данных и должен решить задачу как можно быстрее. Соответственно нужно загрузить все ядра и параллельно выполнить на них работу. Как это сделать? Без потоков никак.
    Второй тип, это обычное десктоп приложение. В нем, в главном потоке идет обработка run-loop и любая сколько-нибудь тяжелая задача в главном потоке скажется на отзывчивости приложения. Как бороться? Сделать отдельный пул рабочих потоков для фоновых задач, в которых доставать задачи из очереди и обрабатывать.
    т.е. решений достаточно много и нельзя говорить, что «потоки — зло». Да, надо думать о синхронизации доступа к ресурсам, делать доступ к общим ресурсам в одном и том же порядке, может даже использовать новомодные lock-free структуры. Но страшного или плохого в этом ничего нету.
    • +7
      Автор не говорит, что потоки это плохо. Он говорит, что это слишком низкоуровневый инструмент (также как goto), и призывает использовать более высокоуровневые абстракции, а именно (поскольку пост в блоге Интел) что-то вроде Intel Thread Building Blocks (TBB) и Intel Cilk+.
      • –3
        Ну, это очень зависит от языка. В Си это так. На высоком/интерпретируемом уровне, например, на том же Python, потоки + Exceptions + threading.Event порождают довольно читаемый и производительный код.
    • +5
      Статья, вообще-то, не про отказ от потоков, а про необходимость закрытия их дополнительными уровнями абстракции.
    • +5
      Мне кажется что вы не поняли про что статья, в ней же не предлагается всем писать однопоточные приложения. Как я понял речь идет о том чтобы заменить в программах низкоуровневые абстрации (создать поток, синхронизовать ресурс) на другие более высокоуровневые абстракции.
    • –3
      Полностью поддерживаю. Думаю, что содержимое статьи в большей степени применимо к случаям перемалывания данных. Случай же структуризации всего приложения не освещен.
  • +3
    Эппл вместо потоков предлагает свой Grand Central Dispatch. Жаль только, что его толком не портировали платформы, отличные от их OSX/iOS.
    • +1
      Я хоть с экосистемой Apple по жизни почти не сталкиваюсь, тоже часто жалею о том, что их GCD не взлетел кроссплатформенно. С другой стороны, Apple протолкнуло OpenCL, за что им спасибо.
    • +2
      зашёл в тред чтобы написать про GCD. Все проблемы, описанные в топике прекрасно им решаются. Вся балансировка и абстрагирование возлагается именно на него, а программист уже пишет вполне понятный код.
      А то что не портировали — это да, несмотря на открытость кода, как то не спешат взять этот прекрасный инструмент
  • 0
    Более того, я не припомню ассемблера, в котором аппаратно сделан оператор for или while.

    А я могу вспомнить и даже не одну реализацию на различных архитектурах. Используется обычно мнемоника loop. Причем есть loop'ы как по аппаратному счетчику (for-like), так и по условию (while-like).

    Код может выглядеть примерно так:
        loop    15, endloop1
        nop
        nop
        nop
    endloop1:
        nop
    
    • 0
      Я попробовал объяснить это своё высказывание на примере с loop здесь:
      habrahabr.ru/company/intel/blog/206030/#comment_7532679
      Т.е. дело не в автоматическом счёте операций, а «скобках», создающих структуру.
  • +2
    На фото новое лого хабра?
    • 0
      Всего лишь запутанные нити шафрана. Но аналогия с логотипом хороша :-)
  • 0
    Нам преподаватель по ЯП в универе как то выдал — «только алкоголики боятся пить в одиночку», когда ему сделали замечание по поводу использованного goto в коде.
  • +1
    Да, полностью поддерживаю, как только я узнал что в хаскеле ввод-вывод по умолчанию неблокирующий и платформа сама порождает нечто типа green threads я понял что потоки и всякая явная асинхрощина (особенно на коллбеках, типа nodejs), это что-то вроде разработки на ассемблере — низкий уровнь, а значит низкая эффективность программиста
  • 0
    На правах редактора замечу, что первую проблему (названную «отсутствие композиции») решает нормальная документация, а как раз OpenMP решает вторую проблему " необязательности параллелизма".
    И еще — вот очень интересная штука www.hoopoesnest.com/cstripes/cstripes-sketch.htm
  • –1
    На каждый файл — свой поток, который открывает файл, читает его, считает его, и пишет результат в другой файл.
    И — никакой синхронизации!

    И время выполнения расчета в десятки и сотни раз превышающее время выполнения с разбиением на традиционные два потока: читающий/пишущий и считающий.
  • +1
    Пост ни о чем, вроде вначале собирались, что-то рассказать — но так ничего и не рассказали.
  • 0
    Вот буквально недавно размышлял о том, что хвостовая рекурсия в Erlang это по сути дела цикл с условным выходом из него (по типу goto). В структурированных языках мы от этого стремимся избавиться, но иногда такие решения всетаки нужны. А рекурсивный вызов всегда будет выращивать стек. Таким образом, получается, что хвостовая рекурсия позволяет пользоваться преимуществами производительности с операциями goto и в то же время обладает понятным синтаксисом.
  • 0
    Акторная модель?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка