関連記事

本記事は Geek-Space Advent Calendar 2020 の 5 日目です。（間に合ってない）

Golang による順列列挙のパフォーマンス研究 1. 再帰を用いたやり方
Golang による順列列挙のパフォーマンス研究 2. スタックを用いたやり方（本記事）
Golang による順列列挙のパフォーマンス研究 3. 繰り上がり法（仮名）
Golang で順列・組み合わせ・重複順列・重複組み合わせの列挙

はじめに

前回、DFS には再帰を用いるやり方とスタックを用いるやり方があるということで、再帰を用いるやり方の方を探っていきました。
今回はスタックを用いるやり方について同様に探っていきます。
再帰呼び出しは言語によって重かったりとかもあると思うので、再帰を避けることでもっとパフォーマンスの良い実装が見つかるといいなぁという感じです。
前回得られた「使用可能な数字をチェックリスト式で管理した方が良さそう」「1 つの配列を全順列分使い回した方が良い」といった結論は、今回は自明になったものとして最初から導入していきます。

コードは前回同様、全てこちらのリポジトリに上げてあります。
https://github.com/ikngtty/benchmark-go-combinatorics

実装

下準備

計測環境については前回と同様なので省略。

コールスタックを再現する

「再帰呼び出し」と「スタック」の共通点を考えてみて、「そういえば再帰呼び出しはコール"スタック"を積み上げてるな…」と思い浮かびました。そこから「コールスタックもどきを自分で実装すれば再帰しなくてもいいのでは？」と思い至ったので、試してみることにします。

コールスタックについて詳しく知っているわけではないですが、積む必要がありそうな情報はおそらく、ある一つの実行中の関数呼び出しについて

各引数や変数の中身
どこまでコードを実行したか

あたりじゃないでしょうか。

ちょっと再帰の場合のコードを見てみましょう。

combinatorics/perm.go

func PermutationsRecursive6(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	pattern := make([]int, k)

	var body func(pos int)
	body = func(pos int) {
		if pos == k {
			f(pattern)
			return
		}

		for num := range checklist {
			if checklist[num] {
				continue
			}

			pattern[pos] = num
			checklist[num] = true
			body(pos + 1)
			checklist[num] = false
		}
	}
	body(0)
}

この body 関数を繰り返し呼んだ時、コールスタックには

各引数や変数の中身
- pos の中身
- num の中身
どこまでコードを実行したか
- checklist[num] = false の直前まで実行した

といった情報がどんどん積まれていくのではないかと思われます。

「どこまでコードを実行したか」の情報は今回 1 パターンしかないので、これから実装するコードスタックもどきにはこの情報は要らなそうです。
pos と num の情報だけ積んでみます。

combinatorics/perm.go

type callStackItem0 struct {
	pos          int // 順列の何桁目について扱っているか
	chosenNumber int // 順列の該当桁にどの数字を入れているか。上で言う`num`。
}

type callStack0 struct {
	last *callStack0Node
}

type callStack0Node struct {
	parent *callStack0Node
	value  *callStackItem0
}

func newCallStack0() *callStack0 {
	return &callStack0{nil}
}

func (s *callStack0) push(elem *callStackItem0) {
	node := callStack0Node{s.last, elem}
	s.last = &node
}

func (s *callStack0) pop() *callStackItem0 {
	value := s.last.value
	s.last = s.last.parent
	return value
}

func (s *callStack0) peek() *callStackItem0 {
	return s.last.value
}

func (s *callStack0) empty() bool {
	return s.last == nil
}

func PermutationsWithStack0(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	callStack := newCallStack0()
	pattern := make([]int, k)

	callStack.push(&callStackItem0{pos: 0, chosenNumber: -1})
	for !callStack.empty() {
		// この1ループ内では、このコールスタックアイテムが担当する桁について
		// 値を増やすことを試みる
		env := callStack.peek()

		// 該当桁が右端を超えている時は、完成した順列をコールバック関数に渡し、
		// この桁については終了
		if env.pos == k {
			f(pattern)

			callStack.pop()
			continue
		}

		// 該当桁についてチェックリストの使用済みチェックを外しておく
		if env.chosenNumber > -1 {
			checklist[env.chosenNumber] = false
		}

		// 値増やしチャレンジ
		willContinue := false // 大域脱出用
		for env.chosenNumber++; env.chosenNumber < n; env.chosenNumber++ {
			// 使おうとする数字が使用済みならスキップ
			if checklist[env.chosenNumber] {
				continue
			}

			// 使用可能な数字を無事見つけたケース
			// 見つけた数字で順列を書き換え
			pattern[env.pos] = env.chosenNumber
			checklist[env.chosenNumber] = true

			// 1つ右の桁担当のコールスタックアイテムを積む。再帰呼び出しに相当。
			newEnv := callStackItem0{
				pos: env.pos + 1, chosenNumber: -1,
			}
			callStack.push(&newEnv)
			willContinue = true // 大域脱出
			break
		}
		// 大域脱出
		if willContinue {
			continue
		}

		// 値を増やすのに失敗したケース
		// コールスタックを1つ掘り下げて、1つ左の桁に戻って考え直す
		callStack.pop()
	}
}

PermutationsRecursive6	 191816791 ns	        96 B	       2 allocs
PermutationsWithStack0	1004648553 ns	 315651624 B	19728208 allocs

比較対象の PermutationsRecursive6 は前回記事での優勝記録です。全然勝てない…。

「各桁に今どの数字を入れているか」の情報を、コールスタックアイテムから省く

各桁に今どの数字を入れているかは、生成中の順列を見れば分かります。

combinatorics/util.go

type IntStack struct {
	last *intStackNode
}

type intStackNode struct {
	parent *intStackNode
	value  int
}

func NewIntStack() *IntStack {
	return &IntStack{nil}
}

func (s *IntStack) Push(elem int) {
	node := intStackNode{s.last, elem}
	s.last = &node
}

func (s *IntStack) Pop() int {
	value := s.last.value
	s.last = s.last.parent
	return value
}

func (s *IntStack) Peek() int {
	return s.last.value
}

func (s *IntStack) Empty() bool {
	return s.last == nil
}

combinatorics/perm.go

func PermutationsWithStack1(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	posStack := NewIntStack() // コールスタックアイテムが`pos`のみになった
	pattern := make([]int, k)
	// 生成中の順列には、「まだちゃんと値を入れていない」という情報を
	// ちゃんと-1として埋め込む必要が出てきた
	for i := range pattern {
		pattern[i] = -1
	}

	posStack.Push(0)
	for !posStack.Empty() {
		pos := posStack.Peek()

		if pos == k {
			f(pattern)

			posStack.Pop()
			continue
		}

		chosenNumber := pattern[pos] // 生成中の順列から値取得
		if chosenNumber > -1 {
			checklist[chosenNumber] = false
		}

		willContinue := false
		for chosenNumber++; chosenNumber < n; chosenNumber++ {
			if checklist[chosenNumber] {
				continue
			}

			pattern[pos] = chosenNumber
			checklist[chosenNumber] = true

			posStack.Push(pos + 1)
			willContinue = true
			break
		}
		if willContinue {
			continue
		}

		pattern[pos] = -1 // ちゃんと-1にリセットしないといけない
		posStack.Pop()
	}
}

PermutationsRecursive6	 191816791 ns	        96 B	       2 allocs
PermutationsWithStack0	1004648553 ns	 315651624 B	19728208 allocs
PermutationsWithStack1	 572861294 ns	 157825764 B	 9864104 allocs

再帰には相変わらず勝てる気がしませんが、先の実装と比べると、やたら速くなりました。
構造体に比べて int の方が遥かに軽く扱えるということなんでしょうか。

樹形図のノードをスタックに積む

ここまでのやり方は、「for 文開始 -> ある桁の値をちょっとだけ増やす -> break（次のスタックアイテムへ） -> 戻ってきたら続きからまた for 文開始 -> ちょっとだけ増やしたらまた break」みたいな感じでした。
例えば「3 桁目に 1 を入れる -> 3 を入れる -> 4 を入れる」の場合、「for -> 1 -> break -> for -> 3 -> break -> for -> 4 -> break」という感じです。
このちまちま何度も for 文を使う感じ、なんかすごい無駄な気がします。

さて、DFS についてたとえば Wikipedia を調べてみると、どうやらスタックの使い方が違うことが分かります。
木構造の各ノードをスタックに積むのが普通みたいですね。
こっちのやり方なら、「for -> 4 をスタックに積む -> 3 をスタックに積む -> 1 をスタックに積む -> break」と一回の for 文実行でひと通り済ませることができます。
言葉で言っても分かりづらそうなので、以下が実際のコード；

combinatorics/perm.go

type patternNode2 struct {
	pos    int // 順列の何桁目か
	number int // 該当桁の数字
}

type patternNodeStack2 struct {
	last *patternNodeStack2Node
}

type patternNodeStack2Node struct {
	parent *patternNodeStack2Node
	value  *patternNode2
}

func newPatternNodeStack2() *patternNodeStack2 {
	return &patternNodeStack2{nil}
}

func (s *patternNodeStack2) push(elem *patternNode2) {
	node := patternNodeStack2Node{s.last, elem}
	s.last = &node
}

func (s *patternNodeStack2) pop() *patternNode2 {
	value := s.last.value
	s.last = s.last.parent
	return value
}

func PermutationsWithStack2(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	patternNodeStack := newPatternNodeStack2()
	pattern := make([]int, k)

	patternNodeStack.push(&patternNode2{pos: -1, number: 0})
	for !patternNodeStack.empty() {
		patternNode := patternNodeStack.pop()

		// 以前の順列のノードに関する後始末をここで行っている
		for i := patternNode.pos; i < k; i++ {
			if i > -1 && pattern[i] > -1 {
				checklist[pattern[i]] = false
				// `pattern`もリセットしておかないと`checklist`のリセット時に
				// 狂いが生じる。
				pattern[i] = -1
			}
		}

		// ノード通りに順列を書き換え
		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
			checklist[patternNode.number] = true
		}

		// 該当桁が右端の場合、完成した順列をコールバック関数に渡し、
		// この桁については終了
		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		// 1つ右の桁担当のコールスタックアイテムをひと通り積む
		for num := n - 1; num >= 0; num-- {
			if checklist[num] {
				continue
			}

			childNode := patternNode2{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack.push(&childNode)
		}
	}
}

以前は peek したり pop したりだったのが、今回はひたすら pop するだけなので、その辺も分かりやすくなったと思います。

一方で、ノードを扱った後の後始末（チェックリストのリセット）のタイミングが「次の順列についてのノードを取り扱い始めた時の最初」という歪なタイミングになってしまい、このへんは分かりづらくなりました。
「1 ノード : 1 スタックアイテム : 1 処理」が対応している形なので、ノードを一度移ってしまったらもう元のノードに帰ってくるタイミングが無く、こうなっています。

PermutationsWithStack0	1004648553 ns	 315651624 B	19728208 allocs
PermutationsWithStack1	 572861294 ns	 157825764 B	 9864104 allocs
PermutationsWithStack2	 843198178 ns	 315651816 B	19728210 allocs

パフォーマンスはまあまあですね。

ポインタではなく値でスタックアイテムを持つ

上記のコードで、各スタックアイテムは一度作ったら特に値を書き換えることなく使い捨てるようになりました。
この場合、スタックアイテムが参照（ポインタ）である必要はありません。
値にしたらパフォーマンスがどう変わるか見てみましょう。

combinatorics/perm.go

type patternNode3 struct {
	pos    int
	number int
}

type patternNodeStack3 struct {
	last *patternNodeStack3Node
}

type patternNodeStack3Node struct {
	parent *patternNodeStack3Node
	value  patternNode3 // ポインタから値になった
}

func newPatternNodeStack3() *patternNodeStack3 {
	return &patternNodeStack3{nil}
}

// 引数`elem`がポインタから値になった
func (s *patternNodeStack3) push(elem patternNode3) {
	node := patternNodeStack3Node{s.last, elem}
	s.last = &node
}

// 返り値がポインタから値になった
func (s *patternNodeStack3) pop() patternNode3 {
	value := s.last.value
	s.last = s.last.parent
	return value
}

func (s *patternNodeStack3) empty() bool {
	return s.last == nil
}

// `patternNode3`を使うようになったこと以外は、
// `PermutationsWithStack2`とほぼ同じ。
func PermutationsWithStack3(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	patternNodeStack := newPatternNodeStack3()
	pattern := make([]int, k)

	patternNodeStack.push(patternNode3{pos: -1, number: 0})
	for !patternNodeStack.empty() {
		patternNode := patternNodeStack.pop()

		for i := patternNode.pos; i < k; i++ {
			if i > -1 && pattern[i] > -1 {
				checklist[pattern[i]] = false
				pattern[i] = -1
			}
		}

		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
			checklist[patternNode.number] = true
		}

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for num := n - 1; num >= 0; num-- {
			if checklist[num] {
				continue
			}

			childNode := patternNode3{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack.push(childNode)
		}
	}
}

PermutationsWithStack1	 572861294 ns	 157825764 B	 9864104 allocs
PermutationsWithStack2	 843198178 ns	 315651816 B	19728210 allocs
PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs

結構速くなりました。

"-1桁目"から始めるのをやめる

だんだん

if patternNode.pos > -1 {
}

みたいな細かい if 文が増えてきて気持ち悪くなってきました。
どうやら -1 桁目（実際には存在せず、実装の都合で設けている）で始めているのが、今の実装と相性が悪そうです。
おとなしく 0 桁目から始めてみます。

combinatorics/perm.go

func PermutationsWithStack4(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	patternNodeStack := newPatternNodeStack3()
	pattern := make([]int, k)

	// エッヂケースとして別途処理しなきゃいけなくなった
	if k == 0 {
		f(pattern)
		return
	}

	// 0桁目のノード準備。-1桁目と違いn個分ある。
	for num := n - 1; num >= 0; num-- {
		patternNodeStack.push(patternNode3{pos: 0, number: num})
	}

	for !patternNodeStack.empty() {
		patternNode := patternNodeStack.pop()

		for i := patternNode.pos; i < k; i++ {
			if pattern[i] > -1 { // 条件減った
				checklist[pattern[i]] = false
				pattern[i] = -1
			}
		}

		// if文消えた
		pattern[patternNode.pos] = patternNode.number
		checklist[patternNode.number] = true

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for num := n - 1; num >= 0; num-- {
			if checklist[num] {
				continue
			}

			childNode := patternNode3{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack.push(childNode)
		}
	}
}

ちょっとすっきりした箇所もあればちょっと煩雑になった箇所もあり、という感じ。イマイチですね。

PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs
PermutationsWithStack4	 663686560 ns	 315651548 B	 9864106 allocs

パフォーマンスは当然大して変わらないです。

チェックリスト式から整数配列式に戻す

ノードの後始末なんてしなきゃいけないからこんなややこしいコードになるんや！
なんで後始末が必要なんや！
チェックリストを管理しなきゃいけないからや！
というわけで、ここでチェックリストをやめてみます。
使用可能な数字群の管理には、代わりに元の整数配列を使うことにします。

combinatorics/perm.go

type patternNode5 struct {
	pos    int
	number int
	rest   []int // 樹形図の該当ノードより右のノードに使える、まだ使っていない数字群
}

type patternNodeStack5 struct {
	last *patternNodeStack5Node
}

type patternNodeStack5Node struct {
	parent *patternNodeStack5Node
	// 検証の結果、構造体の要素が1つ増えた今でも参照より値の方がパフォーマンスが良かった
	// （具体的な検証結果についてはだるいので省略）
	value  patternNode5
}

func newPatternNodeStack5() *patternNodeStack5 {
	return &patternNodeStack5{nil}
}

func (s *patternNodeStack5) push(elem patternNode5) {
	node := patternNodeStack5Node{s.last, elem}
	s.last = &node
}

func (s *patternNodeStack5) pop() patternNode5 {
	value := s.last.value
	s.last = s.last.parent
	return value
}

func (s *patternNodeStack5) empty() bool {
	return s.last == nil
}

func PermutationsWithStack5(a []int, k int, f func([]int)) {
	patternNodeStack := newPatternNodeStack5()
	pattern := make([]int, k)

	patternNodeStack.push(patternNode5{pos: -1, number: 0, rest: a})
	for !patternNodeStack.empty() {
		patternNode := patternNodeStack.pop()

		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
		}

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for i := len(patternNode.rest) - 1; i >= 0; i-- {
			// i番目の項目を抜いた配列を新しく作る
			newRest := make([]int, len(patternNode.rest)-1)
			for j := 0; j < i; j++ {
				newRest[j] = patternNode.rest[j]
			}
			for j := i + 1; j < len(patternNode.rest); j++ {
				newRest[j-1] = patternNode.rest[j]
			}

			childNode := patternNode5{
				pos:    patternNode.pos + 1,
				number: patternNode.rest[i],
				rest:   newRest,
			}
			patternNodeStack.push(childNode)
		}
	}
}

ちょっとスッキリして分かりやすくなったんじゃないでしょうか。

PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs
PermutationsWithStack5	 969391196 ns	 557476872 B	16099412 allocs

代わりにパフォーマンスは悪化しました。
やはり我々はもうチェックリスト無しでは行きていけないのだ…。

生成中の順列配列から残りの使用可能な数字を判断する

チェックリストに代わる策をめげずにもう 1 つ試してみます。

combinatorics/perm.go

func PermutationsWithStack6(n, k int, f func([]int)) {
	patternNodeStack := newPatternNodeStack3()
	pattern := make([]int, k)

	patternNodeStack.push(patternNode3{pos: -1, number: 0})
	for !patternNodeStack.empty() {
		patternNode := patternNodeStack.pop()

		if patternNode.pos > -1 {
			pattern[patternNode.pos] = patternNode.number
		}

		if patternNode.pos == k-1 {
			f(pattern)
			continue
		}

		for num := n - 1; num >= 0; num-- {
			// 数字が使われていたらスキップ
			willContinue := false // 大域脱出用
			for i := 0; i <= patternNode.pos; i++ {
				if pattern[i] == num {
					willContinue = true // 大域脱出
					break
				}
			}
			// 大域脱出
			if willContinue {
				continue
			}

			childNode := patternNode3{
				pos: patternNode.pos + 1, number: num,
			}
			patternNodeStack.push(childNode)
		}
	}
}

PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs
PermutationsWithStack5	 969391196 ns	 557476872 B	16099412 allocs
PermutationsWithStack6	1170586330 ns	 315651632 B	 9864109 allocs

うん。駄目ですね。

操作内容を構造体で表してスタックに積む

ここまで問題としてきたのは、「スタックに沿って樹形図のノードを処理していくと、ノードを処理したあと（そこからもっと右に生えていくノードも全部処理したあと）の後始末をしたい時に、そのノードを表すスタックアイテムがもう無くなっているので、次のノードに移ってから無理やり前のノードについて後始末しなければいけなくなり、コードが煩雑になる」という点でした。

解決策としてここまで「後始末の必要性をなくせばいいのでは？」と取り組んできたけれども、どれもパフォーマンスを犠牲にする結果に。

今度は別の解決策として、「じゃあ後始末のためのスタックアイテムも積んでおけばいいじゃない」というのを試してみます。

この場合、スタックアイテムにはノードの情報だけでなく「通常処理をすべきか後始末をすべきか」の情報が必要になってきます。
こうなってくると、スタックアイテムが指すものはノード自体というよりも、「このノードをこうしろ」という「操作内容」の方が近いです。

combinatorics/perm.go

const (
	// 操作の種類
	operationMode7ReflectValue = iota // 通常処理1
	operationMode7ExecuteOrDelegate   // 通常処理2
	operationMode7ResetValue          // 後始末
)

type operation7 struct {
	pos    int // 該当ノードについて、順列の何桁目か
	number int // 該当ノードについて、該当桁の数字
	mode   int // 操作の種類
}

type operationStack7 struct {
	last *operationStack7Node
}

type operationStack7Node struct {
	parent *operationStack7Node
	value  operation7
}

func newOperationStack7() *operationStack7 {
	return &operationStack7{nil}
}

func (s *operationStack7) push(elem operation7) {
	node := operationStack7Node{s.last, elem}
	s.last = &node
}

func (s *operationStack7) pop() operation7 {
	value := s.last.value
	s.last = s.last.parent
	return value
}

func (s *operationStack7) empty() bool {
	return s.last == nil
}

func PermutationsWithStack7(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	operationStack := newOperationStack7()
	pattern := make([]int, k)

	operationStack.push(operation7{
		pos:    -1,
		number: 0,
		mode:   operationMode7ExecuteOrDelegate,
	})
	for !operationStack.empty() {
		operation := operationStack.pop()

		switch operation.mode {
		case operationMode7ReflectValue:
			pattern[operation.pos] = operation.number
			checklist[operation.number] = true

		case operationMode7ExecuteOrDelegate:
			if operation.pos == k-1 {
				// Execute
				f(pattern)
			} else {
				// Delegate
				for num := n - 1; num >= 0; num-- {
					if checklist[num] {
						continue
					}

					// スタックなので、先に入れた操作ほど後に実行されることに注意
					operationStack.push(operation7{
						pos:    operation.pos + 1,
						number: num,
						mode:   operationMode7ResetValue,
					})
					operationStack.push(operation7{
						pos:    operation.pos + 1,
						number: num,
						mode:   operationMode7ExecuteOrDelegate,
					})
					operationStack.push(operation7{
						pos:    operation.pos + 1,
						number: num,
						mode:   operationMode7ReflectValue,
					})
				}
			}

		case operationMode7ResetValue:
			checklist[operation.number] = false
		}
	}
}

通常処理と後始末を分けるついでに、通常処理も 2 つに分けることにより、"-1 桁目"について通常処理 1（順列への値の反映）をスキップしなければいけない部分も綺麗に書けました。
冗長な気もしますが、個人的には他のパターンより書きやすかったです。

PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs
PermutationsWithStack5	 969391196 ns	 557476872 B	16099412 allocs
PermutationsWithStack6	1170586330 ns	 315651632 B	 9864109 allocs
PermutationsWithStack7	1766143475 ns	 946954664 B	29592321 allocs

しかしパフォーマンスは悪くなる一方。

いっそ操作を関数で表してスタックに積む

操作ってそれもう関数じゃ〜ん、と思ったので、関数自体をスタックに積めないか試してみました。

combinatorics/util.go

type FuncStack struct {
	last *funcStackNode
}

type funcStackNode struct {
	parent *funcStackNode
	value  func()
}

func NewFuncStack() *FuncStack {
	return &FuncStack{nil}
}

func (s *FuncStack) Push(elem func()) {
	node := funcStackNode{s.last, elem}
	s.last = &node
}

func (s *FuncStack) Pop() func() {
	value := s.last.value
	s.last = s.last.parent
	return value
}

func (s *FuncStack) Peek() func() {
	return s.last.value
}

func (s *FuncStack) Empty() bool {
	return s.last == nil
}

combinatorics/perm.go

func PermutationsWithStack8(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	operationStack := NewFuncStack()
	pattern := make([]int, k)

	reflectValue := func(pos, number int) {
		pattern[pos] = number
		checklist[number] = true
	}
	resetValue := func(number int) {
		checklist[number] = false
	}
	// 中で再帰的に自身を呼ぶので、宣言を先に済ませる必要がある
	var executeOrDelegate func(pos int)
	executeOrDelegate = func(pos int) {
		if pos == k-1 {
			f(pattern)
			return
		}

		for num := n - 1; num >= 0; num-- {
			if checklist[num] {
				continue
			}

			// 以降で作る関数の中で`num`を直接参照してしまうと、実際にその関数が実行されて
			// `num`を使う頃には、`num`の値がもうfor文によって書き換えられてしまっている、
			// という状態になってしまう。
			// そのためループ毎に新しい変数`numFrozen`を作り、そっちに値を退避させておく必要がある。
			numFrozen := num
			operationStack.Push(func() {
				resetValue(numFrozen)
			})
			operationStack.Push(func() {
				executeOrDelegate(pos + 1)
			})
			operationStack.Push(func() {
				reflectValue(pos+1, numFrozen)
			})
		}
	}

	operationStack.Push(func() {
		executeOrDelegate(-1)
	})
	for !operationStack.Empty() {
		operation := operationStack.Pop()
		operation()
	}
}

いやもう再帰しちゃってるじゃん！

PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs
PermutationsWithStack5	 969391196 ns	 557476872 B	16099412 allocs
PermutationsWithStack6	1170586330 ns	 315651632 B	 9864109 allocs
PermutationsWithStack7	1766143475 ns	 946954664 B	29592321 allocs
PermutationsWithStack8	3088975270 ns	1420431936 B	59184625 allocs

もうだめぽ。

まとめ

ここまでの計測結果を前回の優勝結果とともに全て並べてみると、

PermutationsRecursive6	 191816791 ns	        96 B	       2 allocs
PermutationsWithStack0	1004648553 ns	 315651624 B	19728208 allocs
PermutationsWithStack1	 572861294 ns	 157825764 B	 9864104 allocs
PermutationsWithStack2	 843198178 ns	 315651816 B	19728210 allocs
PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs
PermutationsWithStack4	 663686560 ns	 315651548 B	 9864106 allocs
PermutationsWithStack5	 969391196 ns	 557476872 B	16099412 allocs
PermutationsWithStack6	1170586330 ns	 315651632 B	 9864109 allocs
PermutationsWithStack7	1766143475 ns	 946954664 B	29592321 allocs
PermutationsWithStack8	3088975270 ns	1420431936 B	59184625 allocs

このようになり、結局再帰には全然勝てませんでした。
（少なくともGo の場合は）おとなしく再帰で書いた方が良い模様。
生半可な自作スタックより、本物のコールスタックの方が色々最適化されているんですかね。

「どうしても再帰が書けないからスタックを使って書きたい！」という人は、書きやすさとパフォーマンスのトレードオフを鑑みながら、どれか好きなのを選んでください。
個人的には構造体で操作を表すやつが好きです。

と思いきや！大事な追記

「スタックをスライスで実装したらどうなるの？」というツッコミが入ったので、試してみました。

// PermutationsWithStack0のスライス使った版
func PermutationsWithSlice0(n, k int, f func([]int)) {
	checklist := make([]bool, n)
	callStack := make([]callStackItem0, 1) // スライスに変更
	pattern := make([]int, k)

	callStack[0] = callStackItem0{pos: 0, chosenNumber: -1}
	for len(callStack) > 0 {
		env := &callStack[len(callStack)-1] // peek

		if env.pos == k {
			f(pattern)

			callStack = callStack[:len(callStack)-1] // pop(discard)
			continue
		}

		if env.chosenNumber > -1 {
			checklist[env.chosenNumber] = false
		}

		willContinue := false
		for env.chosenNumber++; env.chosenNumber < n; env.chosenNumber++ {
			if checklist[env.chosenNumber] {
				continue
			}

			pattern[env.pos] = env.chosenNumber
			checklist[env.chosenNumber] = true

			newEnv := callStackItem0{
				pos: env.pos + 1, chosenNumber: -1,
			}
			callStack = append(callStack, newEnv) // push
			willContinue = true
			break
		}
		if willContinue {
			continue
		}

		callStack = callStack[:len(callStack)-1] // pop(discard)
	}
}

// PermutationsWithSlice1以降も同様なので省略。
// また、PermutationsWithSlice3はPermutationsWithSlice2と同じなので除いた。

PermutationsRecursive6	 191816791 ns	        96 B	       2 allocs
PermutationsWithStack0	1004648553 ns	 315651624 B	19728208 allocs
PermutationsWithStack1	 572861294 ns	 157825764 B	 9864104 allocs
PermutationsWithStack2	 843198178 ns	 315651816 B	19728210 allocs
PermutationsWithStack3	 648371094 ns	 315651576 B	 9864106 allocs
PermutationsWithStack4	 663686560 ns	 315651548 B	 9864106 allocs
PermutationsWithStack5	 969391196 ns	 557476872 B	16099412 allocs
PermutationsWithStack6	1170586330 ns	 315651632 B	 9864109 allocs
PermutationsWithStack7	1766143475 ns	 946954664 B	29592321 allocs
PermutationsWithStack8	3088975270 ns	1420431936 B	59184625 allocs
PermutationsWithSlice0	 234075281 ns	       576 B	       6 allocs
PermutationsWithSlice1	 184274404 ns	       336 B	       6 allocs
PermutationsWithSlice2	 186323035 ns	      2112 B	       8 allocs
PermutationsWithSlice4	 183515108 ns	      2496 B	       6 allocs
PermutationsWithSlice5	 360493641 ns	  84004413 B	 6235310 allocs
PermutationsWithSlice6	 657643570 ns	      2096 B	       7 allocs
PermutationsWithSlice7	 183175502 ns	      9504 B	       9 allocs
PermutationsWithSlice8	2023963760 ns	 946958520 B	29592322 allocs

再帰相手にも勝ちまくれるようになりました。アイヤー。

Next: Golang による順列列挙のパフォーマンス研究 3. 繰り上がり法（仮名）