c - 指针追踪在此基准测试中的工作方式

Question

尝试了解指针追踪在以下基准测试中的工作方式(基本上是访问模式):

https://github.com/google/multichase/blob/master/multichase.c

对于简单的追逐:

static void chase_simple(per_thread_t *t) {
  void *p = t->x.cycle[0]; ----> here p is pointing to initial address 

  do {
    x200(p = *(void **)p;) ----> didn't get this statement, is x200 some compiler built-in ?
  } while (__sync_add_and_fetch(&t->x.count, 200));

  // we never actually reach here, but the compiler doesn't know that
  t->x.dummy = (uintptr_t)p;
}

在代码中的何处以及如何使访问模式变得有些不可预测，以至于 H/W 预取器无法正确猜测？

Answer 1

我假设 x200 是一个 CPP 宏，它重复其操作数 200 次，用于循环展开。将 x200 读作“乘以 200”。可能的实现:

#define x5(x)  x x x x x
...
#define x200(x)  x100(x) x100(x)

摊销原子 RMW 的成本以增加 t->x.count 是有意义的。

您可以通过查看 C 预处理器输出来检查，例如gcc -E，或在包含的文件中搜索宏定义。

---

重复的实际陈述，p = *(void **)p;，只是取消引用一个指针以获取另一个指针。如果你有 struct foo *p，你通常会有 p = p->next;，但是只有 void* 你需要一个强制转换以使编译器满意并获得汇编指令，如 mov rax, [rax]。

如果没有可以包含指向相同结构类型的指针的内存的结构，取消引用指针将改变类型。 C 没有办法声明一个无限间接指针，当你取消引用它时，它只会产生相同的类型。

---

where and how in the code, access pattern is made somewhat unpredictable so that H/W prefetcher doesn't guess it properly?

在这个函数中没有任何地方；它只是遍历现有的链表。

查找分配空间并将指针存储到其中的代码。可能分配为一个大数组，因此它可以控制布局，这与它分配许多小 malloc 不同。整数 0..n-1 的随机洗牌可以映射转换为指向指针的指针数组。或类似的东西;也许您需要反转该映射以确保没有短周期。或者可能有一些更简单的方法来生成一个链表，该链表以随机顺序覆盖所有槽，最后一个元素指向第一个，因此它是一个闭环，可以根据需要迭代多次。