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. Полностью не блокирующая очередь для нескольких поставщиков и потребителей.

< offtopic > Active Perl, DBD-Pg < /offtopic >

Запишу сюда, что бы не забыть, только не спрашивайте зачем оно мне понадобилось ;).
При использовании связки Active Perl и DBD-Pg возникают проблемы при установке последнего. Делать следует так:

ppm install http://pgfoundry.org/frs/download.php/1891/DBD-Pg-2.10.0-Perl5.10.ppd

Должно поставиться, если проблемы, смотрите сюда: http://pgfoundry.org/projects/dbdpgppm/ у него там домик, ищите рабочую ссылку соответствующую вашей версии perl'а. Далее. Качаете http://pgfoundry.org/frs/download.php/1851/msvcr80.zip, распаковываете туда где лежит ваш perl.exe

Последний штрих. Все это работать не будет :). Копируете <ваш perl>\site\lib\auto\DBD\Pg\Pg.dll.manifest --> <ваш perl>\bin\perl.exe.manifest (внимание, переименуйте файл!).

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

Алгоритм параллельной очереди. Часть 2. Очередь с двумя блокировками.

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

Базовой структурой данных для очереди выберем однонаправленный список. Для упрощения кода, поместим пограничный пустой элемент в начале очереди, таким образом, логически, первый элемент будет содержаться в узле фактически следующим за первым. Рис. 1 демонстрирует остояние пустой очереди, рис. 2 демонстрирует очередь из нескольких объектов.

Каждый узел содержит указатель на объект T и поле дополнения.

template <typename T>
struct LowLockQueue {
  private:
    struct Node {
      Node( T* val ) : value(val), next(nullptr) { }
      T* value;
      atomic<Node*> next;
      char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic<Node*>)];
    };

Как и любая другая разделяемая переменная, указатель next должен быть защищен мьютексом, или, как здесь, объявлен атомарным (C++0x atomic<>, Java/.NET volatile). Поле дополнения, здесь, добавлено что бы гарантировано предупредить поадание двух узлов на одну линию кэша; на практике, в случае непустой очереди, попадание первого и последнего узла очереди на одну линию кэша отрицательно скажется на производительности, вызывая невидимое соперничество между потребителем и поставщиком. Несмотря на то, что дополнение структуры используется здесь и далее, ошибка в том, что мы перестраховываемся: каждый узел будет выделен в куче, что уже добавит накладные расходы распределителя памяти: выравнивание и служебную информацию, сыграющие роль дополнения. Если так, и если мы узнаем величину накладных расходов, мы сможем уменьшить наше внутреннее дополнение пропорционально, что бы размеры Node соответствовали размерам одной линии кэша.

Рис. 1

Рис. 2

Далее, переменные управления очередью:

char pad0[CACHE_LINE_SIZE];

// для потребителяа
Node* first;

char pad1[CACHE_LINE_SIZE - sizeof(Node*)];

// для синхронизации потребителей
atomic<bool> consumerLock;

char pad2[CACHE_LINE_SIZE - sizeof(atomic<bool>)];

// для поставщика
Node* last;

char pad3[CACHE_LINE_SIZE - sizeof(Node*)];

// для синхронизации поставщиков
atomic<bool> producerLock;

char pad4[CACHE_LINE_SIZE - sizeof(atomic<bool>)];

И опять, мы добавляем дополнение что бы обеспечить раздельное положение данных различных потоков в памяти и кэше. Точнее, мы хотим обеспечить пложение данных поставщика и потребителя в различных линиях кэша, кроме того, даже если один поставщик и один потребитель будут активны, необходимо добиться что бы переменные блокировки находились отдельно, и потребители ожидающие consumerLock не влияли на линию кэша, содержащую first, которую обновляет активный потребитель, а поставщики, ожидающие producerLock, не замедляли активного поставщик, обновляющего last.

Конструктор всего лишь инициализирует начальное пустое состояние, а деструктор (в .NET или Java, это выполнит сборщик мусора), проходит по внутреннему списку и и уничтожает элементы.

public:
LowLockQueue() {
 first = last = new Node( nullptr );
 producerLock = consumerLock = false;
}
~LowLockQueue() {
 while( first != nullptr ) {        
   Node* tmp = first;
   first = tmp->next;
   delete tmp->value;      
   delete tmp;
 }
}

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

Мы в Microsoft всегда считаем, что стандарт можно улучшить.

Цитата, вынесенная в заголовок, уже стала крылатой (вот источник: "Основы COM" Дейл Роджерсон). И правда, могут...

Visual C++ departs from the ANSI Standard in its implementation of exception specifications. The following table summarizes the Visual C++ implementation of exception specifications:
...

throw(type): The function can throw an exception of type type. However, in Visual C++ .., this is interpreted as throw(...). (MSDN)

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

Вступление от переводчика. Позволю себе некоторое количество околофилософских замечаний перед десертом. В качестве же самого вкусного предлагаю Вашему вниманию попытку перевода-пересказа статьи "Writing a Generalized Concurrent Queue" by Herb Sutter. Первый номер Dr. Dobb's Journal попал мне в руки в далеком девяносто каком-то, наверное в девяносто третьем. Тогда, на буме проникновния IT в Россию этот журнал даже издавали у нас в переводе. Кроме прочего, в каждом номере бумажного издания публиковлась статья с подробным разбором алгоритма. Вот она, та, самая первая, прочитанная мной статья: "Fletcher's Checksum" by John Kodis. Ничего сверхъестественного, но это одна из тех вех, которая определила моё отношение к разработке эффективных алгоритмов. А именно: соображения целесообразности должны определять выбор используемого решения.

Две блокировки и неплохой результат.

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

Во-превых, мы будем использовать (эквивалент) двух блокировок: одной для управления поставщиками, другой, для управления потребителями. Кроме того, будем использовать атомарные переменные (C++0x atomic<>, Java/.NET volatile) напрямую, фактически реализуя цикл ожидания (spinlock), а не предоставляемые мютексы. Хотя это и означает, что алгоритм не полностью свободен от блокировок, тем не менее он позволяет множеству поставщиков и потребителей работать на столько одновременно, на сколько это возможно, минимизировав критический участок кода, обновляющий хвост и голову очереди.

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

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

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

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

Гарвардская архитектура и реализация printf()

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

Итак, потратив целый день на анализ кода различных вариаций printf() доступных в используемой clib (да, дизассемблер наш лучший друг) можно сделать следующие заключения. В предлагаемой в комплекте с IAR clib нет реализации printf() корректно работающей, когда и строка форматирования и аргументы расположены во флеше. Выход один - копировать в локальный буфер и выводить (привет ребятам и Гарварда, да идея мухи(код) отдельно, котлеты(код) отдельно неплоха, но если заранее не известно чего будет больше данных или кода, то получаем костыли компилятора типа __flash, позполяющие располагать данные в сегменте кода, и при уданом стечении обстоятельст пробежимся по все памяти обязательно).

Мысль следующая. Человеческая лень - неистребимое зло. Гораздо легче найти в интернете хрен знает какой код, чем почитать документаци. Вывод: если не хватает функционала, а самому писать лень или таланту не хватает, то следует использовать следующие варианты с понижением приоритета:

• стандартная библиотека
• сторонние реализации (чем более распространена реализация, тем лучше)
• все-таки писать самому и подружиться с отладчиком

Наконец, последнее.

за это нужно гнать из профессии:
#ifdef printf
#undef printf
#endif
#define printf printf_P

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

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

Так уж исторически случилось, что сейчас пишу под AVR, а точнее под ATmega64. Железка сама по себе интересная, с богатой переферией, но речь не об этом. Среда разработки IAR, компилятор их же. Это вводная, а теперь суть.

Есть у IAR'а некоторый набор расширений, для удобства, так сказать. Предметом разговора сегодня будет ключевое слово __monitor. Вот что нам говорит про него документация:

The __monitor keyword causes interrupts to be disabled during execution of the function. This allows atomic operations to be performed, such as operations on semaphores that control access to resources by multiple processes. A function declared with the __monitor keyword is equivalent to any other function in all other respects. (IAR C/C++ Compiler Reference Guide p. 210)

Ну что можно сказать, просто отлично, то что надо, кроме того, обещают:
A monitor function causes interrupts to be disabled during execution of the function. At function entry, the status register is saved and interrupts are disabled. At function exit, the original status register is restored, and thereby the interrupt status that existed before the function call is also restored. (IAR C/C++ Compiler Reference Guide p. 52)

А дальше приводиться пример кода реализующего атомарную блокировку ресурса. Всё бы хорошо, но не дайте себе обмануться. Может сложиться впечатление что по выходу из __monitor функции разрешает прерываия, но нет.

Понять, что такое поведение было бы некорректно, просто. Предположим случай вложенного вызова одной __monitor функции foo() из другой __monitor функции bar(). Если бы по выходу из foo() прерывания разрешались, то остаток bar() выполнялся бы не эксклюзивно и мог быть прерван. Такое поведение не предполагалось нами при объявлении bar(). Вызов не __monitor из bar() так же неоднозначен. Единственным разумным выходом оказалось не разрешать прерывания по выходу из __monitor функций, что и подтвердил дизассемблированный код.

Разработчики же документации на компилятор получают минус в карму за откровенный обман:
A monitor function causes interrupts to be disabled during execution of the function. At function entry, the status register SREG is saved and global interrupts are disabled. At function exit, the global interrupt enable bit (I) is restored in the SREG register, and thereby the interrupt status existing before the function call is also restored. (IAR C/C++ Compiler Reference Guide p. 107)

Из всего этого можно сделать простой вывод, что

только критическая оценка и эксперимент дают адекватное представление о действительности.

Начало

В то время, пока идеи статей потихоньку собираются мыслями в буквы, главная идея блога уже вполне оформилась. Последнее время, занимаясь систематизацией своих знаний по такой богатой на различные мифы и разночтения теме как программирование на C++ столкнулся с тем, как слабо люди понимают тот инструмент, которым пользуются ежедневно. Знание правил несомненно приводит их к результату за конечное время, и на этом можно было бы остановиться, но к сожалению, такой подход не может использоваться для решения принципиально новых задач; такие знания не переходят из навыка в понимания и никогда не станут фундаментом нового знания. А все остальное просто. Помните,

"Код должен быть ясным, алгоритм эффективным, а компилятор оптимизирующим."