Доложился на семинаре Отдела динамических систем Института математики и механики УрО РАН, выкладываю презентацию и связанную с ней статью. Тема: численное построение решений (нэшевские решения) в линейных неантагонистических позиционных дифференциальных играх двух лиц с терминальными показателями качества в фазовом пространстве размерности больше двух (да, длинно, но могло быть ещё длиннее).
Not long ago I’ve read the following article: Solving the Multicore Dilemma.
The article proposes an interesting approach to enabling automaic parallelization of high-level code. This approach is presented as an alternative to enforcing immutability of values (pure functional programming). We can think of it as (full) scatter-gather paradigm (while pure FP corresponds to the “gather” part).
As for me, I don’t think that this approach is really universally applicable, but it may be fruitful anyway even as a mindset for parallelization by hand.
The post you’re reading is devoted to a small special case, which was used as a simple example in the aforementioned article. It’s about getting the histogram of a string (I call it “counting codes” below). Imagine that the simple sequential algorithm is transformed into a scatter-gather counterpart. There each character codepoint has its own container where 1s are accumulated. I think that a sophisticated parallelizing compiler should find out that we don’t need real containers but just a bunch of simple counters.
Well, this way of reasoning may lead to a structure consisting of atomic counters and replacing pushing and summing with atomic increment (so no scatter-gather anymore). People doing parallel algorithms may guess that atomic counters being used so intensively will prevent us from gaining any performance increase (even with state-of-the-art hardware support for atomic operations) for this “parallel” code. More likely, it will be working slower than that simple sequential algorithm. I don’t claim that our would-be sophisticated compiler couldn’t find out the problem with atomic increment. But too clever compilers may produce quite unpredictable code…
Meanwhile, it seems logical to parallelize this algorithm just by providing each thread with it’s own array of counters and then summing the results. I found it to be interesting to measure real-life speed of these algorithms.
For simplicity I used 8-bit char, so I can use a plain C array of 256 integers fitting exactly in 1kb of RAM to store counters for all possible codepoints. Strings are generated using Mersenne twister mt19937 and uniform_int_distribution. The source code containing all the details is available via URLs given below.
Tested algorithms:
Other code: random_string.h, test.cpp. Archived MSVC project with compiled exe (x64) and the testing results: here.
Compiler/OS used: Microsoft Visual C++ 2012 (x64, default release settings + /GS- /Qpar) / Windows 7SP1 Pro x64.
Testing machines: AMD Phenom 2 x4 @ 2.1GHz and 3.2GHz with 2x2Gb DDR3-1333 RAM, Intel Celeron U3400 1.07GHz with 4Gb DDR3-800.
I tried std::atomic just to see “lock xadd” in assembly (MSVC transforms OpenMP atomic directive into “call _vcomp_atomic_add_i4″ here, the procedure is hidden somewhere in the runtime). What’s interesting and counter-intuitive (at least for me), OpenMP variant stably works faster than std::atomic on Phenom and vice versa: std::atomic is quite faster on Celeron.
Both atomic variants work an order of magnitude SLOWER than simple sequential algorithm – a serious warning to everyone using atomics indiscriminately. Atomic operations prevent caching of counters and lock memory bus (therefore each iteration loads from and stores to DRAM an integer, and no matter how many threads try to do it, they do it serially).
“Normal” parallel variant works only twice faster on my quad-core machine (and almost no faster on the dualcore machine) than a sequential one not reaching even 1Gbps string reading speed @ 2.1GHz and hardly reaching 1.33Gbps @ 3.2GHz (in a perfect situation the counters array should reside in L1D, string parts should be prefetched to cores’ caches line by line effectively reaching RAM subsystem throughput limit). So, a field for some improvement obviously exists.
Performance scaling with string length and CPU frequency is almost linear. However doing small strings in parallel may lead to high overhead (threads starting and joining, possible context switches).
UPDATE 2013.03.25.
The code was revised and published on Bitbucket.
Представим простую ситуацию. Вы поставили на плиту что-нибудь вариться и, пока оно варится, включили музыку, решили почитать ленту Твиттера, написать пару строчек кода, etc. Проблема даёт о себе знать через обонятельные рецепторы. Конечно, часы перед глазами, но мозг (по крайней мере, мой) абсолютно отказывается отслеживать время.
В очередной раз столкнувшись с этой проблемой, я решил поступить как нормальный программист – сел и набросал простенькую программку-таймер. Заодно попробовал в работе Lazarus. Результат работы под названием AlarmClock здесь (exe для Win32 вместе с исходниками по лицензии ISC). Один из мелких недостатков Lazarus – большой размер получающихся exe, но, думаю, это не критично. Зато не требуется ничего устанавливать, и GUI выглядит как “родной” что в WinXP, что в Win7.
Итак, запустив эту программу, можно установить или требуемый интервал времени (например, 10 минут) или заданный момент на ближайшие сутки (в 24-часовом формате). Указать в нижнем текстовом поле причину тревоги и нажать кнопку “вниз” для интервала или “T” для момента времени – отсчёт пошёл. Теперь можно свернуть окно, чтобы не мешалось (оно спрячется в трее). Когда придёт заданное время, окно AlarmClock всплывёт и будет настойчиво демонстрировать себя, пока не будет нажата кнопка “0″ (сброс) или “пауза”. Также можно включить звуковое сопровождение (использует стандартный звук Windows в качестве “сирены”).
V.1.01. Bugfix: при смене дат (наступлении 00:00) счётчик сбивался. Fix: счётчик теперь не останавливается при изменении поля причины (однако тревога выключается).
V.1.1. Первоначально я не думал развивать проект, но раз уж выложил его на Bitbucket, то придётся попиливать по-маленьку :). Добавлено окно “О программе” со ссылкой на репозиторий и краткой справкой.
V.1.2. Поддержка параметров командной строки.
В академической среде известен лозунг “publish or perish”. Многим (в том числе, и мне) трудно заставлять себя писать. Вместо этого (а также преподавания, которое накладывает ответственность, необходимость разбираться в вещах, в которых порой не чувствуешь себя уверенно, и это сильно угнетает) я с удовольствием бы копался в каком-нибудь низкоуровневом коде, не имея иных обязательств.
(Самое забавное, что эта неуверенность иногда каким-то чудом может приводить к ложному впечатлению наличия каких-то “глубоких познаний” в тайнах “чего-то очень сложного”. Печально.)
Блог воодушевляет быть более открытым, не гнаться за наукообразностью, за перфекционизмом (который, увы, порой так увлекает). Да, blogging is hard.
Не стоит гнаться за “репутацией”. Чем её “больше” (как кажется человеку), тем страшнее её потерять, страшнее оступиться, сделать ошибку, а не ошибается, как известно, тот, кто ничего не делает. Это путь в никуда – предел роста репутации = полный паралич.
Голова, несмотря на все эти миллиарды нейронов, всё равно слишком маленькая. В конце концов, до тебя, по большому счёту, почти никому нет никакого дела.
Важно сделать что-то полезное. Это источник настоящей репутации. Больше попыток, больше доступность, больше информации – выше вероятность успеха.
Необходимо публиковать код (чем мне ещё предстоит заставить себя заняться!). Лозунг разработчика – “ship or die”.
В студенческой среде встречается превратное представление о том, что собой представляет “профессионализм”. На мой (идеалистический) взгляд, в первую очередь, профессионализм – это честность с самим собой и с теми, кто зависит от твоей работы. Это умение заставить себя взглянуть в будущее, принять взвешенное решение и действовать в соответствии с ним. Если ты объективно проанализировал свою подготовку и пришёл к выводу, что находишься на первой ступени компетентности в некотором вопросе, то, наверное, не стоит браться за эту работу.
Организованность, знания и умение поставить и эффективно выполнить задачи – лишь следствие. Ни опыт, ни знания, ни заработок сами по себе не являются мерилом профессионализма.
Напоследок
Маленькая забавная задачка
Дана строчка “123456789″. Между любыми двумя цифрами можно поставить *, + или – (или ничего не ставить), требуется найти все варианты расстановки знаков, дающие при вычислении (с учётом приоритетов операций) полученного таким образом арифметического выражения 2002.
Задачка сравнительно легко решается на языках, имеющих встроенные средства вычисления выражений (например, Perl). Я написал решение на C, представляющее каждую возможную формулу в виде 16-битного целого (8 возможных позиций для знаков, 4 варианта в каждой позиции) и перебирающее все 65536 вариантов. Академический интерес представляет вопрос, сколько кода понадобится, чтобы заставить решить эту задачку компилятор C++ (надо написать соответствующие шаблоны). Я пожалел своё время и не стал это выяснять :).
В этой записи я решил представить алгоритм, придуманный мной под впечатлением от распределённых (distributed) алгоритмов. Алгоритм строит (субоптимальную) правильную вершинную раскраску неориентированного графа. Алгоритм довольно прост и, возможно, был в том или ином виде представлен в литературе.
Алгоритм
Под конфликтами понимается наличие одинаково окрашенных вершин-соседей. Проверка “есть конфликты” перебирает все вершины и составляет список C троек (вершина v, количество конфликтов n, минимальный неконфликтный цвет c), отвечающий конфликтующим вершинам (n = количество соседей v, имеющих тот же цвет, что и v). Если вершину v перекрасить в цвет c, то конфликт будет разрешён (при условии сохранения прежних цветов соседями v). Если конфликтов нет, то список C будет пуст, и алгоритм закончит работу — будет получена правильная раскраска вершин графа.
“Разрешение конфликтов” производится следующим образом.
Свойства алгоритма
По завершении работы алгоритма получаем правильную вершинную раскраску. Необходимо доказать, что работа алгоритма завершится. Строгого доказательства я выполнять не стал. Однако, нетрудно заметить, что всего конфликтов может быть не больше, чем всего вершин в графе (N), за одно разрешение конфликтов разрешается как минимум один конфликт и не добавляется новых, поэтому достаточно N итераций цикла. Одна итерация цикла требует O(N + M) действий (для каждой вершины проверить всех её соседей). Отсюда можно сделать вывод, что алгоритм имеет сложность O(N(N + M)) ≤ O(N3).
Реализация
Была написана реализация алгоритма на C++, включающая набор простых графов для проверки. Для всех простых тестов алгоритм даёт оптимальную раскраску.
Нередко ведутся жаркие неконструктивные споры на тему “какой язык программирования лучше/хуже”. В лучшем случае, они переходят в плоскость конкретных применений тех или иных языков, которые, как и любые инструменты, более уместны каждый для своего круга задач. Как известно, не следует забивать гвозди отвёрткой. Однако, если нет молотка, то можно забивать гвозди и кирпичом.
Существует определённый класс наиболее широко используемых (в компаниях-разработчиках ПО) языков, называемый “промышленные языки программирования”. Обычно, их активно ругают адепты “новых” языков, не используемых столь же широко. Впрочем, когда (и если) база пользователей разрастётся, эти языки, в свою очередь, могут стать “промышленными” с такими же печальными для их репутации последствиями.
Старые же “промышленные” языки превращаются в этаких легендарных монстров: таковы Fortran, PL/I, COBOL и, возможно, VB/VBA (до .net). Современные примеры: C, C++, Java, C#, JavaScript и (особенно критикуемый) PHP. Возможно, один из главных недостатков промышленного программирования в том, что оно практически “выродилось” в довольно рутинную работу — склеивание мириад кусочков фреймворков в конечное “приложение”.
Промышленные языки традиционно занимают верхние строчки рейтингов популярности (например, Tiobe). Проводя оценку этих рейтингов, не следует забывать проанализировать способ их расчёта.
Другие люди испытывают “аллергию” на языки, использовавшиеся для обучения: как правило, диалекты Basic и Pascal.
Как сказал Б. Страуструп: “there are only two kinds of languages: the kind everybody bitches about, and the kind nobody uses” (есть только два вида языков: те, которые все ругают, и те, которые никто не использует). Ругать не буду. Вместо этого попробую привести список интересных, с моей точки зрения, и при том, не слишком новых языков программирования (есть множество интересных языков, появившихся недавно, о них пока речь не идёт).
Итак, наиболее важный для меня язык — C++. Основные достоинства C++ — это обширная база доступных библиотек любой направленности и наличие развитых оптимизирующих компиляторов (g++, clang, icc, msvc, pgi, open64, …) для большинства актуальных платформ, способных производить глубокую оптимизацию кода. Поэтому C++ обычно выбирают в случаях, когда важна высокая (и предсказуемая) производительность ПО (3D игры, вычислительно-тяжёлые задачи, управление автоматизированными системами).
Наблюдаемое постепенное снижение популярности C++ должно приостановиться с появлением существенно обновлённого стандарта 2011 года (жаль, не добавили концепты, хотя многие и так ругают за чрезмерное раздувание и без того немаленького стандарта) и релизом Microsoft Windows 8. К слову, по тому же рейтингу Tiobe видим очень высокую популярность C относительно C++. Не останавливаясь на возможных систематических ошибках статистики, способствующих указанной ситуации, замечу, что выбор C вместо C++ для написания нового ПО вряд ли целесообразен в большинстве случаев, кроме ряда ниш, в которых требуются особенно большая предсказуемость и легковесность “чистого C”: написание элементов ядра ОС, драйверов, firmware, ПО для встраиваемых систем и DSP.
У C и C++ много общих проблем, отчасти следующих из их кросс-платформенности и относительной низкоуровневости, и C++ добавляет свою специфику. Тем не менее, при соблюдении определённой культуры, он может обеспечить прирост производительности труда программиста относительно C без последствий для качества продукта.
C++ искушает программиста чрезмерно обобщать код, выстраивая библиотеки шаблонов. Потом это всё начинает ломаться, что весьма огорчает и, видимо, даёт свой вклад в нелестные отзывы о C++. KISS — жизненно необходимый принцип при программировании в C++.
Довольно интересно (для программистов на C++) выглядит пока ещё относительно малопопулярный и малоизвестный язык D, разрабатывавшийся компанией Digital Mars именно как замена C++ с отказом от совместимости с C (как полагают авторы D, стремление сохранить эту совместимость внесло немалый вклад в сложность программирования на C++).
D решает многие из характерных проблем C++, выглядит проще и логичнее. Хотя, способы решения этих проблем порой вызывают негативные оценки. К сожалению, в виду низкой популярности, качество компиляторов D (dmd, gdc и clang D), количество доступных библиотек и открытого кода, да и просто литературы весьма отстаёт от таковых для C++. А. Александреску недавно опубликовал книгу по D: “Язык программирования D”. Есть плагин для Visual Studio, позволяющий добавить к её языкам язык D: Visual D. Сайт, посвящённый D.
Я не могу не упомянуть семейство языков Н. Вирта (к которым относится и не любимый многими Pascal). Интерес могут представлять языки на основе Oberon-2: собственно Oberon-2007 , Component Pascal и Zonnon (Active Oberon). Что необычно, так это постепенное уменьшение сложности и объёма описаний языков, создаваемых Виртом (Algol W → Pascal → Modula → Modula-2 → Oberon → Oberon-2). Изначально Oberon разрабатывался вместе с интерактивной средой (аналогично Smalltalk). Пример ОС написанной на Active Oberon: A2. Возможно, с точки зрения обучения программированию “с нуля”, языки семейства Oberon — это не такой уж плохой выбор?
Хотя, может быть полезнее использовать для этого Eiffel, основные отличительные черты которого — прямая поддержка контрактов функций (пред- и постусловия) и инвариантов классов, а также интересная модель (множественного) наследования.
Среди ”скриптовых” языков с динамической типизацией я хотел бы выделить два языка: Lua и Python. Оба языка активно используются как скриптовые, т.е. встраиваются в приложения, например, в игры для реализации высокоуровневой логики, элементов AI или даже управления пользовательским интерфейсом. Это удобно, так как можно быстро вносить изменения, не производя повторную компиляцию кода. Оба языка имеют минималистичный синтаксис. Lua отличается особенной легковесностью и скоростью выполнения байткода. Не помню, чтобы видел сравнение с JavaScript “на стероидах”, но программы на Lua обычно выполняются гораздо быстрее аналогов на Python и Ruby.
К слову, о “стероидах”. Авторы виртуальных машин JavaScript идут на множество ухищрений, вплоть до распознавания в коде характерных образцов и JIT-подмены их глубоко оптимизированными на низком уровне реализациями, поэтому высокая скорость в таких случаях не является гарантией такой же высокой скорости на другом коде, особенно, если он в каком-то смысле необычен.
В свою очередь, сейчас Python широко применяется и как основной язык разработки приложений. Обычно его любят за то, что можно быстро набросать и выполнить некий код (например, желая быстро создать прототип), не разбираясь со множеством низкоуровневых деталей и не решая множества мелких проблем, не имеющих прямого отношения к делу.
Благодаря относительной простоте старта, Python и Lua нередко рекомендуют в качестве первых языков программирования.
В качестве первого языка программирования часто рекомендуется JavaScript, потому что для работы с ним достаточно современного браузера. Можно сразу начать делать что-нибудь интересное (вплоть до 3D средствами WebGL). Отмечу, что внешне гораздо привлекательнее смотрится CoffeeScript — язык, транслируемый в JavaScript.
Но я бы хотел упомянуть ещё три группы языков, менее популярных, нежели рассматривавшиеся выше.
Первая группа — это набирающие популярность функциональные языки. Если вы пользуетесь Visual Studio и желаете познакомиться с ними, то удобно начать с F#, поддерживаемом Visual Studio 2010 и новее. Лично мне интересны следующие три представителя функциональных языков.
Erlang — язык, предназначенный для реализации больших устойчивых к ошибкам распределённых систем с параллельной работой отдельных узлов, весьма удачно реализующий акторную модель. Erlang не самый сложный в изучении ФЯ, обладающий синтаксисом, который иногда находят “архаичным”. Имеется общедоступная opensource реализация.
Haskell — язык-знамя ФП. Интересен двумя особенностями: высокой чистотой с точки зрения функционального программирования, насыщенностью различными идеями, благодаря чему эффективен в качестве учебного пособия (покрывает множество вопросов, в этом он напоминает C++), и наличием компилятора в машинный код (GHC), что позволяет рассматривать Haskell как язык, подходящий для написания вычислительно интенсивных программ.
SBCL — реализация компилятора Common Lisp в машинный код с широкими возможностями низкоуровневой оптимизации. Что ещё к этому можно добавить?
Две оставшихся группы языков таковы, что о них слышал не каждый современный программист. Они интересны хотя бы с точки зрения развития программистских способностей. Тексты программ на этих языках с непривычки довольно тяжело читать. Для того, чтобы осознать их гибкость и внутреннюю красоту, требуется изучить хотя бы несколько примеров.
Forth-подобные языки. Среди них есть и объектно-ориентированный язык с динамической типизацией — Factor (реализация).
APL/FP-подобные языки. Листингом на таком языке можно ввести в замешательство тех, кто уже привык к C++ или Perl. К сожалению, сейчас это семейство языков занимает позицию чуть ли не эзотерических языков. Тем не менее, это реальные языки, с помощью которых можно решать реальные задачи. Кратко об идеях, заложенных в языке Дж.Бэкуса FP, можно прочитать на Википедии. Современный язык этого типа с общедоступной реализацией — J. Язык “заточен” на работу с массивами.
Наконец, последнее замечание касательно обучения программированию. На мой взгляд, существует две основных крайности.
Можно дать “нюхнуть пороху” — обрушить на обучающегося весь груз относительно низкоуровневого языка, с одной стороны, со всей его сложностью и тысячью исключений из общих правил, с другой стороны, со всем его богатством идей и решений (и “костылей”, конечно же).
Теоретически, те, кто выплывет, будет способен быстро освоить многие другие языки и быстро начать работать (со многими “если”). Например, освоив C и C++, сравнительно легко перейти на Java, C#, Objective C. Хотя, человек, привыкший к C++, наверняка будет сначала плеваться от того же C# — вроде синтаксис так знаком, а за ним скрывается совсем другой язык.
Сюда же можно отнести (уже ставший историей) Basic на ранних микрокомпьютерах. Существует поколение программистов, начинавших с него в детстве (к ним отношусь и я сам). В своё время Э.Дейкстра негативно (хотя и с юмором) отзывался о тогдашнем BASIC (ещё более раннем; кстати, это прообраз скриптовых языков, можно сказать, первый из них), но существует и другое мнение (ещё). Некоторое сходство (по духу) с тем Basic, как мне показалось, демонстрирует язык Euphoria (по простоте сравним с Lua).
Можно же наоборот, максимально оберегать обучающегося от технических деталей и проблем. Пытаться раскрыть саму суть программирования и вычислений. Теоретики любят для этого использовать Scheme (далее следует глубокое погружение в матан ”computer science”).
Также к этой крайности ближе обычное обучение языкам Lua, Python и Ruby. Более того, существуют языки и среды программирования (например, на основе Logo), нацеленные именно на обучение (в том числе, младших школьников или даже дошкольников — вплоть до отказа от написания кода).
Лично я склоняюсь к тому, что для обучения профессиональных программистов полезнее быть ближе к первой крайности : ).
Программирование — это ремесло, и лучшие его образцы становятся искусством. Его нелегко заковать в узкие рамки логичной, но обезличенной теории.
Ещё несколько ссылок “на засыпку”.
Yet another list of languages worth studying.
Why use Erlang.
Play with Lua: turning a Lua program into an executable.
It seems to me it was this way (in “industrial mainstream”).
60‘ ad-hoc calculations, procedural programming (Fortran)
70‘ standardized, structural programming, databases (COBOL, PL/I)
80‘ portable assembly, system programming, libraries, 4GL, micros boom (C, Pascal, SQL, Basic)
90‘ object-based/oriented programming (C++, VB, Object Pascal)
00‘ managed static-typed languages, heavily-OO frameworks (Java, C#)
10‘ dynamic-typed languages, still mostly OOP-like (Python, Ruby, JS)
20‘ functional programming? asynchronous/massive parallelism? native code renaissance?
What languages will see mainstream use in 20′s? Probably, it will be “hybrids” based upon current ones (and possibly bearing the same names).
