【譯】采用Tagged Pointer的字符串
本文由CocoaChina譯者@ALEX吳浩文翻譯
作者：Mike Ash
原文：Friday Q&A 2015-07-31: Tagged Pointer Strings
Tagged Pointer是一個能夠提升性能、節省內存的有趣的技術。在OS X 10.10中，NSString就采用了這項技術，現在讓我們來看看該技術的實現過程。本話題由Ken Ferry提出。
回顧
對象在內存中是對齊的，它們的地址總是指針大小的整數倍，通常為16的倍數。對象指針是一個64位的整數，而為了對齊，一些位將永遠是零。
Tagged Pointer利用了這一現狀，它使對象指針中非零位有了特殊的含義。在蘋果的64位Objective-C實現中，若對象指針的最低有效位為1(即奇數)，則該指針為Tagged Pointer。這種指針不通過解引用isa來獲取其所屬類，而是通過接下來三位的一個類表的索引。該索引是用來查找所屬類是采用Tagged Pointer的哪個類。剩下的60位則留給類來使用。
Tagged Pointer有一個簡單的應用，那就是NSNumber。它使用60位來存儲數值。最低位置1。剩下3位為NSNumber的標志。在這個例子中，就可以存儲任何所需內存小於60位的數值。
從外部看，Tagged Pointer很像一個對象。它能夠響應消息，因為objc_msgSend可以識別Tagged Pointer。假設你調用integerValue，它將從那60位中提取數值並返回。這樣，每訪問一個對象，就省下了一次真正對象的內存分配，省下了一次間接取值的時間。同時引用計數可以是空指令，因為沒有內存需要釋放。對於常用的類，這將是一個巨大的性能提升。
NSString似乎並不適合Tagged Pointer，因為它的長度即可變，又可遠遠超過60位。然而，Tagged Pointer是可以與普通類共存的，即對一些值使用Tagged Pointer，另一些則使用一般的指針。例如，對於NSNumber，大於2^60-1的整數就不能采用Tagged Pointer來存儲，而需要在內存中分配一個NSNumber的對象來存儲。只要創建對象的代碼編寫正確，就沒有問題。
NSString也是如此。對於那些所需內存小於60位的字符串，它可以創建一個Tagged Pointer。其余的則被放置在真正的NSString對象裡。這使得常用的短字符串的性能得到明顯的提升。實際代碼就是如此嗎？似乎Apple是這麼認為的，因為他們這麼做了並實現了它。
可能的實現方法
在看Apple的實現之前，讓我們花點時間想想我們自己會如何實現這種字符串。最初想法很簡單：置最低位為1，剩下的3位作為類的標志，60位為真正的數據。如何使用這60位是一個大問題。我們想要最大限度地利用這60位。
一個Cocoa字符串在概念上是一系列的Unicode字符。一共有1,112,064個有效的Unicode字符，所以需要21位代表一個字符。這意味著我們可以放兩個字符在這60位裡，浪費掉了18位。我們可以用一些額外的位來存儲長度。所以一個采用Tagged Pointer的字符串可以是零個、一個或兩個字符。然而被限制為只有兩個字符的字符串似乎並沒什麼用。
NSString API實際上是基於UTF-16的實現，而不是直接基於Unicode。UTF-16用16位的序列值來表示Unicode。最常見的基本多文種平面（Basic Multilingual Plane，BMP）字符需要16位，字符編碼超過65,535的則需要兩個。我們可以放三個16位進60位，剩下12位。再借用一些表示長度的位，這將允許我們表示0-3個UTF-16字符。這將允許三個BMP字符，且其中一個字符可以超出BMP的范圍。被限制為三個字符的字符串的使用仍然有限。
大多數APP裡的字符串是ASCII。即使APP本地化到非ASCII語言，字符串也遠遠不止用於顯示UI。它們用於URL組件、文件擴展名、對象鍵、屬性列表值等等。UTF-8編碼是一種ASCII兼容的編碼，它將每一個ASCII字符編碼為一個字節，用四字節編碼其他Unicode字符。我們可以在60位裡放七個字節，剩下的4位表示長度。這樣這種字符串可以存儲七個ASCII字符，或者少一些的非ASCII字符，這取決於這些字符是什麼。
如果我們要優化ASCII，我們不妨放棄對Unicode的完整支持。畢竟包含非ASCII字符的字符串可以使用真正的NSString對象。ASCII是一個七位編碼，如果我們給每個字符只分配7位會發生什麼？讓我們存儲八個ASCII字符在這60位裡，再用剩下的4位存儲長度。這聽起來很有用。在一個APP裡可能有大量的字符串是純ASCII並且只包含8個字符或更少。
接著往下想，完整的ASCII裡有很多不常用的東西。比如一堆控制字符和不常用的符號。字母和數字才是最常使用的。我們能不能把編碼縮短到6位？
6位可以存儲64個不同的值。ASCII裡有26個字母，算上大寫小寫則有52個，再加上數字0-9則多達62個。如果說有兩個地方需要節省，那就是空間和時間。可能有很多只包含這些字符的字符串。每6位1個字節，我們可以在60位裡存儲十個字符！等等！我們沒有剩余空間存儲長度。所以要麼我們存儲9個字符加長度，要麼在那64個不同值裡刪除一個(我認為可以刪除空格)，然後對於那些小於10個字符的字符串使用零作為結束符。
如果是5位呢？這不是完全荒謬的。可能有很多只存在小寫字符的字符串。例如，5位可以存儲32個不同的值。算上整個小寫字母，也還有6個額外的值，你可以再分配一些更常見的大寫字母、符號、數字或組合。如果你發現其中的一些情況更常見，你甚至可以刪除一些不太常見的小寫字母，例如q。如果我們省下存儲長度的空間，5位編碼我們可以存儲十一個字符，如果我們借一個符號位並使用一個結束符則可以存儲十二個字符。
接著往下想，作為一個合理的編碼，5位已經盡可能的短了。你可以用一個可變長度的編碼，如霍夫曼編碼。常見的，這將允許字母e比起字母q有更短的編碼。這將可能允許最短1位來編碼一個字符，在一些極端的情況下假如你的字符串全部都是e。這樣也將導致更復雜的空間開銷，編碼也可能更慢。
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的代碼生成，如果編譯器把它們嵌入二進制裡，那麼前提就被打破了（字符串常量就是這樣）。因此我們需要copy常量字符串來獲取Tagged Pointer。
mutableCopy是必要的，因為NSString太聰明，而且也知道一個不可變字符串的副本是一個毫無意義的操作，所以它會返回原字符串的當作“copy”。字符串常量是不可變的，所以[a copy]結果只是a。一個可變量的副本強迫它產生真正副本，這樣一個可變量副本的不可變的副本足以讓系統給我們產生一個采用Tagged Pointer的字符串。
注意不要在你自己的代碼裡依賴這些細節！這是NSString的當前情況，它隨時可能改變。如果你的代碼某種程度上依賴於此，那麼代碼最終將失效。幸運的是，只有非正常的代碼才會這樣。所有正常、合理的代碼都沒有問題，傻傻的不知道任何Tagged Pointer而幸福著吧。
以下是上面代碼在我電腦上的輸出。
0x10ba41038 0x6115 NSTaggedPointerString
首先你可以看到原始指針，一個真正的對象指針。副本是第二個值，非常清楚，這是一個奇數，這意味著它不是一個有效的對象指針。這也是一個較小的數，在未映射且不可映射的4GB零頁的64位Mac地址空間的開頭裡，這使它更加不可能是一個對象指針。
我們從這個0x6115中可以推斷出什麼？我們知道，Tagged Pointer的最低4位是其機制本身的一部分。最低半字節5的二進制是0101。最低位表示它是一個Tagged Pointer。接下來的3位表示其所屬類。010，表明字符串類在類表中的索引為2。這些信息並不是很有用。
開頭的61是有啟發性的。61在十六進制裡正好是小寫字母a的ASCII編碼，這正是字符串的值。看來是直接的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
正如我們所想的那樣，最低的四位並沒有改變。即那個5將保持不變，表明這是一個NSTaggedPointerString類型的Tagged Pointer。
前面的61沒變，並加入了62。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
循環還經過兩次迭代之後才停止。數據部分繼續增長，其余部分變成亂碼。發生了什麼？讓我們看看其具體實現。
反編譯
NSTaggedPointer類在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告訴我們哪些寄存器獲取哪些參數。讓我們用_cmd替換rsi，用self替換rdi。因為arg2實際上就是index，所以讓我們用index替換r13。讓我們去掉所有__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替換rcx。最後，length的副本被賦給rdx。看來將被用作某種游標，讓我們用cursor替換rdx。現在我們的代碼長這樣：
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。這實際上是幀指針，所以編譯器直接從幀指針做一些索引。加一個0xffffffffffffffbf常數是二進制補碼中“一切都是一個無符號整數（everything is ultimately an unsigned integer）”減去65的方法。然後，它減去64。這在堆棧上可能都是相同的局部變量。鑒於按字節索引，這可能是一個放在堆棧種的緩沖。奇怪的是，其實有一個方法能夠直接讀取緩沖區而無需專門編寫。發生了什麼？
原來Hopper忘了反編譯在if外的else的部分。整合在一起變成了這樣：
mov rax, rdi
shr rax, 0x8
mov qword [ss:rbp+var_40], rax
var_40在Hopper的反編譯中表示的偏移量64。(40是64的十六進制版本)讓我們調用這個指向位置緩沖區的指針。這個錯失部分的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的值並提取指定的字節，然後返回給調用者。既然ASCII編碼在ASCII范圍內匹配Unicode編碼，也就無需額外的操作來讀出正確的值。我們之前猜測純ASCII的字符串是以這種方式存儲，這裡證實了這種猜測。
如果長度是8或者更長呢？如果長度是8或者更長但比10（0xa）小，代碼進入一個循環。這個循環取低6位的stringData，當作一個表的索引，然後將該值復制到緩沖區。然後把stringData右移6位並循環，直到它遍歷整個字符串。這是六位編碼，先把六位編碼映射到ASCII字符再存儲在表中。在緩沖區建立臨時字符串，然後在索引操作結束時從中提取所要求的字符。
如果長度是10或者更長呢？代碼幾乎相同，除了它是五位循環一次，而不是六位。這是一個更緊湊的編碼，使字符串能存儲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”。
同樣，二進制of0x0880e28045a54195去掉末尾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
正如我們所想的那樣。
創建采用Tagged Pointer的字符串
既然我們已經知道這種字符串如何編碼，我就不在創建它們的代碼中涉及具體細節。我們發現了一個叫__CFStringCreateImmutableFunnel3的私有方法，這個巨大的方法處理了所有情況下的字符串創建。這個函數包含在CoreFoundation的開源版本裡，在opensource.apple.com上。但別激動：采用Tagged Pointer的字符串並不包括在開源版本裡。
這裡的代碼基本上和上面的相反。如果字符串的長度和內容適合Tagged Pointer，它構建一個Tagged Pointer，包含ASCII、六位編碼或五位編碼。其中有一個逆查詢表。這個表視為一個全局的字符串常量稱為sixBitToCharLookup，並有相應的稱為charToSixBitLookup的表在方法Funnel3裡。
神秘的表
完整的六位編碼表是：
eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX
一個顯然的問題是：為什麼這個指令這麼奇怪?
因為這個表同時用於六位編碼和五位編碼，它不完全按字母順序排列是有意義的。最常使用的字符應該是上半部分，而較少使用的字符應該在下半部分。這可以確保盡可能多的長字符串可以使用五位編碼。
然而，這種分為兩個部分的分割，每個部分內的順序並不重要。每個部分內本身是可以按照字母表順序排列的，然而實際上沒有這樣。
表中前幾個字母與字母出現在英語裡的頻率相似。最常見的英文字母是E，然後是T，A，O，I，N，S。E作為表的開頭是正確的，其他的則靠近開頭。表似乎是按使用頻率排序。與英語的差異可能是因為Cocoa APP中的短字符串並不是一個從英語散文中隨機選擇的單詞，而是更專業的語言。
我推測Apple最初想使用一個更漂亮的變長編碼，可能基於霍夫曼編碼。但是太困難，或者不值得，或者他們時間不夠了，所以他們退而求其次推出一個如上所述的不那麼雄心勃勃的版本，字符串使用定長的八位，六位，或五位編碼。奇怪的表是當前版本的一個殘留物，也是一個起點，如果他們決定在未來去采用變長編碼。這是純粹的猜測，它看起來更像是我會做的事。
結論
Tagged Pointer是一個很棒的技術，能把它運用在字符串上很不尋常。顯然Apple花了很多心思在這上面，他們必須要看到一個顯著的好處。看他們如何把這些技術融合在一起，看他們如何在非常有限的空間裡面盡可能的存儲信息，實在有趣。
