グローバルnew&deleteオペレータを書き換えるパラレル化の実践
最近1つの機能をしていて、計算量が大きくて、プログラムを並列化してマルチコアの優位性を利用する必要があります.
げんしょう
最初はOpenMPを使っていましたが、私の机械では、4 C 8 Tのi 7、CPUは90%以上に达することができます.タスクマネージャの小さなアイコンの中で见るとCPUがいっぱいになっているのと同じです.だから、このプログラムの并行化は终わってもいいと思います.だから、プログラムを48コアのクラウドホストに置いて走りました.その结果、CPUの利用率は最大40%にしかなりませんでした.どこかに依存が生じているようだ.
omp critical
私が最初に考えたのは、スレッドで使用されるomp critical文の場所です.これは結果セットを保護するために使用されます.つまり、すべてのスレッドが1つの結果セットにデータを書き込むので、これは保護する必要があります.したがって、最初の試みは、各スレッドに結果セットを個別に割り当て、計算結果が完了した後、メインスレッドによって各サブセットをマージすることです.このようにして完成した後、何の違いもなく、合併度が上がらないのは、この原因ではないようだ.
Sqlite
それからまたコードの中で疑いの対象を探して、SQLiteはまた私の目の中に入りました.SQLiteの1つの接続が同時読み取りを行う際に性能がよくないことが以前に発見されましたが、今はそうです.安全のため、Demoを1つ書いて検証しました.単一プロセス内の複数の読み取り専用接続の同時読み取り性能は、単一の読み取り専用接続の同時よりも確かに優れています.だから私は自信を持ってプログラムをSQLite接続に変更して、各スレッドに1つ使用させます.それからまた走って、やはり何の違いもないことに気づいた.
山が尽きる
これで,すべてのスレッドは関係なく,それぞれのデータを用い,それぞれのコアを用いる.
まさかタスクスケジューリングの問題ですか?それからいろいろなscheduleモードとブロックサイズを試してみましたが、効果はありませんでした.その後、PPLでスレッドプールを実現し、自分でスケジューリングを行い、結果はそのままでした.
それから私は心配して、ネット上で同時ボトルネックを探すことができるツールを探して、何も探していません......
この間、複数のプロセスを使用してこれらの計算を行うと、同時度が向上することを発見しました.それから、同時モードをマルチプロセスに変更するかどうかを考えました.MPIを使用すれば、後でマルチマシン計算をするのに便利です.
柳暗花明
しかし、同僚に注意されると、手にはずっとこのようなツールがありました.それはデバッガです.マルチスレッドプログラムに並列依存がある場合は、プログラムの実行中に中断し、各スレッドがどこに止まっているかを見て、ボトルネックの位置に位置する確率が高いはずです.
それから私は私の機械で試して、中断するたびに4つぐらいのスレッドがnew/deleteに中断されていることを発見して、それから私が作成したデータ構造はすべてスレッドのコピーがあって、しかしスタックはプロセス内のすべてのスレッドが共用して、間違いなくロックがあって、基本的に問題の所在を確定するべきです.
問題を再現する.
念のため、まずDemoを書いて検証してみましょう.最初のバージョンはこうでした.
CPUをいっぱい走ることができることを発見して、これはnew/deleteの性能がやはりとても良いことを説明するべきで、まさか私はそれらを責めましたか?
その後、大神の注意を受けて、申請の大きさをランダムにして、大きくして、申請と釈放はランダムな間隔を隔てています.
最後にコードは次のように変更されました.
そしてCPU利用率は確かに上がらず、30%~40%程度で問題が再現されたと思います.それでは、それぞれスレッド別にスタックメモリ申請を行いましょう.
その結果vector初期化時にスペースが申請されnewが呼び出され、すべてのカスタムheapが作成されません.実はここでは主にheap[0]が作成されていません.なぜなら、非同時環境ではomp_get_thread_numは0を返します.
だから変更を続けます.
私の環境では1024個のスタックで十分で、現在は数GBのメモリを浪費しても受け入れられます.
死なない
Demoでは、すべてのスタックメモリの申請と解放を分けることができ、CPUを満タンにしてから、これらのコードをワークコードに移植することができます.その結果、HeapFreeは異常を投げます.作業環境下では、すべてのdeleteが申請時のスレッドで行われているわけではないので、メモリが他のスタックで放出され、当然エラーが報告されます.
スレッドが不確定である以上、何が確定しているのでしょうか.
メモリアドレス?できないようです.newの時にheapIndexを確定する必要がありますが、この時はまだメモリアドレスがありません.どうしてheapIndexを確定しますか.
メモリのサイズは?はい、これは申請する前からあったので、heapIndexを計算するのに使えます.でもdeleteの時はこのパラメータがなかったので、また袋小路に出たような・・・
当日の帰り道、このsizeを記録してもいいかなと思って、申請するときに何バイトか申請して、この長さを保存して、呼び出し元の何バイトかの後の住所に戻ります.deleteの時にこのアドレスを返して、前の数バイトに行ってこの長さを取って、heapIndexを再び計算することができます!
やると言ったらやる.
よさそうですね.一周します.
そしてすぐに間違えて、deleteの時に明らかに間違った長さを得ました.分析によると、ある依存ライブラリがVCのデフォルトのnew申請を通過する空間であるはずなのに、書き換えたdeleteで解放された.
実はここまで来て、私はすでに心を退けて、“全局のnew&deleteを書き直すのはほとんど良い考えではありません”!
しかし、もう一度やってみたいのですが、問題に基づいて、2つの場所から申請したメモリを分けましょう.この長さだけでは足りないに違いない.デフォルトのnew申請の空間の前のセグメントにも通常の長さのデータがある可能性が高いからだ.では、自分で特別な標識を追加します.コードは以下の通りです.
これにより、デフォルトnew出願のメモリの先頭がちょうどこの識別であり、デフォルトnew出願のメモリの先頭が読み取り不能な領域であるなど、問題がないことを本当に100%保証することはできない.デフォルトnewのメモリレイアウトはわかりませんが、この2つの状況が現れる確率は大きくないと推測して、先に一周します!
前の計算過程はすべて正常で、間違いなく、CPUの利用率は100%に達していないが、以前より大きく進歩した.しかし、最後に掃除をするときは間違いを報告します.
死んだ
ここまで来たら、私はもうこの道を歩き続ける気はありません.すべてのメモリの申請と解放をコントロールできない限り、このようなやり方は危険です.
次にMPIでマルチプロセス同時化を行いましょう.後で分散計算に変更するのも便利です.
げんしょう
最初はOpenMPを使っていましたが、私の机械では、4 C 8 Tのi 7、CPUは90%以上に达することができます.タスクマネージャの小さなアイコンの中で见るとCPUがいっぱいになっているのと同じです.だから、このプログラムの并行化は终わってもいいと思います.だから、プログラムを48コアのクラウドホストに置いて走りました.その结果、CPUの利用率は最大40%にしかなりませんでした.どこかに依存が生じているようだ.
omp critical
私が最初に考えたのは、スレッドで使用されるomp critical文の場所です.これは結果セットを保護するために使用されます.つまり、すべてのスレッドが1つの結果セットにデータを書き込むので、これは保護する必要があります.したがって、最初の試みは、各スレッドに結果セットを個別に割り当て、計算結果が完了した後、メインスレッドによって各サブセットをマージすることです.このようにして完成した後、何の違いもなく、合併度が上がらないのは、この原因ではないようだ.
Sqlite
それからまたコードの中で疑いの対象を探して、SQLiteはまた私の目の中に入りました.SQLiteの1つの接続が同時読み取りを行う際に性能がよくないことが以前に発見されましたが、今はそうです.安全のため、Demoを1つ書いて検証しました.単一プロセス内の複数の読み取り専用接続の同時読み取り性能は、単一の読み取り専用接続の同時よりも確かに優れています.だから私は自信を持ってプログラムをSQLite接続に変更して、各スレッドに1つ使用させます.それからまた走って、やはり何の違いもないことに気づいた.
山が尽きる
これで,すべてのスレッドは関係なく,それぞれのデータを用い,それぞれのコアを用いる.
まさかタスクスケジューリングの問題ですか?それからいろいろなscheduleモードとブロックサイズを試してみましたが、効果はありませんでした.その後、PPLでスレッドプールを実現し、自分でスケジューリングを行い、結果はそのままでした.
それから私は心配して、ネット上で同時ボトルネックを探すことができるツールを探して、何も探していません......
この間、複数のプロセスを使用してこれらの計算を行うと、同時度が向上することを発見しました.それから、同時モードをマルチプロセスに変更するかどうかを考えました.MPIを使用すれば、後でマルチマシン計算をするのに便利です.
柳暗花明
しかし、同僚に注意されると、手にはずっとこのようなツールがありました.それはデバッガです.マルチスレッドプログラムに並列依存がある場合は、プログラムの実行中に中断し、各スレッドがどこに止まっているかを見て、ボトルネックの位置に位置する確率が高いはずです.
それから私は私の機械で試して、中断するたびに4つぐらいのスレッドがnew/deleteに中断されていることを発見して、それから私が作成したデータ構造はすべてスレッドのコピーがあって、しかしスタックはプロセス内のすべてのスレッドが共用して、間違いなくロックがあって、基本的に問題の所在を確定するべきです.
問題を再現する.
念のため、まずDemoを書いて検証してみましょう.最初のバージョンはこうでした.
#omp parallel for
for(int I = 0 ; I < 1000000; ++i)
{
for(int j = 0 ; j < 10000; ++j)
delete new int;
}CPUをいっぱい走ることができることを発見して、これはnew/deleteの性能がやはりとても良いことを説明するべきで、まさか私はそれらを責めましたか?
その後、大神の注意を受けて、申請の大きさをランダムにして、大きくして、申請と釈放はランダムな間隔を隔てています.
最後にコードは次のように変更されました.
#pragma omp parallel for schedule(static, 1000)
for (auto i = 0ll; i < 10000000000; ++i)
{
for (int j = 0; j < 1000000; ++j)
{
const auto l = rand() * 1000 + 1000; //32,767,000
auto p = new int[l];
const auto t = rand() % 100000;
for (int k = 0; k < t; ++k)
p[0] += p[1];
delete[] p;
}
}そしてCPU利用率は確かに上がらず、30%~40%程度で問題が再現されたと思います.それでは、それぞれスレッド別にスタックメモリ申請を行いましょう.
std::vector initHeaps()
{
std::vector res(omp_get_num_procs(), NULL);
for(auto & h : res)
h = HeapCreate(HEAP_NO_SERIALIZE, 1024 * 1024, 0);
return res;
}
auto g_heaps = initHeaps();
void* operator new(size_t size)
{
const auto heapIndex = omp_get_thread_num();
auto p = HeapAlloc(g_heaps[heapIndex], HEAP_NO_SERIALIZE, size);
if (!p)
throw std::bad_alloc();
else
return p;
}
void operator delete(void* p)
{
const auto heapIndex = omp_get_thread_num();
auto res = HeapFree(g_heaps[heapIndex], HEAP_NO_SERIALIZE, p);
} その結果vector初期化時にスペースが申請されnewが呼び出され、すべてのカスタムheapが作成されません.実はここでは主にheap[0]が作成されていません.なぜなら、非同時環境ではomp_get_thread_numは0を返します.
だから変更を続けます.
const auto HEAP_COUNT = 1024;
HANDLE* initHeaps()
{
static HANDLE s_heaps[HEAP_COUNT] = { 0 };
for (int i = 0; i < HEAP_COUNT; ++i)
s_heaps[i] = HeapCreate(0, 1024 * 1024, 0);
return s_heaps;
}
HANDLE* g_heaps = initHeaps();私の環境では1024個のスタックで十分で、現在は数GBのメモリを浪費しても受け入れられます.
死なない
Demoでは、すべてのスタックメモリの申請と解放を分けることができ、CPUを満タンにしてから、これらのコードをワークコードに移植することができます.その結果、HeapFreeは異常を投げます.作業環境下では、すべてのdeleteが申請時のスレッドで行われているわけではないので、メモリが他のスタックで放出され、当然エラーが報告されます.
スレッドが不確定である以上、何が確定しているのでしょうか.
メモリアドレス?できないようです.newの時にheapIndexを確定する必要がありますが、この時はまだメモリアドレスがありません.どうしてheapIndexを確定しますか.
メモリのサイズは?はい、これは申請する前からあったので、heapIndexを計算するのに使えます.でもdeleteの時はこのパラメータがなかったので、また袋小路に出たような・・・
当日の帰り道、このsizeを記録してもいいかなと思って、申請するときに何バイトか申請して、この長さを保存して、呼び出し元の何バイトかの後の住所に戻ります.deleteの時にこのアドレスを返して、前の数バイトに行ってこの長さを取って、heapIndexを再び計算することができます!
やると言ったらやる.
void* operator new(size_t size)
{
const auto heapIndex = size % HEAP_COUNT;
auto p = HeapAlloc(g_heaps[heapIndex], 0, size + sizeof(size_t));
if (!p)
throw std::bad_alloc();
else
{
*(size_t*)p = size;
return (byte*)p + 8;
}
}
void operator delete(void* p)
{
auto realP = (byte*)p - 8;
const auto size = *(size_t*)realP;
const auto heapIndex = size % HEAP_COUNT;
if (FALSE == HeapFree(g_heaps[heapIndex], 0, realP))
{
const auto e = GetLastError();
}
}よさそうですね.一周します.
そしてすぐに間違えて、deleteの時に明らかに間違った長さを得ました.分析によると、ある依存ライブラリがVCのデフォルトのnew申請を通過する空間であるはずなのに、書き換えたdeleteで解放された.
実はここまで来て、私はすでに心を退けて、“全局のnew&deleteを書き直すのはほとんど良い考えではありません”!
しかし、もう一度やってみたいのですが、問題に基づいて、2つの場所から申請したメモリを分けましょう.この長さだけでは足りないに違いない.デフォルトのnew申請の空間の前のセグメントにも通常の長さのデータがある可能性が高いからだ.では、自分で特別な標識を追加します.コードは以下の通りです.
const auto HEAP_COUNT = 256;
const auto HEAP_FLAG = 0;
HANDLE* initHeaps()
{
static HANDLE s_heaps[HEAP_COUNT] = { 0 };
for (int i = 0; i < HEAP_COUNT; ++i)
s_heaps[i] = HeapCreate(HEAP_FLAG, 1024*1024, 0);
return s_heaps;
}
HANDLE* g_heaps = initHeaps();
const size_t UNIQUE_MASK = 0xF0E1D2C3B4A59687;
inline byte hash(const size_t& size)
{
byte res = 0;
for (int i = 0 ; i < 8; ++i)
{
res ^= byte((size >> (i * 8)) & 0xff);
}
return res;
}
void* operator new(size_t size)
{
const auto heapIndex = hash(size);
auto p = HeapAlloc(g_heaps[heapIndex], HEAP_FLAG, size + sizeof(size_t) * 2);
if (!p)
throw std::bad_alloc();
else
{
*(size_t*)p = size;
*((size_t*)p + 1) = UNIQUE_MASK;
return (byte*)p + sizeof(size_t) * 2;
}
}
void operator delete(void* p)
{
auto pMask = (size_t*)((byte*)p - sizeof(UNIQUE_MASK));
if (UNIQUE_MASK == *pMask)
{
auto pSize = pMask - 1;
auto realP = pSize;
const auto heapIndex = hash(*pSize);
if (FALSE == HeapFree(g_heaps[heapIndex], HEAP_FLAG, realP))
{
const auto e = GetLastError();
}
}
else
{
free(p);
}
}これにより、デフォルトnew出願のメモリの先頭がちょうどこの識別であり、デフォルトnew出願のメモリの先頭が読み取り不能な領域であるなど、問題がないことを本当に100%保証することはできない.デフォルトnewのメモリレイアウトはわかりませんが、この2つの状況が現れる確率は大きくないと推測して、先に一周します!
前の計算過程はすべて正常で、間違いなく、CPUの利用率は100%に達していないが、以前より大きく進歩した.しかし、最後に掃除をするときは間違いを報告します.
死んだ
ここまで来たら、私はもうこの道を歩き続ける気はありません.すべてのメモリの申請と解放をコントロールできない限り、このようなやり方は危険です.
次にMPIでマルチプロセス同時化を行いましょう.後で分散計算に変更するのも便利です.