c++ - 为什么我的 C++ 代码比 LeetCode 上的 C 代码慢三倍？

Question

已结束。此问题需要 debugging details .它目前不接受答案。

---

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem .这将有助于其他人回答问题。

关闭 7 年前。

Improve this question

我一直在做一些 LeetCode problems ，我注意到 C 解决方案比 C++ 中完全相同的解决方案快几倍。例如:

更新了几个更简单的例子:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. (Link to question on LeetCode)

我的 C 语言解决方案在 3 毫秒内运行:

int searchInsert(int A[], int n, int target) {
    int left = 0;
    int right = n;
    int mid = 0;
    while (left<right) {
        mid = (left + right) / 2;
        if (A[mid]<target) {
            left = mid + 1;
        }
        else if (A[mid]>target) {
            right = mid;
        }
        else {
            return mid;
        }
    }
    return left;
}

我的其他 C++ 解决方案，完全相同，但作为解决方案类的成员函数在 13 毫秒内运行:

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int left = 0;
        int right = n;
        int mid = 0;
        while (left<right) {
            mid = (left + right) / 2;
            if (A[mid]<target) {
                left = mid + 1;
            }
            else if (A[mid]>target) {
                right = mid;
            }
            else {
                return mid;
            }
        }
        return left;
    }
};

更简单的例子:

Reverse the digits of an integer. Return 0 if the result will overflow. (Link to question on LeetCode)

C 版本在 6 毫秒内运行:

int reverse(int x) {
    long rev = x % 10;
    x /= 10;
    while (x != 0) {
        rev *= 10L;
        rev += x % 10;
        x /= 10;
        if (rev>(-1U >> 1) || rev < (1 << 31)) {
            return 0;
        }
    }
    return rev;
}

和 C++ 版本完全一样，只是作为解决方案类的成员函数，运行时间为 19 毫秒:

class Solution {
public:
    int reverse(int x) {
        long rev = x % 10;
        x /= 10;
        while (x != 0) {
            rev *= 10L;
            rev += x % 10;
            x /= 10;
            if (rev>(-1U >> 1) || rev < (1 << 31)) {
                return 0;
            }
        }
        return rev;
    }
};

我看到如果 LeetCode 测试系统没有在启用优化的情况下编译代码，那么在原始示例中使用 vector 的 vector 作为 2D 数组会有相当大的开销。但是上面更简单的例子不应该遇到这个问题，因为数据结构非常原始，尤其是在第二种情况下，你所拥有的只是长整数或整数算术。这仍然慢了三倍。

我开始认为 LeetCode 通常进行基准测试的方式可能会发生一些奇怪的事情，因为即使在整数反转问题的 C 版本中，仅替换行就会导致运行时间大幅增加 if (rev>(-1U >> 1) || rev < (1 << 31)) {和 if (rev>INT_MAX || rev < INT_MIN) {

现在，我想必须 #include<limits.h>可能与此有关，但这个简单的更改将执行时间从 6 毫秒提高到 19 毫秒，这似乎有点极端。

Answer 1

最近我看到了vector<vector<int>>在 C++ 中做二维数组的建议很多，我一直在向人们指出为什么这真的不是一个好主意。知道何时将临时代码拼凑在一起是一个方便的技巧，但是(几乎)从来没有任何理由将它用于真正的代码。 right thing to do是使用一个包装连续内存块的类。

所以我的第一 react 可能是指出这是差异的可能来源。但是，您也在使用 int**在 C 版本中，这通常表示与 vector<vector<int>> 完全相同的问题.

所以我决定只比较这两种解决方案。

http://coliru.stacked-crooked.com/a/fa8441cc5baa0391

6468424
6588511

这是“C 版本”与“C++ 版本”所用的时间(以纳秒为单位)。

我的结果与您描述的差异不符。然后我想到检查人们在进行基准测试时常犯的错误

http://coliru.stacked-crooked.com/a/e57d791876b9252b

18386695
42400612

请注意，第一个示例中的 -O3 标志已变为 -O0，这会禁用优化。

结论:您可能在比较未优化的可执行文件。

C++ 支持构建不需要开销的丰富抽象，但消除开销确实需要对代码的“可调试性”造成严重破坏的某些代码转换。

这意味着调试构建避免了这些转换，因此 C++ 调试构建通常比 C 样式代码的调试构建慢，因为 C 样式代码不使用太多抽象。在计时时，例如使用函数调用代替简单存储指令的机器代码，看到上述 130% 的减速一点也不奇怪。

---

有些代码确实需要优化，以便即使在调试时也能获得合理的性能，因此编译器通常会提供一种应用一些优化的模式，这些优化不会给调试器带来太多麻烦。 Clang 和 gcc 使用 -O1为此，您可以看到，即使是这种级别的优化，也基本上消除了该程序中 C 样式代码和更多 C++ 样式代码之间的差距:

http://coliru.stacked-crooked.com/a/13967ebcfcfa4073

8389992
8196935

---

更新:

在后面的示例中，优化不应该产生影响，因为 C++ 没有使用 C 版本所做的任何抽象。我猜想对此的解释是这些示例是使用不同的编译器或其他一些不同的编译器选项编译的。在不知道编译是如何完成的情况下，我会说比较这些运行时数字是没有意义的； LeetCode 显然没有进行苹果与苹果的比较。