java - 如何解决恒定时间操作的循环瓶颈？

Question

为了乐趣而开发与规则无关的扑克模拟器。测试枚举中的瓶颈，对于总是从“唯一”数组中拉出的手，我发现了一个有趣的瓶颈。我测量了运行每个变体的平均计算时间低于 1,000,000,000 次，然后重复 100 次，以让 JIT 和 Hotspot 发挥它们的魔力。我发现

public int getRank7(int ... cards) {
  int q = (cards[0] >> 16) | (cards[1] >> 16) | (cards[2] >> 16) | (cards[3] >> 16) | (cards[4] >> 16) | (cards[5] >> 16) | (cards[6] >> 16);
  int product = ((cards[0] & 0xFF) * (cards[1] & 0xFF) * (cards[2] & 0xFF) * (cards[3] & 0xFF) * (cards[4] & 0xFF) * (cards[5] & 0xFF) * (cards[6] & 0xFF));
  if(flushes[q] > 0) return flushes[q];
  if(unique[q] > 0) return unique[q];
  int x = Arrays.binarySearch(products, product);
  return rankings[x];
}

和

public int getRank(int ... cards) {
  int q = 0;
  long product = 1;
  for(int c : cards) {
    q |= (c >> 16);
    product *= (c & 0xFF);
  }
  if(flushes[q] > 0) return flushes[q];
  if(unique[q] > 0) return unique[q];
  int x = Arrays.binarySearch(products, product);
  return rankings[x];
}

问题肯定是 for 循环，而不是在函数顶部添加处理乘法。我对此有点困惑，因为我在每个场景中运行相同数量的操作......我意识到我在这个函数中总是有 6 张或更多卡片，所以我通过将它更改为

public int getRank(int c0, int c1, int c2, int c3, int c4, int c5, int ... cards)

但随着卡片数量的增加，我将遇到同样的瓶颈。有什么方法可以解决这个问题，如果没有，有人可以向我解释为什么相同数量的操作的 for 循环要慢得多吗？

Answer 1

我认为您会发现最大的区别在于分支。您的 for 循环场景需要在 for 循环的每次迭代中进行检查和条件分支。您的 CPU 将尝试预测将采用哪个分支，并相应地流水线指令，但是当它预测错误时(每个函数调用至少一次，当循环终止时)，流水线停止，这是非常昂贵的。

要尝试的一件事是使用固定上限的常规 for 循环(而不是基于数组长度的循环)； Java JRE 可能会展开这样一个循环，这将导致与您的更高效版本相同的操作顺序。