一 简介
Copy-On-Write 简称 COW, 是一种用于程序设计中的优化策略. 其基本思路是, 从一开始大家都在共享同一个内容, 当某个人想要修改这个内容的时候, 才会真正把内容 Copy 出去形成一个新的内容然后再改, 这是一种延时懒惰策略. 总的来说, COW 通过浅拷贝 (shallow copy) 只复制引用而避免复制值; 当的确需要进行写入操作时, 首先进行值拷贝, 再对拷贝后的值执行写入操作, 这样减少了无谓的复制耗时.
CopyOnWrite 并发容器用于读多写少的并发场景. 比如白名单, 黑名单, 商品类目的访问和更新场景, 假如我们有一个搜索网站, 用户在这个网站的搜索框中, 输入关键字搜索内容, 但是某些关键字不允许被搜索. 这些不能被搜索的关键字会被放在一个黑名单当中, 黑名单每天晚上更新一次. 当用户搜索时, 会检查当前关键字在不在黑名单当中, 如果在, 则提示不能搜索.
CopyOnWrite 有很多优点, 但是同时也存在两个问题, 即内存占用问题和数据一致性问题. 所以在开发的时候需要注意一下.
内存占用问题. 因为 CopyOnWrite 的写时复制机制, 所以在进行写操作的时候, 内存里会同时驻扎两个对象的内存, 旧的对象和新写入的对象(注意: 在复制的时候只是复制对象的引用, 只是在写的时候会创建新对象(之前对象的 copy), 而旧对象还在使用, 所以有两份对象内存, 这对于 c++ 这种不需要 gc 的语言来说, 无非是占用额外的内存, 但是对于 java 等需要 gc 的语言来说, 不光是占用内存这么简单, 有可能会引起 full gc, 造成 stw 时间过长).
数据一致性问题. CopyOnWrite 容器只能保证数据的最终一致性, 不能保证数据的实时一致性. 所以如果你希望写入的的数据, 马上能读到, 请不要使用 CopyOnWrite 容器.
二 标准 C++ 类 std::string 的 Copy-On-Write
在我们经常使用的 STL 标准模板库中的 string 类, 也是一个具有写时才拷贝技术的类. C++ 曾在性能问题上被广泛地质疑和指责过, 为了提高性能, STL 中的许多类都采用了 Copy-On-Write 技术. 这种偷懒的行为的确使使用 STL 的程序有着比较高要性能.
我们来看一段别人的代码.
- #include <string>
- #include <cstring>
- #include <cstdio>
- #include <iostream>
- using namespace std;
- int main()
- {
- string str1 = "hello world";
- string str2 = str1;
- printf ("Sharing the memory:\n");
- printf ("str1's address: %x\n", str1.c_str());
- printf ("str2's address: %x\n", str2.c_str());
- str1[1]='q';
- str2[1]='w';
- printf ("After Copy-On-Write:\n");
- printf ("str1's address: %x\n",str1.c_str());
- printf ("str2's address: %x\n",str2.c_str());
- printf("Hello world!");
- return 0;
- }
运行结果
g++ 版本 6.2 运行环境
我们可以看到, 在修改两个 string 之前他们的地址是一样的, 修改后地址就变了, 这就是在 write 的时候发生了 copy.
透过现象看本质, 这种机制实际上就是对象之间的内存共享, 那么如何管理这块共享的内存呢, 最简单有效的方法就是引用计数了.
我们先看一下 c++ 源码中的一个结构:
- struct _Rep_base
- {
- size_type _M_length;
- size_type _M_capacity;
- _Atomic_word _M_refcount;
- };
我们可以看到一个名为_M_refcount 的变量, 他就记录了当前引用该 string 所持有的字符数组实际内存的数量. 根据我们的需求只要每当我们为 string 分配内存时, 我们总是要多分配一个空间用来存放这个引用计数的值, 只要发生拷贝构造可是赋值时, 这个内存的值就会加一. 而在内容修改时, string 类为查看这个引用计数是否为 0, 如果不为零, 表示有人在共享这块内存, 那么自己需要先做一份拷贝, 然后把引用 计数减去一, 再把数据拷贝过来. 首先我们来看操作这个引用值得方法.
bool _M_is_leaked() const _GLIBCXX_NOEXCEPT // 所有引用者是否已释放
- {
- #if defined(__GTHREADS)
- return __atomic_load_n(&this->_M_refcount, __ATOMIC_RELAXED) <0;
- #else
- return this->_M_refcount <0;
- #endif
- }
- bool _M_is_shared() const _GLIBCXX_NOEXCEPT // 当前是否有对象引用
- {
- #if defined(__GTHREADS)
- return __atomic_load_n(&this->_M_refcount, __ATOMIC_ACQUIRE)> 0;
- #else
- return this->_M_refcount> 0;
- #endif
- }
- // 设置当前内存已释放(不可用)
- void_M_set_leaked() _GLIBCXX_NOEXCEPT
- { this->_M_refcount = -1; }
- // 设置当前的内存可用(可共享当前引用数为 0)
- void _M_set_sharable() _GLIBCXX_NOEXCEPT
- { this->_M_refcount = 0; }
- void _M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT // 释放一个引用
- {
- #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
- if (__builtin_expect(this != &_S_empty_rep(), false))
- #endif
- {
- if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
- -1) <= 0) // 如果当前的引用数小于等于 0 书房
- {
- _M_destroy(__a);
- }
- }
- } // XXX MT
- _CharT*//copy 后增加一个引用
- _M_refcopy() throw()
- {
- #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
- if (__builtin_expect(this != &_S_empty_rep(), false))
- #endif
- __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
- return _M_refdata();
- } // XXX MT
这里我们要注意所有改变引用计数的操作如果有必要都是原子操作(c++11), 是线程安全的, copy on write 在历史的 c++ 版本里曾因为线程安全的问题被抛弃(所以如果你的 c++ 版本运行第一段程序没有出现和我一样的结果升级 c++ 版本后 try again), 但是 c++11 后标准库添加了原子操作问题自然就解决了.
接下来就是最关键的部分了, 只要在拷贝, 复制时改变引用值就可以了.
- template<typename _CharT, typename _Traits, typename _Alloc> // 拷贝构造函数
- basic_string<_CharT, _Traits, _Alloc>::
- basic_string(const basic_string& __str)
- : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
- __str.get_allocator()),
- __str.get_allocator())
- { }
- _CharT* _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
- {
- // 如果相等则增加引用,_M_refcopy 函数见上, 否则调用_M_clone 函数 copy 目标
- return (!_M_is_leaked() && __alloc1 == __alloc2) ? _M_refcopy() : _M_clone(__alloc1);
- }
~basic_string() _GLIBCXX_NOEXCEPT
{ _M_rep()->_M_dispose(this->get_allocator()); } // 析构函数释放引用
家下来看赋值操作符
- basic_string&
- operator=(const basic_string& __str)
- { return this->assign(__str); }
- template<typename _CharT, typename _Traits, typename _Alloc>
- basic_string<_CharT, _Traits, _Alloc>&
- basic_string<_CharT, _Traits, _Alloc>::
- assign(const basic_string& __str)
- {
- if (_M_rep() != __str._M_rep()) // 如果不是自赋值
- {
- // XXX MT
- const allocator_type __a = this->get_allocator();
- _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); // 拷贝目标
- _M_rep()->_M_dispose(__a); // 释放原来的引用
- _M_data(__tmp);
- }
- return *this;
- }
看到这里所有关于 c++string copy on write 的操作都清楚了, 不过 string 的内存布局还是有一点意思的, 我们知道除了 string 的 char * 其他 string 有关的信息存储在一个 Rep 对象中 (集成了_Rep_base 见上) 为了一次申请 string 所有的内存, string 把次对象和 char * 数组放在了同一个 char * 指针里, 当要取此对象是就去该指针的 - 1 索引.
- struct _Alloc_hider : _Alloc //string 实际的内部对象构造类型
- {
- _Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT
- : _Alloc(__a), _M_p(__dat) { }
- _CharT* _M_p; // The actual data.
- };
mutable _Alloc_hider _M_dataplus;
_Rep* _M_rep() const _GLIBCXX_NOEXCEPT // 获取长度, 引用数等信息对象
{ return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
_CharT* _M_data() const _GLIBCXX_NOEXCEPT
{ return _M_dataplus._M_p; }
说到这里可以看到现在 c++string 的实现相当的复杂, 更多的细节就不说了, 看源码是最直接有效的方法. 现在想想面试的时候我们自己实现的 string 类简直弱爆了.
来源: https://blog.csdn.net/d_guco/article/details/79833665