在 C++ 中更快执行两个程序的可能解释（Python 比较）？

Question

更新：C++ 程序（如下所示）编译时没有附加标志，即 g++ program.cpp。然而，提高优化级别并不会改变蛮力运行速度比记忆技术快的事实（在我的机器上是 0.1 秒 VS 1 秒）。

上下文

我尝试计算最长Collatz sequence的数字（<100万）。我写了一个蛮力算法并将其与建议的优化程序（基本上使用记忆）进行了比较。

我的问题是：暴力执行比 C++ 中假定的优化（记忆）版本更快的原因可能是什么？

低于我在我的机器（Macbook Air）上的比较；时间在评论中程序代码的开头。

C++（暴力破解）

/**
 * runs in 1 second
 */

#include <iostream>
#include <vector>

unsigned long long nextSequence(unsigned long long n)
{
  if (n % 2 == 0)
    return n / 2;
  else
  {
    return 3 * n + 1;
  }
}

int main()
{
  int max_counter = 0;
  unsigned long long result;
  for (size_t i = 1; i < 1000000; i++)
  {
    int counter = 1;
    unsigned long long n = i;
    while (n != 1)
    {
      n = nextSequence(n);
      counter++;
    }
    if (counter > max_counter)
    {
      max_counter = counter;
      result = i;
    }
  }

  std::cout << result << " has " << max_counter << " sequences." << std::endl;

  return 0;
}

C++（记忆）

/**
 * runs in 2-3 seconds 
 */

#include <iostream>
#include <unordered_map>

int countSequence(uint64_t n, std::unordered_map<uint64_t, uint64_t> &cache)
{
  if (cache.count(n) == 1)
    return cache[n];

  if (n % 2 == 0)
    cache[n] = 1 + countSequence(n / 2, cache);
  else
    cache[n] = 2 + countSequence((3 * n + 1) / 2, cache);

  return cache[n];
}

int main()
{
  uint64_t max_counter = 0;
  uint64_t result;
  std::unordered_map<uint64_t, uint64_t> cache;
  cache[1] = 1;
  for (uint64_t i = 500000; i < 1000000; i++)
  {
    if (countSequence(i, cache) > max_counter)
    {
      max_counter = countSequence(i, cache);
      result = i;
    }
  }

  std::cout << result << std::endl;

  return 0;
}

在 Python 中，记忆技术确实运行得更快。

Python（记忆）

# runs in 1.5 seconds

def countChain(n):
    if n in values:
        return values[n]
    if n % 2 == 0:
        values[n] = 1 + countChain(n / 2)
    else:
        values[n] = 2 + countChain((3 * n + 1) / 2)
    return values[n]


values = {1: 1}
longest_chain = 0
answer = -1

for number in range(500000, 1000000):
    if countChain(number) > longest_chain:
        longest_chain = countChain(number)
        answer = number

print(answer)

Python（暴力破解）

# runs in 30 seconds


def countChain(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1 + countChain(n / 2)
    return 2 + countChain((3 * n + 1) / 2)


longest_chain = 0
answer = -1

for number in range(1, 1000000):
    temp = countChain(number)
    if temp > longest_chain:
        longest_chain = temp
        answer = number

print(answer)

Answer 1

我知道你的问题是关于两个 C++ 变体之间的区别，而不是编译的 C++ 和解释的 python 之间的区别。果断地回答它需要在打开优化的情况下编译代码并分析其执行情况。并明确编译器目标是 64 位还是 32 位。

但是考虑到两个版本的 C++ 代码之间的数量级，快速检查已经表明您的记忆化消耗的资源多于获得的资源。

这里一个重要的性能瓶颈是无序映射的内存管理。一个unordered_map works with buckets of items。映射在必要时调整桶的数量，但这需要内存分配（并且可能移动内存块，具体取决于桶的实现方式）。

现在，如果您在缓存初始化之后和显示结果之前添加以下语句，您会看到 number of buckets allocated 发生了巨大的变化：

std::cout << "Bucket count: "<<cache.bucket_count()<<"/"<<cache.max_bucket_count()<<std::endl;

为避免与此相关的开销，您可以在构造时预先分配桶数：

std::unordered_map<uint64_t, uint64_t> cache(3000000);

在 ideone 上执行此操作以进行小型非正式测试，节省了近 50% 的性能。

但尽管如此...在 unordered_map 中存储和查找对象需要计算由大量算术运算组成的哈希码。所以我猜想这些操作只是比进行蛮力计算更重。

Answer 2

主内存访问大大比计算慢，以至于当需要关心时，您应该在极少数（cpu-模型-dependent) 从 I/O 或网络设备检索到的 meg。

与整数操作相比，即使从 L1 获取数据也很昂贵。

很久很久以前，这不是真的。几十年来，计算和内存访问至少处于同一水平，因为晶体管预算中根本没有足够的空间来制造足够大的快速缓存来支付费用。

所以人们计算了 CPU 次操作，并假设内存或多或少可以跟上。

如今，它只是……不能。 CPU 缓存未命中的惩罚是数百整数操作，并且您的百万 16 字节条目哈希映射几乎可以保证不仅会破坏 cpu 的内存高速缓存以及 TLB，它使延迟损失从痛苦变为毁灭性。

在 C++ 中更快执行两个程序的可能解释（Python 比较）？

Possible explanation for faster execution of two programs in C++ (with Python comparison)?

python

c++

algorithm

performance

execution-time

上下文

C++（暴力破解）

C++（记忆）

Python（记忆）

Python（暴力破解）