ヒープメモリの割り当てを解除するのがなぜそれを割り当てるよりもずっと遅いのですか？

Question

これは経験的な前提です（割り当てが速いと割り当てが解除される）。

この

は、ヒープベースのストレージが（ STLコンテナまたはその他のような） はシュリンク・トゥ・フィット理由です（システムに現在使用されていないメモリを返すように選択していない理由を私は、推測、また理由のですイディオムが生まれました）。

そして、我々はもちろん、混同してはならない、「ヒープ」「ヒープ」様なデータ構造を持つメモリ。割り当て解除は遅い理由

---

ので？

は、それがWindowsの固有またはOS独立した（私は勝利8.1にそれを参照してください）ですか？

は、自動的に「新しい」/を使用することに関わるいくつかのC++固有のメモリマネージャは、または全体MEM「を削除」あります。管理はOSに完全に依存していますか？ （私は私が実際に使ったことがないいくつかのガベージコレクションのサポートを、導入C++ 11は、より良い古いスタックと静的期間または自己に頼ることコンテナとRAIIを管理知っています）。

はまた、FOLLY列のコードでは、私は古いCヒープの割り当て/割り当て解除を使用して、それはC++「新しい」が高速です/見た「を削除」？

---

P. S.質問はないについて仮想メモリ力学であることに注意してください、私はユーザ空間プログラムが本当のMEMを使用していないことを理解しています。 addresation。

Answer 1

私は@Basileと同じ考えを持っていました。私はあなたのベース仮定が実際に（さらに近くに）正確であったかどうか疑問に思いました。あなたがC++の質問にタグを付けたので、私はC++で簡単なベンチマークを書きました。

#include <vector> 
#include <iostream> 
#include <numeric> 
#include <chrono> 
#include <iomanip> 
#include <locale> 

int main() { 
    std::cout.imbue(std::locale("")); 

    using namespace std::chrono; 
    using factor = microseconds; 

    auto const size = 2000; 

    std::vector<int *> allocs(size); 

    auto start = high_resolution_clock::now(); 

    for (int i = 0; i < size; i++) 
     allocs[i] = new int[size]; 

    auto stop = high_resolution_clock::now(); 
    auto alloc_time = duration_cast<factor>(stop - start).count(); 

    start = high_resolution_clock::now(); 

    for (int i = 0; i < size; i++) 
     delete[] allocs[i]; 

    stop = high_resolution_clock::now(); 

    auto del_time = duration_cast<factor>(stop - start).count(); 

    std::cout << std::left << std::setw(20) << "alloc time: " << alloc_time << " uS\n"; 
    std::cout << std::left << std::setw(20) << "del time: " << del_time << " uS\n"; 
} 

Linuxでgccの代わりにWindowsでVC++を使用しました。結果はそれほど大きくはありませんでした。メモリを解放することは、それを割り当てることよりも大幅に時間がかかりませんでした。ここでは、3回連続して実行された結果を示します。

alloc time:   2,381 uS 
del time:   1,429 uS 

alloc time:   2,764 uS 
del time:   1,592 uS 

alloc time:   2,492 uS 
del time:   1,442 uS 

Iは、（同じコンパイラを使用した場合であっても）が、割り当てと解放は、標準ライブラリによって（主に）処理されるので、これは一つの標準ライブラリと他の間で異なる可能性があり、警告するだろう。これがマルチスレッドコードで多少変更されるのであれば私には驚かないことにも気付くでしょう。実際には正しいわけではありませんが、マルチスレッド環境で解放するには、排他アクセスのためにヒープをロックする必要があると誤解されている著者がいるようです。これは避けることができますが、そうする手段は必ずしもすぐには明らかではありません。あなたは小さなメモリブロックを割り当てると

Answer 2

ここでの問題はヒープフラグメンテーションです。明示的なポインタ算術を持つ言語で書かれたプログラムは、ヒープの断片化を解消する現実的な方法がありません。

ヒープが断片化している場合、メモリをOSに戻すことはできません。 OSは仮想メモリを除いて、brk(2)のような仕組みに依存します。つまり、参照するすべてのメモリアドレスの上限を設定します。しかし、1つのバッファが割り当てられていても、既存の境界の近くで使用されている場合、OSに明示的にメモリを返すことはできません。プログラム内のすべてのメモリの99％が解放されても問題ありません。

割り当ては割り当てよりも遅くする必要はありません。しかし、ヒープ・フラグメント化を伴う手動の割り振り解除があるという事実は、割り振りをより遅く複雑にします。

GCはヒープを圧縮することでこれと戦います。この方法では、割り当てはポインタをインクリメントするだけであり、オブジェクトの大部分には割り当て解除は必要ありません。

Answer 3

ご迷惑をおかけして申し訳ございません。私は次のプログラムを書いています（Linuxでは、あなたのシステムに移植できることを願っています）。

// public domain code 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <errno.h> 
#include <string.h> 
#include <assert.h> 


const unsigned possible_word_sizes[] = { 
    1, 2, 3, 4, 5, 
    8, 12, 16, 24, 
    32, 48, 64, 128, 
    256, 384, 2048 
}; 

long long totalsize; 

// return a calloc-ed array of nbchunks malloced zones of 
// somehow random size 
void ** 
malloc_chunks (int nbchunks) 
{ 
    const int nbsizes = 
    (int) (sizeof (possible_word_sizes) 
    /sizeof (possible_word_sizes[0])); 
    void **ad = calloc (nbchunks, sizeof (void *)); 
    if (!ad) 
    { 
     perror ("calloc chunks"); 
     exit (EXIT_FAILURE); 
    }; 
    for (int ix = 0; ix < nbchunks; ix++) 
    { 
     unsigned sizindex = random() % nbsizes; 
     unsigned size = possible_word_sizes[sizindex]; 
     void *zon = malloc (size * sizeof (void *)); 
     if (!zon) 
    { 
     fprintf (stderr, 
      "malloc#%d (%d words) failed (total %lld) %s\n", 
      ix, size, totalsize, strerror (errno)); 
     exit (EXIT_FAILURE); 
    } 
     ((int *) zon)[0] = ix; 
     totalsize += size; 
     ad[ix] = zon; 
    } 
    return ad; 
} 

void 
free_chunks (void **chks, int nbchunks) 
{ 
// first, free the two thirds of chunks in random order 
    for (int i = 0; 3 * i < 2 * nbchunks; i++) 
    { 
     int pix = random() % nbchunks; 
     if (chks[pix]) 
    { 
     free (chks[pix]); 
     chks[pix] = NULL; 
    } 
    } 
// then, free the rest in reverse order 
    for (int i = nbchunks - 1; i >= 0; i--) 
    if (chks[i]) 
     { 
    free (chks[i]); 
    chks[i] = NULL; 
     } 
} 

int 
main (int argc, char **argv) 
{ 
    assert (sizeof (int) <= sizeof (void *)); 
    int nbchunks = (argc > 1) ? atoi (argv[1]) : 32768; 
    if (nbchunks < 128) 
    nbchunks = 128; 
    srandom (time (NULL)); 
    printf ("nbchunks=%d\n", nbchunks); 
    void **chks = malloc_chunks (nbchunks); 
    clock_t clomall = clock(); 
    printf ("clomall=%ld totalsize=%lld words\n", 
     (long) clomall, totalsize); 
    free_chunks (chks, nbchunks); 
    clock_t clofree = clock(); 
    printf ("clofree=%ld\n", (long) clofree); 
    return 0; 
} 

私のDebian /シド/ x86-64でのgcc -O2 -Wall mf.c -o mf（i3770k、16ギガ）とそれをコンパイル。私はtime ./mf 100000を実行しました：私のシステムclock上

nbchunks=100000 
clomall=54162 totalsize=19115681 words 
clofree=83895 
./mf 100000 0.02s user 0.06s system 95% cpu 0.089 total 

はCPUのマイクロ秒を与えます。 randomへの呼び出しが無視できる場合（およびそれがわからない場合）w.r.t. malloc & free時間、私はあなたの観察に同意しがちです。 freeはmallocの2倍の速さです。私のgccは6.1、私のlibcはGlibc 2.22です。

上記のベンチマークをシステムにコンパイルし、タイミングを報告するのに時間をかけてください。

FWIW、私はJerry's codeと

g++ -O3 -march=native jerry.cc -o jerry 
time ./jerry; time ./jerry; time ./jerry 

が

alloc time:   1940516 
del time:   602203 
./jerry 0.00s user 0.01s system 68% cpu 0.016 total 
alloc time:   1893057 
del time:   558399 
./jerry 0.00s user 0.01s system 68% cpu 0.014 total 
alloc time:   1818884 
del time:   527618 
./jerry 0.00s user 0.01s system 70% cpu 0.014 total 

Answer 4

に割り当てたメモリが、それは私には少し奇妙に思えたので、私はそれをテストして割り当て解除よりも高速であるという主張を与えました。私は32MBのチャンクで64MBのメモリを割り当てたテストを行ったので（2Mはnewに2Mコール）、割り当てられたのと同じ順序で、ランダムな順序でそのメモリを削除しようとしました。線形割り振り解除は約3％より速く、割り振りよりもであり、そのランダム割り振り解除は約10％遅いよりも線形割り振りよりも大きいことがわかりました。

私は64MBの割り当て済みメモリでテストを実行した後、2M回新しいメモリを割り当てたり既存のメモリを削除したりしました。ここでは、割り振り解除が割り当てより約4.3％遅かったことがわかりました。

だから、あなたが正しいと分かりました - 割り振り解除は割り振りよりも遅いです（私はそれを「ずっと遅く」と呼んでいませんが）。私は容疑者これは単により多くのランダムアクセスとは関係がありますが、私はこれ以外に線形解読が速いという証拠はありません。ご質問のいくつかに答えるために

：

は、自動的に「新しい」/「削除」を使用してに関わるいくつかのC++固有のメモリマネージャはありますか？

はい。 OSには、メモリページ（通常は4KBのチャンク）をプロセスに割り当てるシステムコールがあります。これらのページをオブジェクトに分割するのはプロセスの仕事です。 "GNU Memory Allocator"を調べてみてください。

古いCヒープ割り当て/割り当て解除を使用していましたが、C++の「新しい」/「削除」より速いのですか？

ほとんどのC++ new/delete実装はちょうどボンネットの下mallocとfreeを呼び出します。ただし、これは標準では必要ではないため、特定のオブジェクトに対して常に同じ割り当ておよび割り当て解除関数を使用することをお勧めします。

私は、Visual Studio 2015で提供されるネイティブテストフレームワークと私のテストは、Windowsの10の64ビットマシン上で（テストは、64ビットでした）走りました。コードは次のとおりです。

#include "stdafx.h" 
#include "CppUnitTest.h" 

using namespace Microsoft::VisualStudio::CppUnitTestFramework; 

namespace AllocationSpeedTest 
{  
    class Obj32 { 
     uint64_t a; 
     uint64_t b; 
     uint64_t c; 
     uint64_t d; 
    }; 
    constexpr int len = 1024 * 1024 * 2; 
    Obj32* ptrs[len]; 
    TEST_CLASS(UnitTest1) 
    { 
    public: 
     TEST_METHOD(Linear32Alloc) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
     } 
     TEST_METHOD(Linear32AllocDealloc) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
      for (int i = 0; i < len; ++i) { 
       delete ptrs[i]; 
      } 
     } 
     TEST_METHOD(Random32AllocShuffle) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
      srand(0); 
      for (int i = 0; i < len; ++i) { 
       int pos = (rand() % (len - i)) + i; 
       Obj32* temp = ptrs[i]; 
       ptrs[i] = ptrs[pos]; 
       ptrs[pos] = temp; 
      } 
     } 
     TEST_METHOD(Random32AllocShuffleDealloc) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
      srand(0); 
      for (int i = 0; i < len; ++i) { 
       int pos = (rand() % (len - i)) + i; 
       Obj32* temp = ptrs[i]; 
       ptrs[i] = ptrs[pos]; 
       ptrs[pos] = temp; 
      } 
      for (int i = 0; i < len; ++i) { 
       delete ptrs[i]; 
      } 
     } 
     TEST_METHOD(Mixed32Both) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
      srand(0); 
      for (int i = 0; i < len; ++i) { 
       if (rand() % 2) { 
        ptrs[i] = new Obj32(); 
       } 
       else { 
        delete ptrs[i]; 
       } 
      } 
     } 
     TEST_METHOD(Mixed32Alloc) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
      srand(0); 
      for (int i = 0; i < len; ++i) { 
       if (rand() % 2) { 
        ptrs[i] = new Obj32(); 
       } 
       else { 
        //delete ptrs[i]; 
       } 
      } 
     } 
     TEST_METHOD(Mixed32Dealloc) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
      srand(0); 
      for (int i = 0; i < len; ++i) { 
       if (rand() % 2) { 
        //ptrs[i] = new Obj32(); 
       } 
       else { 
        delete ptrs[i]; 
       } 
      } 
     } 
     TEST_METHOD(Mixed32Neither) 
     { 
      for (int i = 0; i < len; ++i) { 
       ptrs[i] = new Obj32(); 
      } 
      srand(0); 
      for (int i = 0; i < len; ++i) { 
       if (rand() % 2) { 
        //ptrs[i] = new Obj32(); 
       } 
       else { 
        //delete ptrs[i]; 
       } 
      } 
     } 
    }; 
} 

ここではいくつかの実行についての生の結果があります。すべての数値はミリ秒単位です。

Answer 5

は、指定したブロック・サイズは、メモリの断片化を避けるために、一般的に同じサイズのレコードを含むメモリの「スラブ」として表現され、そのサイズ、用suballocatorに直接マップします。アレイアクセスに似ていますが、これは非常に高速です。しかし、そのようなブロックを解放することは、未知のサイズのメモリーへのポインターを渡しているため、ブロックが適切な場所に戻される前に、スラブが属するスラブを判別するために追加の作業が必要になるため、簡単です。

あなたは仮想メモリの大きなブロックを割り当てる

は、メモリのページ範囲は、実際には、物理​​的なメモリをマッピングすることなく、あなたのプロセス空間に設定されている、それは達成するために非常に少し作業が必要です。解放されたポインタが最初の物理の全てを、それがまたがるメモリ範囲のページのすべてのエントリを歩いて、そして解放することによって、その後、その範囲のためのページテーブルに一致しなければならないので、しかし、このような大規模なブロックを解放することは、より多くの作業が必要になります介在するページフォルトによってその範囲に割り当てられたメモリページ。

もちろん、これの詳細は使用される実装に応じて変わりますが、原則はほとんど変わりません。既知のブロックサイズのメモリ割り当ては、不明なサイズのメモリブロックへのポインタを解放することよりも簡単です。これに関する私の知識は、高性能商用RAIIメモリアロケータの開発経験から直接得られたものです。

Iはまた、すべてのヒープ割り当てが一致し、対応する放出を有しているので、操作のこのペアは、すなわち、1種のコインの両面のように、単一の割当周期を表すことを指摘すべきです。一緒に実行時間を正確に測定することはできますが、ブロックサイズ、類似のサイズの以前のアクティビティ、キャッシングおよびその他の運用上の考慮事項によって大きく異なるため、個別に計測するのは難しいです。しかし、最終的には、あなたが他のものを使わずに行うことはできないので、割り当て/自由な相違はそれほど重要ではないかもしれません。