日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

[[170381]]

Copy-on-write(以下簡(jiǎn)稱(chēng)COW)是一種很重要的優(yōu)化手段。它的核心思想是懶惰處理多個(gè)實(shí)體的資源請(qǐng)求，在多個(gè)實(shí)體之間共享某些資源，直到有實(shí)體需要對(duì)資源進(jìn)行修改時(shí)，才真正為該實(shí)體分配私有的資源。

COW技術(shù)的一個(gè)經(jīng)典應(yīng)用在于Linux內(nèi)核在進(jìn)程fork時(shí)對(duì)進(jìn)程地址空間的處理。由于fork產(chǎn)生的子進(jìn)程需要一份和父進(jìn)程內(nèi)容相同但完全獨(dú)立的地址空間，一種做法是將父進(jìn)程的地址空間完全復(fù)制一份，另一種做法是將父進(jìn)程地址空間中的頁(yè)面標(biāo)記為”共享的“(引用計(jì)數(shù)+1)，使子進(jìn)程與父進(jìn)程共享地址空間，但當(dāng)有一方需要對(duì)內(nèi)存中某個(gè)頁(yè)面進(jìn)行修改時(shí)，重新分配一個(gè)新的頁(yè)面(拷貝原內(nèi)容)，并使修改進(jìn)程的虛擬地址重定向到新的頁(yè)面上。

COW技術(shù)有哪些優(yōu)點(diǎn)呢?

1. 一方面減少了分配(和復(fù)制)大量資源帶來(lái)的瞬間延遲(注意僅僅是latency，但實(shí)際上該延遲被分?jǐn)偟胶罄m(xù)的操作中，其累積耗時(shí)很可能比一次統(tǒng)一處理的延遲要高，造成throughput下降是有可能的)

2. 另一方面減少不必要的資源分配。(例如在fork的例子中，并不是所有的頁(yè)面都需要復(fù)制，比如父進(jìn)程的代碼段(.code)和只讀數(shù)據(jù)(.rodata)段，由于不允許修改，根本就無(wú)需復(fù)制。而如果fork后面緊跟exec的話，之前的地址空間都會(huì)廢棄，花大力氣的分配和復(fù)制只是徒勞無(wú)功。)

COW的思想在資源管理上被廣泛使用，甚至連STL中的std::string的實(shí)現(xiàn)也要沾一下邊。陳碩的這篇博客《C++工程實(shí)踐(10)：再探std::string》充分探討了各個(gè)STL實(shí)現(xiàn)中對(duì)std::string的實(shí)現(xiàn)方式，其中g(shù)++ std::string和Apache stdcxx就使用了COW技術(shù)。(其他對(duì)std::string的實(shí)現(xiàn)包括eager copy和small string optimization，建議參考原博客，圖文并茂十分清楚)

很簡(jiǎn)單一段代碼，就能查看當(dāng)前std::string實(shí)現(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()? 
 

如果實(shí)現(xiàn)使用了COW，那么第一個(gè)比較會(huì)返回true，第二個(gè)比較會(huì)返回false。經(jīng)測(cè)試libstdc++(gcc 4.5)確實(shí)使用了COW，而查看STL中string的源碼，也確實(shí)采用了引用計(jì)數(shù)的手段。

但要注意，std::string的lazy-copy行為只發(fā)生在兩個(gè)string對(duì)象之間的拷貝構(gòu)造，賦值和assign()操作上，如果一個(gè)string由(const)char*構(gòu)造而來(lái)，則必然會(huì)分配內(nèi)存和進(jìn)行復(fù)制，因?yàn)閟tring對(duì)象并不知道也無(wú)權(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()); 
 

實(shí)際上，std::string c = a.data()確實(shí)是一種在字符串賦值時(shí)禁止COW行為的方法。

看起來(lái)使用COW管理string來(lái)減少不必要的拷貝似乎很有效，然而在多數(shù)C++ STL實(shí)現(xiàn)中，只有寥寥兩種使用了COW，而同樣著名的Visual C++(2010)和clang libc++卻不約而同拋棄了COW，選擇了SSO(small string optimization，足夠小的字符串直接放在對(duì)象本身的棧內(nèi)存中，避免了向Heap動(dòng)態(tài)請(qǐng)求內(nèi)存的開(kāi)銷(xiāo))。

SSO對(duì)小字符串的高效是原因之一(程序中通常會(huì)有大量的短字符串)，而COW本身的缺陷更是原因之一。

一、性能：for thread-safety!

想要實(shí)現(xiàn)COW，必須要有引用計(jì)數(shù)(reference count)。string初始化時(shí)rc=1，每當(dāng)該string賦值給了其他sring，rc++。當(dāng)需要對(duì)string做修改時(shí)，如果rc>1，則重新申請(qǐng)空間并復(fù)制一份原字符串的拷貝，rc--。當(dāng)rc減為0時(shí)，釋放原內(nèi)存。

基于”共享“和”引用“計(jì)數(shù)的COW在多線程環(huán)境下必然面臨線程安全的問(wèn)題。那么：

std::string是線程安全的嗎?

在stackoverflow上對(duì)這個(gè)問(wèn)題的一個(gè)很好的回答：是又不是。

從在多線程環(huán)境下對(duì)共享的string對(duì)象進(jìn)行并發(fā)操作的角度來(lái)看，std::string不是線程安全的，也不可能是線程安全的，像其他STL容器一樣。

c++11之前的標(biāo)準(zhǔn)對(duì)STL容器和string的線程安全屬性不做任何要求，甚至根本沒(méi)有線程相關(guān)的內(nèi)容。即使是引入了多線程編程模型的C++11，也不可能要求STL容器的線程安全：線程安全意味著同步，同步意味著性能損失，貿(mào)然地保證線程安全必然違背了C++的哲學(xué)：

Don't pay for things you don't use.

但從不同線程中操作”獨(dú)立“的string對(duì)象來(lái)看，std::string必須是線程安全的。咋一看這似乎不是要求，但COW的實(shí)現(xiàn)使兩個(gè)邏輯上獨(dú)立的string對(duì)象在物理上共享同一片內(nèi)存，因此必須實(shí)現(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.

簡(jiǎn)單說(shuō)來(lái)就是：你瞞著用戶使用共享內(nèi)存是可以的(比如用COW實(shí)現(xiàn)string)，但你必須負(fù)責(zé)處理可能的競(jìng)態(tài)條件。

而COW實(shí)現(xiàn)中避免競(jìng)態(tài)條件的關(guān)鍵在于：

1. 只對(duì)引用計(jì)數(shù)進(jìn)行原子增減

2. 需要修改時(shí)，先分配和復(fù)制，后將引用計(jì)數(shù)-1(當(dāng)引用計(jì)數(shù)為0時(shí)負(fù)責(zé)銷(xiāo)毀)

先談?wù)勗硬僮鳎?/strong>

不同的體系結(jié)構(gòu)一般會(huì)有不同的底層原語(yǔ)以支持原子操作。如Intel CPU本身就引入了#LOCK指令前綴，該前綴允許置于指定的操作(如算法指令、邏輯指令、bit指令、exchange指令等)之前使用，如lock inc會(huì)在執(zhí)行inc指令時(shí)鎖總線(鎖定包含目標(biāo)地址的一片內(nèi)存區(qū)域，防止其他CPU在此期間的并發(fā)訪問(wèn))，從而序列化對(duì)同一地址的訪問(wèn)。

比起mutex之類(lèi)的同步手段，原子操作自然要輕上不少，但比起普通的算術(shù)指令，依然算得上完全的重量級(jí)：

1. 系統(tǒng)通常會(huì)lock住比目標(biāo)地址更大的一片區(qū)域，影響邏輯上不相關(guān)的地址訪問(wèn)。

2. lock指令具有”同步“語(yǔ)義，會(huì)阻止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."

也就是會(huì)等待之前發(fā)出的load和store指令的完成(由于CPU store buffer的存在，如果數(shù)據(jù)之前沒(méi)有依賴，不需要等待load和store的結(jié)果)

3. 兩個(gè)CPU對(duì)同一個(gè)地址進(jìn)行原子操作，必然會(huì)導(dǎo)致cache-bounce。SMP系統(tǒng)中由于Cache一致性協(xié)議的存在，一個(gè)CPU對(duì)共享內(nèi)存的修改必然會(huì)invalidate另一個(gè)CPU對(duì)該地址的cache，最終導(dǎo)致兩個(gè)CPU對(duì)同一片內(nèi)存不斷”爭(zhēng)奪“(cache不斷被對(duì)方invalidate，需要重新從內(nèi)存中讀取)，這是多線程編程中經(jīng)典的False Sharing問(wèn)題。

歸根結(jié)底，COW為了保證”線程安全“而使用了原子操作，而原子操作本身的效率并不十分高。而且在多線程環(huán)境下，多個(gè)CPU對(duì)同一個(gè)地址的原子操作開(kāi)銷(xiāo)更大。COW中”共享“的實(shí)現(xiàn)，反而影響了多線程環(huán)境下string”拷貝“的性能，并不scale。

再談?wù)劜僮黜樞颍?/strong>

為了避免競(jìng)態(tài)條件，在需要修改string時(shí)，如果引用計(jì)數(shù)>1，必須先分配和拷貝，然后才能將引用計(jì)數(shù)減1。(而不能先減1再拷貝)

某些條件下，這樣的操作序列會(huì)導(dǎo)致不必要的額外操作：

string A在線程1中訪問(wèn)，string B在線程2中訪問(wèn)，string A 和 string B 共享同一片內(nèi)容(rc = 2)

假設(shè)當(dāng)線程1操作string A時(shí)線程2恰好也在操作string B，雙方發(fā)現(xiàn)該string的內(nèi)容是共享的，都遵守先分配復(fù)制，后減引用計(jì)數(shù)的執(zhí)行序列。(最終會(huì)有一方發(fā)現(xiàn)rc=0，銷(xiāo)毀原string內(nèi)容)。

到此為止，COW一共進(jìn)行了3次內(nèi)存分配和復(fù)制(初始化時(shí)1次，修改時(shí)2次)和1次內(nèi)存釋放

實(shí)際上，如果沒(méi)有使用COW技術(shù)，從string的初始化到目前為止也只進(jìn)行了2次內(nèi)存分配和復(fù)制(都是在初始化時(shí)進(jìn)行)

二、”失效“問(wèn)題：草木皆兵!

假設(shè)當(dāng)前的string實(shí)現(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! 
 

程序僅僅以”只讀“的方式訪問(wèn)了b中一個(gè)字符，但b已經(jīng)進(jìn)行了一份私有的拷貝，a與b不再共享同一片內(nèi)容。

由于string的operator[]和at()會(huì)返回某個(gè)字符的引用，而判斷程序是否更改了該字符實(shí)在是超出string本身能力范圍的東西，為了保證COW實(shí)現(xiàn)的正確性，string只得統(tǒng)統(tǒng)認(rèn)定operator[]和at()具有修改的“語(yǔ)義”。

連begin()/end()也不能幸免，天曉得用戶取得迭代器后會(huì)做什么!

這些無(wú)奈的”write alarm“實(shí)際上是由于std::string本身接口的定義上沒(méi)有對(duì)”只讀“和”修改“語(yǔ)義做嚴(yán)格的區(qū)分。

為此，Alexandrescu在它的”Scalable Use of STL“的演講中對(duì)std::string的接口做了如下建議：

1. offer set(n, c)

2. make default iterator non-mutating

僅僅是建議而已，實(shí)際上他本人反對(duì)使用COW：

"The COW is dead, long live eager-copy"

總結(jié)：

1. string的COW實(shí)現(xiàn)確有諸多的弊端，并不如想象中那般美好，也因此受到了Visual C++和clang++的拋棄，轉(zhuǎn)而使用實(shí)現(xiàn)簡(jiǎn)單，且對(duì)小字符串更友好的SSO實(shí)現(xiàn)。

2. Alexandrescue在他的“Scalable Use of STL”中建議對(duì)性能敏感的程序?qū)崿F(xiàn)自己的string，比如針對(duì)string的長(zhǎng)度進(jìn)行選擇優(yōu)化(短字符串SSO，中等長(zhǎng)度eager copy，長(zhǎng)字符串COW)，以及提供更加友好的接口等，并預(yù)期至少會(huì)有10%的整體性能提升。但我覺(jué)得，這實(shí)在不是普通程序員該干的事：暫且不論10%的底限能否達(dá)到，維護(hù)非標(biāo)準(zhǔn)的接口本身就是一筆重大的開(kāi)銷(xiāo)。

3. 雖然我們的選擇不多，但了解COW的缺陷依然可以使我們優(yōu)化對(duì)string的使用：盡量避免在多個(gè)線程間false sharing同一個(gè)“物理string“，盡量避免在對(duì)string進(jìn)行只讀訪問(wèn)(如打印)時(shí)造成了不必要的內(nèi)部拷貝。

最后發(fā)一句感慨：C++中的性能陷阱無(wú)處不在！