3 年 ago

韵, 科

2 minutes

この記事について

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

はじめに

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

この記事について

目次

はじめに

結論

実装について

パフォーマンスについて

まとめ

最後に

参考文献