この記事について

appned()の裏側の実装、またパフォーマンスについての調査です

目次

1.はじめに
 2.結論
 3.実装について
 4.パフォーマンスについて
 5.まとめ
 6.最後に

はじめに

golangにはappend()という関数があります

package main

import "fmt"

func main(){
	x := []int{1,2,3}
	fmt.Println(x) // x = [1,2,3]

	x = append(x, 4)
	fmt.Println(x) // x = [1,2,3,4]
}

上記の例のようにappend()は
スライスに要素を付け加える関数 です

しかしそんな都合よく 可変長配列 (実行時に長さが決定される配列) のようなものがあるのでしょうか......
(C言語を触りすぎて疑いの目👀)

見た目は可変長配列のような動きをしていますが
裏側の実装 はどうなっているのでしょう

また、パフォーマンス的には固定長配列と比べて どうなのでしょうか

ということで調査していきます！！⛑️

結論

さきに結論を
そんな 都合よくはありませんでした ...

裏側の処理でうまいこと可変長配列のようなものを実装していました
実際は 固定長配列 です

実装について

ソースコードにしっかりと書いてありました

// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
//	slice = append(slice, elem1, elem2)
//	slice = append(slice, anotherSlice...)
// As a special case, it is legal to append a string to a byte slice, like this:
//	slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type

append 組み込み関数は、スライスの末尾に要素を追加する。

もし、十分な容量がある場合は、新しい要素を収容するためにスライスされます。
新しい要素に対応するように再スライスされます。

十分な容量がない場合は、新しい配列が確保されます。

(以下略)

つまりappend()し続けて割り当てられたサイズを 使い果たした場合 、
新たにメモリを確保しそこにスライスの内容をコピーするわけです

ちなみに古い配列にアクセスするスライスや変数がなくなったら
自動でメモリを解放してくれるみたいです（なんてこった）

パフォーマンスについて

続いて、メモリが確保されている様子を確認してみましょう

package main

import "fmt"

func main() {
	x := []int{}
	for i := 1; i < 10; i++ {
		x = append(x, i)
		fmt.Printf("[Size = %d] Capacity = %d \n", i, cap(x))
	}
}

実行結果は以下になります

$ go run .
[Size = 1] Capacity = 1
[Size = 2] Capacity = 2
[Size = 3] Capacity = 4
[Size = 4] Capacity = 4
[Size = 5] Capacity = 8
[Size = 6] Capacity = 8
[Size = 7] Capacity = 8
[Size = 8] Capacity = 8
[Size = 9] Capacity = 16

Size が 配列のサイズ
Capacity が 最大容量 になります

サイズを使い果たしたタイミングで、新たにメモリを確保 していますね

では以下のコードで どのタイミングでメモリのサイズが更新されるか 確認します

package main

import "fmt"

func main() {
	x := []int{}
	preCap := cap(x)
	for i := 1; i < 10000; i++ {
		x = append(x, i)
		if preCap != cap(x) {
			fmt.Printf("[Size = %d] Capacity = %d \n", i, cap(x))
			preCap = cap(x)
		}
	}
}

実行結果は以下になります

$ go run .
[Size = 1] Capacity = 1 
[Size = 2] Capacity = 2       
[Size = 3] Capacity = 4       
[Size = 5] Capacity = 8       
[Size = 9] Capacity = 16      
[Size = 17] Capacity = 32     
[Size = 33] Capacity = 64     
[Size = 65] Capacity = 128    
[Size = 129] Capacity = 256   
[Size = 257] Capacity = 512   
[Size = 513] Capacity = 1024  
[Size = 1025] Capacity = 1280 
[Size = 1281] Capacity = 1696 
[Size = 1697] Capacity = 2304 
[Size = 2305] Capacity = 3072 
[Size = 3073] Capacity = 4096 
[Size = 4097] Capacity = 5120
[Size = 5121] Capacity = 7168
[Size = 7169] Capacity = 9216
[Size = 9217] Capacity = 12288

GOの処理系では1024までは 2倍ずつメモリを確保する ようですが
それ以降は 1280、1696、2304 ... と上記のように確保するようです

メモリを確保するコスト と メモリの再確保、コピーのバランス をとり、
上記のような確保の仕方をするようです

version 1.18 からは「256 未満は2倍、それ以降は 1.25倍+定数」になるそうです！
( 追記 2022/5/5　ご指摘いただきました、ありがとうございます）

ここまでの説明より

必要な要素数や最大量などが事前にわかっている場合 はmake() を使ってサイズを指定し、
メモリ確保したほうが パフォーマンスが上がる と考えられます

以下は make() の使用例です

makeの引数は
make(型, 長さ, 最大容量)
となっています

// sizeが1000のスライスを用意
// len = 1000
// cap = 1000
s1 := make([]int, 1000)

// 最大容量1000のスライスを用意
// len = 0
// cap = 1000
s2 := make([]int, 0, 1000)

事前に容量を設定しておくことで
メモリが確保、またコピーされる回数が減ります

まとめ

本記事では append()の裏側の実装とパフォーマンスについて調査してみました

便利な append() ですが、場合によってはコピーやメモリ確保により
パフォーマンスを下げる原因 になるかもしれません

あらかじめサイズがわかっている場合は make() を使っていきましょう

最後に

最後まで読んでいただきありがとうございました

ほかの言語の append() も同じような実装なのかな??

@Nabetani 様が関連記事を書いてくださいました！ありがとうございます。
「可変長配列に要素を追加する処理の色々」

もし間違いなどあれば、お手数おかけしますが
@sino0042900までご連絡お願いいたします 🙇

参考文献

実用 Go言語 ―システム開発の現場で知っておきたいアドバイス

Go builtin