建站
咨詢
售后
建站咨詢
新聞中心
[[170381]]
Copy-on-write(以下簡稱COW)是一種很重要的優(yōu)化手段。它的核心思想是懶惰處理多個實體的資源請求，在多個實體之間共享某些資源，直到有實體需要對資源進行修改時，才真正為該實體分配私有的資源。
COW技術(shù)的一個經(jīng)典應(yīng)用在于Linux內(nèi)核在進程fork時對進程地址空間的處理。由于fork產(chǎn)生的子進程需要一份和父進程內(nèi)容相同但完全獨立的地址空間，一種做法是將父進程的地址空間完全復(fù)制一份，另一種做法是將父進程地址空間中的頁面標記為”共享的“(引用計數(shù)+1)，使子進程與父進程共享地址空間，但當有一方需要對內(nèi)存中某個頁面進行修改時，重新分配一個新的頁面(拷貝原內(nèi)容)，并使修改進程的虛擬地址重定向到新的頁面上。
COW技術(shù)有哪些優(yōu)點呢?
1. 一方面減少了分配(和復(fù)制)大量資源帶來的瞬間延遲(注意僅僅是latency，但實際上該延遲被分攤到后續(xù)的操作中，其累積耗時很可能比一次統(tǒng)一處理的延遲要高，造成throughput下降是有可能的)
2. 另一方面減少不必要的資源分配。(例如在fork的例子中，并不是所有的頁面都需要復(fù)制，比如父進程的代碼段(.code)和只讀數(shù)據(jù)(.rodata)段，由于不允許修改，根本就無需復(fù)制。而如果fork后面緊跟exec的話，之前的地址空間都會廢棄，花大力氣的分配和復(fù)制只是徒勞無功。)
COW的思想在資源管理上被廣泛使用，甚至連STL中的std::string的實現(xiàn)也要沾一下邊。陳碩的這篇博客《C++工程實踐(10)：再探std::string》充分探討了各個STL實現(xiàn)中對std::string的實現(xiàn)方式，其中g(shù)++ std::string和Apache stdcxx就使用了COW技術(shù)。(其他對std::string的實現(xiàn)包括eager copy和small string optimization，建議參考原博客，圖文并茂十分清楚)
很簡單一段代碼，就能查看當前std::string實現(xiàn)是否使用了COW：
- std::string a = "A medium-sized string to avoid SSO";
- std::string b = a;
- //a.data() == b.data()?
- b.append('A');
- //a.data() == b.data()?
如果實現(xiàn)使用了COW，那么第一個比較會返回true，第二個比較會返回false。經(jīng)測試libstdc++(gcc 4.5)確實使用了COW，而查看STL中string的源碼，也確實采用了引用計數(shù)的手段。
但要注意，std::string的lazy-copy行為只發(fā)生在兩個string對象之間的拷貝構(gòu)造，賦值和assign()操作上，如果一個string由(const)char*構(gòu)造而來，則必然會分配內(nèi)存和進行復(fù)制，因為string對象并不知道也無權(quán)控制char*所指內(nèi)存的生命周期。
- std::string a = "Hello";
- std::string b = "Hello";//Never COW!
- assert(b.data() != a.data());
- std::string c = a.data();//Never COW!
- assert(c.data() != a.data());
實際上，std::string c = a.data()確實是一種在字符串賦值時禁止COW行為的方法。
看起來使用COW管理string來減少不必要的拷貝似乎很有效，然而在多數(shù)C++ STL實現(xiàn)中，只有寥寥兩種使用了COW，而同樣著名的Visual C++(2010)和clang libc++卻不約而同拋棄了COW，選擇了SSO(small string optimization，足夠小的字符串直接放在對象本身的棧內(nèi)存中，避免了向Heap動態(tài)請求內(nèi)存的開銷)。
SSO對小字符串的高效是原因之一(程序中通常會有大量的短字符串)，而COW本身的缺陷更是原因之一。
一、性能：for thread-safety!
想要實現(xiàn)COW，必須要有引用計數(shù)(reference count)。string初始化時rc=1，每當該string賦值給了其他sring，rc++。當需要對string做修改時，如果rc>1，則重新申請空間并復(fù)制一份原字符串的拷貝，rc--。當rc減為0時，釋放原內(nèi)存。
基于”共享“和”引用“計數(shù)的COW在多線程環(huán)境下必然面臨線程安全的問題。那么：
std::string是線程安全的嗎?
在stackoverflow上對這個問題的一個很好的回答：是又不是。
從在多線程環(huán)境下對共享的string對象進行并發(fā)操作的角度來看，std::string不是線程安全的，也不可能是線程安全的，像其他STL容器一樣。
c++11之前的標準對STL容器和string的線程安全屬性不做任何要求，甚至根本沒有線程相關(guān)的內(nèi)容。即使是引入了多線程編程模型的C++11，也不可能要求STL容器的線程安全：線程安全意味著同步，同步意味著性能損失，貿(mào)然地保證線程安全必然違背了C++的哲學(xué)：
Don't pay for things you don't use.
但從不同線程中操作”獨立“的string對象來看，std::string必須是線程安全的。咋一看這似乎不是要求，但COW的實現(xiàn)使兩個邏輯上獨立的string對象在物理上共享同一片內(nèi)存，因此必須實現(xiàn)邏輯層面的隔離。C++0x草案(N2960)中就有這么一段：
The C++0x draft (N2960) contains the section "data race avoidance" which basically says that library components may access shared data that is hidden from the user if and only if it activly avoids possible data races.
簡單說來就是：你瞞著用戶使用共享內(nèi)存是可以的(比如用COW實現(xiàn)string)，但你必須負責處理可能的競態(tài)條件。
而COW實現(xiàn)中避免競態(tài)條件的關(guān)鍵在于：
1. 只對引用計數(shù)進行原子增減
2. 需要修改時，先分配和復(fù)制，后將引用計數(shù)-1(當引用計數(shù)為0時負責銷毀)
先談?wù)勗硬僮鳎?/strong>
不同的體系結(jié)構(gòu)一般會有不同的底層原語以支持原子操作。如Intel CPU本身就引入了#LOCK指令前綴，該前綴允許置于指定的操作(如算法指令、邏輯指令、bit指令、exchange指令等)之前使用，如lock inc會在執(zhí)行inc指令時鎖總線(鎖定包含目標地址的一片內(nèi)存區(qū)域，防止其他CPU在此期間的并發(fā)訪問)，從而序列化對同一地址的訪問。
比起mutex之類的同步手段，原子操作自然要輕上不少，但比起普通的算術(shù)指令，依然算得上完全的重量級：
1. 系統(tǒng)通常會lock住比目標地址更大的一片區(qū)域，影響邏輯上不相關(guān)的地址訪問。
2. lock指令具有”同步“語義，會阻止CPU本身的亂序執(zhí)行優(yōu)化。
Intel Developer's Manual vol 3的chapter 8 : Multiple-Processor Management中就有提到：
"Locked instructions can be used to synchronize data written by one processor and read by another processor."
也就是會等待之前發(fā)出的load和store指令的完成(由于CPU store buffer的存在，如果數(shù)據(jù)之前沒有依賴，不需要等待load和store的結(jié)果)
3. 兩個CPU對同一個地址進行原子操作，必然會導(dǎo)致cache-bounce。SMP系統(tǒng)中由于Cache一致性協(xié)議的存在，一個CPU對共享內(nèi)存的修改必然會invalidate另一個CPU對該地址的cache，最終導(dǎo)致兩個CPU對同一片內(nèi)存不斷”爭奪“(cache不斷被對方invalidate，需要重新從內(nèi)存中讀取)，這是多線程編程中經(jīng)典的False Sharing問題。
歸根結(jié)底，COW為了保證”線程安全“而使用了原子操作，而原子操作本身的效率并不十分高。而且在多線程環(huán)境下，多個CPU對同一個地址的原子操作開銷更大。COW中”共享“的實現(xiàn)，反而影響了多線程環(huán)境下string”拷貝“的性能，并不scale。
再談?wù)劜僮黜樞颍?/strong>
為了避免競態(tài)條件，在需要修改string時，如果引用計數(shù)>1，必須先分配和拷貝，然后才能將引用計數(shù)減1。(而不能先減1再拷貝)
某些條件下，這樣的操作序列會導(dǎo)致不必要的額外操作：
string A在線程1中訪問，string B在線程2中訪問，string A 和 string B 共享同一片內(nèi)容(rc = 2)
假設(shè)當線程1操作string A時線程2恰好也在操作string B，雙方發(fā)現(xiàn)該string的內(nèi)容是共享的，都遵守先分配復(fù)制，后減引用計數(shù)的執(zhí)行序列。(最終會有一方發(fā)現(xiàn)rc=0，銷毀原string內(nèi)容)。
到此為止，COW一共進行了3次內(nèi)存分配和復(fù)制(初始化時1次，修改時2次)和1次內(nèi)存釋放
實際上，如果沒有使用COW技術(shù)，從string的初始化到目前為止也只進行了2次內(nèi)存分配和復(fù)制(都是在初始化時進行)
二、”失效“問題：草木皆兵!
假設(shè)當前的string實現(xiàn)是COW，考慮下面的代碼：
- std::string a = "some string";
- std::string b = a;
- assert(b.data() == a.data());// We assume std::string is COW-ed
- std::cout << b[0] << std::endl;
- assert(b.data() != a.data()); // Oops!
程序僅僅以”只讀“的方式訪問了b中一個字符，但b已經(jīng)進行了一份私有的拷貝，a與b不再共享同一片內(nèi)容。
由于string的operator[]和at()會返回某個字符的引用，而判斷程序是否更改了該字符實在是超出string本身能力范圍的東西，為了保證COW實現(xiàn)的正確性，string只得統(tǒng)統(tǒng)認定operator[]和at()具有修改的“語義”。
連begin()/end()也不能幸免，天曉得用戶取得迭代器后會做什么!
這些無奈的”write alarm“實際上是由于std::string本身接口的定義上沒有對”只讀“和”修改“語義做嚴格的區(qū)分。
為此，Alexandrescu在它的”Scalable Use of STL“的演講中對std::string的接口做了如下建議：
1. offer set(n, c)
2. make default iterator non-mutating
僅僅是建議而已，實際上他本人反對使用COW：
"The COW is dead, long live eager-copy"
總結(jié)：
1. string的COW實現(xiàn)確有諸多的弊端，并不如想象中那般美好，也因此受到了Visual C++和clang++的拋棄，轉(zhuǎn)而使用實現(xiàn)簡單，且對小字符串更友好的SSO實現(xiàn)。
2. Alexandrescue在他的“Scalable Use of STL”中建議對性能敏感的程序?qū)崿F(xiàn)自己的string，比如針對string的長度進行選擇優(yōu)化(短字符串SSO，中等長度eager copy，長字符串COW)，以及提供更加友好的接口等，并預(yù)期至少會有10%的整體性能提升。但我覺得，這實在不是普通程序員該干的事：暫且不論10%的底限能否達到，維護非標準的接口本身就是一筆重大的開銷。
3. 雖然我們的選擇不多，但了解COW的缺陷依然可以使我們優(yōu)化對string的使用：盡量避免在多個線程間false sharing同一個“物理string“，盡量避免在對string進行只讀訪問(如打印)時造成了不必要的內(nèi)部拷貝。
最后發(fā)一句感慨：C++中的性能陷阱無處不在！
網(wǎng)站題目：std::string的Copy-on-Write：不如想象中美好
文章來源：http://m.fisionsoft.com.cn/article/ccopsep.html
