* kclib1について#4
-(by [[K]], 2019.04.09)
** (1) KMalloc
-KPtrPoolを100個以上使って実現した、シンプルだけど高速なmalloc/freeもどきです。
-KPtrPoolを使っているので、freeしたメモリは前後の未使用メモリと結合されることはありません。むしろそれをやらないからこそ高速なのです。→''ベンチーマーク(a)〜(c)''
-サイズは、 4, 8, 12, 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128, ...のように飛び飛びになっています。
--シンプルな方法としては、4, 8, 16, 32, 64, 128, ... みたいに倍々にすることだったのですが、これだと1025バイトを要求した時に2048バイトの領域を渡すことになり、約50%のメモリが利用されないことになります。それはメモリ効率が良くないと思いました。
--だからKMallocでは2倍の間を4つに刻んでいます。これで最も効率が悪い時でも、ロス率は20%で済みます。またメモリサイズの近いものはある程度同一視しないと、メモリの再利用が進みません。メモリブロックの再結合をしないKMallocでは、再利用が進まないとメモリ不足に追い込まれるので、やはり8分割や16分割はやり過ぎになってしまうと思われます。
--ロス率20%はワーストケースで、平均はおそらく10%になるでしょう。だからほとんど問題にならないと私は考えています。
-freeするときにもサイズを指定しなければけないという手間はありますが、その代わりメモリ使用効率は高いです。小さいメモリをたくさん確保してもメタデータのためにメモリ消費がうんと増えてしまうということはありません。→''ベンチーマーク(d)〜(e)''
--free時にサイズ指定する手間よりも、それで得られる性能向上の方が得だと考えてこの仕様にしています。
-「この場面でmalloc/freeを使うのはためらいがあるなー」と思うことがよくある私ですが（性能低下などが怖い）、KMallocならいつでも気軽に使える感じです。
-[Q]メモリをfreeしたときに再結合しないことで何か問題はないのか？
--[A]小さなメモリブロックをたくさん使って解放した後に、大きなメモリブロックを使おうとしてもメモリ不足で失敗する可能性があります。・・・しかし近年のコンピュータのメモリ積載量は私にとっては十分すぎるもので、私のプログラミングスタイルなら、KMallocでもメモリ不足に悩まされることはまず起こらない気がします。メモリがたくさんあっても使いこなせていない私ですが、それを活用して高速化してくれるのがKMallocであるとも言えます。
--別の論点としては、KMallocはそもそも完璧を目指していません。だから問題点がいくつあっても関係ないのです。簡単な仕組みでmalloc/freeもどきを作れたので、この程度で十分な範囲でのみ使っていけばいいと思っています。再結合が必要な場面ではKMallocなんか使わずに素直にmalloc/freeすればいいのです。用途に応じて使い分けることもプログラマの腕前だと思っています。
----
-論より証拠で簡単なベンチマークを取ったので書いておきます。
--(a) まず標準関数のmalloc/freeを使った、以下のプログラムの実行時間を測定しました。「1万回のmalloc&free」を1万回繰り返したときの時間を測っています。最初に10回ほど余計に回していますが、その間は時間を測りません。こうすることで初期のあまり速くない処理時間を混ぜずにトップスピードを測っています。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int i, j, **a = malloc(10000 * sizeof (int *));
clock_t t0 = 0, t1;
for (j = -10; j < 10000; j++) {
if (j == 0) t0 = clock();
for (i = 0; i < 10000; i++)
a[i] = malloc(256 * sizeof (int));
for (i = 0; i < 10000; i++)
free(a[i]);
}
t1 = clock();
printf("time: %.3f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
return 0;
}
---シンプルすぎてツッコミどころがない感じですが、 Core i7-2600 3.40GHz で測定したところ''35.188秒''でした。まあそんなものだろうなという感じです。
--(b) 次にKMallocを使ってみます。大きな違いは、freeするときにもサイズを指定しなければいけないところでしょうか。KMallocではメモリ管理のメタデータをあえて持たないので、freeするときにもサイズを教えてやらなければいけないのです。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "kclib1.h"
int main()
{
int i, j, **a = malloc(10000 * sizeof (int *));
clock_t t0 = 0, t1;
KAutoReleasePool_init();
KAutoReleasePool_open();
for (j = -10; j < 10000; j++) {
if (j == 0) t0 = clock();
for (i = 0; i < 10000; i++)
a[i] = KMalloc_alloc(256 * sizeof (int));
for (i = 0; i < 10000; i++)
KMalloc_free(256 * sizeof (int), a[i]);
}
t1 = clock();
printf("time: %.3f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
return 0;
}
---最初の KAutoReleasePool_init() の呼び出しは、これをやっておけばKMallocの初期化もついでにやってくれるので、決まり文句的に書いているものです。
---最初の KAutoReleasePool_open() の呼び出しは、これをやっておけばKMallocの初期化もついでにやってくれるので、決まり文句的に書いているものです。
---これでどのくらい速くなるのかなと思ったのですが、 Core i7-2600 3.40GHz で測定したところ''2.812秒''でした。これは我ながらすごいです。初めは何かの間違いじゃないかと思ったほどです。''12.5倍''くらい高速になっています。
--(c) さらに一歩進んで、KPtrPoolを直接使ってみます。KMallocでは同じサイズを何度もalloc/freeするのであれば、KPtrPoolを直接使って高速化してくれということになっています。だからそうしてみたわけです。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "kclib1.h"
int main()
{
int i, j, **a = malloc(10000 * sizeof (int *));
clock_t t0 = 0, t1;
KAutoReleasePool_init();
KPtrPool *pool = KMalloc_work->p + KMalloc_index(256 * sizeof (int));
for (j = -10; j < 10000; j++) {
if (j == 0) t0 = clock();
for (i = 0; i < 10000; i++)
a[i] = KPtrPool_alloc(pool);
for (i = 0; i < 10000; i++)
KPtrPool_free(pool, a[i]);
}
t1 = clock();
printf("time: %.3f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
return 0;
}
---これを実行すると、 Core i7-2600 3.40GHz で測定したところ''1.903秒''でした。
---ちなみにまだ速くする余地はあって、それは「今どのサイズのメモリブロックがいくつ使われているか」の集計機能をOFFにすることです（デフォルトではデバッグ支援のためにONにしてあります）。本家のmalloc/freeにはそんな機能は無いことですし、だからそれを同等にそろえて比較するのなら、このモードで比較する意味はあるでしょう。・・・そうすると、''1.882秒''になります。これは実に''18.7倍''くらい速いことになります。
--(d) 今度はメモリ効率の確認です。まずは以下のプログラムを実行してみました。
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i, *p;
char tmp[10000];
printf("[phase1] continue? (y/ctrl-c):");
scanf("%s", tmp);
for (i = 0; i < 1000000; i++) {
p = malloc(sizeof (int));
*p = i;
}
printf("[phase2] continue? (y/ctrl-c):");
scanf("%s", tmp);
return 0;
}
---これを実行すると、最初の消費メモリは356KBで、次の時点では16,312KBになっていました。つまり15,956KBほど消費メモリが増えたということです。どうやら1回のmallocで''16バイト''ずつ消費しているようです。そもそもmallocは16バイトアラインするというルールもありましたよね、確か。
--(e) これに対して以下のプログラムだとどうでしょうか？
#include <stdio.h>
#include "kclib1.h"
int main()
{
int i, *p;
char tmp[10000];
KAutoReleasePool_init();
printf("[phase1] continue? (y/ctrl-c):");
scanf("%s", tmp);
for (i = 0; i < 1000000; i++) {
p = KMalloc_alloc(sizeof (int));
*p = i;
}
printf("[phase2] continue? (y/ctrl-c):");
scanf("%s", tmp);
return 0;
}
---これを実行すると、最初の消費メモリは420KBで、ライブラリのワークエリアの分だけ消費メモリが増えていますが、次の時点では4,656KBで済みます。だから1回のmallocで''4バイト''ずつ消費しているのです。まあsizeof (int)が4バイトなので、当然と言えば当然の結果です。KMallocは4バイトのメモリに対しては4バイトのアラインは保証しますが、16バイトアラインは保証しないのです。
----
-（編集中）
* こめんと欄
#comment
![[K Wiki]](k.jpg "[K Wiki]")
