> Source: https://www.ymotongpoo.com/works/goblog-ja/allocation-optimizations/ # スタック上へのアロケーション [Allocating on the Stack](https://go.dev/blog/allocation-optimizations) by Keith Randall 私たちは常にGoプログラムを高速化する方法を探しています。直近の2つのリリースでは、処理速度低下の特定の原因、すなわちヒープアロケーションを緩和することに力を注いできました。Goプログラムがヒープからメモリを確保するたびに、そのアロケーションを満たすためにかなりの量のコードが実行される必要があります。加えて、ヒープアロケーションはガベージコレクタに追加の負荷をかけます。[Green Tea](/blog/greenteagc) のような最近の改良があってもなお、ガベージコレクタには依然としてかなりのオーバーヘッドが伴います。 そこで私たちは、より多くのアロケーションをヒープではなくスタック上で行う方法に取り組んできました。スタックアロケーションはかなり低コストで実行でき（場合によっては完全に無料です）、しかもガベージコレクタに負荷をかけません。スタックアロケーションはスタックフレームそのものと一緒に自動的に回収されるからです。スタックアロケーションはまた即座の再利用を可能にするため、キャッシュにも非常に優しい性質を持ちます。 ## 定数サイズのスライスのスタックアロケーション 処理すべきタスクのスライスを構築するケースを考えてみましょう。 ```go func process(c chan task) { var tasks []task for t := range c { tasks = append(tasks, t) } processAll(tasks) } ``` チャンネル `c` からタスクを取り出し、スライス `tasks` に追加する際に実行時に何が起きるかを順に見ていきましょう。 1回目のループでは `tasks` にはまだバッキングストア（実体となる配列）が存在しないため、`append` はそれを新たに確保しなければなりません。スライスが最終的にどれだけの大きさになるかがわからないため、あまり積極的なサイズにはできません。現在の実装では、サイズ1のバッキングストアを確保します。 2回目のループでは、バッキングストアはすでに存在していますが、いっぱいになっています。`append` は再び新しいバッキングストアを確保しなければならず、今度はサイズ2になります。サイズ1だった古いバッキングストアはガベージになります。 3回目のループでは、サイズ2のバッキングストアがいっぱいになっています。`append` は*またしても*新しいバッキングストアを確保しなければならず、今度はサイズ4になります。サイズ2だった古いバッキングストアはガベージになります。 4回目のループでは、サイズ4のバッキングストアにはまだ3つの要素しか入っていません。`append` は既存のバッキングストアにそのまま要素を置き、スライスの長さを増やすだけで済みます。やった、今回はアロケータの呼び出しが不要です。 5回目のループでは、サイズ4のバッキングストアがいっぱいになり、`append` は再び新しいバッキングストアを確保しなければならず、今度はサイズ8になります。 以下同様です。私たちは一般に、いっぱいになるたびにアロケーションのサイズを倍にしていくので、最終的にはほとんどの新しいタスクをアロケーションなしでスライスに追加できるようになります。しかし、スライスが小さいうちの「起動」フェーズにはかなりのオーバーヘッドがあります。この起動フェーズの間、私たちはアロケータに多くの時間を費やし、大量のガベージを生み出しますが、これはかなり無駄に思えます。そして、あなたのプログラムではスライスが実際には大きくならないということもあるでしょう。その場合、あなたが目にするのはこの起動フェーズだけかもしれません。 このコードがプログラムの本当にホットな部分であれば、これらのアロケーションをすべて回避するために、スライスを最初から大きめのサイズで始めたくなるかもしれません。 ```go func process2(c chan task) { tasks := make([]task, 0, 10) // おそらく最大でも10個程度のタスク for t := range c { tasks = append(tasks, t) } processAll(tasks) } ``` これは妥当な最適化です。決して誤りにはならず、プログラムは正しく動作し続けます。見積もりが小さすぎれば、以前と同様に `append` によるアロケーションが発生します。見積もりが大きすぎれば、いくらかメモリを無駄にします。 タスクの個数の見積もりが的確であれば、このプログラムにはアロケーション箇所が1つしかなくなります。`make` の呼び出しが正しいサイズのスライスバッキングストアを確保し、`append` は再アロケーションを一切行う必要がなくなります。 驚くべきことに、このコードをチャンネル内の要素数10でベンチマークすると、アロケーション回数が1回に減ったのではなく、0回に減っていることがわかります。 理由は、コンパイラがバッキングストアをスタック上に確保することを決めたからです。必要なサイズ（`task` のサイズの10倍）がわかっているため、ヒープではなく `process2` のスタックフレーム内にその領域を確保できるのです（注1）。なお、これはバッキングストアが `processAll` の内部で[ヒープにエスケープ](/doc/gc-guide#Escape_analysis)しないという事実に依存しています。 ## 可変サイズのスライスのスタックアロケーション しかしもちろん、見積もりのサイズをハードコードするのは少し硬直的です。推定の長さを引数として渡せるようにしてはどうでしょうか。 ```go func process3(c chan task, lengthGuess int) { tasks := make([]task, 0, lengthGuess) for t := range c { tasks = append(tasks, t) } processAll(tasks) } ``` こうすることで、呼び出し元が `tasks` スライスに適したサイズを選べるようになります。このサイズは、このコードがどこから呼び出されるかによって変わってくることでしょう。 残念ながら、Go 1.24ではバッキングストアのサイズが定数でなくなるため、コンパイラはもはやバッキングストアをスタック上に確保できません。結局はヒープ上に置かれることになり、私たちの0アロケーションのコードは1アロケーションのコードに変わってしまいます。`append` にすべての中間アロケーションをやらせるよりはましですが、残念な結果です。 しかし心配は無用です。Go 1.25の登場です！ 見積もりが小さい場合にのみスタックアロケーションを得るために、次のようにすることを考えてみましょう。 ```go func process4(c chan task, lengthGuess int) { var tasks []task if lengthGuess <= 10 { tasks = make([]task, 0, 10) } else { tasks = make([]task, 0, lengthGuess) } for t := range c { tasks = append(tasks, t) } processAll(tasks) } ``` 多少不格好ですが、これでうまくいくでしょう。見積もりが小さい場合は定数サイズの `make` を使うことでスタックに確保されたバッキングストアになり、見積もりが大きい場合は可変サイズの `make` を使うことでヒープからバッキングストアを確保することになります。 しかしGo 1.25では、このような不格好な道を進む必要はありません。Go 1.25のコンパイラがこの変換を自動的に行ってくれるのです。特定のスライスアロケーション箇所において、コンパイラは自動的に小さな（現在は32バイトの）スライスバッキングストアを確保し、要求されたサイズが十分小さければ、そのバッキングストアを `make` の結果として使用します。そうでなければ、通常どおりヒープアロケーションを使用します。 Go 1.25では、`lengthGuess` がその長さのスライスが32バイトに収まるほど十分小さければ、`process3` はヒープアロケーションをゼロにできます（もちろん、その `lengthGuess` が `c` に含まれる要素数についての正しい見積もりである場合に限りますが）。 私たちは常にGoのパフォーマンスを改善し続けています。ですから最新のGoリリースにアップグレードして、あなたのプログラムがどれだけ高速に、メモリ効率良くなるか[驚いてみてください](https://youtu.be/FUm0pfgWehI?si=QRTt_JYwr-cRHDNJ&t=960)！ ## appendによって確保されるスライスのスタックアロケーション とはいえ、この奇妙な長さの見積もりを追加するためにAPIを変更したくはないでしょう。他に何かできることはあるでしょうか？ Go 1.26へアップグレードしましょう！ ```go func process(c chan task) { var tasks []task for t := range c { tasks = append(tasks, t) } processAll(tasks) } ``` Go 1.26では、同じような小さな投機的バッキングストアをスタック上に確保しますが、今度はそれを `append` の呼び出し箇所で直接使用できるようになりました。 1回目のループでは `tasks` にはまだバッキングストアが存在しないため、`append` は最初のアロケーションとして小さなスタック確保のバッキングストアを使用します。たとえばそのバッキングストアに `task` を4つ収められるとすると、最初の `append` はスタックから長さ4のバッキングストアを確保します。 続く3回のループはスタック上のバッキングストアに直接追加するので、アロケーションは不要です。 4回目のイテレーションでついにスタック上のバッキングストアがいっぱいになり、追加のバッキングストアを求めてヒープに頼らざるを得なくなります。しかし、この記事の前半で説明した起動時のオーバーヘッドはほぼすべて回避できています。サイズ1、2、4のヒープアロケーションは発生せず、それらが最終的にガベージになることもありません。スライスが小さければ、ヒープアロケーションが一度も発生しないこともあるでしょう。 ## エスケープするスライスのスタックアロケーション さて、ここまでは `tasks` スライスがエスケープしない場合の話でした。しかし、もしそのスライスを返り値として返す場合はどうでしょうか？その場合はスタック上に確保できないのでは、と思うかもしれません。 その通りです！ 以下の `extract` が返すスライスのバッキングストアはスタック上に確保できません。なぜなら `extract` が返る際に `extract` のスタックフレームは消えてしまうからです。 ```go func extract(c chan task) []task { var tasks []task for t := range c { tasks = append(tasks, t) } return tasks } ``` しかし、こう考えることもできます。*返り値の*スライスはスタックに確保できないとしても、途中でガベージになるだけの中間スライスについてはどうでしょうか？それらならスタックに確保できるのではないでしょうか。 ```go func extract2(c chan task) []task { var tasks []task for t := range c { tasks = append(tasks, t) } tasks2 := make([]task, len(tasks)) copy(tasks2, tasks) return tasks2 } ``` こうすれば `tasks` スライスは `extract2` の外にエスケープすることは決してありません。これまで説明してきたすべての最適化の恩恵を受けられます。そして `extract2` の最後で、スライスの最終的なサイズがわかった時点で、必要なサイズのヒープアロケーションを1回だけ行い、そこに `task` をコピーして、そのコピーを返します。 しかし、本当にこれだけの追加コードを書きたいでしょうか？ミスを誘発しそうです。この変換をコンパイラがやってくれないものでしょうか？ Go 1.26では、それが可能になりました！ エスケープするスライスに対して、コンパイラは元の `extract` のコードを次のようなものに変換します。 ```go func extract3(c chan task) []task { var tasks []task for t := range c { tasks = append(tasks, t) } tasks = runtime.move2heap(tasks) return tasks } ``` `runtime.move2heap` はコンパイラとランタイムが連携する特殊な関数で、すでにヒープに確保されているスライスに対しては恒等関数として振る舞います。スタック上にあるスライスに対しては、ヒープ上に新しいスライスを確保し、スタック上のスライスをそのヒープ側のコピーへコピーしたうえで、そのヒープ側のコピーを返します。 これにより、元の `extract` のコードでは、要素数が小さなスタック確保のバッファに収まる場合、正確に必要なサイズのアロケーションをちょうど1回だけ行うことになります。要素数が小さなスタック確保のバッファの容量を超える場合は、そのバッファがあふれた時点から通常通りの倍加方式のアロケーションを行います。 Go 1.26が行うこの最適化は、実は手動で最適化したコードよりも優れています。なぜなら、手動最適化コードが最後に必ず行っている余分なアロケーション+コピーが不要になるからです。アロケーション+コピーが必要になるのは、返り値を返す時点までスタック上のスライスだけを操作していた場合に限られます。 コピーのコストは確かに発生しますが、そのコストは起動フェーズで行う必要がなくなったコピーによってほぼ完全に相殺されます（実のところ、新しい方式は最悪の場合でも旧方式よりコピーする要素が1つ多くなるだけです）。 ## まとめ 手動での最適化は、特にスライスサイズについて事前によい見積もりがある場合には、依然として有益であり得ます。しかしこれで、コンパイラが多くの単純なケースを代わりに拾ってくれるようになり、開発者は本当に重要な残りのケースに集中できるようになるはずです。 これらの最適化をすべて正しく機能させるために、コンパイラが保証しなければならない詳細は数多くあります。もしこれらの最適化のいずれかが正当性の問題や（悪い方向への）パフォーマンスの問題を引き起こしていると思われる場合は、`-gcflags=all=-d=variablemakehash=n` を指定することでオフにできます。これらの最適化をオフにすることで問題が解決する場合は、私たちが調査できるよう[イシューを報告してください](/issue/new)。 ## 脚注 （注1） Goのスタックには、動的サイズのスタックフレームのための `alloca` のような仕組みは一切ありません。Goのスタックフレームはすべて固定サイズです。 By Keith Randall