Swiftのメモリアライメントについて動かしながら推測

Advent Calendar の25日目の記事です。Advent Calendarの起源を見たら、25日目はおかしいんじゃないかと思いましたが、とりあえず Merry Christmas !!

内容について

クリスマスの記事なので何か関係性のある Merry 記事にしようと思いましたが、特に思いつかなかったので Memory について書こうと思います。

前職はコンシューマ向けゲーム機のプログラムをC++で実装していたので、メモリ整列は意識すべき観点の１つでした。今回は、そのメモリアライメントが Swift ではどうなっているのか気になったので、動かしながら調べてみました。

SwiftはProtocol-Oriented Programmingの構造体とクラスがきちんと分かれ、構造体+Protocolなコードを見かける機会が増えてきているので、いいタイミングかなと思います。

調べたい内容

• Swift にもアライメントの観点は存在するか？
• データ がアライン(整列)されてないとき、現場レベルでの影響は？

注意

コードで動かしながら、結果から推測しているので、推測自体が間違っている可能性があります。
ただし結果は結果なので、調べたい内容にブレは恐らくないとは思います。

さきに結論ありきで記事を見たい方は、記事下部にある まとめからお読みください。

調査方法

8バイトより小さい型を歯抜けに配置した構造体のメモリを見て、歯抜け箇所に暗黙のパディングがあるか確認します。

またサイズを確認します。
C言語では sizeof で調べられたけど Swift ではいつの間にかビルドエラー。
調べていたら Swift では MemoryLayout という 型のメモリレイアウトに関する情報を取得できるらしいので、これを使って調べます。

enum MemoryLayout

サイズ

サイズは、連続したメモリ領域のサイズを表します。

ストライド

ストライドは、インスタンスの頭（C言語で言うポインタ）から次のインスタンスへの頭までのバイト数です
配列のインデックス移動をイメージすると分かりやすいです。

アライメント

アライメントは、メモリ上アドレスの倍数を表します。

メモリーをのぞく

Xcode上で変数が指すメモリを見る方法を簡単に載せます。

次のように構造体を変数に落とし

var hoge = Hoge()
print(hoge)

print関数でブレイクポイントを貼り、次のようにlldbを実行

(lldb) frame var -L hoge
0x000000016fdd1f08: (ResearchMemoryAlign.AnyStructureA) hoge = {
0x000000016fdd1f08:   integer0 = 0
}

16進表記の値がアドレスになります.
ここで hoge を var ではなく let だとアドレスが取れません.

ビューメモリーを開く

1. 表示した値を見るために Debug > Debug Workflow > View Memory でメモリマップを開く
2. Address欄に 先ほど表示した値（アドレス） 0x000000016fdd1f08 を入れる

もし画面左が10進数表記の場合はクリックすれば16進数表記に切り替わります。

色んな構造体をのぞく

MemoryLayoutを使って色んな構造体を見てみようと思います。

たとえば下記のような構造体があったとする。

struct AnyStructureA {
    var integer0:UInt8
}
struct AnyStructureB {
    var integer0:UInt8
    var integer1:UInt16
}
struct AnyStructureC {
    var integer0:UInt8
    var integer1:UInt16
    var integer2:UInt32
}
struct AnyStructureD {
    var integer0:UInt8
    var integer1:UInt16
    var integer2:UInt32
    var integer3:UInt64
}
struct AnyStructureE {
    var integer0:UInt8
    var integer1:UInt16
    var integer2:UInt32
    var integer3:UInt64
    var structure0:AnyStructureD
}
struct AnyStructureF {
    var integer0:UInt8
    var integer1:UInt16
    var integer2:UInt32
    var integer3:UInt64
    var structure0:AnyStructureA
}
struct AnyStructureG {
    var integer0:UInt32
    var structure0:AnyStructureA
}
struct AnyStructureH {
    var integer0:UInt32
    var structure0:AnyStructureD
}
struct AnyStructureI {
    var string0:String
}

各構造体のMemoryLayoutは下表に結果になった

構造体名	size	stride	alignment	状態
AnyStructureA	1	1	1	1バイト整数
AnyStructureB	4	4	2	1〜2バイト整数
AnyStructureC	8	8	4	1〜4バイト整数
AnyStructureD	16	16	8	1〜8バイト整数
AnyStructureE	32	32	8	1〜8バイト整数 + 最大8バイト構造体
AnyStructureF	17	24	8	1〜8バイト整数 + 最大1バイト構造体
AnyStructureG	5	8	4	4バイト整数 + 最大1バイト構造体
AnyStructureH	24	24	8	4バイト整数 + 最大8バイト構造体
AnyStructureI	24	24	8	文字列オブジェクト

結果から考えると

アライメント(Alignment)

• 構造体内の 一番大きい型のサイズ になる
• 構造体の中に構造体を持っている場合は、 全構造体の中で一番大きい型のサイズになる ※1

※1

下記のようなデータ構造の場合、 出力結果は 8 になる.
しかし、構造体 C.valの型を UInt64 から UInt16 にすると、出力結果は 4 になる.

struct A{
  var val:UInt8
  var b:B
}
struct B{
  var val:UInt32
  var c:C
}
struct C{
  var val:UInt64
}
struct D{
  var a:A
}
print(MemoryLayout<D>.alignment)

ストライド(Stride)

• アライメントの倍数になる

サイズ(size)

• アドレスの先頭から連続したメモリのサイズになる
• 暗黙なパディングも連続したメモリとみなされる ※2

※2

次のような初期化された構造体があったとする

struct A{
    var val0:UInt8
    var val1:UInt64
}
struct B{
    var val0:UInt64
    var val1:UInt8
}
var a = A(val0:170, val1:UINT64_MAX)
var b = B(val0:UINT64_MAX, val1:170)

MemoryLyaout.size（サイズ）はそれぞれ

• a は 16バイト
• b は 9バイト

この場合の 変数a のメモリは次のようになっている.

アドレス

メモリ

メモリ 0x7FFF59DB5A20 番には 170(0xAA) が代入されている。
しかしアライメントが 8バイトなので、残り 7バイトはパディングされている
メモリ 0x7FFF59DB5A20 番から 8バイト飛んだ メモリ 0x7FFF59DB5A28 番地には、
val1 の値 UINT64_MAX(0xFFFFFFFFFFFFFFFF)が入っている.

変数B のメモリは次のようになっている.

アドレス
メモリ

メモリ 0x7FFF59DB5A10 番には、val0 の値 UINT64_MAX が入っている.
同じように 8バイト飛んだ先のメモリ 0x7FFF59DB5A18 番には、
val1の値 170(0xAA) が入っており、残り 7バイトはパディングされている

MemoryLayout＜T＞.size は隣接したメモリサイズを表しているが、イマイチいい説明が思い浮かばない。
ポインタで移動できる範囲って言っても伝わりそうにない。

ちなみに何度かパディングの値を確認しているが、おそらく前回の値が残っているだけであって、上の変数Bのように綺麗に0クリアしているわけではない。

いろいろ測定してみる

測定環境

• iPhone 6
• iOS 10.0.2

仮説１．データバスが8バイトなら 「アライメント4の8バイト構造体」と「アライメント8の8バイト構造体」は理論上は同速になるはず

プログラム

1. 構造体を生成して配列に追加を10000回繰り返す.
2. 配列をクリア(キャパもリセット）.
3. 上記10回繰り返す.
4. 計測.
5. 上記を5回測定,1回目を無視した平均.

測定結果

構造体	速度
アライメント4の8バイト構造体	平均 33.8 ms
アライメント8の8バイト構造体	平均 33.4 ms

ほぼ同速。

仮説２．暗黙のパディングが入ることで4バイトアライメントされているなら、「1バイト1個と4バイト1個の構造体」と「4バイト2個の構造体」は、理論上は同速になるはず

プログラム

1. 構造体を生成して配列に追加を10000回繰り返す.
2. 配列をクリア(キャパもリセット）.
3. 上記10回繰り返す.
4. 計測.
5. 上記を5回測定,1回目を無視した平均.

測定結果

構造体	速度
暗黙パディングあり	平均 33.2 ms
暗黙パディングなし	平均 33.1 ms

ほぼ同速

仮説３．上記の法則は、構造体を使わず単純な 「1バイト変数のコピー」と「4バイト変数のコピー」にも適用されるのか？

プログラム

測定結果

状態	速度
1バイト変数	平均 14.4 ms
4バイト変数	平均 21.8 ms
8バイト変数	平均 28.0 ms

適用されず、単純に処理速度はメモリ量に反比例。
ただし、メモリを覗いてみると、1バイト変数も4バイト変数も8バイト領域が確保されていた。
これ以上は詳しい情報得られず。 メモリ条件は同じようなので、別観点が作用しているかもしれない。

仮説４．「整列されていない構造体」と「ユーザーが意識して整列された構造体」は構造体のメモリサイズは異なり、サイズ増加によるコピー速度にも影響するか？

プログラム

• 同じ目的の構造体を3種類用意
• 整列されていない構造体
• 整列された構造体
• 整列かつ型が適したサイズにされた構造体
• 構造体の配列に5万件追加
• 5万件のデータから条件検索
• 5万件のデータを先頭から１件ずつ削除

構造体ごとのメモリレイアウト情報

構造体	サイズ	ストライド	アライメント	備考
UserProfile	26	32	8	未整列な構造体
UserProfileAligned	17	24	8	整列した構造体
UserProfileOptAligned	11	12	4	整列＆型最適化

構造体ごとの測定結果

構造体	平均sec	最小sec	最大sec
UserProfile	1.973380	1.955525	2.010761
UserProfileAligned	1.478901	1.472935	1.487146
UserProfileOptAligned	0.768146	0.759845	0.773918

• 一番早かったのは、メモリ配置と型を意識した構造体。
• 一番遅かったのは、メモリ配置も型も意識しなかった構造体。

まとめ

Swift にも メモリアライメント の概念はあった.

構造体の変数宣言順によっては 暗黙的な Padding が発生、メモリがもっとも大きい型のサイズに整列されサイズが増加していた。
ただの変数にも暗黙的な Padding が起きていた.ただしこちらは常に8バイトだった。

メモリが増加したことによりデータアクセス速度低下を抑制したかどうかは、判断できなかった。
しかし、暗黙的な Padding が発生したことによるメモリ増加が原因で、扱うメモリ量が増えて、パフォーマンスに影響した。

構造体のアライメントが可変な理由

ただの変数には常に8バイト整列なのに対し、構造体がもっとも大きい型のサイズで整列している理由は、MemoryLayoutのコメントにヒントがあった。

T may have a lower minimal alignment that trades runtime performance for space efficiency.
T は、スペース効率のためにランタイム性能を犠牲にするより低い最小配列を有するかもしれない。 by Google翻訳

メモリ効率のチャンスがあれば、速度を犠牲にして、メモリ効率を選んでいるようですね。

考察

構造体の変数宣言の順番をメモリ意識することで、パフォーマンスに影響が出ることが分かった。
特に構造体のアライメントサイズを抑えることができれば、ストライド値を抑えやすくなり、構造体サイズを小さくできそうだ。

だが、アライメントサイズを抑える、つまり Int(8バイト) を使わず Int32(4バイト) を使いかつ、String(8バイト) を使わない構造体に限定されるため、現場レベルにおいては、実践的なテクニックとは言い難い。

おそらく効果が少なからず期待できるのは、ライブラリレベルやDBテーブルのModelにおいて、構造体の変数宣言の順番を意識する程度になりそうだ。
しかし、メモリサイズが大きくなりがちな構造体 ＆ メモリコピーが何度も発生しそうな処理というのは、そもそも構造体を選択したことが間違っている可能性もある。
そうなると、ほとんどのケースにおいては意識する必要はなさそうだ。

もし意識することと言えば、クリティカルな処理においてパフォーマンス低下が課題の場合、仮説３．の構造体を使わないメモリアクセスを意識すると、少しは貢献できる可能性もありそうだ。

参考URL

アライメントとは何か
http://www5d.biglobe.ne.jp/~noocyte/Programming/Alignment.html
http://www5d.biglobe.ne.jp/~noocyte/Programming/Alignment.html#WhatIsAlignment

今回使ったソース

今回調査したときに書いたコードは、下記にあげております。
ただし、散らかっております。
https://github.com/mothule/ResearchMemoryAlign