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