たとえば、文字列やベクターなど、より多くのメモリを必要とするデータ構造があるとします。 新しい要素がバッファーに配置されていない場合、新しいバッファーが作成され、古いコンテンツがすべてそこにコピーされ、その後、古いバッファーが解放されます。 通常の
realloc()
が実行されます。
だからここに。 最初の1バイトバッファーが1 MiBのサイズに達するまで1バイトずつ増加するとします。 彼のためにどれだけのメモリを累積的に使用しましたか？
1 + 2 + 3 + ... + 1,048,575 + 1,048,576 = 549,756,338,176バイト
弱くないよね？
経験豊富なプログラマーにとって、このニュアンスは長い間知られているので、バッファーの線形的な増加でさえ「典型的な初心者の間違い」であると考える人もいます。
一番下の行は、新しい配列が常に前の配列より一定の値だけ大きい場合、合計作業量はO（n 2 ）になるということです。 新しい配列が定数因子Nだけ増加する場合、合計作業量はO（n）になります。 「作業」とは、
malloc()
および
realloc()
関数の呼び出しと、それに続くメモリ内の値の再配布とコピー、つまりシステムの総負荷を意味します。
もちろん、たとえば、ハードウェア用の組み込みファームウェアには、ルールの例外と見なされる状況があります。 しかし、デスクトップシステムの場合、これは実際には法律です。 唯一の質問は、使用する要因：2または1.5です。
Nicholas Neterkotは、メモリマネージャがバッファのサイズを丸めるので、実際には合計メモリ消費はもちろん少なくなるという例に追加しています。 たとえば、同じFirefox（jemallocの高度に変更された古いバージョン）のマネージャーは、4 KiB〜1 MiBのメモリ割り当て要求を最も近い4 KiB乗数に切り上げます。 つまり、この例では、合計ボリュームが1 MiBのバッファーの場合、次のもののみが取得されます。
4,096 + 8,192 + 12,288 + ... + 1,044,480 + 1,048,576 = 134,742,016バイト
比較のために、すぐに係数2を使用した場合：
4,096 + 8,192 + 16,384 + 32,768 + 65,536 + 131,072 + 262,144 + 524,288 + 1,048,576 = 2,093,056バイト
彼らは、I / Oタスクがバッファのサイズをスケーリングしない場合、「典型的な初心者の間違い」が非常に多くのプロジェクトに現れると言います。 Neterkotは、 XDRBuffer 、 nsTArray 、およびSQLiteのアルゴリズムの実装で、最適でないコードの対応するフラグメントをすぐに見つけました。