什么是Copy On Write

Copy On Write(COW)作为一种优化技术被广泛使用，在string的实现中也不例外。考虑如下的代码：

1
2
3

string s("1234");
string t = s;
cout<<t[1]<<endl;

第二行，通过调用copy constructor（注意，这里调用的是copy constructor，而不是copy assignment，因为它是从无到有构造对象，而不是设置已有对象）构造对象t，第三行对t中的某个元素进行只读操作。

如果让你实现copy constructor，你会怎么做呢？教科书里的、简单的实现大概是这样：

1
2
3
4
5
6
7
8
9
10

class string
{
  private:
    char *data_;
};
string(const string &other)
{
  data_ = new char[strlen(other.data_) + 1/*加1是考虑\0*/];
  strcpy(data_, other.data_);
}

好了，既然只是对t进行只读，那么就没完全必要分配内存、拷贝字符串等昂贵操作了，而是复用s的字符串空间即可。这就是我们要谈到的string中的COW。

如何实现Copy On Write

显然，现在是有多个对象绑定或者说涉及或者说引用到某个字符串缓冲区上了。事实上，正如你能想到的，引用计数（Reference Counting，RC）是实现COW的重要基础。当执行上面最上面代码的第二行时，并不为t分配内存、拷贝字符串，而是相应的字符串的引用计数加1即可。

我们把buffer和引用计数抽离出来，单独放到某处。这种实现方式一般称为非侵入式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

struct stringvalue
{
    char *data_;
    int rc_;
}
class string
{
  private:
    stringvalue *sv_;
};
string(const string &other)
{
  sv_ = other.sv_;
  (other.sv_)->rc_++;
}

就这么简单，仅仅是attach，仅仅是增加引用计数。没有memory allocation，没有strcpy或者memcpy了。

如果仅仅是只读操作，那么这没任何问题。但是如果要写了呢？这时候没办法了，必须复制了。这就是所谓lazy evaluation，拖延战术(对应的是eager evaluation)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void set_char(const int idx, char new_char)
{
  if (sv_->rc_ > 1) {
    //引用计数至少是2。说明除了自己，还有别人也引用到了这个buffer，不得不分配内存了，否则影响到别人了。
    stringvalue *tmp = sv_;
    sv_ = new stringvalue();//重新搞一份
    sv_->data_ = new char[strlen(tmp->char_) + 1];
    strcpy(sv_->data_, tmp->char_);
    sv_->rc_ = 1;
    --tmp->rc_;//把原来的引用计数减1
    //......
} else {
  //......
}

Copy On Write 会带来什么问题？

在单线程环境下，使用Copy On Write不容易出问题。不过多线程下，就险象环生了。

如果string内部做同步，那么这无疑增加了string的实现复杂度，并且STL的初衷其实是只考虑单线程环境的。同步操作无疑会带来大量的开销。

如果string内部不做同步，那么问题就来了。

加锁啊，加锁不就完了么？没那么容易。你看：

1
2
3
4
5
6
7

 string s;//临界资源，全局变量
 void f()
 {
   lock.lock();
   string t = s;
   lock.unlock();
   //这里可能读写操作t

那么，对t的操作也得加锁，如果有人通过t又复制了一个对象w，那么操作w的时候也得加锁，这太难了。这里，本质困难在于，可能会有很多对象，我们无法控制的对象都绑定到一块buffer上。

不过这样也没什么，毕竟不管有没有使用COW，使用STL时候都不应该对它有多线程安全的幻想。但是使用COW后确实更加危险，因为加锁的难度变大了，甚至都不知道在哪里加了。

想想看，在多线程环境下，假如string使用了COW优化，将c_str()返回的指针强制去掉const，以及operator []的读写可能会有什么问题。

使用Copy On Write 么？

假如你是库设计和实现者，你会用COW么？

Soupen是一款高性能的nosql数据库，旨在能在某些方面替代Redis。它由不著名码农、秦汉史历史学家、本站站长Yebangyu同学在业余时间独立开发完成。

Soupen也实现了自己的string，并不使用Copy On Write(lazy evaluation)。而是使用eager evaluation，立即分配内存，立即拷贝。

在我们的应用中，调用copy constructor后对它进行写（而不是只读）的概率很大，拉拉扯扯各种引用计数加加减减，还不如直接分配+拷贝，反正后面也要做这个工作，何必自寻烦恼。

而且Soupen是服务器，不是类库，使用者是自己而不是广大用户，不需要考虑各种各样的情况。

当然，对于短字符串Soupen是做了优化的，可以参考这里的源码解读。