3-1 スレッド間のヒープ競合の回避

システムヒープからのメモリーの割り当ては、単純な処理ではありません。これは、システム・ランタイム・ライブラリーが、ヒープへのアクセス同期にロックを使用するためです。このロックの競合は、マルチスレッド化によってもたらされるパフォーマンスの妨げとなることがあります。この問題は、共有ロックを使用しない割り当て手法やサードパーティーのヒープ・マネージャーを使用することで解決できます。

この記事は、「マルチスレッド・アプリケーションの開発のためのインテル・ガイド」の一部で、インテル^® プラットフォーム向けにマルチスレッド・アプリケーションを効率的に開発するための手法について説明します。

システムヒープ (malloc で使用される) は共有リソースです。そのため、複数のスレッドが安全に使用できるようにするためには、共有ヒープへのアクセスを制御する同期が必要になります。同期 (この場合はロックの取得) には、オペレーティング・システムとの間に 2 つの処理 (例えば、ロックとアンロック) が必要となるためオーバーヘッドが生じます。一方、すべてのメモリーの割り当てを直列化すると、スレッドが処理ではなく、ロックの待機に多くの時間を費やすことになり、より大きな問題を引き起こします。

図 1 と図 2 は、インテル^® Parallel Amplifier により、マルチスレッド化された CAD アプリケーションのヒープ競合問題が示されています。

図 1. ヒープ割り当てルーチンとカーネル関数の呼び出しにアプリケーション実行時間のほとんどが費やされており、これらがボトルネックになっていることがわかります。

図 2. ヒープ割り当てルーチンで使用されているクリティカル・セクションで同期オブジェクトの競合が最も多く発生しており、長時間の待機と CPU が有効利用されていない原因になっていることがわかります。

インテル^® コンパイラーの OpenMP* 実装では、kmp_malloc と kmp_free の 2 つの関数をエクスポートします。これらの関数は、OpenMP で使用する各スレッドのヒープを管理し、標準のシステムヒープへのアクセスを保護するロックを使用しないようにします。

Win32* API HeapCreate 関数を使用して、アプリケーションで使用するすべてのスレッドに個別のヒープを割り当てることができます。各ヒープにアクセスするスレッドは 1 つだけであるため、HEAP_NO_SERIALIZE フラグを使用して、この新しいヒープ上の同期を無効にできます。ヒープハンドルをスレッド・ローカル・ストレージ (TLS) に格納することで、アプリケーション・スレッドが、このヒープを使用して、いつでもメモリーの割り当てや解放を行えるようになります。ただし、この方法で割り当てたメモリーは、割り当てを行ったスレッドによって明示的に解放する必要があります。

以下の例では、前述の Win32 API 関数を使用してヒープ競合を回避する方法について示します。この方法では、ダイナミック・リンク・ライブラリー (.DLL) を使用して、新しいスレッドを作成時に登録し、スレッドごとに独立して管理される非同期ヒープを要求し、TLS を使って各スレッドに割り当てられたヒープを記録しています。

#include 
static DWORD tls_key;
__declspec(dllexport) void *
thr_malloc( size_t n )
{
  return HeapAlloc( TlsGetValue( tls_key ), 0, n );
}
__declspec(dllexport) void 
thr_free( void *ptr )
{
  HeapFree( TlsGetValue( tls_key ), 0, ptr );
}
// This example uses several features of the WIN32 programming API 
// It uses a .DLL module to allow the creation and destruction of 
// threads to be recorded.
BOOL WINAPI DllMain(
  HINSTANCE hinstDLL, // handle to DLL module
  DWORD fdwReason, // reason for calling function
  LPVOID lpReserved ) // reserved
{
  switch( fdwReason ) { 
    case DLL_PROCESS_ATTACH:
    // Use Thread Local Storage to remember the heap
    tls_key = TlsAlloc();
    TlsSetValue( tls_key, GetProcessHeap() );
      break;
    case DLL_THREAD_ATTACH:
      // Use HEAP_NO_SERIALIZE to avoid lock overhead
    TlsSetValue( tls_key, HeapCreate( HEAP_NO_SERIALIZE, 0, 0 ) );
      break;
  case DLL_THREAD_DETACH:
    HeapDestroy( TlsGetValue( tls_key ) );
      break;
  case DLL_PROCESS_DETACH:
    TlsFree( tls_key );
      break;
  }
  return TRUE; // Successful DLL_PROCESS_ATTACH.
}

POSIX* スレッド (Pthreads*) を使用するアプリケーションで、個別のヒープを作成するための共通な API がない場合は、pthread_key_create API と pthread_{get|set}specific API を使用して TLS へアクセスできます。各スレッドに大きなメモリー領域を割り当てて、そのアドレスを TLS に格納することができますが、TLS の管理はプログラマーの責任で行う必要があります。

互いに独立した複数のヒープを使用する方法だけでなく、その他の手法も併用することで、システムヒープを保護する共有ロックの競合を最小限に抑えることもできます。メモリーへのアクセスが、小さなコンテキスト範囲内に限られる場合は、alloca ルーチンを使用して、現在のスタックフレームからメモリーを割り当てることができます。このメモリーは、関数がリターンすると自動的に解放されます。

// Uses of malloc() can sometimes be replaces with alloca()
{
  …
  char *p = malloc( 256 );
  // Use the allocated memory 
  process( p );
  free( p );
  …
}
// If the memory is allocated and freed in the same routine.
{
  …
  char *p = alloca( 256 );
  // Use the allocated memory 
  process( p );
  …
}

Microsoft* では _alloca を廃止し、代わりにセキュリティーが強化されている _malloca ルーチンの使用を推奨しています。このルーチンは、要求されたサイズに応じて、スタックまたはヒープからメモリーを割り当てます。そのため、_malloca で取得したメモリーは、_freea で解放する必要があります。

スレッドごとの解放リストを使用するのも 1 つの手法です。最初に、malloc を使用してシステムヒープからメモリーを割り当てます。通常ならメモリーを解放するはずの時点で、スレッドごとのリンクリストにメモリーを追加します。スレッドが同じサイズのメモリーを再び割り当てる場合は、システムヒープに戻らずに、リンクリストに格納されている割り当てを直ちに取得することができます。

struct MyObject {
  struct MyObject *next;
  …
};
// the per-thread list of free memory objects
static __declspec(thread)
struct MyObject *freelist_MyObject = 0;
struct MyObject *
malloc_MyObject( )
{
  struct MyObject *p = freelist_MyObject;
  if (p == 0)
    return malloc( sizeof( struct MyObject ) );
  freelist_MyObject = p->next;
  return p;
}
void
free_MyObject( struct MyObject *p )
{
  p->next = freelist_MyObject;
  freelist_MyObject = p;
}

ここで紹介した手法を利用できない場合 (例えば、メモリーの割り当てと解放を行うスレッドが異なる場合) や、これらの手法でメモリー管理のボトルネックを解消できない場合は、サードパーティーのヒープ・マネージャーを使用してみると良いでしょう。インテル^® スレッディング・ビルディング・ブロック (インテル^® TBB) は、インテル^®TBB や OpenMP を使用したアプリケーションだけでなく、手動でスレッド化したアプリケーションにも使用できる、マルチスレッド化に対応したメモリー・マネージャーを提供します。

最適化にはトレードオフが伴います。ここでは、システムヒープの競合を抑えることでメモリー使用量が増加します。スレッドごとに個別のプライベート・ヒープやオブジェクト群を保持するため、ほかのスレッドはこれらの領域にアクセスすることができません。そのため、スレッドの作業量が異なる場合、スレッド間でメモリー・インバランス (ロード・インバランスのようなもの) が生じることがあります。メモリー・インバランスは、アプリケーションのワーキング・セット・サイズやメモリー使用量の増加に繋がることがあります。通常、メモリー使用量の増加によるパフォーマンスへの影響はわずかです。ただし、メモリー使用量の増加により利用可能なメモリーを使い果たした場合は、例外が発生します。この場合、アプリケーションは終了するか、ディスクへスワップします。