3

Can anyone point me to a thread-safe implementation of the Copy-on-write (COW) idiom? The sample code on this site looks good -- is it thread-safe?

In case anyone is wondering what I will be using it for: I have a Foo class that has a std::map<int,double> member. Foo objects are copied very frequently in my code, but the copies rarely modify the contained map. I found that COW gives me a 22% performance boost, compared to copying the whole map contents in the Foo copy constructor, but my COW implementation crashes when multiple threads are used.

UPDATE:

Okay, here is the code, reduced to a minimal example, since you asked for it:

First, a reference-counting map:

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_;
};

And here is the class Foo that contains such a map RcMap, using a Copy-on-write mechanism:

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_;
};

I haven't yet been able to reproduce the crash using this minimal example, but in my original code it happens when I use the copy constructor or assignment operator of Foo objects in parallel. But maybe someone can spot the thread-safety bug?

Frank
  • 64,140
  • 93
  • 237
  • 324
  • And can anyone explain how to implement it using the Compare-and-swap idiom, as hinted here (http://en.wikipedia.org/wiki/Copy-on-write)? – Frank Nov 30 '10 at 00:57
  • 1
    If your COW is crashing, it might help if you can post a minimal code sample that illustrates the problem. Also, what kind of crash do you get? – Marcelo Cantos Nov 30 '10 at 01:06
  • Okay, I added a minimal code sample. The crash happens on `delete m_` in the `Foo` destructor. – Frank Nov 30 '10 at 02:13
  • If you can use C++0x, I'd suggest comparing move c'tor against your COW implementation to see which is faster. – Zach Saw Nov 30 '10 at 02:19
  • @Zach: it doesn't sound like that would fit his use case, because he seems to actually want a copy of the object. – Ken Bloom Nov 30 '10 at 02:40
  • @Zach: Would that look like this? `Foo(const Foo&& other) : m_(std::move(other.m_)) {}` Unfortunately, I only have access to gcc 4.1 currently, which doesn't support rvalue references. :( – Frank Nov 30 '10 at 02:44

3 Answers3

3

COW is inherently thread-safe, since the original is essentially immutable, and only the thread that induces the copy sees the copied version in the process of being created. You only need to watch for two things:

  1. Make sure the original doesn't get deleted by another thread while the copy is occurring. This an orthogonal problem, though (e.g., you could use thread-safe ref-counting).
  2. Make sure all the read operations you perform while copying are thread-safe. This is rarely a problem, but sometimes a read might populate a cache, for instance.
    • In fact, if this assumption is violated, that's a problem with the read operation not being thread-safe, and will probably affect more code than just the COW.
Marcelo Cantos
  • 181,030
  • 38
  • 327
  • 365
2

RcMap's reference counts need to be made atomic in order to be thread safe. In G++ 4.1, you an use the atomic builtins to implement this.

Ken Bloom
  • 57,498
  • 14
  • 111
  • 168
1

If you're copying a mutable map (it looks like you are), then don't decrease the reference count on the original object until after the copy is complete. (Because otherwise you may wind up allowing writes to the object you're copying, thereby breaking thread safety.)

Better yet, use a fully immutable map implementation (that makes copies and updates even cheaper by using shared substructure) if you can. There's a previous question on this topic that's currently unanswered.

Community
  • 1
  • 1
Ken Bloom
  • 57,498
  • 14
  • 111
  • 168