Lock-free queues
Подписан я на работе на журнал Dr.Dobb's Journal. Уже хотел отписаться, как в июльском номере наконец-то нашел пару интересных статей. Одна из них про Lock-free queues (от программиста из Morgan Stanley, который там в должности Vice President — там что, все программисты вице-президенты?).

Главная фича таких очередей — один поток может туда писать, а второй оттуда читать без всяких синхронизаций, а значит без потерь времени на них.
Реализуется очень просто на любом языке программирования, например на c++:

template<typename T>
struct LockFreeQueue
{
  LockFreeQueue()
  {
    list.push_back(T());
    iHead = list.begin();
    iTail = list.end();
  }

  void Produce(const T& t)
  {
    list.push_back(t);
    iTail = list.end();
    list.erase(list.begin(), iHead);
  }

  bool Consume(T& t)
  {
    typename TList::iterator iNext = iHead;
    ++iNext;
    if (iNext != iTail)
    {
      iHead = iNext;
      t = *iHead;
      return true;
    }
  return false;
  }

private:
  typedef std::list<T> TList;
  TList list;
  typename TList::iterator iHead, iTail;
};

Это весь код!
Единственное ограничение — может быть только 1 поток-писатель и только 1 поток-читатель. Иначе нужно уже их было бы синхронизировать.
Большая часть статьи посвящена тестам и тому, как сделать так, чтобы Consume не ждал долго и не съедал 100% CPU, когда очередь пустая. Предлагается использовать всякие Sleep и nanosleep. Но вывод таков, что под Windows все равно ты можешь получить 10 милисекунд и больше при вызове даже nanosleep.
Имхо, тут лучший вариант — засыпать в потоке-читателе, когда очередь пуста и будить этот поток в потоке-писателе после вызова Produce — тогда и CPU usage не пострадает и данные будут обрабатываться мгновенно.

Кто-нибудь знает недостатки этого метода? Или какой-нибудь другой настолько же простой и эффективный?

Кросспост с http://bishop3000.livejournal.com/20588.html

Здравствуйте, _Bishop_, Вы писали:
...
_B_>Кто-нибудь знает недостатки этого метода? Или какой-нибудь другой настолько же простой и эффективный?

Из-за std::list<T>::push_back это можно выбросить.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, _Bishop_, Вы писали:
А>...
_B_>>Кто-нибудь знает недостатки этого метода? Или какой-нибудь другой настолько же простой и эффективный?

А>Из-за std::list<T>::push_back это можно выбросить.

Из-за cache miss в std::list?
Но это можно решить своими алокаторами, которые стараются память последовательно выделять.
Или что еще?

Здравствуйте, _Bishop_, Вы писали:

А>>Из-за std::list<T>::push_back это можно выбросить.

_B_>Из-за cache miss в std::list?
_B_>Но это можно решить своими алокаторами, которые стараются память последовательно выделять.
_B_>Или что еще?

По умолчанию там используется блокирующий new, применение которого в алгоритмах претендующих на lock-free выглядит весьма странно.

Здравствуйте, _Bishop_, Вы писали:

_B_>Lock-free queues
_B_>Подписан я на работе на журнал Dr.Dobb's Journal. Уже хотел отписаться, как в июльском номере наконец-то нашел пару интересных статей. Одна из них про Lock-free queues (от программиста из Morgan Stanley, который там в должности Vice President — там что, все программисты вице-президенты?).

_B_>Большая часть статьи посвящена тестам и тому, как сделать так, чтобы Consume не ждал долго и не съедал 100% CPU, когда очередь пустая. Предлагается использовать всякие Sleep и nanosleep. Но вывод таков, что под Windows все равно ты можешь получить 10 милисекунд и больше при вызове даже nanosleep.
_B_>Имхо, тут лучший вариант — засыпать в потоке-читателе, когда очередь пуста и будить этот поток в потоке-писателе после вызова Produce — тогда и CPU usage не пострадает и данные будут обрабатываться мгновенно.

_B_>Кто-нибудь знает недостатки этого метода? Или какой-нибудь другой настолько же простой и эффективный?

_B_>Кросспост с http://bishop3000.livejournal.com/20588.html

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

Здравствуйте, _Bishop_, Вы писали:


_B_> void Produce(const T& t)
_B_> {
_B_> list.push_back(t);
_B_> iTail = list.end();
_B_> list.erase(list.begin(), iHead);
_B_> }

_B_> bool Consume(T& t)
_B_> {
_B_> typename TList::iterator iNext = iHead;
_B_> ++iNext;
_B_> if (iNext != iTail)
_B_> {
_B_> iHead = iNext;
_B_> t = *iHead;
_B_> return true;
_B_> }
_B_> return false;
_B_> }

не совсем понятно,
первый:
>list.erase(list.begin(), iHead);
второй:
>iHead = iNext;

предполагается что запись машинного слова атомарна,
или я что-то не увидел?

Здравствуйте, merk, Вы писали:

M>Здравствуйте, _Bishop_, Вы писали:

_B_>>Lock-free queues
_B_>>Подписан я на работе на журнал Dr.Dobb's Journal. Уже хотел отписаться, как в июльском номере наконец-то нашел пару интересных статей. Одна из них про Lock-free queues (от программиста из Morgan Stanley, который там в должности Vice President — там что, все программисты вице-президенты?).

_B_>>Большая часть статьи посвящена тестам и тому, как сделать так, чтобы Consume не ждал долго и не съедал 100% CPU, когда очередь пустая. Предлагается использовать всякие Sleep и nanosleep. Но вывод таков, что под Windows все равно ты можешь получить 10 милисекунд и больше при вызове даже nanosleep.
_B_>>Имхо, тут лучший вариант — засыпать в потоке-читателе, когда очередь пуста и будить этот поток в потоке-писателе после вызова Produce — тогда и CPU usage не пострадает и данные будут обрабатываться мгновенно.

_B_>>Кто-нибудь знает недостатки этого метода? Или какой-нибудь другой настолько же простой и эффективный?

_B_>>Кросспост с http://bishop3000.livejournal.com/20588.html

M>а теперь покажите разницу между засыпанием на мьютексе и каким-то тут еще засыпанием...с пробуждением.
M>разницы-то нет!
M>тема эта недавно обсасывалась в "общих вопросах програмирования", в топике — критическая секция на...
короче тут. но там нужны атомарные операции.
http://rsdn.ru/forum/message/2988602.1.aspx

Здравствуйте, _Bishop_, Вы писали:

_B_>Кто-нибудь знает недостатки этого метода?

http://groups.google.ru/group/comp.programming.threads/browse_frm/thread/effb92d0bfb53962

Здравствуйте, _Bishop_, Вы писали:

_B_>Lock-free queues
_B_>Подписан я на работе на журнал Dr.Dobb's Journal. Уже хотел отписаться, как в июльском номере наконец-то нашел пару интересных статей. Одна из них про Lock-free queues (от программиста из Morgan Stanley, который там в должности Vice President — там что, все программисты вице-президенты?).


Мне кажется этот код не имеет большого смысла, если только не как академическая задача. Обыкновенная CriticalSection в большинстве случаев неблокирующая. Она просто инрементирует щетчик входов через Interlocked операции. Таким образом, если один поток вызывает Produce, а другой Consume, то никаких ожиадний не происходит пока эти вызовы не перекрылись по времени. Так как операция вставки (push) и выемки (pop) черезвычайно быстрые (константое время, которое раскрывается в доступ по указателю), то и одновременное выполнение Produce и Consume редкий случай и нормально использовать обычную критическую секцию, которая синхронизирует эти операции. Нужно иметь ввиду, что в "T" может быть реализовать сложный и медленный оператор =, который возникает в методе Consume. В таком случае лучше хранить в очереди shared_ptr<T> — здесь время копирования ничтожно мало.

Оригинальный код можно переписать как:

template<typename T>
struct LockFreeQueue
{

CRITICAL_SECTION m_CritSec;
std::deque<T>    m_queue;


LockFreeQueue()
{
    InitializeCriticalSection(&m_CritSec);
}

~LockFreeQueue()
{
    DeleteCriticalSection(&m_CritSec);
}

void Produce(const T& t)
{
    CLock crc(m_CritSec);
    m_queue.push_front(t);
}

bool Consume(T& t)
{
    CLock crc(m_CritSec);
    if( m_queue.empty()) 
       return false;
    t = m_queue.front  ();
    m_queue.pop_front();
    return true;
}
};

Здравствуйте, _Bishop_, Вы писали:

_B_>Кто-нибудь знает недостатки этого метода? Или какой-нибудь другой настолько же простой и эффективный?

Основной недостаток — что это нерабочий код.
Во-первых, итераторы std::list<> не атомарно читаются/пишутся.
Во-вторых, не упорядочиваются обращения к памяти.

Другой способ — корректно реализовать single-producer/single-consumer очередь. Вариаций много — на чём основывать очередь (list, vector, nested-list), интрузивная/неинтрузивная.


_B_>Имхо, тут лучший вариант — засыпать в потоке-читателе, когда очередь пуста и будить этот поток в потоке-писателе после вызова Produce — тогда и CPU usage не пострадает и данные будут обрабатываться мгновенно.

Слабо набросать вариант реализации?

Здравствуйте, remark, Вы писали:

R>Здравствуйте, _Bishop_, Вы писали:

_B_>>Кто-нибудь знает недостатки этого метода? Или какой-нибудь другой настолько же простой и эффективный?

R>Основной недостаток — что это нерабочий код.
R>Во-первых, итераторы std::list<> не атомарно читаются/пишутся.
R>Во-вторых, не упорядочиваются обращения к памяти.

В статью внесены соотв. правки:

http://www.ddj.com/hpc-high-performance-computing/208801974

This article as written assumes a sequentially consistent model. In particular, the code relies on specific order of instructions in both Consumer and Producer methods. However, without inserting proper memory barrier instructions, these instructions can be reordered with unpredictable results (see, for example, the classic Double-Checked Locking problem).

Another issue is using the standard std::list<T>. While the article mentions that it is the developer responsibility to check that the reading/writing std::list<T>::iterator is atomic, this turns out to be too restrictive. While gcc/MSVC++2003 get it right (4-byte iterator), the MSVC++2005 has 8-byte iterators in Release Mode and 12-byte iterators in the Debug Mode.

The solution to prevent this is to use memory barriers/volatile variables. The downloadable code for the article has fixed that issue.