Skip to content

Instantly share code, notes, and snippets.

@koher
Created November 23, 2020 18:14
Show Gist options
  • Save koher/54f4d631684d02bd5c4005be64e6d6c3 to your computer and use it in GitHub Desktop.
Save koher/54f4d631684d02bd5c4005be64e6d6c3 to your computer and use it in GitHub Desktop.

キャパシティが増加したタイミングでバッファが作り直されている気がします

これはそうだと思います。その上で、↓のような疑問を持っています。

まず、 ArraySlice の挙動として、 popFirst した場合 startIndex がインクリメントされるだけで、各要素のインデックスは変化しません。

var a: ArraySlice<Int> = [2, 3, 5]
_ = a.popFirst()
print(a[1]) // 3
print(a[0]) // 実行時エラー

これは「 Swift の ArraySlice は元となった Array とインデックスを共有する」という仕様との整合性のためです。

let a: [Int] = [2, 3, 5]
let b: ArraySlice<Int> = a[1...]
print(b[1]) // 3
print(b[0]) // 実行時エラー

他の多くの言語では部分配列のインデックスが 0 始まりなのに対して、 Swift の ArraySlice は上記のように元となる Array とインデックスを共有します。この仕様によって、 ArraySlice の実装ではインデックスのオフセット計算を省略することも可能です(理論上 Array と同等のパフォーマンスを実現可能だと思います)。

しかし、もしバッファの作り直し時に新バッファの先頭から要素をつめなおすようにコピーする場合、バッファの先頭がインデックス 0 でなくなってしまうためインデックスのオフセット計算が必要となります。 ArraySlice のユースケースとして、バッファの作り直しが起こるようなケースは比較的まれです。そのようなケースのために常時オフセット計算を必要とする実装を採用するのではなく、バッファ作り直し時に要素を先頭から詰めず、無駄なリード領域を保持する代わりにオフセット計算を行わないような実装になっている可能性もあるのではないかと考えています。

他の方法として、参照しているバッファへのポインタとは別にオフセット分だけ前にずらしたポインタも保持しておくことでオフセット計算を省略するような実装も可能ですが、そのような実装は少しトリッキーな気がします(オフセットが大きいとポインタが 0 を超えてオーバーフローしますし)。

capacity がバッファ長を表していれば簡単なんですが、どうやら capacitystartindex からバッファ末尾までの長さを表しているらしく、仮に「無駄なリード領域を保持する」実装だったとしても capacity で見分けることはできません。

ArraySlice のソースを確認する他には、 append N 回 → popFirst M 回 → append K 回のような順で実行して、メモリ使用量を監視すれば「無駄なリード領域」が存在するかわかるかもしれませんね。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment