Edited at

SwiftとObjective-Cの短い文字列

これは https://qiita.com/advent-calendar/2018/ios2 の22日目の記事です。

WWDC 2018のセッション What's New in Swift にて、Swift 4.2は「small string optimization」を行なっていることが紹介された。

概要としては、15文字までの文字列を、ヒープを消費せずにスタックに確保できるというものである。また、以前は24バイトを占めていたが16バイトに短縮されたとのこと。

どういう実装になっているか気になったので少しだけ調べてみた。また、Objective-Cでも短い文字列が特別扱いされることがあるので、そちらについても調べた。


Swift 4.2 (Xcode 10.1)


デバッガで観察する

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


SmallStringTest.swift

import Foundation

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


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

xcode1

今回の文字列"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

※ 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に種類の説明が載っている。(下図)

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ビットに長さが入るようである。上の例だと0xED0xEimmortal, 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」に、iOSでは「64bit環境におけるObjective-Cのポインタ」などに解説がある。これにより、ヒープを消費せずに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から作ることができる。

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++で書くとこんな感じになる。

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となる。


参考


修正点


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