Почему size_t и unsigned int медленнее, чем int?

Я экспериментировал с различными целочисленными типами в проекте Visual Studio в Windows, используя простой алгоритм сортировки обмена ниже. Процессор Intel. Код был скомпилирован в Выпуске x64. Параметр оптимизации - "Максимизировать скорость (/O2)". Командная строка, соответствующая настройкам компиляции:

/permissive- /GS /GL /W3 /Gy /Zc:wchar_t /Zi /Gm- /O2 /sdl /Fd"x64\Release\vc141.pdb" /Zc:inline /fp:precise /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /errorReport:prompt /WX- /Zc:forScope /Gd /Oi /MD /Fa"x64\Release\" /EHsc /nologo /Fo"x64\Release\" /Fp"x64\Release\SpeedTestForIntegerTypes.pch" /diagnostics:classic

Сам код:

#include <ctime>
#include <vector>
#include <iostream>

void sort(int N, int A[], int WorkArray[]) // exchange sort
{
    int i, j, index, val_min;
    for (j = 0; j < N; j++)
    {
        val_min = 500000;
        for (i = j; i < N; i++)
        {
            if (A[i] < val_min)
            {
                val_min = A[i];
                index = i;
            }
        }
        WorkArray[j] = A[j];
        A[j] = val_min;
        A[index] = WorkArray[j];
    }
}

int main()
{
    std::vector<int> A(400000), WorkArray(400000);
    for(size_t k = 0; k < 400000; k++)
        A[k] = 400000 - (k+1);

    clock_t begin = clock();

    sort(400000, &A[0], &WorkArray[0]);

    clock_t end = clock();
    double sortTime = double(end - begin) / CLOCKS_PER_SEC;
    std::cout << "Sort time: " << sortTime << std::endl;
    return 0;
}

WorkArray требуется только для сохранения вектора перед сортировкой. Дело в том, что эта сортировка заняла у меня 22,3 секунды. Интересно то, что если я изменю тип int в size_t для массивов A, WorkArray (оба в std::vector и в списке аргументов функции sort), а также для val_minвремя увеличивается до 67,4! Это втрое медленнее! Новый код ниже:

#include <ctime>
#include <vector>
#include <iostream>

void sort(int N, size_t A[], size_t WorkArray[]) // exchange sort
{
    int i, j, index;
    size_t val_min;
    for (j = 0; j < N; j++)
    {
        val_min = 500000U;
        for (i = j; i < N; i++)
        {
            if (A[i] < val_min)
            {
                val_min = A[i];
                index = i;
            }
        }
        WorkArray[j] = A[j];
        A[j] = val_min;
        A[index] = WorkArray[j];
    }
}

int main()
{
    std::vector<size_t> A(400000), WorkArray(400000);
    for(size_t k = 0; k < 400000; k++)
        A[k] = 400000 - (k+1);

    clock_t begin = clock();

    sort(400000, &A[0], &WorkArray[0]);

    clock_t end = clock();
    double sortTime = double(end - begin) / CLOCKS_PER_SEC;
    std::cout << "Sort time: " << sortTime << std::endl;
    return 0;
}

Обратите внимание, что я все еще держу тип int для локальных переменных функции i, j, index, Nи так только две арифметические операции, которые i++ а также j++ должно занять одинаковое количество времени для выполнения в обоих случаях. Следовательно, это замедление связано с другими причинами. Это связано с проблемой выравнивания памяти или размерами регистров или чем-то еще?

Но самая возмутительная часть была, когда я изменился int в unsigned int, И то и другое unsigned int а также int занимают такое же количество байтов, которое составляет 4 (sizeof показало, что). Но время выполнения для unsigned int было 65,8 с! В то время как первый результат был несколько приемлем, второй полностью смущает меня! Почему существует такая значительная разница во времени, необходимая для запуска такого простого алгоритма, который даже не включает проверку знаков?

Спасибо всем за решение обоих этих вопросов. Где я могу начать читать больше об этих особенностях оптимизации аппаратного уровня? Мне не важен сам алгоритм сортировки, он приведен только для иллюстрации проблемы.

ОБНОВЛЕНИЕ: еще раз, я подчеркиваю факт, что я использую целые числа для индексов массива во всех трех случаях.

Источник

2 ответа

Решение

Проверка сгенерированной сборки на все 3 варианта (int, unsigned, size_t), большая разница в том, что в int случай петли в sort Функция развернута и использует инструкции SSE (работающие на 8 дюймах за раз), в то время как в двух других случаях она не работает ни одна. Интересно, что sort функция вызывается в int случай, в то время как он встраивается в main в двух других (вероятно, из-за увеличенного размера функции из-за развертывания цикла).

Я компилирую из командной строки, используя cl /nologo /W4 /MD /EHsc /Zi /Ox, с помощью dumpbin чтобы получить разборку, с набором инструментов Microsoft (R) C/C++ Optimizing Compiler Version 19.12.25830.2 for x64,

Я получаю время выполнения около 30 секунд для int и 100 секунд для двух других.

Источник

Я попробовал этот код в VS2017. Мне удалось воспроизвести.

Я изменил код следующим образом, чтобы время было почти таким же.

Причина, по-видимому, связана с неявным приведением индекса массива.

#include <ctime>
#include <vector>
#include <iostream>

using namespace std;

// exchange sort
template<typename elem_t, typename index_t>
void sort(index_t size, elem_t* a, elem_t* b)
{
    index_t index = 0, i, j;
    elem_t min;

    for (j = 0; j < size; j++)
    {
        min = 500000;
        for (i = j; i < size; i++)
        {
            if (a[i] < min)
            {
                min = a[i];
                index = i;
            }
        }
        b[j] = a[j];
        a[j] = min;
        a[index] = b[j];
    }
}

template<typename elem_t, typename index_t, index_t size>
void test() {
    //vector<elem_t> a(size);
    //vector<elem_t> b(size);

    elem_t a[size];
    elem_t b[size];

    for (index_t k = 0; k < size; k++)
        a[k] = (elem_t)(size - (k + 1));

    clock_t begin = clock();
    sort(size, &a[0], &b[0]);
    clock_t end = clock();

    double sortTime = double(end - begin) / CLOCKS_PER_SEC;
    cout << "Sort time: " << sortTime << endl;
}

int main()
{
    const int size = 40000;

    cout << "<size_t, int>" << endl;
    test<size_t, int, size>();
    cout << endl;

    cout << "<size_t, size_t>" << endl;
    test<size_t, size_t, size>();
    cout << endl;

    cout << "<int, int>" << endl;
    test<int, int, size>();
    cout << endl;

    cout << "<int, size_t>" << endl;
    test<int, size_t, size>();
    cout << endl;

    cout << "<uint, int>" << endl;
    test<unsigned int, int, size>();
    cout << endl;

    cout << "<uint, size_t>" << endl;
    test<unsigned int, size_t, size>();
    cout << endl;

    cout << "<uint, uint>" << endl;
    test<unsigned int, unsigned int, size>();
    cout << endl;
}

Лично я не люблю неявное кастинг. Для устранения неполадок такого рода увеличьте уровень предупреждений до максимума и устраните все предупреждения, а затем преобразуйте их в общий код. Это поможет вам определить проблему.

Результат этого кода появляется в результате различных комбинаций.

  • подписано против неподписанного: почему в C подписано int быстрее, чем unsigned int?

  • размер шрифта (int32 против int64)

  • код сборки индекса массива

  • оптимизация vC++: /O2 (максимальная оптимизация (скорость фаворита))

    • это быстро для (int / int).
Источник
Другие вопросы по тегам