効率的なメモリブロックサイズ

とっても環境依存で実装依存な事なんですが、一方で、メモリ効率っていうのは非常に大事なファクターです。
特に小さな構造体をメモリにたくさん配置するような場合、メモリのアラインメント(データをCPUが効率的にアクセスできるきりの良いアドレスに配置すること、16バイトとか、32バイトといった単位になることが多い)のため、メモリが無駄になることが多いです。

例えば、現状のIntel x86系で32-bit OSだと、6バイトのメモリを確保するなんてことをすると、アラインメント単位がおそらく、16バイトなので、10バイト分が利用されることなく無駄な領域として残されることになります。ただし、一般的に、mallocやnewで確保されるメモリブロックには管理領域という領域が確保されるので、

char* p = new char[10];

っていう処理が果たして何バイトの領域を必要として、結果、どれだけの領域を確保するのかは実際に試してみないといけません(コードを読んでも良いんですが、それだと環境毎にソースを読まないといけないので、簡単なコードを実行する方が楽です)。

ということで、実験コード。テスト用コードなのでメモリを解放していません。

// memalign.cpp
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
  if(argc < 3)
  {
    printf("%s BLOCK_SIZE COUNT\n", argv[0]);
    return -1;
  }
  
  size_t blockSize = atoi(argv[1]);
  size_t count = atoi(argv[2]);
  
  for(size_t i = 0; i < count; i++)
  {
    unsigned char *p = new unsigned char[blockSize];
    printf("%u\t%p\n", i, p);
  }
}

32ビット環境でのテスト

これを、Visual Studio 2010 SP1の32ビット版コンパイラ

Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.40219.01 for 80x86

でビルドしてテストしてみます。最初に、10バイトのブロックを10個確保してみます。

C:\work>memalign 10 20
0       00793C08
1       00791A00
2       00791A18
3       00791A30
4       00791A48
5       00791A60
6       00791A78
7       00791A90
8       00791AA8
9       00791AC0

そうすると、最初の奴は無視するとして、メモリブロックの間隔が、0x18(24)バイト単位で推移していることになります。つまり、10バイト確保すると、実際には、24バイトが消費されているわけです!
次は、8バイトを確保する実験。

C:\work>memalign 8 10
0       00963C08
1       00961A00
2       00961A10
3       00961A20
4       00961A30
5       00961A40
6       00961A50
7       00961A60
8       00961A70
9       00961A80

綺麗に16バイトずつ確保されているのが分かります。結論から言うと、この環境においては、管理ブロックが8バイトで、さらに、メモリブロックの先頭が8バイトに揃うようにメモリが確保されているわけです。つまり、1〜8バイトのメモリ確保は、結果的には、16バイトのメモリを消費するということです。16バイトのメモリ確保は、32バイトのメモリ消費です。メモリがもったいないと思って、メモリ確保のサイズをケチるときにはこの事実をキッチリと頭に入れておく必要があります。実装依存ですけど。

1バイトを確保してみると、

C:\work>memalign 1 10
0       00513C10
1       00511A00
2       00511A10
3       00511A20
4       00511A30
5       00511A40
6       00511A50
7       00511A60
8       00511A70
9       00511A80

やっぱり16バイト持って行かれます。無駄すぎる。

64ビット環境でのテスト

次に、Visual Studio 2010 SP1の64ビット版コンパイラ:

Microsoft (R) C/C++ Optimizing Compiler Version 16.00.40219.01 for x64

で試します。最初は、さっきと同じで、10バイトのブロックを10個確保してみます。

C:\work>memalign 10 10
0       00000000004A8520
1       00000000004A8540
2       00000000004A8560
3       00000000004A8580
4       00000000004A85A0
5       00000000004A85C0
6       00000000004A85E0
7       00000000004A8600
8       00000000004A8620
9       00000000004A8640

64ビットなのでアドレス表記が16桁になっています。今回はアドレスの間隔が32バイト。
つまり、10バイト確保する毎に、32バイトを消費しています。
試しに1バイト確保してみると、

C:\work>memalign 1 10
0       0000000000538E30
1       0000000000538E50
2       0000000000538E70
3       0000000000538E90
4       0000000000538EB0
5       0000000000538ED0
6       0000000000538EF0
7       0000000000538F10
8       0000000000538F30
9       0000000000538F50

やっぱりというかなんというか、32バイト確保しています!32ビット版に輪を掛けてもったいなさ過ぎ!
32バイトというのは64ビット環境での最小ブロック単位なわけです。
テストすれば分かりますが、こっちは、24バイト確保すると32バイト消費し、25バイト確保すると、48バイト消費します。
つまり、管理領域は、8バイト。32ビット版と管理領域のサイズが同じなので、よく考えるとお得かも知れません。

Mac OS X 10.7 + g++ 4.2.1

OS X 10.7での結果。

$ ./memalign 16 10
0	0x10df00a00
1	0x10df00a10
2	0x10df00a20
3	0x10df00a30
4	0x10df00a40
5	0x10df00a50
6	0x10df00a60
7	0x10df00a70
8	0x10df00a80
9	0x10df00a90

素敵なことに、メモリのブロックには管理ブロックは付きません。綺麗に、16バイト単位で並んでいます。

Ubuntu 11.10 (GNU/Linux 3.0.0-13-server x86_64) + g++ 4.6.1

$ ./memalign 1 10
0	0x1186010
1	0x1186030
2	0x1186050
3	0x1186070
4	0x1186090
5	0x11860b0
6	0x11860d0
7	0x11860f0
8	0x1186110
9	0x1186130

$ ./memalign 24 10
0	0x1045010
1	0x1045030
2	0x1045050
3	0x1045070
4	0x1045090
5	0x10450b0
6	0x10450d0
7	0x10450f0
8	0x1045110
9	0x1045130

$ ./memalign 28 10
0	0x1a5d010
1	0x1a5d040
2	0x1a5d070
3	0x1a5d0a0
4	0x1a5d0d0
5	0x1a5d100
6	0x1a5d130
7	0x1a5d160
8	0x1a5d190
9	0x1a5d1c0

1バイトでも32バイトを消費してくれます。24バイト確保と28バイト確保の結果から、管理領域は、8バイト。Windows 64ビット版と大きくは変わらないようですね。

参考文献

x64 Software Conventionsについてっぽいので、32ビットについては微妙だけど、mallocは16バイトアラインメントと書いてある。
malloc Alignment - Visual Studio .2010


glibcのアラインメントは、8の倍数(64ビットなら、16の倍数)
3.2.2.7 Allocating Aligned Memory Blocks - The GNU C Library


Mac OS Xのアラインメント(というかメモリ粒度)は16バイト。
Tips for Allocating Memory - Mac OS X Developer Library

追記

誤解を招くといけないので、追記しておきますが、

int *p = new int[10];

が10*16バイト消費したりするわけではありません。この場合、ブロックの先頭は16バイト単位にアラインメントされますが、32ビットのintの値は継ぎ目なく確保されるので、この場合は、おそらく、4*10+8=48バイトしか消費しません。
あくまでも、malloc/newした時のメモリ確保の最小単位が16バイトで、管理ブロックのサイズが8バイトだということです。