LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

この記事誰得？ 私しか得しないニッチな技術で記事投稿！
Qiita Engineer Festa20242024年7月17日まで開催中！
@warawara28(Yuki Kogawara)

Goでメモリアロケータを実装&ベンチマークで比較してみた

Last updated at Posted at 2024-07-15

はじめに

警告
以下の記事、実装はあくまで検証用です。

Go 1.20 で 標準パッケージの実験的なものとして、 arena パッケージが提供されました。
Goのメモリ管理 / Memory management in Go - Speaker Deck のスライドを見ていて、メモリ割り当てサイズにより割り当て速度がどのように変化するのか、またメモリアロケータを実装して速度を改善することができるのかと思い今回の検証を試してみることにしました。

TL;DR

  • Goにおいて、ほとんどの通常用途ではメモリ管理の実装は不要。
  • 今回の検証においては、1MB近いデータを確保する場合は、自作メモリアロケータ(TLSF)の方が約25倍ほど高速。
    • ただし、unsafe.Pointerを扱わなくてはいけないため、メモリ管理のコストを払う必要がある

検証イメージ

アプリケーションから見た時のメモリ割り当て元の関係性を図にしてみました。

tlsf.png

今回は、一定サイズのバイトスライスの割り当てに関して、以下の3パターンで検証を行います。

  • make を使った割り当て (標準割り当てと呼びます)
  • arena.MakeSlice を使った割り当て
  • arena.Arena から arena.MakeSlice にてバイトスライスを確保して、独自実装の TLSFArena.Allocate でメモリの割り当て

TLSFとは

動的メモリ確保 - Wikipedia

2の累乗ごとのフリーリストでは、最大で50%の無駄が生じる。たとえば、65バイトのデータを格納するために、128バイトの領域を割り当てる必要があるためである。Two-Level Segregated Fit アロケータ (TLSFアロケータ、「2レベル分離適合割り当て器」) は、2のべき乗の分類の下に、さらに細かい分類を行なうことでメモリ利用効率を改善する。空き領域を細かく分類して管理するので、要求されたサイズに最適なブロックがないこともあるが、細分類ごとの空き領域の有無をビットマップとして保持しているので、最適なサイズのブロックを即座に見つけだせるように工夫されている[4][5]。
速度については、平均的なケースではdmallocと比べて少し遅いが、固定サイズブロック割り当ての応用であるためどのような状況でも同じ時間で動作し、最悪時間が存在しないのでリアルタイムシステムに向いている

ざっくりまとめると以下のようになります。

  • TLSF とは Two-Level Segregated Fit の頭文字
  • メモリ管理手法のひとつ、随時必要なメモリ領域の確保と解放を行なう仕組みの一種である
  • メモリサイズを2段階で細かく分類することで、要求サイズに応じてメモリ利用効率の無駄が少なく割り当てることができる
  • 最悪時間が存在しないので、メモリの割り当て速度が安定している

詳細な解説は、わかりやすい解説記事がいくつかあるので、参考記事のリンクからご覧ください。

実装(一部)

こちらの v2.4.6 を参考に、Goで実装しました。

TLSFの構造体

この構造体には以下が含まれています。

  • arena: 内部で作成した arena.Arena の保持
  • flBitmap 第1レベルのビットマップ
  • slBitmap 第2レベルのビットマップ
  • matrix 未使用ブロックのポインタ2次元配列
  • head 確保したバイト配列([]byte)の先頭ポインタ
type TLSFArena struct {
	arena *arena.Arena

	flBitmap uint32
	slBitmap [RealFLI]uint32
 
	matrix [RealFLI][MaxSLI]*FreeBlockHeader
	head uintptr
}

メモリの割り当て

メモリアロケータに使用する割り当て元のメモリ領域は arena.MakeSlice にて []byte のバイトスライスを確保します。

	a := arena.NewArena()
	tlsf := arena.New[TLSFArena](a)
	bytes := arena.MakeSlice[byte](a, int(allocationBytes), int(allocationBytes))
	tlsf.arena = a
	tlsf.head = uintptr(unsafe.Pointer(&bytes[0]))

ブロック管理ヘッダー

この構造体には以下が含まれています。

  • prevHeader 前のブロックヘッダーへのポインタ
  • blockSize ブロックサイズ + ブロック使用状況のステータス管理
    • blockSize の 0〜3ビット目：
      • blockSize の 0ビット目： 対象のブロックが使用済みかどうか表す
      • blockSize の 1ビット目： 前のブロックが使用済みかどうか表す
      • blockSize の 2〜3ビット目： 未使用(0)
    • blockSize の 4ビット目以降： ブロックのバイト数

確保したメモリ、使用できるメモリはすべてブロックで管理されており、確保したブロックのサイズやブロックのステータスは blockSize に格納されています。
blockSize の 0~3ビット目の4ビット目をサイズとして使用していないのは、16バイト単位(4ビット)でブロックの割り当てを行うため、割り当てサイズは必ず16バイトの割り当てになるためです。
(例: 460バイトの領域を確保しようとすると、切り上げて464バイトを確保する)

// BlockHeader .
type BlockHeader struct {
	prevHeader *BlockHeader
	blockSize  blockStatus
}

// UsedBlockHeader .
type UsedBlockHeader struct {
	BlockHeader
	ptr uintptr // actual data
}

// FreeBlockHeader .
type FreeBlockHeader struct {
	BlockHeader
	prev *FreeBlockHeader // previous unused block header
	next *FreeBlockHeader // next unused block header
}

元の実装では、未使用のブロックを管理するヘッダを Cの共用体(union) を用いて以下のように表現されています。

  • 未使用のブロックは prev_hdr + size + ptr.free_ptr の構造体として使用
  • 使用中のブロックは prev_hdr + size + ptr.buffer の構造体として使用
typedef struct free_ptr_struct {
    struct bhdr_struct *prev;
    struct bhdr_struct *next;
} free_ptr_t;

typedef struct bhdr_struct {
    /* This pointer is just valid if the first bit of size is set */
    struct bhdr_struct *prev_hdr;
    /* The size is stored in bytes */
    size_t size;                /* bit 0 indicates whether the block is used and */
    /* bit 1 allows to know whether the previous block is free */
    union {
        struct free_ptr_struct free_ptr;
        u8_t buffer[1];         /*sizeof(struct free_ptr_struct)]; */
    } ptr;
} bhdr_t;

Goに共用体はありません。
そのため、Embedding と unsafe.Pointer を利用して、実現しています。
メモリのアラインメントなどを意識する必要があり、非常に危険な実装となっております。

// UsedBlockHeader .
type UsedBlockHeader struct {
	BlockHeader
	ptr uintptr // actual data
}

// FreeBlockHeader .
type FreeBlockHeader struct {
	BlockHeader
	prev *FreeBlockHeader // previous unused block header
	next *FreeBlockHeader // next unused block header
}

全ての実装を紹介すると、それで記事が終わってしまうのであとはソースコードをご覧下さい。

ベンチマーク

ベンチマークは 1KB/10KB/100KB/500KBのメモリ領域を1000回ずつ割り当てを行い、結果を確認します。
arena パッケージを利用するため、 -tags goexperiment.arenas または、 GOEXPERIMENT=arenas を使用します。
ベンチマークの環境に結果が強く依存しますので、あくまで参考結果としてご覧ください。

go test -bench . -benchmem -benchtime=1000x -cpu=1 -tags goexperiment.arenas

確認環境は以下になります。

  • MacBook Pro (13-inch, M1, 2022)
  • macOS Sonoma 14.5（23F79）
  • CPU Apple M2 8-Core / Memory 24GB
  • go1.22.5 darwin/arm64

ベンチマークの結果

  • 1KB程度の小さいバイト配列の確保は、Arenaが最速だった。ただし何度か動かしているとGoのランタイムによる確保(make)のほうが早いこともあり安定しない
  • TLSFによる実装は割り当て容量に依存せず、割り当て時間が安定している
  • このケースだと100KB以上は自作メモリアロケータ(TLSF)の方が高速、標準の割り当てと Arena による割り当ては割り当て容量に応じて性能が悪化

benchmark_results.png

goos: darwin
goarch: arm64
pkg: tlsf
BenchmarkSlice_NoArena/testBytes=1024         	    1000	       198.5 ns/op	    1024 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=10240        	    1000	       812.9 ns/op	   10240 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=102400       	    1000	      8322 ns/op	  106496 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=512000       	    1000	     15390 ns/op	  516096 B/op	       1 allocs/op
BenchmarkSlice_Arena/testBytes=1024           	    1000	        17.88 ns/op	       0 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=10240          	    1000	       964.9 ns/op	    8257 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=102400         	    1000	     24132 ns/op	   99090 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=512000         	    1000	    129998 ns/op	  520224 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=1024       	    1000	       461.4 ns/op	 1024000 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=10240      	    1000	       806.0 ns/op	 1024000 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=102400     	    1000	       270.5 ns/op	 1024000 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=512000     	    1000	       598.8 ns/op	 1024000 B/op	       0 allocs/op
PASS
ok  	tlsf	0.625s

別環境でのベンチマーク

参考までに、 linux/amd64 環境でのテスト結果も載せておきます。
上記とあまり違いはありません。
Github Actionsでベンチマークした結果をグラフにしています。

benchmark_results_amd64.png

goos: linux
goarch: amd64
pkg: tlsf
cpu: AMD EPYC 7763 64-Core Processor                
BenchmarkSlice_NoArena/testBytes=1024         	    1000	       101.2 ns/op	    1024 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=10240        	    1000	       820.2 ns/op	   10240 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=102400       	    1000	      6242 ns/op	  106496 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=512000       	    1000	     19558 ns/op	  516096 B/op	       1 allocs/op
BenchmarkSlice_Arena/testBytes=1024           	    1000	        13.34 ns/op	       0 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=10240          	    1000	       608.6 ns/op	    8257 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=102400         	    1000	     10240 ns/op	   99090 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=512000         	    1000	     48764 ns/op	  520224 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=1024       	    1000	       872.0 ns/op	 1024000 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=10240      	    1000	       823.8 ns/op	 1024000 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=102400     	    1000	       816.3 ns/op	 1024000 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=512000     	    1000	       785.7 ns/op	 1024000 B/op	       0 allocs/op
PASS
ok  	tlsf	0.206s

割り当て回数を減らしてベンチマーク

割り当て回数を減らすと、標準割り当てと Arena のほうが早い結果となりました。
割り当て回数が少ない場合は、標準割り当てで良いですね。

--- a/scripts/generate-plot.sh
+++ b/scripts/generate-plot.sh
@@ -1,6 +1,6 @@
 #!/bin/sh -eu
 
-BENCHMARK_SCRIPT="go test -bench  . -benchmem -benchtime=1000x -cpu=1 -tags goexperiment.arenas"
+BENCHMARK_SCRIPT="go test -bench  . -benchmem -benchtime=10x -cpu=1 -tags goexperiment.arenas"

benchmark_results_10.png

goos: darwin
goarch: arm64
pkg: tlsf
BenchmarkSlice_NoArena/testBytes=1024         	      10	       766.7 ns/op	    1024 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=10240        	      10	       904.2 ns/op	   10240 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=102400       	      10	      4342 ns/op	  106496 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=512000       	      10	     19296 ns/op	  516096 B/op	       1 allocs/op
BenchmarkSlice_Arena/testBytes=1024           	      10	       858.3 ns/op	       5 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=10240          	      10	      1533 ns/op	       5 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=102400         	      10	       691.7 ns/op	       5 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=512000         	      10	       675.0 ns/op	       5 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=1024       	      10	    839450 ns/op	102400006 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=10240      	      10	    572800 ns/op	102400006 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=102400     	      10	     21358 ns/op	102400006 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=512000     	      10	     22312 ns/op	102400006 B/op	       0 allocs/op
PASS
ok  	tlsf	0.654s

割り当て回数を増やしてベンチマーク

1KB/10KB に絞って割り当て回数を1000万回にしてベンチマークを実行してみました。
結果はTLSFのほうがどちらも早い結果とはなりましたが、標準割り当てでも十分早いかなと思いました。

--- a/scripts/generate-plot.sh
+++ b/scripts/generate-plot.sh
@@ -1,6 +1,6 @@
 #!/bin/sh -eu
 
-BENCHMARK_SCRIPT="go test -bench  . -benchmem -benchtime=1000x -cpu=1 -tags goexperiment.arenas"
+BENCHMARK_SCRIPT="go test -bench  . -benchmem -benchtime=10000000x -cpu=1 -tags goexperiment.arenas"

--- a/tlsf_test.go
+++ b/tlsf_test.go
@@ -7,10 +7,10 @@ import (
 )
 
 var testCases = []int{
-       1_024,   /*1KB*/
-       10_240,  /*10KB*/
-       102_400, /*100KB*/
-       512_000, /*500KB*/
+       1_024,  /*1KB*/
+       10_240, /*10KB*/
+       // 102_400, /*100KB*/
+       // 512_000, /*500KB*/
}

benchmark_results.png

goos: darwin
goarch: arm64
pkg: tlsf
BenchmarkSlice_NoArena/testBytes=1024         	10000000	        83.86 ns/op	    1024 B/op	       1 allocs/op
BenchmarkSlice_NoArena/testBytes=10240        	10000000	       286.5 ns/op	   10240 B/op	       1 allocs/op
BenchmarkSlice_Arena/testBytes=1024           	10000000	       162.5 ns/op	    1023 B/op	       0 allocs/op
BenchmarkSlice_Arena/testBytes=10240          	10000000	      1245 ns/op	   10245 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=1024       	10000000	        14.28 ns/op	     102 B/op	       0 allocs/op
BenchmarkSlice_TLSFArena/testBytes=10240      	10000000	        13.14 ns/op	     102 B/op	       0 allocs/op
PASS
ok  	tlsf	18.732s

まとめ

いかがでしょうか。
実際にこのメモリアロケータの改善点や課題を以下に記載します。

  • unsafe.Pointerを避けられない
  • 32バイト環境や各OSでの動作確認や対応
  • テストコード不足
  • メモリリークのチェックや確保した領域外へのアクセス検知
    • 確保したブロックにフッターを追加して、メモリの終端の目標を設定して変更されたことを検知する など
  • 確保した領域が unsafe.Pointer なので、 []byte や string で扱いやすい関数
  • メモリアロケータの確保領域拡張や、 Allocate 関数の確保領域を変更できる関数 (realloc相当)
  • ブロックやメモリの使用状況を確認できる統計情報取得用の関数を用意する

そもそも Go でメモリアロケータの実装をするくらいなら、 別の言語で書き直すことを視野に入れた方が良さそうです。
今回の実装をすることで、メモリ割り当ての高速化について考え直すいいきっかけになりました。

最後に

今回の検証で使用した実装を公開しております。
よければ参考にしてみてください。
https://github.com/warawara28/tlsf-go

参考記事

TLSF

Arena

その他

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?