3. 第三篇原文如下：
本文流程
一、解釋分離鎖是什么。
二、舉例闡述SideTables、SideTable、RefcountMap三者關(guān)系。
三、前面文章所說的N路并發(fā)是什么意思。
四、SideTables所使用的Hash算法解密。
五、RefcountMap是什么結(jié)構(gòu)。
一、分離鎖
分離鎖并不是一種鎖，而是一種對鎖的用法。(下面繼續(xù)上一張感人的手繪圖。哈哈我寫的字也出現(xiàn)了。如果比寫字丑，一般很少有人能比我寫的丑)
6DA5F9AD-73C5-4888-9E03-1C72D0E848F1.png
圖1這樣對一整個表加一把鎖，是我們平時比較常見的。如果我一次寫操作需要操作表中多個單元格的數(shù)據(jù)，比如第一次操作0、1、2位置的數(shù)據(jù)，第二次操作0、2、3位置的數(shù)據(jù)。像這種情況鎖的粒度就是以整張表為單位的，才能保證數(shù)據(jù)的安全。
圖2這樣對表中的各個元素分別加一把鎖就是我們說的分離鎖。適用于表中元素相互獨立，你對第一個元素做寫操作的時候不需要影響到其他元素。
上文中所說的結(jié)構(gòu)就是SideTables這個大的Hash表中每一個小單元格(SideTable)都帶有一把鎖。做寫操作的時候(操作對象引用計數(shù))單元格之間相互獨立，互相沒影響。所以降低了鎖的粒度。
對比一下圖1和圖2的并發(fā)性。
圖1因為任何操作都需要鎖整張表，所以寫操作的時候相當于串行操作。沒有并發(fā)。
圖2因為每一個單元格都有一把鎖，所以寫操作的時候有多少個單元格并發(fā)數(shù)就可以是多少。
這里注意區(qū)分一下并發(fā)和并行的區(qū)別。
當有多個線程在操作時,如果系統(tǒng)只有一個CPU,則它根本不可能真正同時進行一個以上的線程,它只能把CPU運行時間劃分成若干個時間段,再將時間段分配給各個線程執(zhí)行,在一個時間段的線程代碼運行時,其它線程處于掛起狀態(tài).這種方式我們稱之為并發(fā)(Concurrent).
當系統(tǒng)有一個以上CPU時,則線程的操作有可能非并發(fā).當一個CPU執(zhí)行一個線程時,另一個CPU可以執(zhí)行另一個線程,兩個線程互不搶占CPU資源,可以同時進行,這種方式我們稱之為并行(Parallel)
可以看到在單元格之間相互獨立的情況下圖2的方法效率更高。
看了上面的例子有同學(xué)會有疑問。既然分離鎖可以實現(xiàn)高并發(fā)，那么為什么不對每一個內(nèi)存對象加一把鎖呢？為什么還會有Hash表還會沖突呢？這個問題我在下面通過一個例子和RefcountMap一起解釋。
二、為什么SideTables會沖突、SideTable又扮演著什么角色、RefcountMap是用來干嘛的？
下面我用一個不太恰當?shù)睦觼碚f明問題
假設(shè)有80個學(xué)生需要咱們安排住宿，同時還要保證學(xué)生們的財產(chǎn)安全。應(yīng)該怎么安排？
顯然不會給80個學(xué)生分別安排80間宿舍，然后給每個宿舍的大門上加一把鎖。那樣太浪費資源了鎖也挺貴的，太多的宿舍維護起來也很費力氣。
我們一般的做法是把80個學(xué)生分配到10間宿舍里，每個宿舍住8個人。假設(shè)宿舍號分別是101、102 、... 110。然后再給他們分配床位，01號床、02號床等。然后給每個宿舍配一把鎖來保護宿舍內(nèi)同學(xué)的財產(chǎn)安全。為什么不只給整個宿舍樓上一把鎖，每次有人進出的時候都把整個宿舍樓鎖上？顯然這樣會造成宿舍樓大門口阻塞。
OK假如現(xiàn)在有人要找102號宿舍的2號床的人聊天。這個人會怎么做？
1、找到宿舍樓(SideTables)的宿管，跟他說自己要找10202(內(nèi)存地址當做key)。
2、宿管帶著他SideTables[10202]找到了102宿舍SideTable，然后把102的門一鎖lock，在他訪問102期間不再允許其他訪客訪問102了。(這樣只是阻塞了102的8個兄弟的訪問，而不會影響整棟宿舍樓的訪問)
3、然后在宿舍里大喊一聲:"2號床的兄弟在哪里？"table.refcnts.find(02)你就可以找到2號床的兄弟了。
4、等這個訪客離開的時候會把房門的鎖打開unlock，這樣其他需要訪問102的人就可以繼續(xù)進來訪問了。
SideTables == 宿舍樓
SideTable? == 宿舍
RefcountMap里存放著具體的床位
蘋果之所以需要創(chuàng)造SideTables的Hash沖突是為了把對象放到宿舍里管理，把鎖的粒度縮小到一個宿舍SideTable。RefcountMap的工作是在找到宿舍以后幫助大家找到正確的床位的兄弟。
三、N路的并發(fā)寫操作那句話是什么意思？
上一篇文章中提到:
因為是使用對象的內(nèi)存地址當key所以Hash的分部也很平均。假設(shè)Hash表有n個元素，則可以將Hash的沖突減少到n分之一，支持n路的并發(fā)寫操作。
我們在分配宿舍的時候是先給同學(xué)分配宿舍和床位，然后再給宿舍和床位編號。所以我們可以很平均的給每個宿舍分配8個人。
那么如果我們用對象內(nèi)存地址當做Hash算法的key，所得到的散列值可能會出現(xiàn)某些宿舍分配了4個人，某些宿舍分配了12個人的情況。這樣人員分配就不平均了。如果某一時間段正好這個宿舍的12個人的訪問量都特別大，那么訪問起來就又會出現(xiàn)阻塞了。而那4人間的宿舍就會閑置，造成了資源的浪費。會不會造成這種資源浪費主要看兩點。
1、我們的key值分部是否平均。
2、我們采用的散列算法能不能盡量把輸出值平均分配。
1、在數(shù)據(jù)量足夠大的情況下我們的key值分部是平均的。因為key值是內(nèi)存地址。從低位0x0000...0000到高位0xffff...ffff分配。并且操作系統(tǒng)的內(nèi)存管理模塊本身也會對內(nèi)存分配做很多優(yōu)化。畢業(yè)年頭長了,內(nèi)管管理具體的細節(jié)我也扯不出來了。趕緊貼一片文章壓壓驚，有興趣的同學(xué)可以看操作系統(tǒng)內(nèi)存管理——分區(qū)、頁式、段式管理。
2、那么SideTables使用的Hash算法是什么呢？我們來開一個新的大標題。
四、SideTables所使用的Hash算法解密。
????SideTables的定義：NSObject.mm line 207-209
staticStripedMap& SideTables() {return*reinterpret_cast*>(SideTableBuf);}
如果看不懂沒關(guān)系,當它是一個C++的Map。咱們來看StripedMap的定義：objc-private.h line 867-906
其中有用的部分是這樣的
...//如果是嵌入式系統(tǒng)StripeCount=8。我們這里StripeCount=64enum{ StripeCount =64};...staticunsignedintindexForPointer(constvoid*p){//這里是類型轉(zhuǎn)換，不用在意uintptr_taddr =reinterpret_cast(p);//這里就是我們要找的Hash算法了return((addr >>4) ^ (addr >>9)) % StripeCount;}
1、將對象的內(nèi)存地址addr右移4位得到結(jié)果1
2、將對象的內(nèi)存地址addr右移9位得到結(jié)果2
3、將結(jié)果1和結(jié)果2做按位異或得到結(jié)果3
4、將結(jié)果3和StripeCount做模運算得到真正的Hash值。
因為最后模運算的結(jié)果范圍是在0-63之間，可見SideTables一共有64個單元格。
五、RefcountMap是什么結(jié)構(gòu)。
前面文章中提到過if(引用計數(shù)器 != table.refcnts.end())因此有同學(xué)提問end()是什么？那么咱們得研究一下RefcountMap是什么類型的。
看定義NSObject.mm line 137
typedefobjc::DenseMap,size_t,true> RefcountMap;
看起來好復(fù)雜，先不管它。一路順著定義找下去。找到DenseMap ==> DenseMapBase ==> inline iterator end()發(fā)現(xiàn)咱們當前在llvm-DenseMap.h line 77-79。艾瑪嚇死我了怎么看到llvm了。llvm我也不懂，所以還是不要扯的太遠。趕緊打開llvm的相關(guān)文檔看看DenseMapBase中的公開方法有
09719F81-A6B1-4B4E-A906-DAD8F260B052.png
當然還有更多其他方法，我只是截取了一部分。通過這部分我們可以看出來我們操作的refcnts.find()和refcnts.end()其實都是對一個C++迭代器iterator的操作。而end()的狀態(tài)表示的是從頭開始查找，一直找到最后都沒有找到。當前指針指向的是結(jié)束位,而不是最后一個元素。
所以if(引用計數(shù)器 == table.refcnts.end())表示查找到最后都沒找到if(引用計數(shù)器 != table.refcnts.end())表示中途找到了。
到這里基本結(jié)束了，結(jié)合2位大牛的3篇文章順序來讀，基本都能理解引用計數(shù)的原理了，希望對大家有幫助！
