SwiftとObjective-Cの短い文字列

これは https://qiita.com/advent-calendar/2018/ios2 の22日目の記事です。
WWDC 2018のセッション [What's New in Swift](https://developer.apple.com/videos/play/wwdc2018/401/) にて、Swift 4.2は「small string optimization」を行なっていることが紹介された。
概要としては、15文字までの文字列を、ヒープを消費せずにスタックに確保できるというものである。また、以前は24バイトを占めていたが16バイトに短縮されたとのこと。
どういう実装になっているか気になったので少しだけ調べてみた。また、Objective-Cでも短い文字列が特別扱いされることがあるので、そちらについても調べた。

## Swift 4.2 (Xcode 10.1)

### デバッガで観察する

print文にブレークを張って実行する。

```swift:SmallStringTest.swift
import Foundation

class SmallStringTest {
    init() {
        let str = "0123456789abc"
        print(str)
    }
}
```

見たい変数(str)を右クリックして「View Memory of "str"」をクリック

![xcode1](https://qiita-image-store.s3.amazonaws.com/0/20902/96990baa-e618-2ed3-9c07-3f2d7d9e59e6.png)

今回の文字列```"0123456789abc"```は、```38 39 61 62 63 00 00 ED 30 31 32 33 34 35 36 37```のように格納されているようだ。
なお```0x7FFEE23E6B70```は、```register read```してみて、EBP(スタックフレームを指すレジスタ、シミュレータの場合)の値に近いので、ヒープではなくスタックであろう。
ちなみに、試した限りではmacOSでもiOSでも同じ値(```0xED...```)にエンコードされるようである。

![xcode2](https://qiita-image-store.s3.amazonaws.com/0/20902/9500874a-ec3a-b558-fc80-0d4ce8d0ba37.png)

※ macOSやiOSはlittle endianなので、1ワードの値は下位から格納される。```0x123456789ABCDEF0```という値は、バイト単位だと```F0 DE BC 9A 78 56 34 12```という順番で格納される。今回の場合、先頭の1ワード(64ビット、8バイト)は```38 39 61 62 63 00 00 ED```なので、内部のUInt64の値としては```0xED00006362613938```となる。

### ソースコード

なんとなく探したところ、これが該当するクラスの実装のようである。
https://github.com/apple/swift/blob/master/stdlib/public/core/SmallString.swift
leadingRawBitsとtrailingRawBitsという二つの64ビットの値により一つの文字列を表現する。
先頭の8文字まではleadingRawBitsに、後半の7文字とdiscriminator(後述)がtrailingRawBitsに格納されている。0から15までのどの長さでも16バイトを占めるようである。
trailingRawBitsの最上位の4ビットの部分はdiscriminatorと呼ばれており、オブジェクトの種類を判別するのに使われている。
[StringObject.swift](b/master/stdlib/public/core/StringObject.swift)に種類の説明が載っている。(下図)

| Form | b63 | b62 | b61 | b60 |
| --- | --- | --- | --- | --- |
| Immortal, Small | 1 | ASCII | 1 | 0 |
| Immortal, Large | 1 | 0 | 0 | 0 |
| Native | 0 | 0 | 0 | 0 |
| Shared | x | 0 | 0 | 0 |
| Shared, Bridged | 0 | 1 | 0 | 0 |
| Foreign | x | 0 | 0 | 1 |
| Foreign, Bridged | 0 | 1 | 0 | 1 |

これによるとASCIIのsmall string上位4ビットは```1110```なので、16進数だと```0xE???????????????```となる。
次の4ビットに長さが入るようである。上の例だと```0xED```の```0xE```が```immortal, small, ASCII```を、```0xD```が長さが13を示している。

leadingRawBitsは```_storage.0```となっているので、メモリ上は先に来そうな気がするが、実際のメモリレイアウトとしてはtrailingRawBitsが先に格納されている。
おそらくオブジェクトを読み込むとき、まず先頭の8バイトを読み込み、discriminatorがsmall stringだったら、追加で8バイトを読み込むようになっているのではないかと思うが、逆にしている部分を見つけることができなかった。(TODO)

StringObjectにはこんな図があったが、これはSwift 4.2の現況とは少し違う気がする。

```
 ┌───────────────────────────────┬─────────────────────────────────────────────┐
 │ _countAndFlags                │ _object                                     │
 ├───┬───┬───┬───┬───┬───┬───┬───┼───┬───┬────┬────┬────┬────┬────┬────────────┤
 │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ 10 │ 11 │ 12 │ 13 │ 14 │     15     │
 ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼────┼────┼────┼────┼────┼────────────┤
 │ a │ b │ c │ d │ e │ f │ g │ h │ i │ j │ k  │ l  │ m  │ n  │ o  │ 1x0x count │
 └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴────┴────┴────┴────┴────┴────────────┘
```

## Objective-C

### tagged pointer

64bit環境のObjective-Cでは、tagged pointerが導入された。NSObjectのidは通常、ヒープやスタックのオブジェクトを取得するための(間接的な)情報であるが、そのかわり、idとして特定の型の値そのものを保持する仕組みである。macOSについては「[mikeash.com: Friday Q&A 2015-07-31: Tagged Pointer Strings](https://www.mikeash.com/pyblog/friday-qa-2015-07-31-tagged-pointer-strings.html)」に、iOSでは「[64bit環境におけるObjective-Cのポインタ](https://labs.gree.jp/blog/2015/01/13437/)」などに解説がある。これにより、ヒープを消費せずにNSNumberやNSStringを保持したり渡したりできる。

### NSTaggedPointerString

NSStringのtagged pointer版がNSTaggedPointerStringである。64ビットのうち、1ビットがtagged pointerかどうか(macOSの場合最下位ビット、iOSの場合最上位ビット)、3ビットがtag(macOSの場合bit1-3、iOSの場合bit60-62)、4ビットが長さ(macOSの場合bit4-7、iOSの場合bit0-3)で、残りの56ビットにデータが入る。
NSTaggedPointerStringの場合、flagの部分が```1```で、tagの部分に```010```が入る。すなわちmacOSなら下位4ビットが```0101```(16進数だと```0x???????????????5```)、iOSなら上位4ビットが```1010```(16進数だと```0xA???????????????```)となる。(下図参照)
```"a"```はmacOSなら```0x0000000000006115```、iOSだと```0xA000000000000611```である。

macOS

|payload|length|tag|tagged pointer flag|
|---|---|---|---|
|56bit|4bit|3bit(010)|1bit(1)|

iOS

|tagged pointer flag|tag|payload|length|
|---|---|---|---|
|1bit(1)|3bit(010)|56bit|4bit|

なお文字列定数はNSTaggedPointerStringにならない。以下のようにNSMutableStringから作ることができる。

```Objective-C
NSString *a = [[@"a" mutableCopy] copy];
NSLog(@"a: %@, class: %@", a, a.class);
```

デバッガ(Xcode、lldb console)からも以下のようにすると、文字列がどんな値にエンコードされるか確認できる。

```
p [(NSObject *)[@"a" mutableCopy] copy]
```

### iOS 12以外

NSTaggedPointerStringは割とカオスな実装になっており、以下のように長さで場合分けされている。
- 長さが0から7のとき: 1文字が8ビット
- 長さが8か9のとき: 1文字が6ビット
- 長さが10か11のとき: 1文字が5ビット

文字列の長さが7以下のときにはASCIIコードがそのまま入っている。一方、謎の変換テーブルが存在していて、長さが8以上の場合は文字列が謎テーブルに含まれる文字だけで構成されているときだけNSTaggedPointerStringにすることができる。
たとえばmacOSで10文字以上の場合のデコードをC++で書くとこんな感じになる。

```cpp
static string decode_macos_tagged_pointer_string_10_11(uint64_t a) {
	int length = (a >> 4) & 15;
	string result;
	for (int i = 0; i < length; ++i) {
		result += "eilotrm.apdnsIc ufkMShjTRxgC4013"[(a >> (8 + (length - i - 1) * 5)) & 31];
	}
	return result;
}
```

謎テーブルは```"eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX"```という長さ64の配列(文字列)で、長さが8か9のときには全部を、長さが10か11のときには前半32個を使う。
たとえば```hellohello```は格納できるが```helloworld```は収まらない。

### iOS 12

iOS 12のNSTaggedPointerStringは、iOS 11以前とは別の実装になっているようである。

iOS 10.3.3 (device)

```
(lldb) p [(NSObject *)[@"a" mutableCopy] copy]
(NSTaggedPointerString *) $0 = 0xa000000000000611 @"a"
```

iOS 11.0.1 (simulator)

```
(lldb) p [(NSObject *)[@"a" mutableCopy] copy]
(NSTaggedPointerString *) $0 = 0xa000000000000611 @"a"
```

iOS 11.2.1 (device)

```
(lldb) p [(NSObject *)[@"a" mutableCopy] copy]
(NSTaggedPointerString *) $0 = 0xa000000000000611 @"a"
```

iOS 12.1 (simulator)

```
(lldb) p [(NSObject *)[@"a" mutableCopy] copy]
(NSTaggedPointerString *) $0 = 0xfcfde2aaa91c0f75 @"a"
```

iOS 12.1 (device)

```
(lldb) p [(NSObject *)[@"a" mutableCopy] copy]
(NSTaggedPointerString *) $0 = 0x8fa505414de577e9 @"a"
```

ビットの割り当てはおおむねiOS 11以前に近いようだが、同じ文字列に対して複数の結果が返ってくる。
なぜこうなっているのか不明であるが、値のトラッキングをするときに不便だったりするのだろうか。
まだデコードに成功していないので、そのうちやってみたいと思う。
ちなみにNSTaggedPointerStringのソースコードは非公開のようである。

## その他

###　ブリッジ

small stringやNSTaggedPointerStringは、その言語のランタイムで閉じているため、別のランタイムに渡すときには変換が行われる。
Swiftからsmall stringをObjective-Cに渡すと、NSTaggedPointerStringになることがある。逆に、NSTaggedPointerStringをSwiftに渡すと、small stringとなる。

### 参考

- https://github.com/apple/swift/tree/master/stdlib/public/core
- https://opensource.apple.com/
- [WWDC 2018 - Videos - Apple Developer](https://developer.apple.com/videos/wwdc2018/)
- [mikeash.com: Friday Q&A 2015-07-31: Tagged Pointer Strings](https://www.mikeash.com/pyblog/friday-qa-2015-07-31-tagged-pointer-strings.html)
- [64bit環境におけるObjective-Cのポインタ](https://labs.gree.jp/blog/2015/01/13437/)

### 修正点

- 2018/12にSwiftのdiscriminatorが8ビットから4ビットに減った。その結果フィールド名がcountAndDiscriminatorという名前に変わった。small stringは後続の4ビットも使うので、エンコーディングしたときの値としては変わらない。(Thanks to @omochimetaru)