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

Question

更新：C++程序（如下图）是编译的，没有附加的标志，即^ {CD1>}。然而，提高优化水平并不能改变这样一个事实：暴力比记忆技术运行得更快（在我的机器上是0.1秒对1秒）。你知道吗

上下文

我试图用最长的Collatz sequence来计算数字（<；100万）。我编写了一个暴力算法，并将其与建议的优化程序（基本上使用记忆化）进行了比较。你知道吗

< >我的问题是：什么是蛮力比C++中优化的（记忆化）版本更快的原因？

下面是我在我的机器（macbookair）上所做的比较；时间在程序代码开头的注释中。你知道吗

< H2> C++（蛮力）< /H2>

/**
 * 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;
}

< H2> C++（记忆化）< /H2>

/**
 * 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

主存访问比计算要慢得多，以至于在需要注意的时候，您应该将通过极少数（取决于cpu型号）meg的任何内容视为从I/O或网络设备检索的内容。你知道吗

与整数操作相比，甚至从L1获取也很昂贵。你知道吗

很久很久以前，这不是真的。计算和内存访问至少在几十年里是一致的，因为晶体管预算中没有足够的空间来制造足够大的高速缓存。你知道吗

因此，人们计算CPU操作，只是假设内存可以或多或少跟上。你知道吗

现在，它只是…不可能。CPU缓存未命中的惩罚是整数操作的数百，而且您的百万16字节哈希映射几乎保证不仅会破坏CPU的内存缓存，还会破坏TLB，从而使延迟损失从痛苦到毁灭。你知道吗

Answer 2

<>我知道你的问题是关于两个C++变量之间的区别，而不是在C++ C++和解释的python之间的区别。要果断地回答这个问题，需要在编译代码时启用优化并分析其执行情况。以及编译器目标是64位还是32位的清晰性。你知道吗

但是，C++代码的两个版本之间的数量级，快速检查已经表明，你的记忆化消耗的资源比它使你获得的更多。你知道吗

这里一个重要的性能瓶颈是无序映射的内存管理。^{}与buckets of items一起工作。map会在必要时调整bucket的数量，但这需要内存分配（并可能移动内存块，具体取决于bucket的实现方式）。你知道吗

现在，如果您在初始化缓存之后，在显示结果之前添加以下语句，您将看到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中存储和查找对象需要计算由大量算术运算组成的哈希码。所以我猜这些运算比暴力计算要重。你知道吗