Потокобезопасная реализация идиомы Копировать при записи (COW)? - PullRequest
Новая
       7

Потокобезопасная реализация идиомы Копировать при записи (COW)?

3 голосов
/ 30 ноября 2010

Может кто-нибудь указать мне на потокобезопасную реализацию Копирование при записи (COW) идиома? Пример кода на этом сайте выглядит хорошо - он поточно-ориентирован?

Если кому-то интересно, для чего я буду его использовать: у меня есть класс Foo, в котором есть член std::map<int,double>. Foo объекты очень часто копируются в мой код, но копии редко изменяют содержимое map. Я обнаружил, что COW дает мне повышение производительности на 22% по сравнению с копированием всего содержимого карты в конструкторе копирования Foo, но моя реализация COW дает сбой при использовании нескольких потоков.

UPDATE

Хорошо, вот код, приведенный к минимальному примеру, поскольку вы его просили:

Во-первых, карта подсчета ссылок: 

class RcMap {                             
 public:
  typedef std::map<int,double> Container;
  typedef Container::const_iterator const_iterator;
  typedef Container::iterator iterator;

  RcMap() : count_(1) {}

  RcMap(const RcMap& other) : count_(1) {
    m_ = other.Get();
  }

  unsigned Count() const { return count_; }
  unsigned IncCount() { return ++count_; }
  unsigned DecCount() {
    if(count_ > 0) --count_;
    return count_;
  }
  void insert(int i, double d) {
    m_.insert(std::make_pair(i,d));
  }
  iterator begin() { return m_.begin(); }
  iterator end() { return m_.end(); }
  const_iterator begin() const { return m_.begin(); }
  const_iterator end() const { return m_.end(); }

 protected:
  const Container& Get() const { return m_; }

 private:
  void operator=(const RcMap&); // disallow

  Container m_;
  unsigned count_;
};

А вот класс Foo, который содержит такую ​​карту RcMap с использованием механизма копирования при записи: 

class Foo {
 public:
  Foo() : m_(NULL) {}

  Foo(const Foo& other) : m_(other.m_) {
    if (m_) m_->IncCount();
  }

  Foo& operator= (const Foo& other) {
    RcMap* const old = m_;
    m_ = other.m_;
    if(m_ != 0)
      m_->IncCount();
    if (old != 0 && old->DecCount() == 0) {
      delete old;
    }
    return *this;
  }

  virtual ~Foo() {
    if(m_ != 0 && m_->DecCount() == 0){
      delete m_;
      m_ = 0;
    }
  }

  const RcMap& GetMap() const {
    if(m_ == 0)
      return EmptyStaticRcMap();
    return *m_;
  }

  RcMap& GetMap() {
    if(m_ == 0)
      m_ = new RcMap();
    if (m_->Count() > 1) {
      RcMap* d = new RcMap(*m_);
      m_->DecCount();
      m_ = d;
    }
    assert(m_->Count() == 1);
    return *m_;
  }

  static const RcMap& EmptyStaticRcMap(){
    static const RcMap empty;
    return empty;
  }

 private:
  RcMap* m_;
};

Мне пока не удалось воспроизвести сбой, используя этот минимальный пример, но в моем исходном коде это происходит, когда я использую конструктор копирования или оператор присваивания Foo объектов параллельно. Но, может быть, кто-то может обнаружить ошибку безопасности потока?

Ответы [ 3 ]

3 голосов
/ 30 ноября 2010

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

  1. Убедитесь, что оригинал не удаляется другим потоком во время копирования. Однако это ортогональная проблема (например, вы можете использовать поточный счетчик ссылок).
  2. Убедитесь, что все операции чтения, которые вы выполняете во время копирования, являются поточно-ориентированными. Это редко проблема, но иногда чтение может заполнить кеш, например.
    • На самом деле, если это предположение нарушается, проблема в том, что операция чтения не является поточно-ориентированной, и, вероятно, повлияет на большее количество кода, чем просто COW.
2 голосов
/ 30 ноября 2010
Счетчик ссылок

RcMap должен быть атомарным, чтобы быть потокобезопасным. В G ++ 4.1 вы используете атомарные встроенные для реализации этого.

1 голос
/ 30 ноября 2010

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

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

...