0

这是性能分析器报告的一部分:

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. 如何优化它?

数组访问只发生一次,函数从中获取起始元素。通常,该函数最终会将节点数据与键进行比较,如果比较失败,则返回“p”或 NULL。即大多数时候p->next 是NULL。

即使我们假设内存访问只发生两次:在 array[index] 和 p->next 中,那么为什么第一个比第二个慢得多(大约是函数的 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() 是简单的内联函数。

4

0 回答 0