- C++相談室 part146
479 ：デフォルトの名無しさん[sage]：2019/12/02(月) 15:20:31.50 ID:Vo2mhncO - >>468
実はかなり古くから、C/C++ の malloc(), new のヒープメモリから確保したメモリの
断片化は、実際に問題になるようなことはとても少ないといわれています。
というのは、断片化というのは、確保したメモリを開放したときに出来た
「隙間にある空きメモリ」が再利用されにくい場合に起きるものなんですが、
実際には、再利用されることが多いためです。なぜなら、おなじサイズの
オブジェクトを new することが多いためです。この場合、完全に再利用されるので
断片化の問題と言うものは全く起きないと言っても過言では有りません。
それから、通常、1つのオブジェクトのサイズは小さく、それが多数集まって
データをなしていることが多いのです。このことから、異なるサイズのオブジェクト
であっても、1つ1つのオブジェクトのサイズが小さいため、断片化したとしても、
再利用される確率が高いのです。まず、同じサイズのオブジェクトであれば再利用されます。
異なるサイズであっても、昔開放されたオブジェクトよりも、小さいサイズのオブジェクトを
新しく確保する場合であれば再利用されます。
このようなことから現実の例では、断片化しても、使われないメモリの量はある程度の比率
に収まると言われており、それは GarbageCollection を行うためのオーバーヘッドの
メモリのサイズと比べても余り大きいものではないのです。
ゲームはメモリー効率も求められますが、それでも C/C++ が使われているのは、
メモリー断片化の量が一定比率より多くなら無い事が経験的に知られているためです。
|
- C++相談室 part146
481 ：デフォルトの名無しさん[sage]：2019/12/02(月) 15:33:38.42 ID:Vo2mhncO - >>474
C/C++ では、配列ではなくリンクリストを積極的に使うようにすることに
よって、メモリーが断片化しても再利用される確率を高くすることができます。
というのは、データの基本となっている要素のオブジェクトのサイズが
小さいため、さまざまなサイズのデータを new しても、結果的に、
断片化された空きメモリも高い確率で再利用されるためです。
new、delete するオブジェクトのサイズがランダムな場合で、
断片化空きメモリが残っている場合、確率論的には、おおよそ 2回に1回は
断片化空きメモリが再利用されることになるでしょう。もちろん、
delete された回数が少な過ぎる場合、そもそも断片化空きメモリの個数が少なすぎる
ので、再利用できる確率は低くなります。それは、初期化時やファイルからデータ
読み込み時などにどんどんメモリを new していくよう場合ですので、そもそも
断片化が起きる余地も有りません。
なお、ポインタとリンクリストを組み合わせると、よくある場合には、他の
集合アルゴリズムよりも、効率が高くなりやすいことが知られています。
ただし、文字を集合させて文字列を作るような場合は例外です。
|
- C++相談室 part146
482 ：デフォルトの名無しさん[sage]：2019/12/02(月) 15:39:04.52 ID:Vo2mhncO - >>481
配列の場合、delete するとメモリー上に大きな空き領域が出来ますが、
それより大きなサイズの配列を new しようとすると、そこが再利用できません。
なぜなら、配列の場合、連続したメモリ領域が固まって必要になるため、
要素の個数が N だとすると、N 個全てが一度にまとまって入りきる領域を探す
必要になるためです。
ところが、リンクリストの場合、要素数 N が大きくなっても、バラバラな
領域に分散して格納することが出来ます。すると、とても高い確率で、
分断化された空きメモリが再利用されることになります。
|
- C++相談室 part146
483 ：デフォルトの名無しさん[sage]：2019/12/02(月) 15:50:07.84 ID:Vo2mhncO - >>481
「2回に1回」と書きましたが、実際にはもっと確率は高いです。
リンクリストを使っている場合、要素を全部 delete したような場合は、開放された
空きブロックは、余り断片化せずに、比較的高い確率で結合され、大きな空きブロックに
なるためです。空きメモリは、元の要素のサイズの複数個分以上になっている確率が
高くなります（複雑ですが、管理領域のサイズもこれに加わります。）。
この性質があるため、現実には、小さいサイズのオブジェクトを要素とする集合
が多種類有った場合、それを好きに new, delete した場合、50% よりずっと高い確率で
断片化空きメモリーは再利用されます。
|
- C++相談室 part146
484 ：デフォルトの名無しさん[sage]：2019/12/02(月) 16:10:33.93 ID:Vo2mhncO - >>483
誤解無きように細くしておくと、「50% より大きい」というのは、
「断片化された空き領域が再利用される確率」
のことで、「断片化率」ではありません、。断片化率はもっと
小さな値になり、条件によりますが、例えば、数%〜10%程度
が目安になります。最悪のケースだともっと大きいのですが、
ケースバイケースで適切なデータ構造（集合アルゴリズム）を
使っているとこの程度に収まります。また、適切なデータ構造を
選択することはそんなに難しいわけではありません、。
|
- C++相談室 part146
485 ：デフォルトの名無しさん[sage]：2019/12/02(月) 16:15:53.26 ID:Vo2mhncO - >>475
既に、Windows95くらいの時期のメモリ容量で、C/C++のメモリ断片化は
問題が無い程度になっていました。実際には、MS-DOSの時代でも既に
問題なかったのですが。
とにかく、今の若い人の目線で言えば、古代ともいえるくらい古い時代に
既に C/C++ のメモリー断片化問題は問題が無い程度にハードウェアが
発達済みなのです。PC-8801 の 8BIT 時代には問題があったので、
N88-BASIC を筆頭に、GarbageCollection 方式をとっていましたが、
それは、若い人には「超古代文明」時代でしょう。
|
- C++相談室 part146
486 ：デフォルトの名無しさん[sage]：2019/12/02(月) 16:34:28.08 ID:Vo2mhncO - >>485
また誤解が入りそうなので細くしておきます。
N88-BASIC などが GarbageCollection を使っていたのは、本当に
マシンのメモリが少ないのでデータをぎゅーぎゅー詰めに隙間無く
入れることが重要だったためです。
一方、JavaやC#がGarbageCollection を使っているのは、どちらかと
いうと、「メモリー開放の自動化」のためです。参照カウンタだけで
は、循環参照問題が生じるため、時々、広い範囲のメモリブロックを
巡回して、循環参照していても本当に使って無い場合を厳密に見つけ出して、
徹底的に開放することを行います。
そのため、メモリーの断片化問題とはまた違う意味で、メモリー開放の
自動化には、GarbageCollection が必要となっています。
N88-BASIC 時代と、現在の Java, C# とでは、同じ GarbageCollection
でも主な役割が違うと考えられます。もちろん、断片化を防ぐ役割も同時に
果たしてくれますが。
|
- C++相談室 part146
487 ：デフォルトの名無しさん[sage]：2019/12/02(月) 16:40:43.00 ID:Vo2mhncO - >>486
誤字訂正： 細く ---> 補足
・BASIC言語にはポインタが無かったので、循環参照問題は有りませんでした。
・BASIC言語における GarbageCollection は、主に文字列領域の開放のためです。
A$="HELLO WORLD" と入れた後、A$="" とした時、元の文字列に使っていた
領域は、しばらく経った後に GarbageCollection で開放される仕組みでした。
ですので、文字列を余り使わなければ GarbageCollection も余りおきませんでした。
なお、DIM A(100) のように確保した配列は、余り開放することは有りませんでしたが、
開放した場合も、しばらく後に GarbageCollection の対象になっていたと思われます。
|
- C++相談室 part146
489 ：デフォルトの名無しさん[sage]：2019/12/02(月) 17:15:40.51 ID:Vo2mhncO - >>488
リンクリストでシーケンシャルアクセスする場合、キャッシュ以前に
ポインタをたどるようにアクセスしないといけないのですが、
最近、配列と同じような通し番号方式でアクセスしようとする人が
多くなっています。ライブラリなどは、以前にアクセスした番号が
k の場合、そのポインタを覚えておいて、プログラマが k + 1 の番号
をアクセスしようとした場合、後続のノードへのポインタをたどる
ことで高速化している場合があるので、特に問題が無い場合がありますが、
それを深く理解せずに、本当に先頭のノードからたどってしまった場合、
本来なら O(N)で済むところが、O(N^2) になってしまいます。
|
- C++相談室 part146
491 ：デフォルトの名無しさん[sage]：2019/12/02(月) 17:18:32.46 ID:Vo2mhncO - >>489
C/C++ でのリンクリストは、場所を覚えるのは通し番号ではなく、ポインタ
で行うことが基本です。ところが、最近、通し番号で覚えてしまうプログラムを
書く人が増えているように感じます。それは、キャッシュのために遅くなっているの
ではなく、計算オーダーが完全に違ってくるために遅くなるため、ただごとではない
遅さを招きます。
|