malloc/free は遅いというよくある話 (C)

昔ゲームを作っているときの話、テストプレイ中ときどきガクッ・ガクッと一瞬処理落ちすることがありました。
原因は malloc の呼び出しで、通常は計測しても処理時間は 0 [ns] なのですが 100～1000 回に一度くらいの割合で 1～10 [ms] も掛かることがあったためでした。
60Hzで動くゲームなので1フレームの処理時間は 16.666 [ms] より短くなければならず、メモリ確保に 1 [ms] 以上も掛かるのは致命的です。
# 簡単に再現しようとしてみましたが、再現できませんでした。この辺の問題は解決したということでしょうか。何年も経ってるし。
同じ理由でかは知りませんが、malloc/free は遅いから、使わないようにしているとか、自作したといったインターネット上の記事はたくさんあります。
特に malloc/free を自作された方のコードを拝見すると、複雑なデータ構造を駆使して高速化を図ったり、仮想メモリとか直接触っていたりなど高い技術に頭が下がります。
ですが、特に私のようなケースでは、もっとシンプルな方法で解決できるのではないかという主張をしてみたいと思います。

当時私が書いていたコードは「細々した(短命な)メモリブロックを頻繁に確保・開放している」という特徴がありました。
エフェクトなんかが最たるもので、例えば一点から四方八方に星マークが飛び散るという(よくある)エフェクトを実装すると、最初に星の情報 (画像ハンドル、位置、速度、加速度、消滅までの時間など) を格納するための構造体用の小さなメモリを星マークの数だけ確保して、数フレーム後に消滅した際にメモリを開放する。こんなエフェクトが1フレームで何箇所も発生するといった具合です。
これを以下のような制約と仮定してみます。

殆どのメモリブロックは 10000 バイト以下である。
それらのメモリブロックは 10000 個程度しか「同時に」存在しない。

具体的な数字は仮だとしても全てのアプリケーションに適用できる制約ではありませんが、ツールレベルのプログラムであれば当てはまりそうだし当てはまるアプリケーションは意外と多いのではいかと思います。
この制約のもと速度的な問題を解消するには以下のような実装で良いはずです。
　
　
仮に malloc 等をラップした以下のようなモジュールがあるとします。

MYLIB_malloc.h

#pragma once

#include <malloc.h>

void *MYLIB_malloc(size_t size);
void *MYLIB_realloc(void *ptr, size_t size);
void MYLIB_free(void *ptr);

MYLIB_malloc.c　　(実装 M1)

#include "MYLIB_malloc.h"

void *MYLIB_malloc(size_t size)
{
	return malloc(size);
}
void *MYLIB_realloc(void *ptr, size_t size)
{
	return realloc(ptr, size);
}
void MYLIB_free(void *ptr)
{
	free(ptr);
}

これを以下のとおり実装しなおします。

MYLIB_malloc.c　　(実装 M2)

#include <stddef.h>
#include "MYLIB_malloc.h"

#define BLOCK_NUM  10000
#define BLOCK_SIZE 10000 // mallocと同じアライメントの倍数であること。

static char Linear[BLOCK_NUM * BLOCK_SIZE];
static void *Blocks[BLOCK_NUM];
static size_t BlockCount = BLOCK_NUM;

#define IsLinearBlock(ptr) \
	(Linear <= (ptr) && (ptr) < Linear + sizeof(Linear))

static void InitBlocks(void)
{
	size_t index;

	for(index = 0; index < BLOCK_NUM; index++)
		Blocks[index] = Linear + index * BLOCK_SIZE;
}
void *MYLIB_malloc(size_t size)
{
	if(size <= BLOCK_SIZE && BlockCount)
	{
		if(!Blocks[0])
			InitBlocks();

		return Blocks[--BlockCount];
	}
	else
		return malloc(size);
}
void *MYLIB_realloc(void *ptr, size_t size)
{
	void *ptrNew;

	if(!IsLinearBlock(ptr))
		return realloc(ptr, size);

	if(size <= BLOCK_SIZE)
		return ptr;

	ptrNew = malloc(size);

	if(!ptrNew)
		return NULL;

	memcpy(ptrNew, ptr, BLOCK_SIZE);
	return ptrNew;
}
void MYLIB_free(void *ptr)
{
	if(IsLinearBlock(ptr))
		Blocks[BlockCount++] = ptr;
	else
		free(ptr);
}

単に 10000 バイト × 10000 個分のバイト列 Linear を切り売り(切り貸し？)しているだけの実装です。
制約をはみ出すことも考慮して、本物の malloc/realloc/free を呼び出すようにしてありますが、その考慮もしなければもっと単純な実装になります。
「1バイト確保するのに 10000 バイトも消費して勿体ない」という思い(？)もあったのですが、今日日の潤沢なメモリを使い果たすということを経験したことが滅多にないし、そういう場合はこの方法を使わなければ良いというだけです。
実際に実装したコードでは 4byte, 16byte, 64byte, 256byte, 1KB, 4KB, 16KB, 64KB, 256KB のブロックリストをそれぞれ用意して、足りなくなったら追加でメモリを確保していました。
当時のコードの成れの果て -> https://github.com/stackprobe/Codevil/blob/master/Codevil/Codevil/Common/MemAlloc.cpp
　
　

いちおう処理時間の測定

測定方法はちょっと雑、おかしいところがあるかもしれない。

	実装 M1	実装 M2
1回目	3250 ミリ秒	156 ミリ秒
2回目	3218 ミリ秒	141 ミリ秒
3回目	3203 ミリ秒	141 ミリ秒
4回目	3235 ミリ秒	141 ミリ秒
5回目	3219 ミリ秒	140 ミリ秒

各時間は下のプログラムの実行時間
src

#include <stdio.h>
#include <windows.h>
#include "MYLIB_malloc.h"

// ---- Rand ----

static unsigned int X;

static unsigned int Rand32(void)
{
	// Xorshift-32

	X ^= X << 13;
	X ^= X >> 17;
	X ^= X << 5;

	return X;
}

// ----

#define TEST_COUNT 10000000 // テスト回数

#define ALLOC_NUM_MAX  14000 // 実際に確保されるメモリブロックの最大数は、この 2 / 3 くらいになる。
#define ALLOC_SIZE_MAX 10000

static void *Ptrs[ALLOC_NUM_MAX];

main()
{
	int count;

	X = (unsigned int)GetTickCount64(); // windows.h

	for(count = 0; count < TEST_COUNT; count++)
	{
		size_t index = Rand32() % ALLOC_NUM_MAX;

		if(!Ptrs[index])
		{
			void *ptr = MYLIB_malloc(Rand32() % ALLOC_SIZE_MAX + 1);

			if(!ptr)
				exit(0); // fatal

			Ptrs[index] = ptr;
		}
		else if(Rand32() % 2)
		{
			void *ptr = MYLIB_realloc(Ptrs[index], Rand32() % ALLOC_SIZE_MAX + 1);

			if(!ptr)
				exit(0); // fatal

			Ptrs[index] = ptr;
		}
		else
		{
			MYLIB_free(Ptrs[index]);
			Ptrs[index] = NULL;
		}
	}
	printf("OK!\n");
}

これとは別に解析系のプログラムを作っていた際、更に邪道で高速な malloc を実装したことがあります。
速度に対する要求が厳しかったので、律儀に malloc/free するのを止めたというだけの話です。
制約として以下がありました。

プロセスの開始から終了までに確保されるメモリサイズの合計(の上限)が分かっている。
そしてそれはデータ領域に収まる。

実装は以下のとおり。(当時のコードが無いので、記憶を元に再現)

MYLIB_malloc.c

#include <stddef.h>
#include "MYLIB_malloc.h"

#define LINEAR_SIZE 500000000
#define MEM_ALIGN 4

static char Linear[LINEAR_SIZE];
static size_t NextPos;

void *MYLIB_malloc(size_t size)
{
	void *ptr;

	if(LINEAR_SIZE - NextPos < size)
		return NULL;

	ptr = Linear + NextPos;
	NextPos += ((size + MEM_ALIGN - 1) / MEM_ALIGN) * MEM_ALIGN;
	return ptr;
}
void *MYLIB_realloc(void *ptr, size_t size)
{
	return NULL; // 使用していなかった。
}
void MYLIB_free(void *ptr)
{
	// 何もしない。
}

最初は malloc/free を使っていたけれど「遅い、遅い」と言われて修正していった結果こうなった。
メモリなんて足りれば良い。
ひどいまとめ。

(2021.9.29) バグ見つけたのでこっそり修正こっそり再計測

stackprobe7s_memo

何処にも披露する見込みの無いものを書き落とす場所

malloc/free は遅いというよくある話 (C)

MYLIB_malloc.h

MYLIB_malloc.c　　(実装 M1)

MYLIB_malloc.c　　(実装 M2)

いちおう処理時間の測定

MYLIB_malloc.c

MYLIB_malloc.h

MYLIB_malloc.c (実装 M1)

MYLIB_malloc.c (実装 M2)

いちおう処理時間の測定

MYLIB_malloc.c

MYLIB_malloc.c　　(実装 M1)

MYLIB_malloc.c　　(実装 M2)