[Swift] Swiftにおける文字列処理の最適化テクニック
はじめに
この記事では、Swiftの String に関連した処理の最適化手法について、String の内部処理方法についての「解説」パート、実際のコード例を記載した「実装」の２パートに分けて解説します。
参考資料はこちらになります。
解説
Copy-on-Write
Swiftの文字列は値型として扱われている一方で、データをバッファに保存する際には、メモリ最適化手法の1つである"copy-on-write"が採用されています。"copy-on-write"では、以下のコードのように、文字列をコピーしてもすぐにメモリが複製されるのではなく、同じバッファへの新たな参照が作成され、コピーされた文字列に変更があって初めて、実際のコピーが作成されます。これにより、変更のない文字列を渡す際には、メモリの使用量を削減することができます。
var originalString: String = "Original" // メモリ上のオリジナル文字列
var copiedString: String = originalString // 新たなメモリは割り当てられず、両方とも同じバッファを参照
// 文字列が変更されると、新しいバッファが作成され、以降はメモリを共有しなくなる
copiedString.append("new string")
Lazy Copying: O(n) Cost
続いて、実際に文字列に変更を行った際に、どのような処理が行われるのかについてです。元々の文字列バッファへの参照がある状態で、コピーした文字列の変更を行うと、Swift は以下の処理を行います。
- 新しいメモリの確保
- 元々の文字列バッファの全文字のコピー
- 変更内容の適用
これらの処理は、「文字列の最初の変更時」、または「バッファの容量が不足した場合」に適用されるため、それらが起こった際には元々の文字列の長さに比例したコストがかかりますが、コピーがすでに完了している場合には、効率的に文字の追加を行うことができます。
var longString: String = String(repeating: "a", count: 1_000_000)
var copiedString: String = longString
copiedString.append("!") // 最初の変更は文字列の長さに比例するコスト (O(n))
copiedString.append("?") // コピー後の追加の変更は軽量 (O(1))
Buffer Growth Strategy
上のセクションで触れた、「バッファの容量が不足した場合」についてです。Swiftの文字列バッファは指数関数的に容量を拡大するパターンを採用しており、再割り当て時にはO(n)のコストがかかりますが、多数のappend操作を行った場合では、平均的なコストは一定 (O(1)) となります。
例えば、指数関数的な容量の増加には、以下のようなパターンが考えられます：
- 初期容量：0
- 1文字追加後：容量が16に拡大
- 17文字追加後：容量が32に拡大
- 33文字追加後：容量が64に拡大… など
実装
ここまでの情報を踏まえると、事前に一定量のバッファを確保したり、map や joined() などの手法で文字列を生成することにより、複数回の再割り当てを防ぎ、文字列操作のパフォーマンスを向上させることができます。
悪い例
var result = ""
for i in 1...1000 {
// + 演算子が、左右の文字列を結合し新しいインスタンスを作るため、
// 元の文字列のバッファを再利用せず、再割り当てが発生
result = result + String(i)
}
良い例
// 事前に使用するバッファのサイズが判明している場合は、事前にバッファを確保することで、バッファの再割り当てを防ぐことができる
var preallocatedString = ""
preallocatedString.reserveCapacity(1000) // バッファを事前に確保して効率化
for i in 1...1000 {
preallocatedString.append("a")
}
// Or
// mapを使用して再割り当てを回避
let result = (1...1000).map(String.init).joined()
まとめ
不必要な文字列の変更、コピーをループ内で行うと、再割り当てが複数回発生し、パフォーマンスに悪影響を及ぼします。そのため、事前にバッファの容量を確保するか、もしくは map や joined() などの手法で効率的に文字列を生成するのが良いでしょう。
Discussion