|
本文由CocoaChina譯者@ALEX吳浩文翻譯 Tagged Pointer是一個能夠提升性能、節(jié)省內(nèi)存的有趣的技術(shù)。在OS X 10.10中，NSString就采用了這項(xiàng)技術(shù)，現(xiàn)在讓我們來看看該技術(shù)的實(shí)現(xiàn)過程。本話題由Ken Ferry提出。 回顧 對象在內(nèi)存中是對齊的，它們的地址總是指針大小的整數(shù)倍，通常為16的倍數(shù)。對象指針是一個64位的整數(shù)，而為了對齊，一些位將永遠(yuǎn)是零。 Tagged Pointer利用了這一現(xiàn)狀，它使對象指針中非零位有了特殊的含義。在蘋果的64位Objective-C實(shí)現(xiàn)中，若對象指針的最低有效位為1(即奇數(shù))，則該指針為Tagged Pointer。這種指針不通過解引用isa來獲取其所屬類，而是通過接下來三位的一個類表的索引。該索引是用來查找所屬類是采用Tagged Pointer的哪個類。剩下的60位則留給類來使用。 Tagged Pointer有一個簡單的應(yīng)用，那就是NSNumber。它使用60位來存儲數(shù)值。最低位置1。剩下3位為NSNumber的標(biāo)志。在這個例子中，就可以存儲任何所需內(nèi)存小于60位的數(shù)值。 從外部看，Tagged Pointer很像一個對象。它能夠響應(yīng)消息，因?yàn)閛bjc_msgSend可以識別Tagged Pointer。假設(shè)你調(diào)用integerValue，它將從那60位中提取數(shù)值并返回。這樣，每訪問一個對象，就省下了一次真正對象的內(nèi)存分配，省下了一次間接取值的時(shí)間。同時(shí)引用計(jì)數(shù)可以是空指令，因?yàn)闆]有內(nèi)存需要釋放。對于常用的類，這將是一個巨大的性能提升。 NSString似乎并不適合Tagged Pointer，因?yàn)樗拈L度即可變，又可遠(yuǎn)遠(yuǎn)超過60位。然而，Tagged Pointer是可以與普通類共存的，即對一些值使用Tagged Pointer，另一些則使用一般的指針。例如，對于NSNumber，大于2^60-1的整數(shù)就不能采用Tagged Pointer來存儲，而需要在內(nèi)存中分配一個NSNumber的對象來存儲。只要創(chuàng)建對象的代碼編寫正確，就沒有問題。 NSString也是如此。對于那些所需內(nèi)存小于60位的字符串，它可以創(chuàng)建一個Tagged Pointer。其余的則被放置在真正的NSString對象里。這使得常用的短字符串的性能得到明顯的提升。實(shí)際代碼就是如此嗎？似乎Apple是這么認(rèn)為的，因?yàn)樗麄冞@么做了并實(shí)現(xiàn)了它。 可能的實(shí)現(xiàn)方法 在看Apple的實(shí)現(xiàn)之前，讓我們花點(diǎn)時(shí)間想想我們自己會如何實(shí)現(xiàn)這種字符串。最初想法很簡單：置最低位為1，剩下的3位作為類的標(biāo)志，60位為真正的數(shù)據(jù)。如何使用這60位是一個大問題。我們想要最大限度地利用這60位。 一個Cocoa字符串在概念上是一系列的Unicode字符。一共有1,112,064個有效的Unicode字符，所以需要21位代表一個字符。這意味著我們可以放兩個字符在這60位里，浪費(fèi)掉了18位。我們可以用一些額外的位來存儲長度。所以一個采用Tagged Pointer的字符串可以是零個、一個或兩個字符。然而被限制為只有兩個字符的字符串似乎并沒什么用。 NSString API實(shí)際上是基于UTF-16的實(shí)現(xiàn)，而不是直接基于Unicode。UTF-16用16位的序列值來表示Unicode。最常見的基本多文種平面（Basic Multilingual Plane，BMP）字符需要16位，字符編碼超過65,535的則需要兩個。我們可以放三個16位進(jìn)60位，剩下12位。再借用一些表示長度的位，這將允許我們表示0-3個UTF-16字符。這將允許三個BMP字符，且其中一個字符可以超出BMP的范圍。被限制為三個字符的字符串的使用仍然有限。 大多數(shù)APP里的字符串是ASCII。即使APP本地化到非ASCII語言，字符串也遠(yuǎn)遠(yuǎn)不止用于顯示UI。它們用于URL組件、文件擴(kuò)展名、對象鍵、屬性列表值等等。UTF-8編碼是一種ASCII兼容的編碼，它將每一個ASCII字符編碼為一個字節(jié)，用四字節(jié)編碼其他Unicode字符。我們可以在60位里放七個字節(jié)，剩下的4位表示長度。這樣這種字符串可以存儲七個ASCII字符，或者少一些的非ASCII字符，這取決于這些字符是什么。 如果我們要優(yōu)化ASCII，我們不妨放棄對Unicode的完整支持。畢竟包含非ASCII字符的字符串可以使用真正的NSString對象。ASCII是一個七位編碼，如果我們給每個字符只分配7位會發(fā)生什么？讓我們存儲八個ASCII字符在這60位里，再用剩下的4位存儲長度。這聽起來很有用。在一個APP里可能有大量的字符串是純ASCII并且只包含8個字符或更少。 接著往下想，完整的ASCII里有很多不常用的東西。比如一堆控制字符和不常用的符號。字母和數(shù)字才是最常使用的。我們能不能把編碼縮短到6位？ 6位可以存儲64個不同的值。ASCII里有26個字母，算上大寫小寫則有52個，再加上數(shù)字0-9則多達(dá)62個。如果說有兩個地方需要節(jié)省，那就是空間和時(shí)間?？赡苡泻芏嘀话@些字符的字符串。每6位1個字節(jié)，我們可以在60位里存儲十個字符！等等！我們沒有剩余空間存儲長度。所以要么我們存儲9個字符加長度，要么在那64個不同值里刪除一個(我認(rèn)為可以刪除空格)，然后對于那些小于10個字符的字符串使用零作為結(jié)束符。 如果是5位呢？這不是完全荒謬的。可能有很多只存在小寫字符的字符串。例如，5位可以存儲32個不同的值。算上整個小寫字母，也還有6個額外的值，你可以再分配一些更常見的大寫字母、符號、數(shù)字或組合。如果你發(fā)現(xiàn)其中的一些情況更常見，你甚至可以刪除一些不太常見的小寫字母，例如q。如果我們省下存儲長度的空間，5位編碼我們可以存儲十一個字符，如果我們借一個符號位并使用一個結(jié)束符則可以存儲十二個字符。 接著往下想，作為一個合理的編碼，5位已經(jīng)盡可能的短了。你可以用一個可變長度的編碼，如霍夫曼編碼。常見的，這將允許字母e比起字母q有更短的編碼。這將可能允許最短1位來編碼一個字符，在一些極端的情況下假如你的字符串全部都是e。這樣也將導(dǎo)致更復(fù)雜的空間開銷，編碼也可能更慢。 Apple采用了哪一種方法？讓我們找出答案。 運(yùn)用 Tagged String 這里有一段代碼，它創(chuàng)建了一個這種字符串并輸出它的指針。
mutableCopy/copy是必要的。原因有兩個。首先，盡管像@"a"這樣的字符串可以存儲為一個Tagged Pointer，但是字符串常量卻從不存儲為Tagged Pointer。字符串常量必須在不同的操作系統(tǒng)版本下保持二進(jìn)制兼容，而Tagged Pointer的內(nèi)部細(xì)節(jié)是沒有保證的。其能使用的前提是Tagged Pointer在運(yùn)行時(shí)總是由Apple的代碼生成，如果編譯器把它們嵌入二進(jìn)制里，那么前提就被打破了（字符串常量就是這樣）。因此我們需要copy常量字符串來獲取Tagged Pointer。 mutableCopy是必要的，因?yàn)镹SString太聰明，而且也知道一個不可變字符串的副本是一個毫無意義的操作，所以它會返回原字符串的當(dāng)作“copy”。字符串常量是不可變的，所以[a copy]結(jié)果只是a。一個可變量的副本強(qiáng)迫它產(chǎn)生真正副本，這樣一個可變量副本的不可變的副本足以讓系統(tǒng)給我們產(chǎn)生一個采用Tagged Pointer的字符串。 注意不要在你自己的代碼里依賴這些細(xì)節(jié)！這是NSString的當(dāng)前情況，它隨時(shí)可能改變。如果你的代碼某種程度上依賴于此，那么代碼最終將失效。幸運(yùn)的是，只有非正常的代碼才會這樣。所有正常、合理的代碼都沒有問題，傻傻的不知道任何Tagged Pointer而幸福著吧。 以下是上面代碼在我電腦上的輸出。 首先你可以看到原始指針，一個真正的對象指針。副本是第二個值，非常清楚，這是一個奇數(shù)，這意味著它不是一個有效的對象指針。這也是一個較小的數(shù)，在未映射且不可映射的4GB零頁的64位Mac地址空間的開頭里，這使它更加不可能是一個對象指針。 我們從這個0x6115中可以推斷出什么？我們知道，Tagged Pointer的最低4位是其機(jī)制本身的一部分。最低半字節(jié)5的二進(jìn)制是0101。最低位表示它是一個Tagged Pointer。接下來的3位表示其所屬類。010，表明字符串類在類表中的索引為2。這些信息并不是很有用。 開頭的61是有啟發(fā)性的。61在十六進(jìn)制里正好是小寫字母a的ASCII編碼，這正是字符串的值?？磥硎侵苯拥腁SCII編碼。方便！ 類名告訴了我們這個類的用途，并是一個很好的去考慮其真正的代碼實(shí)現(xiàn)的入手點(diǎn)。我們會很快談到它，但是先讓我們再做一些外部檢查。 以下是一個循環(huán)，構(gòu)建了許多形如abcdef……的字符串，并一個接一個輸出，直到停止產(chǎn)生Tagged Pointer。
第一個輸出： 0x0000000000006115 a NSTaggedPointerString 上面我們看到的這個匹配值。請注意，我輸出了包含所有前導(dǎo)零得完整指針，這樣能更清楚與后續(xù)輸出值比較。讓我們再看看第二個輸出: 0x0000000000626125 ab NSTaggedPointerString 正如我們所想的那樣，最低的四位并沒有改變。即那個5將保持不變，表明這是一個NSTaggedPointerString類型的Tagged Pointer。 前面的61沒變，并加入了62。62顯然是b的ASCII編碼。所以我們可以看到，這是一個八位的ASCII編碼。5之前的值從1變到2，表明這可能是長度。后續(xù)的輸出證實(shí)了這一點(diǎn)： 0x0000000063626135 abc NSTaggedPointerString 0x0000006463626145 abcd NSTaggedPointerString 0x0000656463626155 abcde NSTaggedPointerString 0x0066656463626165 abcdef NSTaggedPointerString 0x6766656463626175 abcdefg NSTaggedPointerString 大概就到這里了。Tagged Pointer已滿，下一次迭代將分配一個真正的NSString對象并終止循環(huán)。對嗎？錯了！ 0x0022038a01169585 abcdefgh NSTaggedPointerString 0x0880e28045a54195 abcdefghi NSTaggedPointerString 0x00007fd275800030 abcdefghij __NSCFString 循環(huán)還經(jīng)過兩次迭代之后才停止。數(shù)據(jù)部分繼續(xù)增長，其余部分變成亂碼。發(fā)生了什么？讓我們看看其具體實(shí)現(xiàn)。 反編譯 NSTaggedPointer類在CoreFoundation框架里，似它乎應(yīng)該在Foundation框架里，但是最近很多核心Objective-C類已經(jīng)搬到CoreFoundation里了，Apple正在慢慢放棄讓CoreFoundation成功一個獨(dú)立的實(shí)體。 讓我們先看看 -[NSTaggedPointerString length] 的實(shí)現(xiàn)： push rbp mov rbp, rsp shr rdi, 0x4 and rdi, 0xf mov rax, rdi pop rbp ret 用Hopper進(jìn)行反編譯
簡而言之，為了得到長度，提取4-7位并返回。這證實(shí)了我們之前的想法。 另一個NSString的原始方法是characterAtIndex:。我將跳過冗長的反編譯，以下是Hopper的反編譯輸出，已經(jīng)相當(dāng)可讀了：
讓我們整理一下。前三行只是Hopper告訴我們哪些寄存器獲取哪些參數(shù)。讓我們用_cmd替換rsi，用self替換rdi。因?yàn)閍rg2實(shí)際上就是index，所以讓我們用index替換r13。讓我們?nèi)サ羲衉_stack_chk，因?yàn)樗皇怯糜诩訌?qiáng)安全性，和方法的具體實(shí)現(xiàn)無關(guān)。這樣整理后變成：
在第一個if語句之前有這一行：
這正是之前看到的提取長度的代碼。讓我們用length替換r12：
在if語句的內(nèi)部，第一行把self右移了8位。這8位記錄的是：Tagged Pointer標(biāo)記和字符串長度。其余部分，就是我們認(rèn)為的真正的數(shù)據(jù)。讓我們用stringData替換rbx使代碼更加清晰。下一行似乎是把某種查詢表賦給rcx，所以讓我們用table替換rcx。最后，length的副本被賦給rdx。看來將被用作某種游標(biāo)，讓我們用cursor替換rdx。現(xiàn)在我們的代碼長這樣：
這幾乎是所有的變量。剩下一個原始寄存器名：rbp。這實(shí)際上是幀指針，所以編譯器直接從幀指針做一些索引。加一個0xffffffffffffffbf常數(shù)是二進(jìn)制補(bǔ)碼中“一切都是一個無符號整數(shù)（everything is ultimately an unsigned integer）”減去65的方法。然后，它減去64。這在堆棧上可能都是相同的局部變量。鑒于按字節(jié)索引，這可能是一個放在堆棧種的緩沖。奇怪的是，其實(shí)有一個方法能夠直接讀取緩沖區(qū)而無需專門編寫。發(fā)生了什么？ 原來Hopper忘了反編譯在if外的else的部分。整合在一起變成了這樣： mov rax, rdi shr rax, 0x8 mov qword [ss:rbp+var_40], rax var_40在Hopper的反編譯中表示的偏移量64。(40是64的十六進(jìn)制版本)讓我們調(diào)用這個指向位置緩沖區(qū)的指針。這個錯失部分的C版本看起來是這樣： *(uint64_t *)buffer = self >> 8 讓我們繼續(xù)并插入這句代碼，并用buffer替換rbp，這使得代碼更加可讀。另外添加一個緩沖區(qū)的聲明來提醒我們：
好多了。雖然有些瘋狂的指針操作語句有點(diǎn)難讀，但是他們只是數(shù)組索引。讓我們解決這個問題：
現(xiàn)在我們已經(jīng)取得了一些進(jìn)展。 我們可以看到根據(jù)不同的長度分為三種情況。長度值小于8走錯失的else分支，只是取值，移位，放到緩沖區(qū)。這是純ASCII的情況。在這里，index是用來索引self的值并提取指定的字節(jié)，然后返回給調(diào)用者。既然ASCII編碼在ASCII范圍內(nèi)匹配Unicode編碼，也就無需額外的操作來讀出正確的值。我們之前猜測純ASCII的字符串是以這種方式存儲，這里證實(shí)了這種猜測。 如果長度是8或者更長呢？如果長度是8或者更長但比10（0xa）小，代碼進(jìn)入一個循環(huán)。這個循環(huán)取低6位的stringData，當(dāng)作一個表的索引，然后將該值復(fù)制到緩沖區(qū)。然后把stringData右移6位并循環(huán)，直到它遍歷整個字符串。這是六位編碼，先把六位編碼映射到ASCII字符再存儲在表中。在緩沖區(qū)建立臨時(shí)字符串，然后在索引操作結(jié)束時(shí)從中提取所要求的字符。 如果長度是10或者更長呢？代碼幾乎相同，除了它是五位循環(huán)一次，而不是六位。這是一個更緊湊的編碼，使字符串能存儲11字符，但使用一個只有32個值的編碼表。這將使用六位編碼表的前半個表作為編碼表。 因此我們可以看到采用Tagged Pointer的字符串的結(jié)構(gòu)是: 1：如果長度介于0到7，直接用八位編碼存儲字符串。 2：如果長度是8或9，用六位編碼存儲字符串，使用編碼表“eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX”。 3：如果長度是10或11，用五位編碼存儲字符串,使用編碼表“eilotrm.apdnsIc ufkMShjTRxgC4013” 讓我們與之前輸出的數(shù)據(jù)對比一下： 0x0000000000006115 a NSTaggedPointerString 0x0000000000626125 ab NSTaggedPointerString 0x0000000063626135 abc NSTaggedPointerString 0x0000006463626145 abcd NSTaggedPointerString 0x0000656463626155 abcde NSTaggedPointerString 0x0066656463626165 abcdef NSTaggedPointerString 0x6766656463626175 abcdefg NSTaggedPointerString 0x0022038a01169585 abcdefgh NSTaggedPointerString 0x0880e28045a54195 abcdefghi NSTaggedPointerString 0x00007fbad9512010 abcdefghij __NSCFString 二進(jìn)制0x0022038a01169585去掉末尾8位再分割成一個個6位的塊變成： 001000 100000 001110 001010 000000 010001 011010 010101 用這些索引去編碼表中獲取值，我們可以看到，這確實(shí)拼出“abcdefgh”。 同樣，二進(jìn)制of0x0880e28045a54195去掉末尾8位再分割成一個個6位的塊變成： 001000 100000 001110 001010 000000 010001 011010 010101 000001 我們可以看到前面是相同的，不過末尾加上i。 但接下來就離奇了。接下來，它本應(yīng)該用五位編碼返回兩個字符串，然而它卻開始生成長度為10的對象。到底發(fā)生了什么？ 五位編碼表是非常有限了，但不包括字母b！在神圣的五位編碼表里，那個字母肯定不是常見到足以留下。讓我們從c開始再試試。以下是輸出： 0x0000000000006315 c NSTaggedPointerString 0x0000000000646325 cd NSTaggedPointerString 0x0000000065646335 cde NSTaggedPointerString 0x0000006665646345 cdef NSTaggedPointerString 0x0000676665646355 cdefg NSTaggedPointerString 0x0068676665646365 cdefgh NSTaggedPointerString 0x6968676665646375 cdefghi NSTaggedPointerString 0x0038a01169505685 cdefghij NSTaggedPointerString 0x0e28045a54159295 cdefghijk NSTaggedPointerString 0x01ca047550da42a5 cdefghijkl NSTaggedPointerString 0x39408eaa1b4846b5 cdefghijklm NSTaggedPointerString 0x00007fbd6a511760 cdefghijklmn __NSCFString 我們現(xiàn)在有長度為11的采用Tagged Pointer的字符串。最后兩個字符串的二進(jìn)制是： 01110 01010 00000 10001 11010 10101 00001 10110 10010 00010 01110 01010 00000 10001 11010 10101 00001 10110 10010 00010 00110 正如我們所想的那樣。 創(chuàng)建采用Tagged Pointer的字符串 既然我們已經(jīng)知道這種字符串如何編碼，我就不在創(chuàng)建它們的代碼中涉及具體細(xì)節(jié)。我們發(fā)現(xiàn)了一個叫__CFStringCreateImmutableFunnel3的私有方法，這個巨大的方法處理了所有情況下的字符串創(chuàng)建。這個函數(shù)包含在CoreFoundation的開源版本里，在opensource.apple.com上。但別激動：采用Tagged Pointer的字符串并不包括在開源版本里。 這里的代碼基本上和上面的相反。如果字符串的長度和內(nèi)容適合Tagged Pointer，它構(gòu)建一個Tagged Pointer，包含ASCII、六位編碼或五位編碼。其中有一個逆查詢表。這個表視為一個全局的字符串常量稱為sixBitToCharLookup，并有相應(yīng)的稱為charToSixBitLookup的表在方法Funnel3里。 神秘的表 完整的六位編碼表是： eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX 一個顯然的問題是：為什么這個指令這么奇怪? 因?yàn)檫@個表同時(shí)用于六位編碼和五位編碼，它不完全按字母順序排列是有意義的。最常使用的字符應(yīng)該是上半部分，而較少使用的字符應(yīng)該在下半部分。這可以確保盡可能多的長字符串可以使用五位編碼。 然而，這種分為兩個部分的分割，每個部分內(nèi)的順序并不重要。每個部分內(nèi)本身是可以按照字母表順序排列的，然而實(shí)際上沒有這樣。 表中前幾個字母與字母出現(xiàn)在英語里的頻率相似。最常見的英文字母是E，然后是T，A，O，I，N，S。E作為表的開頭是正確的，其他的則靠近開頭。表似乎是按使用頻率排序。與英語的差異可能是因?yàn)镃ocoa APP中的短字符串并不是一個從英語散文中隨機(jī)選擇的單詞，而是更專業(yè)的語言。 我推測Apple最初想使用一個更漂亮的變長編碼，可能基于霍夫曼編碼。但是太困難，或者不值得，或者他們時(shí)間不夠了，所以他們退而求其次推出一個如上所述的不那么雄心勃勃的版本，字符串使用定長的八位，六位，或五位編碼。奇怪的表是當(dāng)前版本的一個殘留物，也是一個起點(diǎn)，如果他們決定在未來去采用變長編碼。這是純粹的猜測，它看起來更像是我會做的事。 結(jié)論 Tagged Pointer是一個很棒的技術(shù)，能把它運(yùn)用在字符串上很不尋常。顯然Apple花了很多心思在這上面，他們必須要看到一個顯著的好處?？此麄?nèi)绾伟堰@些技術(shù)融合在一起，看他們?nèi)绾卧诜浅Ｓ邢薜目臻g里面盡可能的存儲信息，實(shí)在有趣。 上面是作者的原文, 這里我做了測試 發(fā)現(xiàn)Tagged Pointer的標(biāo)識由最后4位便到了前4位. |
|
|
