本文由 CocoaChina 譯者 @ALEX吳浩文 翻譯
作者:Mike Ash
原文:Friday Q&A 2015-07-31: Tagged Pointer Strings
Tagged Pointer 是一項兼顧效能與記憶體消耗的漂亮技巧。從 OS X 10.10 起,NSString 也換上了這套機制。本文就來拆解它究竟是怎麼運作的。這個題目由 Ken Ferry 提出。
記憶體中的物件一定是對齊的:位址向來是指針大小的整數倍,實務上多半是 16 的倍數。也就是說,一個 64 位元指標裡,總會有幾個位元註定是 0。
Tagged Pointer 就是拿這件事做文章——它讓指標中那些「永遠用不到的位元」被賦予新的含義。在 Apple 的 64 位元 Objective-C 實作裡,只要物件指標的最低有效位是 1(也就是奇數),這個值就被視為 Tagged Pointer。這類指標不再透過解引用 isa 來得知自己屬於哪個類別,而是取接下來 3 個位元當索引,去查一張「哪些類別支援 Tagged Pointer」的表;剩下的 60 個位元則完全交由該類別自行支配。
Tagged Pointer 最單純的應用就是 NSNumber:它用那 60 個位元存整數值,最低位固定為 1,另外 3 位放 NSNumber 自己的旗標。於是任何位寬小於 60 位的數值,都能直接塞進指標裡,不必真的配置一個物件。
從外部看,Tagged Pointer 的行為與一般物件幾乎無異,因為 objc_msgSend 本身就懂得辨識它。假設你送出一個 integerValue,它會從那 60 個位元中取出數值再回傳。如此一來,每次存取都省下一次真正的記憶體配置,也省下一次間接取值。更別提它的 retain / release 可以是空實作,因為根本沒有記憶體需要釋放。對於高頻使用的類別,這是相當可觀的效能提升。
那 NSString 適合嗎?乍看之下並不適合,因為字串長度可變,而且遠遠可能超過 60 個位元。但 Tagged Pointer 完全可以與一般物件並存:某些值走 Tagged Pointer,其餘照舊走真正的指標。以 NSNumber 為例,大於 2^60-1 的整數就無法用 Tagged Pointer 存放,必須老老實實配置一個 NSNumber 物件。只要負責建立物件的程式碼寫得夠仔細,這一切都不成問題。
NSString 也是同樣的道理。凡是所需空間小於 60 個位元的字串,就做成 Tagged Pointer;其餘的放進真正的 NSString 物件裡。這讓大量常見的短字串在效能上有明顯好處。Apple 真的這麼做了嗎?看起來是的,因為他們確實動手實作並 Shipping 了。
在窺探 Apple 的實作之前,不妨先自己想想:這 60 個位元要怎麼用才能榨乾最後一滴價值?
最直覺的想法是:最低位設為 1,接著 3 位當類別旗標,剩下 60 位放真正的資料。難題在於那 60 位怎麼分配。
概念上,一個 Cocoa 字串就是一串 Unicode 字元。有效 Unicode 字元總共 1,112,064 個,需要 21 個位元才能編碼一個字元。也就是說 60 位裡只塞得下兩個字元,還白白浪費 18 位。再扣掉一些位元存長度,結果就是這種字串只能裝 0 到 2 個字元——實用價值實在有限。
不過 NSString 的 API 並不是直接架在 Unicode 上,而是架在 UTF-16 上。UTF-16 以 16 位元的序列值表示 Unicode:最常見的基本多文種平面(BMP)字元佔 16 位,碼點超過 65,535 的字元則要兩個 16 位元單元。這樣 60 位裡可以放三個 16 位元,還剩 12 位;再借幾位存長度,就能表示 0 到 3 個 UTF-16 字元,其中最多一個可以超出 BMP 範圍。但被限制在三個字元的字串,用處還是偏小。
多數 App 裡的字串其實是 ASCII。就算 App 做了本地化、介面文案不是 ASCII,字串的用途也遠不止顯示 UI:URL 元件、副檔名、物件 key、plist 值等等。UTF-8 是一種與 ASCII 相容的編碼,每個 ASCII 字元佔一 byte,其他 Unicode 字元則佔到四個 byte。那麼 60 位放七個 byte、留 4 位給長度,就能存七個 ASCII 字元,或非 ASCII 字元更少一些的組合。
既然要為 ASCII 優化,那不如乾脆放棄對 Unicode 的完整支援——反正含非 ASCII 字元的字串交給真正的 NSString 就好。ASCII 本身是七位編碼,如果每個字元只給 7 位呢?於是我們可以在 60 位裡塞八個 ASCII 字元,再用剩下的 4 位存長度。這聽起來實用多了,畢竟 App 裡有大量純 ASCII、長度不超過 8 的字串。
再往下想:完整 ASCII 裡有不少罕用角色,一堆控制字元與冷僻符號。真正高頻的只有字母和數字。那能不能壓到 6 位?
6 位可以表示 64 種不同值。ASCII 有 26 個字母,大小寫合起來 52 個,再加上 0-9 剛好 62 個。如果只想省空間又省時間,這條路很誘人:每個字元 6 位,60 位裡就能塞十個字元!等等——沒地方放長度了。所以只能二擇一:存 9 個字元加長度,或是從那 64 個值裡砍掉一個(我會砍掉空白),再對長度小於 10 的字串用 0 當結束符。
那 5 位呢?聽起來荒謬,其實未必。很多字串只有小寫字母。5 位可表示 32 種值,26 個小寫字母用掉之後還剩 6 個額度,可以分配給更常見的大寫字母、符號或數字。如果分析發現某些罕用小寫字母(比如 q)真的很少出現,甚至可以直接砍掉。省下長度欄位後,5 位編碼能存十一個字元;再借一個位元搭配結束符,就能存十二個。
再往下就不合理了。真要壓極限,可以改用變長編碼,例如 Huffman 編碼:常見字母(如 e)用更短的碼,罕用字母(如 q)用長碼。極端情況下最短只要 1 個位元。但代價是更複雜的空間開銷,以及可能更慢的解碼。
那 Apple 到底選了哪一條路?我們來找答案。
下面這段程式碼建立一個此類字串,並把它的指標印出來:
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
首先你會看到原始指標,一個真正的物件指標。副本是第二個值,很明顯是奇數,這意味著它不是有效的物件指標。而且它是個相當小的數,落在 64 位元 Mac 位址空間開頭那片未映射、也不可映射的 4GB 零頁裡,這讓它更不可能是物件指標。
那從 0x6115 我們能推出什麼?我們知道最低 4 位是機制本身的一部分。最低半位元組 5 的二進位是 0101:最低位表示這是一個 Tagged Pointer,接下來 3 位 010 表示該字串類別在類別表中的索引是 2。這些資訊其實沒什麼用處。
開頭的 61 就很有啟發性了。61 在十六進位下正好是小寫字母 a 的 ASCII 碼,也就是這個字串的值。看來是直接的字節編碼,真方便。
類別名稱告訴了我們這個類別的用途,也是思考實作的好切入點。我們等等再談它,先做幾個外部觀察。
下面是一個迴圈,它組出越來越長的 abcdef…… 字串,一個接一個印出來,直到不再產生 Tagged Pointer 為止。
NSMutableString *mutable = [NSMutableString string];
NSString *immutable;
char c = 'a';
do {
[mutable appendFormat: @"%c", c++];
immutable = [mutable copy];
NSLog(@"0x6lx %@ %@", immutable, immutable, object_getClass(immutable));
} while (((uintptr_t)immutable & 1) == 1);第一個輸出:
0x0000000000006115 a NSTaggedPointerString
就是我們剛才看過的那個值。注意我把所有前導零都印了出來,方便後續比較。再看第二個輸出:
0x0000000000626125 ab NSTaggedPointerString
正如預期,最低 4 位沒有變,那個 5 會一直維持不變,代表這是 NSTaggedPointerString 類型的 Tagged Pointer。
前面的 61 沒變,另外加入了 62,而 62 顯然就是 b 的 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]:
push rbp mov rbp, rsp shr rdi, 0x4 and rdi, 0xf mov rax, rdi pop rbp ret
用 Hopper 反編譯:
unsigned long long -[NSTaggedPointerString length](void * self, void * _cmd) {
rax = self >> 0x4 & 0xf;
return rax;
}簡單說,取長度就是把第 4 到第 7 位抽出來回傳,完全印證了我們先前的推測。
另一個 NSString 的原始方法是 characterAtIndex:。我跳過冗長的反編譯,直接看 Hopper 的輸出,已經相當可讀了:
unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long arg2) {
rsi = _cmd;
rdi = self;
r13 = arg2;
r8 = ___stack_chk_guard;
var_30 = *r8;
r12 = rdi >> 0x4 & 0xf;
if (r12 >= 0x8) {
rbx = rdi >> 0x8;
rcx = "eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX";
rdx = r12;
if (r12 < 0xa) {
do {
*(int8_t *)(rbp + rdx + 0xffffffffffffffbf) = *(int8_t *)((rbx & 0x3f) + rcx);
rdx = rdx - 0x1;
rbx = rbx >> 0x6;
} while (rdx != 0x0);
}
else {
do {
*(int8_t *)(rbp + rdx + 0xffffffffffffffbf) = *(int8_t *)((rbx & 0x1f) + rcx);
rdx = rdx - 0x1;
rbx = rbx >> 0x5;
} while (rdx != 0x0);
}
}
if (r12 <= r13) {
rbx = r8;
___CFExceptionProem(rdi, rsi);
[NSException raise:@"NSRangeException" format:@"%@: Index %lu out of bounds; string length %lu"];
r8 = rbx;
}
rax = *(int8_t *)(rbp + r13 + 0xffffffffffffffc0) & 0xff;
if (*r8 != var_30) {
rax = __stack_chk_fail();
}
return rax;
}先整理一下。前三行只是 Hopper 在告訴我們哪個暫存器裝哪個參數。把 rsi 換成 _cmd、rdi 換成 self,由於 arg2 實際上就是 index,把 r13 換成 index。再把所有 __stack_chk 相關的部分拿掉,那只是安全機制,與方法本身的邏輯無關。整理後變成:
unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long index) {
r12 = self >> 0x4 & 0xf;
if (r12 >= 0x8) {
rbx = self >> 0x8;
rcx = "eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX";
rdx = r12;
if (r12 < 0xa) {
do {
*(int8_t *)(rbp + rdx + 0xffffffffffffffbf) = *(int8_t *)((rbx & 0x3f) + rcx);
rdx = rdx - 0x1;
rbx = rbx >> 0x6;
} while (rdx != 0x0);
}
else {
do {
*(int8_t *)(rbp + rdx + 0xffffffffffffffbf) = *(int8_t *)((rbx & 0x1f) + rcx);
rdx = rdx - 0x1;
rbx = rbx >> 0x5;
} while (rdx != 0x0);
}
}
if (r12 <= index) {
rbx = r8;
___CFExceptionProem(self, _cmd);
[NSException raise:@"NSRangeException" format:@"%@: Index %lu out of bounds; string length %lu"];
r8 = rbx;
}
rax = *(int8_t *)(rbp + index + 0xffffffffffffffc0) & 0xff;
return rax;
}第一個 if 之前有這麼一行:
r12 = self >> 0x4 & 0xf
這正是我們剛看過的取長度程式碼,於是可以用 length 取代 r12:
unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long index) {
length = self >> 0x4 & 0xf;
if (length >= 0x8) {
rbx = self >> 0x8;
rcx = "eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX";
rdx = length;
if (length < 0xa) {
do {
*(int8_t *)(rbp + rdx + 0xffffffffffffffbf) = *(int8_t *)((rbx & 0x3f) + rcx);
rdx = rdx - 0x1;
rbx = rbx >> 0x6;
} while (rdx != 0x0);
}
else {
do {
*(int8_t *)(rbp + rdx + 0xffffffffffffffbf) = *(int8_t *)((rbx & 0x1f) + rcx);
rdx = rdx - 0x1;
rbx = rbx >> 0x5;
} while (rdx != 0x0);
}
}
if (length <= index) {
rbx = r8;
___CFExceptionProem(self, _cmd);
[NSException raise:@"NSRangeException" format:@"%@: Index %lu out of bounds; string length %lu"];
r8 = rbx;
}
rax = *(int8_t *)(rbp + index + 0xffffffffffffffc0) & 0xff;
return rax;
}接著看 if 內部。第一行把 self 右移 8 位,那 8 位裝的是 Tagged Pointer 標記與字串長度,剩下的就是我們猜測的真正資料。用 stringData 取代 rbx 讓程式碼更清楚;下一行顯然是把某張查詢表指派給 rcx,就用 table 取代;最後 length 的副本被指派給 rdx,看起來要當某種游標,用 cursor 取代。於是:
unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long index) {
length = self >> 0x4 & 0xf;
if (length >= 0x8) {
stringData = self >> 0x8;
table = "eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX";
cursor = length;
if (length < 0xa) {
do {
*(int8_t *)(rbp + cursor + 0xffffffffffffffbf) = *(int8_t *)((stringData & 0x3f) + table);
cursor = cursor - 0x1;
stringData = stringData >> 0x6;
} while (cursor != 0x0);
}
else {
do {
*(int8_t *)(rbp + cursor + 0xffffffffffffffbf) = *(int8_t *)((stringData & 0x1f) + table);
cursor = cursor - 0x1;
stringData = stringData >> 0x5;
} while (cursor != 0x0);
}
}
if (length <= index) {
rbx = r8;
___CFExceptionProem(self, _cmd);
[NSException raise:@"NSRangeException" format:@"%@: Index %lu out of bounds; string length %lu"];
r8 = rbx;
}
rax = *(int8_t *)(rbp + index + 0xffffffffffffffc0) & 0xff;
return rax;
}幾乎所有變數都有名字了,只剩一個 rbp。它其實是 frame pointer,編譯器直接以它做索引。加上 0xffffffffffffffbf 這個常數,是二補數下「萬物皆為無號整數」減去 65 的寫法,然後再減 64,這些偏移顯然都指向同一個堆疊上的區域。既然是以 byte 為單位索引,那大概是一個放在堆疊上的緩衝區。奇怪的是,程式裡似乎有個方法能直接讀這個緩衝區,卻沒有寫出來。發生了什麼?
原來 Hopper 漏掉了 if 之外的 else 分支。合起來看是這樣:
mov rax, rdi shr rax, 0x8 mov qword [ss:rbp+var_40], rax
var_40 在 Hopper 的輸出中代表偏移量 64(40 是 64 的十六進位寫法)。我們把這個位置稱作 buffer。這個被漏掉的分支,C 版本看起來就是:
*(uint64_t *)buffer = self >> 8;
把它補回去,並用 buffer 取代 rbp,程式碼可讀性立刻改善。也順手加上緩衝區的宣告提醒自己:
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 {
*(int8_t *)(buffer + cursor - 1) = *(int8_t *)((stringData & 0x3f) + table);
cursor = cursor - 0x1;
stringData = stringData >> 0x6;
} while (cursor != 0x0);
}
else {
do {
*(int8_t *)(buffer + cursor - 1) = *(int8_t *)((stringData & 0x1f) + table);
cursor = cursor - 0x1;
stringData = stringData >> 0x5;
} while (cursor != 0x0);
}
} else {
*(uint64_t *)buffer = self >> 8;
}
if (length <= index) {
rbx = r8;
___CFExceptionProem(self, _cmd);
[NSException raise:@"NSRangeException" format:@"%@: Index %lu out of bounds; string length %lu"];
r8 = rbx;
}
rax = *(int8_t *)(buffer + index) & 0xff;
return rax;
}好多了。雖然那些看起來瘋狂的指標運算有點難讀,但它們其實只是陣列索引。我們把這個問題也解決掉:
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) {
rbx = r8;
___CFExceptionProem(self, _cmd);
[NSException raise:@"NSRangeException" format:@"%@: Index %lu out of bounds; string length %lu"];
r8 = rbx;
}
rax = buffer[index];
return rax;
}現在終於有點樣子了。
程式依長度分成三種情況。長度小於 8 時走那個被漏掉的 else 分支:取值、右移、放進緩衝區,這是純 ASCII 的情況。此時 index 直接索引 self 的值並取出指定 byte 回傳。既然 ASCII 編碼在 ASCII 範圍內與 Unicode 碼位一致,就不需要額外轉換。我們先前猜測純 ASCII 字串以這種方式存放,這裡得到了證實。
長度是 8 或更多呢?若長度 ≥ 8 但 < 10(0xa),程式進入一個迴圈:取 stringData 的低 6 位當索引查表,把對應值寫進緩衝區,然後 stringData 右移 6 位繼續,直到走完整個字串。這是六位編碼,映射表存在那張字串常量裡。程式先在緩衝區還原出臨時字串,索引結束後再從中取出你要的字元。
長度 ≥ 10 呢?邏輯幾乎一樣,只是改成每次處理 5 位。這是更緊湊的編碼,能存 11 個字元,代價是編碼表只有 32 個值,也就是六位表的前半段。
於是 Tagged Pointer 字串的配置就清楚了:
1:長度 0 到 7,直接用八位編碼存放字串。
2:長度 8 或 9,用六位編碼存放,編碼表為 “eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX”。
3:長度 10 或 11,用五位編碼存放,編碼表為 “eilotrm.apdnsIc ufkMShjTRxgC4013”。
拿先前印出的資料來對照:
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
把 0x0022038a01169585 去掉末尾 8 位,再切成一個個 6 位的區塊,得到:
001000 100000 001110 001010 000000 010001 011010 010101
拿這些索引去查表,確實拼出了 “abcdefgh”。
同樣地,0x0880e28045a54195 去掉末尾 8 位再切 6 位一組:
001000 100000 001110 001010 000000 010001 011010 010101 000001
前面完全相同,只是末尾多了一個 i。
但接下來就離奇了。它本該改用五位編碼繼續產生字串,卻開始配置長度為 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
正如我們所想。
既然已經知道編碼方式,建立它們的程式碼就不必再逐行細究。我們找到一個名為 __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 編碼。但那太難、太不划算,或者時間不夠,於是他們退而求其次,做出一個如本文所述的、沒那麼雄心勃勃的版本:字串採用定長的八位、六位或五位編碼。那張奇怪的表大概是這個版本的殘留物,同時也是一個起點——如果他們哪天決定改採變長編碼。這純屬推測,只是它看起來比較像我自己會做的事。
Tagged Pointer 是很棒的技術,把它用在字串上更是別出心裁。Apple 顯然在這上面花了大量心思,他們想必看到了相當明顯的好處。看他們如何把這些技巧拼湊起來、如何在極其有限的空間裡盡可能多地塞進資訊,實在很有意思。