Почему оператор сравнительного мода (%) часто показывает 0 затраченного времени, даже для 5000 раундов?

Я хочу получить представление о том, как быстро работает оператор модуля (%). Я установил простую программу для оценки % применения к случайно сгенерированным значениям. Время измеряется в наносекундах часами с высоким разрешением. Часто он сообщает, что прошло 0 нс. Очевидно, что ничего не происходит мгновенно, так почему же так? Если я увеличу количество раундов примерно до 50 000, обычно это займет около 1 000 000 нс. Но даже 5000 раундов всегда 0 нс. Я неправильно измеряю? Какая оптимизация делается для этого?

#include <iostream>
#include <chrono>
#include <random>

void runTest(const int rounds, const int min, const int max);

int main()
{
    std::cout << "started" << std::endl;
    runTest(5000, 1000000, 2000000);

    return 0;
}



/*IN: number of rounds to run on the test, the min and max value to choose between for operands to mod
OUT: time taken (in nanoseconds) to complete each operation on the same randomly generated numbers*/
void runTest(const int rounds, const int min, const int max)
{
    std::random_device rd;     // only used once to initialise (seed) engine
    std::mt19937 rng(rd());    // random-number engine used (Mersenne-Twister in this case)
    std::uniform_int_distribution<int> uni(min,max); // guaranteed unbiased

    std::chrono::nanoseconds durationNormalMod = std::chrono::nanoseconds::zero();
    std::chrono::nanoseconds durationFastMod = std::chrono::nanoseconds::zero();

    long long result = 0;

    for(auto i = 0; i < rounds; i++)
    {
        const int leftOperand = uni(rng);
        const int rightOperand = uni(rng);
        auto t1 = std::chrono::high_resolution_clock::now();
        long long x = (leftOperand % rightOperand);
        auto t2 = std::chrono::high_resolution_clock::now();
        //std::cout << "x: " << x << std::endl;
        result += x;
        durationNormalMod += std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1);
    }

    std::cout << "duration of %: " << durationNormalMod.count() << std::endl;
    std::cout << "result: " << result << std::endl;//preventing optimization by using result
}

Я компилирую с g++ prog.cpp -o prog.exe -O3.

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


person northerner    schedule 16.04.2020    source источник
comment
Вы ничего не делаете с результатом x - возможно, расчет был пропущен оптимизатором (проверьте сгенерированную сборку).   -  person Sander De Dycker    schedule 16.04.2020
comment
Также: 5000 итераций звучит не так уж и много.   -  person Sander De Dycker    schedule 16.04.2020
comment
Очень вероятно, что операция по модулю преобразуется в одну инструкцию на вашей платформе. Так что маловероятно, что ваш другой алгоритм будет работать лучше.   -  person Sander De Dycker    schedule 16.04.2020
comment
@SanderDeDycker, что именно я буду проверять в сборке?   -  person northerner    schedule 16.04.2020
comment
Есть ли способ убедиться, что что-то не оптимизировано, например, с помощью volatile?   -  person northerner    schedule 16.04.2020
comment
вы бы искали любые инструкции, соответствующие вычислению по модулю - вам нужно прочитать документацию по вашей платформе и / или компилятору для получения подробной информации о вашем конкретном вкусе сборки и нотации. Простой способ убедиться, что он не оптимизирован, - это использовать его (например, распечатать все значения или агрегированное значение после цикла). Очевидно, вы также захотите воспользоваться советом из приведенных ниже ответов, чтобы измерить время, которое занимает весь цикл, а не одна итерация.   -  person Sander De Dycker    schedule 16.04.2020
comment
Спасибо, я сделал, и, как я уже сказал, это использовалось.   -  person northerner    schedule 16.04.2020
comment
Если у вас есть особый случай, который, как вы подозреваете, вы могли бы сделать быстрее, вы должны измерить этот особый случай. Вполне возможно, что компилятор работает лучше - он очень хорош в особых случаях.   -  person molbdnilo    schedule 16.04.2020
comment
Чтобы убедиться, что что-то не оптимизировано: -O0. Но тогда бенчмаркинг бесполезен.   -  person Eljay    schedule 16.04.2020
comment
Каково разрешение часов высокого разрешения в вашей системе? Ваш прыжок от 0 до 1 000 000 выглядит для меня так, как будто 0 упал ниже минимально измеримого времени (и что вместо этого вы должны измерять миллисекунды, может быть, микросекунды).   -  person JaMiT    schedule 16.04.2020
comment
Микробенчмаркинг сложен: идиоматический способ оценки производительности?   -  person Peter Cordes    schedule 16.04.2020


Ответы (3)


При бенчмаркинге важно:

  1. Используйте вычисленный результат каким-либо образом. Любой результат, который никогда не использовался, и вычисления, которые привели к нему, могут и будут удалены оптимизирующим компилятором.

  2. Время не отдельного вычисления, а ряда вычислений, так что время, прошедшее между обращениями к часам, составляет порядка миллисекунд. Это связано с тем, что доступ к часам является относительно дорогостоящей операцией и значительно искажает время очень быстрых вычислений.

  3. Отключите масштабирование тактовой частоты ЦП или хотя бы прогрейте ЦП перед измерением времени.

person rustyx    schedule 16.04.2020

Часы, даже high_resolution_clock, в большинстве реализаций не имеют достаточной детализации, чтобы измерять наносекунды.

Вы должны выполнять несколько операций подряд, а общее время делить на количество повторений. У вас уже есть петля: переместите измерение времени за пределы петли. И увеличить количество повторений.

Однако это немного сложно, поскольку цикл иногда может привести к тому, что компилятор выполнит некоторую векторную операцию вместо предполагаемого тривиального повторения.

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

person eerorika    schedule 16.04.2020

Оптимизации выполняются по так называемому правилу «как если бы». Компилятору разрешено выполнять любые преобразования вашего кода, если наблюдаемое поведение остается прежним. Поскольку вы не используете результат вычислений, нет наблюдаемого поведения, которое могло бы измениться, если вычисления вообще не выполняются. Измеренное время не считается наблюдаемым поведением (см. здесь).

person 463035818_is_not_a_number    schedule 16.04.2020
comment
Я не думаю, что это то, что происходит. Почему запуск большего количества итераций приведет к ненулевому времени, если оно было полностью оптимизировано? Также в другой версии я сделал что-то простое с результатом, и это не имело значения. - person northerner; 16.04.2020
comment
@northerner Ваше время измерения времени находится в цикле, поэтому вы измеряете время, необходимое для измерения времени, и складываете измеренные нули вместе. Редактировать: на самом деле добавление выходит за рамки измерения, но накладные расходы измерения все еще существуют. - person eerorika; 16.04.2020
comment
@northerner вот что может случиться. 1,000,000ns вероятно мало по сравнению с точностью ваших часов. Также 50000 довольно маленький - person 463035818_is_not_a_number; 16.04.2020
comment
@northerner и что сказала ээрорика. Компилятор может оптимизировать вычисления, но не измерение времени, поэтому вы в основном добавляете шум 50000 измерений. Если вы получаете шум ~ 100 нс при каждом отдельном измерении (что было бы неплохо), сумма уже составляет 5000000 нс ... - person 463035818_is_not_a_number; 16.04.2020
comment
@northerner вы можете почувствовать, что происходит, удалив весь код и измерив только время пустого цикла. Я не удивлюсь, если вы получите очень похожие результаты. - person 463035818_is_not_a_number; 16.04.2020