Почему мой код на С++ в три раза медленнее, чем эквивалент C на LeetCode?

Я выполнял некоторые проблемы LeetCode, и я замечаю, что решения C в два раза быстрее, чем те же самые вещь в С++. Например:

Обновлено с помощью нескольких простых примеров:

Учитывая отсортированный массив и целевое значение, верните индекс, если цель найдена. Если нет, верните индекс, где он был бы, если бы он был вставлен по порядку. Вы не можете принимать дубликаты в массиве. (Ссылка на вопрос о LeetCode)

Мое решение в C работает в 3 ms:

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

Мое другое решение на С++, точно такое же, но как функция-член класса Solution, запускается в 13 ms:

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

Даже более простой пример:

Обозначьте цифры целого числа. Возвращает 0, если результат будет переполняться. (Ссылка на вопрос о LeetCode)

Версия C работает в формате 6 ms:

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

И версия С++ точно такая же, как и функция-член класса Solution, и работает для 19 ms:

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

Я вижу, как будут значительные накладные расходы от использования вектора вектора в качестве 2D-массива в исходном примере, если система тестирования LeetCode не компилирует код с включенной оптимизацией. Но более простые примеры выше не должны страдать от этой проблемы, потому что структуры данных довольно сырые, особенно во втором случае, когда все, что у вас есть, - это длинная или целая арифметика. Это еще медленнее в три раза.

Я начинаю думать, что может произойти что-то странное с тем, как LeetCode делает бенчмаркинг вообще, потому что даже в C-версии целочисленной проблемы с обращением вы получаете огромный бамп в процессе работы от просто замены строки   if (rev > (- 1U → 1) || rev < (1 < 31)) { с   if (rev > INT_MAX || rev < INT_MIN) {

Теперь я полагаю, что иметь значение #include<limits.h> может иметь какое-то отношение к этому, но кажется немного экстремальным, что это простое изменение приводит к сокращению времени выполнения всего от 6 ms до 19 ms.

Ответы

Ответ 1

В последнее время я много видел предложение vector<vector<int>> для создания 2d-массивов на С++, и я указывал людям, почему это действительно не очень хорошая идея. Это удобный трюк, чтобы узнать, когда шлепает временный код, но там (почти) никогда не было причин когда-либо использовать его для реального кода. правильная вещь - использовать класс, который обертывает непрерывный блок памяти.

Итак, моя первая реакция могла бы указывать на это как на возможный источник несоответствия. Однако вы также используете int** в версии C, что обычно является признаком той же самой проблемы, что и vector<vector<int>>.

Поэтому вместо этого я решил просто сравнить два решения.

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

6468424
6588511

Это время, затраченное версией "C" на "С++-версию" в наносекундах.

Мои результаты не показывают ничего похожего на несоответствие, которое вы описываете. Затем мне пришло в голову проверить общую ошибку, которую люди совершают при бенчмаркинге

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

18386695
42400612

Обратите внимание, что флаг -O3 из первого примера стал -O0, что отключает оптимизацию.

Заключение: вы, вероятно, сравниваете неоптимизированные исполняемые файлы.

С++ поддерживает создание богатых абстракций, которые не требуют накладных расходов, но устранение накладных расходов требует определенных преобразований кода, которые несут хаос с "отлаживаемостью" кода.

Это означает, что отладочные сборки избегают этих преобразований, поэтому сборки отладки С++ часто медленнее, чем отладочные сборки кода стиля C, потому что код стиля C просто не использует много абстракции. Наблюдение 130-процентного замедления, такого как приведенное выше, вовсе не удивительно, когда время, например, машинный код, который использует вызовы функций вместо простых инструкций магазина.

Некоторый код действительно нуждается в оптимизации, чтобы иметь разумную производительность даже для отладки, поэтому компиляторы часто предлагают режим, который применяет некоторые оптимизации, которые не вызывают слишком больших проблем для отладчиков. Clang и gcc используют -O1 для этого, и вы можете видеть, что даже этот уровень оптимизации существенно устраняет пробел в этой программе между кодом стиля C и кодом стиля С++:

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

8389992
8196935

Update:

В этих более поздних примерах оптимизация не должна иметь значения, поскольку С++ не использует абстракции, кроме того, что делает версия C. Я предполагаю, что объяснение этого заключается в том, что примеры компилируются с разными компиляторами или с некоторыми другими вариантами компилятора. Не зная, как выполняется компиляция, я бы сказал, что нет смысла сравнивать эти числа во время выполнения; LeetCode явно не производит сравнение яблок с яблоками.

Ответ 2

Вы используете вектор вектора в своем фрагменте кода на С++. Векторы представляют собой контейнеры последовательностей в С++, которые похожи на массивы, которые могут меняться по размеру. Вместо vector<vector<int>>, если вы используете статически распределенные массивы, это будет лучше. Вы можете использовать свой собственный класс Array, а также с перегрузкой оператора [], но вектор имеет больше накладных расходов, поскольку он динамически изменяет размер, когда вы добавляете больше элементов, чем его первоначальный размер. В С++ вы используете вызов по ссылке, чтобы еще больше сократить время, если вы сравните это с C. С++ должен работать еще быстрее, если он хорошо написан.