c++ - メンバー配列アクセスの最適化 (mov 命令)

Question

パフォーマンス プロファイラー レポートの一部を次に示します。

for (node* p = array[index]; p != NULL; p = p->next )
   52,55 :           cb40a:       mov    (%edi,%edx,4),%ebp

ご覧のとおり、その関数で費やされる時間の半分は、「p = array[index]」アクセスを表す特定の命令に費やされます (%edi は「this」ポインター、%edx は計算されたインデックス)。

1. なぜそんなに時間がかかるのですか？ループ内には呼び出しと比較がありますが、ほとんどの時間は、一度だけ実行される単純な mov に費やされます。通常、このリストにはいくつかの要素しか含まれていないため、ループ本体にはそれほど時間がかからないと思いますが、それでも...
2. それを最適化する方法は？

配列へのアクセスは 1 回だけ行われ、関数はそこから開始要素を取得します。通常、関数はノード データをキーと比較し、比較が失敗した場合は "p" または NULL を返します。つまり、ほとんどの場合、p->next は NULL です。

array[index] と p->next の 2 回だけメモリ アクセスが発生すると仮定しても、最初のアクセスが 2 番目のアクセスよりもはるかに遅いのはなぜでしょうか (これは関数の約 5% です)。

これがキャッシュの問題である場合、なぜそれが発生するのか、可能な解決策を見つける方法 (つまり、メモリ アクセスを再配置するなど) を知りたいと思います。

完全な機能 (種類):

node* list::find(int key)
{
  if (!this->array) return 0;
  node* dummy = 0;
  int index = calcindex(key);
  for (node* p = this->array[index]; p != NULL; p = p->next)
  {
    if (p->key() == key && check(p->data, key))
      return p;
    dummy = p; // forgot to remove this stuff, probably optimized away
  }
  return 0;
}

ここで key() と compare() は単純なインライン関数です。