Или небольшая история, подтверждающая известный афоризм о том, что любая сложная проблема имет очевидное, простое и красивое неправильное решение, на примере реализации теста производительности chameneos, в ходе которой в очередной раз проявились ужасы многопоточного программирования и еще раз довелось столкнуться с задачей, проверка решения которой гораздо важнее и сложнее, чем получение самого решения.
Исходная точка и условие задачи
Началось все с
сообщенияАвтор: Lazy Cjow Rhrr
Дата: 24.04.07
, в котором приводилось решение одной и той же задачи на Java и на Haskell. Глядя на компактный и совершенно непонятный мне код Haskell-варианта я почему-то подумал, что на D можно будет сделать похожее по лаконичности решение. Благодоря помощи
Lazy Cjow Rhrr я получил условие самой задачи в виде текстового описания:
* нужно создать четырех конкурентных (в смысле каждый живет в своем потоке) хамелеонов разных цветов (синий, красный, желтый, синий);
* каждый хамелеон должен регулярно приходить на место встречи и встречаться там с другим хамелеоном. Если на месте встречи еще никого нет, пришедший первым хамелеон должен подождать второго;
* при встрече хамелеоны должны соответствующим образом поменять свои цвета. При вычислении нового цвета хамелеона нельзя использовать арифметические вычисления -- только if/else, switch/case или pattern-matching;
* после того, как на месте встречи образуются N пар, каждый хамелеон должен "пожухнуть" (получить специальный цвет FADED), сообщить количество встреченных лично им хамелеонов и завершить свою работу.
В качестве результата работы программа должна печатать сумму сообщенных каждым хамелеоном встреч. Например, для N=100 результатом программы должно быть 200.
Гранаты не той системы...
...или не стоит приступать к программированию на больную голову
Время поэкспериментировать с задачкой chameneos появилось благодоря тому, что я несколько дней валялся дома с сильной простудой. Отупев в конце-концов от безделья, я решил что сейчас тяп-ляп и дело в шляпе...
Первые признаки того, что все идет не так, появились сразу. Почему-то я долго не мог понять условия задачи. Из-за чего рассматривал решения на Java,
на Scala и оригинальное
решение на D с сайта
The Great Computer Language Shootout. Причем, чем дольше я смотрел на D-шную реализацию, тем меньше понимал, почему ее посчитали правильной реализаций. В подобных сомнениях я пребываю до сих пор. От окончательного вывода меня отделяет лишь то, что я никогда не работал с Unix-овыми семафорами и, поэтому, могу не понимать каких-то их особенностей.
Например, я не понимаю в методе MeetingPlace.OtherCreaturesColour:
private Colour OtherCreaturesColour(Colour me)
{
Colour other = Colour.faded;
sem_wait(&mustWait);
if(firstCall)
{
if(n)
{
first = me;
firstCall = false;
/*1*/ sem_post(&mustWait);
other = second;
n--;
}
sem_post(&mustWait);
} else {
firstCall = true;
/*2*/ second = me;
other = first;
}
return other;
}
одной вещи: каким же образом пришедший первым хемелеон ожидает прихода второго хамелеона. Ведь функция sem_post не блокирует нить первого хамелеона. Поэтому, когда первый хамелеон в точке 1 позволяет еще одному хамелеону войти на место встречи, нет никаких гарантий, что второй хамелеон успел пройти точку 2. Так что здесь, на мой взляд, явная ошибка, но к этому я еще вернусь.
Особенностью текущей версии стандарной библиотеки Phobos в языке D является то, что в ней отсутствуют такие базовые вещи для организации синхронизации нитей, как семафоры, условные переменные или, на худой конец, события. Есть возможность момечать методы как synchronized, но у объектов нет методов wait и notify, как в Java. Поэтому решение с Language Shootout использовало специфические для Unix-а POSIX-семафоры. Поскольку я использовал DMD под Windows, а под Linux-ом у меня DMD нет, то естественным образом встал вопрос о том, чтобы делать свою реализацию на основе библиотеки
Tango.
Первые успехи? 
Не мудрствуя лукаво я просто заменил в исходном варианте реализацию класса MeetingPlace на использующую мутекс и условную переменную. Мутекс для того, чтобы защищать доступ к данным MeetingPlace, а условную переменную для того, чтобы будить первого хамелеона при пришествии второго.
Вот что получилось.
Русским языком логику поведения хамелеонов можно описать так:
* приходит первый на место встречи, пишет свой цвет на записке и кладет записку в специальный ящик (MeetingPlace.first_) и ложится спать в ожидании второго;
* приходит второй, берет цвет первого из его ящичка, пишет своей цвет на второй записке и опускает записку в другой ящичек (MeetingPlace.second_);
* уходя второй хамелеон пинает первого, мол хватит уже спать;
* проснувшись от пинка певый берет записку второго и уходит, освобождая место для следующей пары хамелеонов.
Программа вроде бы работала. Хотя иногда подвисала. Попытки найти причину подвисаний привели к появлению в реализации MeetingPlace.meet вот такого if:
if( remaining_ > 0 )
{
// bla-bla-bla
}
вместо
if( remaining_ ) ...
поскольку remaining_ по каким-то неведомым мне причинам уходил в минус (?!) Нифига себе оптимизатор у DMD, подумал я, вообще проверки выбрасывает. И просто написал remaining_>0 вместо того, чтобы разобраться в чем же дело. Ну нельзя программировать на больную голову.
Так вот программа вроде бы работала, считала все довольно шустро. Иногда были небольшие разбежки в результатах. Например, при N=1000000 можно было получить и 2000000, 2000002 или 20000004. Опять же, догадаться, что поскольку о каждой встрече будут отчитываться два хамелеона и результат всегда должен быть 2N, я вовремя не смог.
В любом случае, мне не очень нравилось, что не хамелеоны управляют своим поведением, а место встречи говорит, что кому делать. Да и наличие двух ящиков для записок с именами цветов казалось мне избыточным. Поэтому я решил переместить логику организации встречи в код самого хамелеона.
Тихо шифером шурша крыша едет не спеша
После небольшой переделки получилось
сие творение. Принцип работы состоит в том, что MeetingPlace теперь содержит только необходимые для проведения встречи данные: мутекс, условную переменную, количество оставшихся встреч и указатель на блок памяти, который будет использоваться очередной парой для обмена цветами (MeetingPlace.swappedColor_).
Первый хамелеон приходит на место встречи, видит, что swappedColor_ равен null, понимает, что он первый. В swappedColor_ помещается указатель на локальную переменную с собственным цветом. И засыпает.
Приходит второй хамелеон, видит, что swappedColor_ не равен null, считывает из нее цвет первого, записывает свой цвет, пинает первого и уходит.
Первый просыпается, обнуляет swappedColor_, берет из своей локальной переменной цвет второго и уходит, освобождая площадку.
если кто-то догадался, просьба помолчать 
Все работает. Разбежка в результатах на больших N проявляется. Но не это страшно. Иногда (где-то на седьмом-восьмом старте) на N=1000000 программа зависает, отжирая по 100% процессора. А вот на значении N=40000 вычисление иногда затягивается на десятки секунд, но завершаются с какими-то фантастическими результатами:
bash-3.2$ time ./my_chameneous 40000
creaturesMeet_: 2579283
creaturesMeet_: 2093332
creaturesMeet_: 2178625
creaturesMeet_: 2290491
9141731
real 0m11.546s
user 0m0.031s
sys 0m0.016s
Откуда берется более 9 миллионов встреченных хамелеонов? Не плодятся ли они там в программе сами по себе? А кто знает:
bash-3.2$ time ./my_chameneous 40000
creaturesMeet_: 40000
creaturesMeet_: 40000
creaturesMeet_: 40000
creaturesMeet_: 0
creaturesMeet_: 0
80000
real 0m0.281s
user 0m0.046s
sys 0m0.015s
как-то же пятое сообщение о завершении работы хамелеона появилось. Причем я точно помнил, что обычно в программе их создается всего четыре!
Помятуя о странном поведении оптимизатора с выбрасыванием проверок вида if(remaining_), я описал возникшую проблему в форуме Tango и лег спать. Надеясь, что утро вечера мудренее.
И оно-таки мудренее
Не получив никаких вразумительных ответов от разработчиков Tango я понял, что спасение утопающих дело рук самих утопающих. Поэтому искать ошибку нужно самому.
С утра я уже не верил в наличие таких серьезных багов в компиляторе DMD. Мысли мои крутились вокруг того, что либо я работая с указателями кому-то что-то затираю. Либо мои манипуляции с указателями на локальные объекты сводят с ума сборщик мусора, который разработчики Tango приделывали к D сами. Но посольку никаких противоправных действий со своей стороны я не видел, то я не придумал ничего лучше, как сделать аналог этой программы на C++. Благо Tango много чего скопировало из ACE, поэтому реализация теста на C++ и ACE практически 1 в 1 получилась всего за полчаса.
Каково же было мое удивление, когда C++ версия на N=40000 вела себя так же, как D-шная!
Где же была зарыта собака
Я не знал, портят ли мои манипуляции с указателями в D, но в корректности работы с указателями в C++ я был уверен. Значит дело было в самом алгоритме. Но где именно?
Я не ограничивал количество хамелеонов, которые могли заходить на место встречи в качестве "второго", т.е. пока первый хамелеон спит или просыпается после очередного пинка.
Хамелеоны висят на одном мутексе
Все дело в том, что перед местом встречи тусуются все не попавшие туда хамелеоны. Вход на место встречи им перекрывает мутекс (MeetingPlace.lock_) который сейчас захвачен вторым хамелеоном (именно вторым, поскольку первый освободил его уснув на MeetingPlace.condition_). Я ошибочно предполагал, что когда сработает MeetingPlace.condition_, первый хамелеон вновь захватит его первым. Не тут-то было! Мутекс мог захватить любой из ожидавших своего часа вне места встречи хамелеонов. И в этом случае второй хамелеон автоматически становился новым вторым. А затем опять первых хамелеон мог "пролететь" мимо мутекса и мутекс мог быть отдан очередному второму. Именно это и приводило к появлению такого большого количества встреч -- первый хамелеон мог встретиться сразу с несколькими вторыми и все это осуществлялось в рамках одной итерации по отношению к MeetingPlace.remaining_.
Проверить это предположение оказалось не сложно. Достаточно было сделать что-то такое:
run()
{
while( true )
{
Color other = my_;
scope localLock = new ScopedLock( meetingPlace_.lock_ );
if( meetingPlace_.remaining_ )
{
static bool repeated_second = false;
if( !meetingPlace_.swappedColor_ )
{
meetingPlace_.swappedColor_ = &other;
repeated_second = false;
meetingPlace_.condition_.wait();
meetingPlace_.swappedColor_ = null;
--meetingPlace_.remaining_;
}
else
{
assert( !repeated_second, "Repeated Second Chameneos!!!" );
repeated_second = true;
other = *meetingPlace_.swappedColor_;
*meetingPlace_.swappedColor_ = my_;
meetingPlace_.condition_.notify();
}
localLock.release;
if( FADED != other )
{
my_ = complement( other );
++creaturesMeet_;
}
}
else
break;
}
}
Пути исправления
Можно использовать семафор с ограничением на вход на место встречи только двух хамелеонов. Но тогда нужно чтобы освобождал семафор только первый хамелеон, причем инкрементируя счетчик семафора сразу на два (освобождая тем самым вход на место встречи). Второй хамелеон не может изменять значение семафора, т.к. это приведет к той же самой проблеме.
Вот вариант, использующий семафор (у меня на WinXP он в два раза медлее второго варианта).
Либо можно использовать счетчик количества хамелеонов на месте встречи и еще одну условную переменную, которая будет разрешать вход на место встречи новым хамелеонам.
Вот этот вариант. (
С++ный близнец.)
В результате
Все заработало. Без каких либо претензий к оптимизатору и разбежек в результатах.
Случай, когда тестирование важнее реализации
На мой взгляд это как раз тот самый случай. У данной задачи есть только один стабильный показатель, который легко контролировать -- итоговое количество встреч. Все остальные вещи выполняются в случайном порядке. Например, при одном запуске могут вначале встретиться красный и синий хамелеон. А при втором -- желтый и красный. И невозможно составить какой-то фиксированный сценарий, который бы всегда выполнялся при определенном N. Поэтому и невозможно прогнать программу на каком-то N и сравнить ее след работы с фиксированным сценарием.
Но "правильные" результирующе значения в данном тесте легко получаются даже при неправильной работе программы. И это легко увидеть на следующих примерах.
Записка с цветом от неизвестно кого
Пришло время вернуться к D-шной реализации с Language Shootout. Я получил возможность поиграться с ней поскольку Sean Kelly, один из разработчиков Tango, сделал
ее порт на Tango. Если модифицировать код MeetingPlace вот так:
class MeetingPlace
{
private static Semaphore mustWait;
private Colour first, second;
private bool firstCall = true;
private int n;
private bool second_was_here = false;
this(int maxMeetings)
{
n = maxMeetings;
mustWait = new Semaphore(1); //sem_init(&mustWait;,0,1);
}
private Colour OtherCreaturesColour(Colour me)
{
Colour other = Colour.faded;
mustWait.acquire(); //sem_wait(&mustWait;);
if(firstCall)
{
if(n)
{
first = me;
firstCall = false;
second_was_here = false;
mustWait.release(); //sem_post(&mustWait;);
/*3*/ assert( second_was_here, "second must was be here" );
other = second;
n--;
}
mustWait.release(); //sem_post(&mustWait;);
} else {
firstCall = true;
second = me;
second_was_here = true;
other = first;
}
return other;
}
}
то assert в точке 3 срабатывает. Т.е., как я и ожидал, первый хамелеон пишет записку со своим цветом, кладет в ящик, разрешает вход на место встречи второму хамелеону. Затем, никого не ожидая, берет записку с цветом второго хамелеона и уходит. Но чья же это записка, если второй хамелеон на месте встречи еще не появился? Вероятно, это мусор, который остается на месте встречи от предыдущих тестов
Итак, получать правильный результат можно даже не проводя реальных втреч и получая из ящика какой-то мусор от предыдущих встреч.
Зачем нам все четыре хамелеона? Можно обойтись и меньшим количеством
...или хамелеон родился пожухшим.
С самого начала
Lazy Cjow Rhrr обратил мое внимание, что в Java и в Scala программах цвета для хамелеонов задаются не так, как требовалось:
val colours = List(RED, BLUE, YELLOW, FADED)
...
val creatures = for(val x <- colours) yield {
val cr = new Creature(mp, x);
cr.start();
cr
}
т.е. последний хамелеон сразу создается с финальным цветом FADED. И как же он участвует в жизни остальных хамелеонов? А никак:
override def run() {
try {
while(colour != FADED) {
mp.meet(this)
if(other == FADED) {
colour = FADED
} else {
met = met + 1
colour = complement(other)
}
}
} catch {
case e:InterruptedException => () // Let the thread exit
}
}
в его нити не выполняется ничего, кроме первой проверки условия в while. После чего хамелеон тихо помирает, вероятно, от врожденного уродства. В чем не сложно убедиться, если добавить в конец метода run() отладочную печать:
override def run() {
try {
while(colour != FADED) {
mp.meet(this)
if(other == FADED) {
colour = FADED
} else {
met = met + 1
colour = complement(other)
}
}
} catch {
case e:InterruptedException => () // Let the thread exit
}
Console.println("I meet: " + met + " creatures" );
}
При запуске сразу можно увидеть, что первая печать появляется мгновенно и сообщает о нуле встреченных хамелеонов. Т.е. правильный результат могут успешно сделать и трое оставшихся, зачем еще четвертый? Тем более, что по условию нужно создавать четырех хамелеонов, но не обязательно, чтобы все четверо потом работали
К тому же, трое с работой справляются несколько быстрее, чем четверо (у меня исходный вариант работает 9сек, против 12сек в случае четырех хамелеонов).
В итоге
Очередное повторение на собственной шкуре банальных истин:
* программировать нужно сначала на бумаге, а не лихим кавалерийским наскоком;
* ошибки при проектировании самые тяжелые;
* неправильно написанная многопоточная программа может вести себя совершенно непредсказуемым образом;
* к проверке правильности работы программы нужно подходить, как минимум, не менее тчательно, чем к ее написанию.
Ну или в нескольких словах: длинный (по сравнению с Haskell) вариант на D, два дня программирования в свое удовольствие (с очередной напряженностью в семье). Подорванная вера в корректность The Great Language Shootout. Ну и этот текст
