您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 訊息 >> iOS 相關資訊

【譯】深入 Tagged Pointer:Apple 如何把字串塞進指標裡

編輯:iOS 相關資訊

本文翻譯自 Mike Ash 的 Friday Q&A 2015-07-31: Tagged Pointer Strings,話題由 Ken Ferry 提出。


Tagged Pointer 是一項兼顧效能與記憶體的有趣技術。OS X 10.10 起,NSString 就用上了它。以下我們一步步拆開看它是怎麼運作的。

基礎回顧

記憶體中的物件是對齊的,位址一定是指標大小的整數倍,通常是 16 的倍數。也就是說,一個 64 位元物件指標裡,總有部分位元永遠是 0。

Tagged Pointer 就是拿這件事做文章:讓物件指標中那些「不可能非零」的位元改作他用。在 Apple 的 64 位元 Objective-C 實作中,若物件指標的最低有效位為 1(也就是奇數),它就是一個 Tagged Pointer。這類指標不再透過解引用 isa 來取得所屬類別,而是用接下來 3 個位元當作索引,去查一張「哪些類別使用 Tagged Pointer」的表。剩下的 60 個位元則完全交給該類別自行運用。

最簡單的應用就是 NSNumber:60 位元存數值,最低位置 1,剩下 3 位元當 NSNumber 的旗標。任何需要空間小於 60 位元的數值都能這樣存。

從外部看,Tagged Pointer 幾乎和一般物件沒有差別,因為 objc_msgSend 認得它,所以照樣能收訊息。你呼叫 integerValue,它就把那 60 位元抽出來傳回。這樣每存取一次物件,就省下一次真正的記憶體配置與一層間接取值;而 retain/release 甚至可以是空指令,因為根本沒有記憶體要釋放。對高頻使用的類別來說,這是相當可觀的效能提升。

那 NSString 呢?它的長度既可以是變動的,又可能遠超 60 位元,乍看並不適合。但 Tagged Pointer 本來就能與一般指標共存:某些值走 Tagged Pointer,某些值走真正的物件。就像 NSNumber 也存不下 2^60-1 以上的整數,那些值得老實配置記憶體。只要建立物件的程式碼寫對了,一切不成問題。

NSString 同理:短字串走 Tagged Pointer,長字串放進真正的 NSString 物件。日常大量出現的短字串因此受益明顯。Apple 不只是這麼想,他們真的做了。

我們會怎麼設計

在窺探 Apple 的實作之前,先想想自己會怎麼做。最直覺的版本是:最低位置 1,接著 3 位元當類別旗標,剩下 60 位元放資料。真正的難題是——這 60 位元要怎麼用才不浪費?

Cocoa 字串在概念上是一串 Unicode 字元。有效 Unicode 字元共 1,112,064 個,至少需要 21 位元表示一個字元,那麼 60 位元只放得進兩個字元,還白白浪費 18 位元。再挪一點位元存長度,結果就是「最多兩個字元」——實用性令人懷疑。

但 NSString 的 API 其實是以 UTF-16 為基礎,而非直接的 Unicode。UTF-16 用 16 位元序列值表示 Unicode,最常見的基本多文種平面(BMP)字元佔 16 位元,編碼超過 65,535 的則要兩個。這樣 60 位元可以放三個 16 位元,還剩 12 位元;再借幾位存長度,就能表示 0 到 3 個 UTF-16 字元,其中還容許一個字元超出 BMP。仍然相當受限。

再往下一想:大多數 App 裡的字串是 ASCII。就算 App 做了本地化,字串的用途遠不只顯示 UI——URL 元件、副檔名、物件鍵、屬性列表值等等,全都是字串。UTF-8 剛好與 ASCII 相容:每個 ASCII 字元佔一個位元組,其他 Unicode 字元佔四個。60 位元放得下七個位元組,還剩 4 位元存長度,也就是最多七個 ASCII 字元。

如果我們打算為 ASCII 做深度優化,不如直接放棄完整 Unicode 支援——反正含非 ASCII 的字串交給真正的 NSString 就好。ASCII 是七位元編碼,那如果每個字元只給 7 位元呢?60 位元就能塞進八個 ASCII 字元,剩 4 位元存長度。這聽起來實用多了,App 裡純 ASCII 且長度不超過 8 的字串應該不少。

繼續往下想:完整 ASCII 裡有不少罕用的控制字元與符號,真正高頻的只有字母和數字。那能不能壓到 6 位元?6 位元可表示 64 種值,26 個小寫加 26 個大寫再加 10 個數字已經 62 個。若要在空間與時間上省,這條路很誘人:每個字元 6 位元,60 位元就能存十個字元!但問題是長度沒地方放了。於是只能二選一:存九個字元加長度,或是從那 64 個值裡砍掉一個(我會砍掉空白),再用 0 當作結束符,讓 10 字元以內的字串也能表示。

那 5 位元呢?聽起來荒謬,但其實未必。很多字串只含小寫字母,而 5 位元剛好能表示 32 種值——26 個小寫字母之外還剩 6 個額度,可以塞幾個常見的大寫字母、符號或數字。若某些情境特別集中,你甚至可以砍掉罕用的小寫字母(比如 q)。省下存長度的空間後,5 位元編碼能存十一個字元;再借一個位元並搭配結束符,就能存十二個。

再往下就該停手了:作為固定長度編碼,5 位元差不多是極限。要更進一步就得改用變長編碼,例如 Huffman 編碼,讓字母 e 比字母 q 用更少的位元,極端情況下(整串都是 e)甚至 1 位元就夠。但代價是更複雜的空間開銷,以及可能更慢的解碼。

Apple 究竟選了哪一條路?我們來找答案。

動手觀察 Tagged String

先看一段程式碼,它建立了一個這樣的字串並印出指標:

NSString *a = @"a";
NSString *b = [[a mutableCopy] copy];
NSLog(@"%p %p %@", a, b, object_getClass(b));

為什麼要繞這麼一圈做 mutableCopy/copy?有兩個原因。第一,雖然 @"a" 這種字串可以存成 Tagged Pointer,但字串常量從來不會是 Tagged Pointer。字串常量必須在不同作業系統版本之間維持二進位相容,而 Tagged Pointer 的內部細節並無任何保證。它能成立的前提是 Tagged Pointer 一律由 Apple 的程式碼在執行期產生;一旦編譯器把它們寫死進執行檔,前提就崩了——字串常量正是這種情況。所以我們必須複製常數字串,才能拿到 Tagged Pointer。

而 mutableCopy 之所以必要,是因為 NSString 很聰明:它知道複製一個不可變字串毫無意義,於是會直接把原物件當作「複本」傳回。字串常量是不可變的,所以 [a copy] 得到的還是 a。而「可變物件的複本」會逼系統真的產生一份新物件,這份可變複本再取不可變複本,就足以讓系統給我們一個 Tagged Pointer 字串。

請注意:不要在自己的程式碼裡依賴這些細節。這只是 NSString 當下的行為,隨時可能改變;任何依賴它的程式碼最終都會失效。所幸只有不太正常的程式碼才會這樣寫,其餘一切照常,不必理會 Tagged Pointer 的存在。

這段程式碼在我的機器上輸出:

0x10ba41038 0x6115 NSTaggedPointerString

第一個值是一個正常的物件指標。第二個值 0x6115 明顯是奇數,所以它不可能是有效的物件指標;而且數值極小,落在 64 位元 Mac 位址空間開頭那片未映射、也無法映射的 4GB 零頁裡,更不可能是物件。

那我們能從 0x6115 解讀出什麼?最低 4 位元是機制本身:最低半位元組是 5,二進位 0101。最低位表示它是 Tagged Pointer,接著 3 位元 010 表示該字串類別在類別表中的索引為 2。這部分資訊其實沒什麼用。

真正有趣的是開頭的 61。十六進位的 61 正好是小寫字母 a 的 ASCII 編碼,也就是字串的內容。看起來就是直接的 ASCII 編碼,非常省事。

類別名稱則替我們指出下一步該去哪裡找實作,這留待後面。先做幾個外部觀察。

下面這個迴圈會造出一長串遞增字串並逐一印出,直到不再產生 Tagged Pointer 為止:

NSMutableString *mutable = [NSMutableString string];
NSString *immutable;
char c = 'a';
do {
    [mutable appendFormat: @"%c", c++];
    immutable = [mutable copy];
    NSLog(@"0x%lx %@ %@", (uintptr_t)immutable, immutable, object_getClass(immutable));
} while (((uintptr_t)immutable & 1) == 1);

第一筆輸出:

0x0000000000006115 a NSTaggedPointerString

與先前看到的一致。這裡我把前導零都補齊,方便後續比較。第二筆:

0x0000000000626125 ab NSTaggedPointerString

最低 4 位元沒變,那個 5 會一直存在,用來標示這是 NSTaggedPointerString。前面的 61 沒變,並多了一個 62——顯然是 b 的 ASCII 編碼。所以這是八位元 ASCII 編碼。而 5 之前的值從 1 變成 2,看起來就是長度。後續輸出證實了這個推測:

0x0000000063626135 abc NSTaggedPointerString

0x0000006463626145 abcd NSTaggedPointerString

0x0000656463626155 abcde NSTaggedPointerString

0x0066656463626165 abcdef NSTaggedPointerString

0x6766656463626175 abcdefg NSTaggedPointerString

差不多該到頂了吧?Tagged Pointer 已滿,下一輪應該要配置真正的 NSString 物件並結束迴圈。對嗎?不對!

0x0022038a01169585 abcdefgh NSTaggedPointerString

0x0880e28045a54195 abcdefghi NSTaggedPointerString

0x00007fd275800030 abcdefghij __NSCFString

迴圈又多跑了兩輪才停。資料段持續變長,其餘部分則變成一團看不懂的數字。發什麼事了?看實作吧。

反編譯

NSTaggedPointerString 類別住在 CoreFoundation 而非 Foundation 裡。看似不合理,但近年不少核心 Objective-C 類別都搬去了 CoreFoundation,Apple 正慢慢讓 CoreFoundation 不再只是個附屬品。

先看 -[NSTaggedPointerString length]:

unsigned long long -[NSTaggedPointerString length](void * self, void * _cmd) {
    rax = self >> 0x4 & 0xf;
    return rax;
}

用 Hopper 反編譯的結果。簡單說:取第 4 到 7 位元並傳回,正好印證我們的猜測。

另一個關鍵的原始方法是 characterAtIndex:。跳過冗長的組合語言,以下是整理後的版本:

unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long index) {
    int8_t buffer[11];
    length = self >> 0x4 & 0xf;
    if (length >= 0x8) {
        stringData = self >> 0x8;
        table = "eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX";
        cursor = length;
        if (length < 0xa) {
            do {
                buffer[cursor - 1] = table[stringData & 0x3f];
                cursor = cursor - 0x1;
                stringData = stringData >> 0x6;
            } while (cursor != 0x0);
        } else {
            do {
                buffer[cursor - 1] = table[stringData & 0x1f];
                cursor = cursor - 0x1;
                stringData = stringData >> 0x5;
            } while (cursor != 0x0);
        }
    } else {
        *(uint64_t *)buffer = self >> 8;
    }
    if (length <= index) {
        [NSException raise:@"NSRangeException" format:@"%@: Index %lu out of bounds; string length %lu", self, index, length];
    }
    rax = buffer[index];
    return rax;
}

這段整理過程值得說明:一開始只是把暫存器換成有意義的名稱,再把編譯器插入的 stack check 去掉(它只跟安全性有關,與實作邏輯無關)。self 右移 8 位元之後,去掉的正是「Tagged Pointer 標記加長度」那 8 位元,剩下的就是真正的資料。接著程式把 self 右移 8 位元後寫進一個 11 位元組的堆疊緩衝區——這一步 Hopper 一開始漏掉了,補回來之後整個邏輯才通順。那些看似瘋狂的指標位移運算,其實只是陣列索引。

於是我們看到三種情況。長度小於 8 時走 else 分支,直接取值、移位、放進緩衝區,這是純 ASCII 的情況;因為 ASCII 編碼與 Unicode 對應一致,不需要額外轉換。我們先前的猜測在此得到證實。

長度為 8 或 9 時進入迴圈:取 stringData 的低 6 位元當索引查表,把字元寫進緩衝區,然後右移 6 位元繼續,直到走完整串。這是六位元編碼,先把 6 位元映射成 ASCII 字元再查表。

長度為 10 或 11 時幾乎相同,只是每次處理 5 位元而非 6 位元。這是一種更緊湊的編碼,能存 11 個字元,代價是編碼表只有 32 個值——實際上就是六位元表的前半段。

於是 Tagged Pointer 字串的結構定案:

  1. 長度 0 到 7:直接用八位元編碼存字串。
  2. 長度 8 或 9:用六位元編碼,查詢表為 eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX。
  3. 長度 10 或 11:用五位元編碼,查詢表為 eilotrm.apdnsIc ufkMShjTRxgC4013。

回頭比對先前的輸出。把 0x0022038a01169585 去掉末尾 8 位元,再切成一段段 6 位元:

001000 100000 001110 001010 000000 010001 011010 010101

拿這些索引去查表,確實拼得出 abcdefgh。而 0x0880e28045a54195 去掉末尾 8 位元後切成 6 位元區塊,前面完全一致,只是末尾多了 i:

001000 100000 001110 001010 000000 010001 011010 010101 000001

但接下來就離奇了。照理該用五位元編碼再多撐兩個字串,它卻開始產生長度 10 的物件。原因很樸素:五位元編碼表太有限,裡面沒有字母 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

這次出現了長度 11 的 Tagged Pointer 字串。最後兩筆的二進位切分是:

01110 01010 00000 10001 11010 10101 00001 10110 10010 00010

01110 01010 00000 10001 11010 10101 00001 10110 10010 00010 00110

與我們的推論一致。

建立 Tagged Pointer 字串

既然已經知道編碼方式,建立方向的邏輯基本上就是反過來做。我們找到一個名為 __CFStringCreateImmutableFunnel3 的私有方法,這個龐大的函式處理了字串建立的所有情況。它在 CoreFoundation 的開源版本裡(opensource.apple.com 上可以找到),但先別太興奮:Tagged Pointer 字串的部分並不在開源內容中。

大致流程是:若字串的長度與內容適合 Tagged Pointer,就組出一個 Tagged Pointer,依情況採用 ASCII、六位元或五位元編碼。其中會用到兩張互相反查的表,一張是全域字串常量 sixBitToCharLookup,另一張是 Funnel3 內部的 charToSixBitLookup。

那張神祕的表

完整的六位元編碼表是:

eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX

很自然會問:這排序也太奇怪了吧?

因為同一張表要同時服務六位元與五位元編碼,所以不按字母序排列是有道理的:常用字元應該排在前半段,罕用字元排在後半段,這樣才能讓盡量多的長字串擠進五位元編碼。

不過這種前後兩段的切分,段落「內部」的順序其實並不重要,理论上按字母序排也可以,但實際上並沒有。表開頭那幾個字母,與它們在英文裡的出現頻率相當接近:最常見的是 E,接著 T、A、O、I、N、S。E 排在開頭完全合理,其餘也都在前段,看起來確實是按使用頻率在排。與英文的落差,可能來自一個現實:Cocoa App 裡的短字串並不是從英文散文隨機抽出的單字,而是更「專業」的語言。

我個人是這樣猜的:Apple 原本想做一個更漂亮的可變長度編碼,或許基於 Huffman,但最終因為太難、不划算或時間不夠而退而求其次,改成上面這種固定長度的 8/6/5 位元方案。那張奇怪的表,就是現版本的殘留物,同時也是日後若要改採變長編碼的一個起點。這純屬推測,不過它看起來確實很像我自己會做的事。

結論

Tagged Pointer 是很棒的技術,把它用在字串上更顯得別出心裁。Apple 顯然在這上面下了不少功夫,他們一定看到了足夠明顯的好處。看他們如何把這些技巧拼湊起來、如何在極度有限的空間裡榨出更多資訊,本身就很有意思。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved