Google Wave инвайты

Порядком поднадоела эта суета сует вокруг распухающего гиганта. И я, наверное, один из немногих, кто не испытавает хоть какого-то восторга от нового сервиса. Посему предлагаю: в обмен на дозу вау-эффекта отдаю инвайты. Тот, кому они нужны, навярняка знает, зачем они ему ;) . Ничего не жалко, усё отдам.

Boost::normal_distribution example

Этот пост для больших любителей типа меня читать документацию по диагонали десять раз одно и то же не замечая искомого, ну и себе в записную книжку естественно ;)

// create the random number generator N(0,0.1) 
boost::mt19937 randomness;
typedef boost::normal_distribution<double> dist_type;
dist_type norm_dist(0.0, 0.1);
boost::variate_generator< boost::mt19937, dist_type > noise(randomness,
norm_dist);

...
noise()
...

Подсмотрел здесь.

Assert vs Breakpoint

Иногда возникают микро-мысли, которые кому-то могут показаться чересчур прозрачными, а для кого-то могут быть полезны. Пусть будут, авось пригодятся.

Последнее время заметил одну особенность, возникла она как-то сама собой, но потом, стала очевидно простой и понятной. Я как-то совершенно внезапно перестал пользоваться точками останова в процессе отладки кода. Не скажу, что до этого я пользовался ими часто, как правило первое что я делал, начиная разбираться в незнакомом и/или некорректно работающем коде - искал возможность воспользоваться существующими в проекте средствами журналирования или встроить свои собственные (элементарный stdout меня как правило более чем устраивал).
И вот разбираясь в новом коде, практически на автомате пишу.. assert(0). Оказалось, такой подход, по крайней мере лично для меня, имеет некоторые преимущества:

• полностью сохраняется модель отладки приложения: расстановка точек останова, запуск, пошаговое выполнение;
• возможность в явной форме записать условие продолжения выполнения (инвариант) кода;
• особо важные утверждения относительно корректности выполнения кода могут служить основой написания тестов и/или проверок корректности данных.
  

Второй пункт возможно расценивать и таким образом - использование assert(..) вместо точек останова принуждает к более осмысленному поведению: формулировка гипотезы, эксперимент, анализ результатов.

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

Алгоритм параллельной очереди. Часть 4. Полностью не блокирующая очередь для нескольких поставщиков и потребителей.

Продолжение перевода статьи "Writing a Generalized Concurrent Queue" by Herb Sutter. Начало: Алгоритм параллельной очереди. Часть 1. Множество поставщиков и потребителей. Алгоритм параллельной очереди. Часть 2. Очередь с двумя блокировками. Алгоритм параллельной очереди. Часть 3. Поставщик и потребитель.

Код, приведенный ранее, все еще использует две блокировки, хотя и умеренно. Что позволит нам реализовать полностью не блокирующую очередь, которую смогут использовать несколько поставщиков и потрбителей одновременно? Для заинтригованных, готовых разобраться в тонкостях и деталях читателей, приведу ссылки на две ключевые работы, заслуживающие внимания.

В 1996 г. Michael и Scott опубликовали работу (M. Michael and M. Scott. "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms"), описывющую два варианта реализации очереди с внутренней синхронизацией. Один из вариантов действительно не блокирующий, другой использует блокировку для поставщиков и еще одну для потребителей, подобно примеру в статье. В 2003 Herlihy, Luchango и Moir показали на проблемы масштабируемости в подходе Michael и Scott представили свою собственную реализацию без блокировок (M. Herlihy, V. Luchango and M. Moir. "Obstruction-Free Synchronization: Double-Ended Queues As an Example").

Особенностью описанных подходов является необходимость использования операции сравнить-и-обменять двойной ширины (так же известной как "DCAS"), способной обрабатывать указатель и целый счетчик атомарно. Это достаточно проблемтично, потому что не все платформы имеют операцию DCAS, особенно широко распространенные процессоры, которым потребуется к тому же 128 битный CAS (Мы можем заставить это заработать и для 64 бит через героические попытки исхитриться обокрасть 64 битное пространство, допуская, что большинсво операционных систем сегодня на самом деле не используют все 64 бита адреса и возможно удасться ухватить пару-тройку битов не заметно. Тем не менее это крайне хрупкое и непортируемое решение, и нет гарантий что и другим людям, тем же разработчикам вашей ОС, не пришла в голову идея умыкнуть пару бит в этом бешенном 64 битном мире, и гонка за них уж началась. В действительности, провернуть подобный трюк вам удасться только если операционная система это вы, ну или ваш лучший друг). В дополнение, потребуется и корректно работающий инициализатор пустого списка.

Это была завершающая часть статьи. Буду очень рад, если данный перевод тем или иным образом помог вам или натолкнул на какие-то мысли. В дальнейшем я планирую продолжать практику перевода статей. Возможно, кому-то может показаться что я понапрасну трачу время, потому что знание английского языка для программиста является самим собой разумеющимся, но таким образом мне хотелось бы попробовать сформировать традицию рускоязычного профессионального журнала, так и не появившегося за все это время.
Оставайтесь на линии ;)

Алгоритм параллельной очереди. Часть 3. Поставщик и потребитель.

Продолжение перевода статьи "Writing a Generalized Concurrent Queue" by Herb Sutter. Начало: Алгоритм параллельной очереди. Часть 1. Множество поставщиков и потребителей. Алгоритм параллельной очереди. Часть 2. Очередь с двумя блокировками.

Поставщик.

Рассмотрим первый из двух основных методов: Produce. Задача состоит в том, что бы позволить им работать на столько параллельно, на сколько возможно:

void Produce(const T& t) {
 Node* tmp = new Node(new T(t));
  while (producerLock.exchange(true)) { }    // вход в критическую секцию
 last->next = tmp;                          // добавить потребителям
 last = tmp;                                // двигаем указатель
 producerLock = false;                      // выход из критической секции
}

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

Во-вторых, мы "применяем" изменения, получая исключительный доступ к хвосту очереди. В цикле while мы пытаемся поменять prodicerLock в true до тех пор, пока старое значение не было false; полученное старое значение true означает, что кто-то другой уже получил доступ в критическую секцию. Подобный цикл while можно прочесть как "до тех пор, пока я не буду единственным, кто поменял значение prodicerLock из false в true". Потом мы можем обновить last->next и, собственно, сам last; это две различные операции доступа (записи) в память, которые не могут быть выполнены одновременно на большенстве процессоров без какой-либо блокировки. В завершении, мы устанавливаем producerLock в false, освобождая критическую секцию.

Потребитель

Подобным же образом мы хотим поддерживать любое количество потоков, называемых Consume, и обеспечивать их выполнение параллельно на столько, на сколько это возможно. Во-первых, мы получаем исключительный доступ к голове очереди.

bool Consume(T& result) {
  while(consumerLock.exchange(true)) { }   // вход в критическую секцию

Далее, мы получаем значение указателя next. Если он не нулевой, мы должны получить первое значение, но важно сократить пребывание в исключительной секции на столько, на сколько это возможно.

  Node* theFirst = first;
 Node* theNext = first->next;
   if(theNext != nullptr) {            // если очередь не пуста
     T* val = theNext->value;          // взять
     theNext->value = nullptr;         // узел
     first = theNext;                  // подвинуть указатель
     consumerLock = false;             // выйти из исключительной секции

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

  result = *val;                // скопируем его обратно
 delete val;                   // удалим значение
 delete theFirst;              // и временный узел
 return true;                  // сообщим об успешном завершении
}

Иначе, нулевое значение theNext, означает, что список пуст и мы можем немедленно выйти из критической секции и вернуть код завершения.

    consumerLock = false;            // выйдем из критической секции
   return false;                    // сообщим, что очередь пуста
 }
};

Продолжение: Алгоритм параллельной очереди. Часть 4. Полностью не блокирующая очередь для нескольких поставщиков и потребителей.