10.002.Stack safety - MCJE-Tech-Community/Datapack-WIki GitHub Wiki
📚 スタック安全性
スタックとは
スタックとは最後に入れた要素が最初に取り出されるようなデータ構造です。 要素を追加する操作はプッシュ、取り出す操作はポップと呼ばれます。
スタック安全性とは
スタック安全性とは、関数を実行する際に定数サイズのスタック領域しか使わないという性質です。 関数の実行に用いられるスタックは動的配列によって実装されているため、スタック領域が不足する度に新しい領域の確保と現在のスタックに入っている全てのコマンドのコピーが必要になります。 また、スタック安全ではない場合、関数の実行中にスタックの底にコマンドオブジェクトが溜まっていくため、これらのオブジェクトのメモリ解放が遅れるということが考えられます。 そのため、スタック安全な関数の方が効率良く実行できることが期待されます。
具体例を見てみましょう。
以下の2つの関数はどちらも1以上のスコアnの分だけhelloを出力する関数です。
#> a.mcfunction
scoreboard players remove n _ 1
execute if score n _ matches 1.. run function a
say hello
#> b.mcfunction
say hello
scoreboard players remove n _ 1
execute if score n _ matches 1.. run function b
関数aはスタック安全ではない一方、関数bはスタック安全です。
上のように再帰する関数がスタック安全であるためには、再帰呼び出しが関数内の最後のコマンドである必要があります。
この違いを理解するために、関数がどのように実行されるのか見てみましょう。
スコアnの値を3として関数aを実行し、実行中のスタックの状態を追ってみましょう。
まず、関数aのコマンドが後ろからスタックにプッシュされ、以下のような状態になります。
# スタックの底
say hello
execute if score n _ matches 1.. run function a
scoreboard players remove n _ 1
# スタックの頂上
全てのコマンドをプッシュし終えると、スタックからコマンドが1つずつポップされて実行されます。
# スタックの底
say hello
execute if score n _ matches 1.. run function a
# スタックの頂上
# ↓ ポップして実行
scoreboard players remove n _ 1
# スタックの底
say hello
# スタックの頂上
# ↓ ポップして実行
execute if score n _ matches 1.. run function a
nは2なので再びfunction aが実行され、関数aのコマンドが後ろからスタックにプッシュされ、以下のような状態になります。
# スタックの底
say hello
say hello
execute if score n _ matches 1.. run function a
scoreboard players remove n _ 1
# スタックの頂上
続けて実行していきましょう。
# スタックの底
say hello
say hello
execute if score n _ matches 1.. run function a
# スタックの頂上
# ↓ ポップして実行
scoreboard players remove n _ 1
# スタックの底
say hello
say hello
# スタックの頂上
# ↓ ポップして実行
execute if score n _ matches 1.. run function a
nは1なので再びfunction aが実行され、関数aのコマンドが後ろからスタックにプッシュされ、以下のような状態になります。
# スタックの底
say hello
say hello
say hello
execute if score n _ matches 1.. run function a
scoreboard players remove n _ 1
# スタックの頂上
続けて実行していきましょう。
# スタックの底
say hello
say hello
say hello
execute if score n _ matches 1.. run function a
# スタックの頂上
# ↓ ポップして実行
scoreboard players remove n _ 1
# スタックの底
say hello
say hello
say hello
# スタックの頂上
# ↓ ポップして実行
execute if score n _ matches 1.. run function a
nは0なので再びfunction aが実行されることはありません。
ここでようやくスタックの底に溜まっていたsay helloの実行が開始されます。
# スタックの底
say hello
say hello
# スタックの頂上
# ↓ ポップして実行
say hello
# スタックの底
say hello
# スタックの頂上
# ↓ ポップして実行
say hello
# スタックの底
# スタックの頂上
# ↓ ポップして実行
say hello
スタックが空になったので実行終了です。 スタックサイズが最大になったのは以下の状態の時で、そのサイズは5でした。
# スタックの底
say hello
say hello
say hello
execute if score n _ matches 1.. run function a
scoreboard players remove n _ 1
# スタックの頂上
関数aを実行するためには、一般にn + 2のスタック領域が必要になります。
そのため、関数aはスタック安全ではありません。
次に、スコアnの値を3として関数bを実行し、実行中のスタックの状態を追ってみましょう。
まず、関数bのコマンドが後ろからスタックにプッシュされ、以下のような状態になります。
# スタックの底
execute if score n _ matches 1.. run function b
scoreboard players remove n _ 1
say hello
# スタックの頂上
続けて実行していきましょう。
# スタックの底
execute if score n _ matches 1.. run function b
scoreboard players remove n _ 1
# スタックの頂上
# ↓ ポップして実行
say hello
# スタックの底
execute if score n _ matches 1.. run function b
# スタックの頂上
# ↓ ポップして実行
scoreboard players remove n _ 1
# スタックの底
# スタックの頂上
# ↓ ポップして実行
execute if score n _ matches 1.. run function b
nは2なので再びfunction bが実行され、関数bのコマンドが後ろからスタックにプッシュされ、以下のような状態になります。
# スタックの底
execute if score n _ matches 1.. run function b
scoreboard players remove n _ 1
say hello
# スタックの頂上
続けて実行していきましょう。
# スタックの底
execute if score n _ matches 1.. run function b
scoreboard players remove n _ 1
# スタックの頂上
# ↓ ポップして実行
say hello
# スタックの底
execute if score n _ matches 1.. run function b
# スタックの頂上
# ↓ ポップして実行
scoreboard players remove n _ 1
# スタックの底
# スタックの頂上
# ↓ ポップして実行
execute if score n _ matches 1.. run function b
nは1なので再びfunction bが実行され、関数bのコマンドが後ろからスタックにプッシュされ、以下のような状態になります。
# スタックの底
execute if score n _ matches 1.. run function b
scoreboard players remove n _ 1
say hello
# スタックの頂上
続けて実行していきましょう。
# スタックの底
execute if score n _ matches 1.. run function b
scoreboard players remove n _ 1
# スタックの頂上
# ↓ ポップして実行
say hello
# スタックの底
execute if score n _ matches 1.. run function b
# スタックの頂上
# ↓ ポップして実行
scoreboard players remove n _ 1
# スタックの底
# スタックの頂上
# ↓ ポップして実行
execute if score n _ matches 1.. run function b
nは0なので再びfunction bが実行されることはありません。
スタックが空になったので実行終了です。 スタックサイズが最大になったのは以下の状態の時で、そのサイズは3でした。
# スタックの底
execute if score n _ matches 1.. run function b
scoreboard players remove n _ 1
say hello
# スタックの頂上
関数bを実行するためには、nの値が何であろうと3のスタック領域があれば十分です。
そのため、関数bはスタック安全です。
スタック安全な条件分岐
TODO