Тестирование скорости алгоритмов. Но как?

В настоящее время я тестирую различные алгоритмы, которые определяют, является ли целое число реальным квадратом или нет. Во время моего исследования я нашел этот вопрос в SOF: Самый быстрый способ определить, является ли квадратный корень целого числа целым числом

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

bool istQuadratSimple(int64 x)
{
    int32 tst = (int32)sqrt(x);
    return tst*tst == x;
}

На самом деле работает быстрее, чем тот, который предоставил А. Рекс в вопросе, который я опубликовал. Я использовал объект NS-Timer для этого тестирования, печатая свои результаты с помощью NSLog.

Теперь мой вопрос: Как выполняется профессиональное тестирование скорости? Как я могу достичь эквивалентных результатов, указанных в вопросе, который я опубликовал выше?

3 2
profiling performance benchmarking micro-optimization

3 ответа:

Проблема с вызовом только этой функции в цикле заключается в том, что все будет находиться в кэше (как данные, так и инструкции). Вы не станете измерять ничего разумного; я не стану этого делать.

Учитывая, насколько мала эта функция, я бы попытался посмотреть на сгенерированный ассемблерный код этой функции и другой, и я бы попытался рассуждать на основе ассемблерного кода (количество инструкций и стоимость отдельных инструкций , например образец). К сожалению, он работает только в тривиальных / почти тривиальных случаях. Например, если коды сборки идентичны, то вы знаете, что нет никакой разницы, вам не нужно ничего измерять. Или если один код похож на другой плюс дополнительные инструкции; в этом случае вы знаете, что более длинный занимает больше времени для выполнения. А тут еще и не совсем понятные случаи... : (
(Смотрите обновление ниже.)

Вы можете получить сборку с флагами -S -emit-llvm из clang и с помощью -S флаг из gcc.

Надеюсь, что это поможет.

UPDATE: ответ на вопрос Пратека в комментарии "есть ли способ определить скорость одного конкретного алгоритма?"

Да, это возможно, но это становится ужасно сложным очень быстро. Короче говоря, игнорирование сложности современных процессоров и простое накопление некоторой предопределенной стоимости, связанной с инструкциями, может привести к очень и очень неточным результатам (the оценка с коэффициентом 100, в том числе из-за кэша и конвейера). Если вы попытаетесь учесть сложность современных процессоров, иерархический кэш, конвейер и т. д. все становится очень трудным. См., например, прогнозирование времени выполнения в наихудшем случае .

Если вы не находитесь в ясной ситуации (тривиальный / почти тривиальный случай), например, сгенерированные коды сборки идентичны или один похож на другой плюс несколько инструкций, это также сложно сравнивать алгоритмы, основанные на их сгенерированной сборке.

Однако здесь показана простая функция из двух строк, и для этого может помочь просмотр сборки. Отсюда и мой ответ.
1

Я не уверен, есть ли какой-либо профессиональный способ проверить скорость (если есть, дайте мне знать). Для метода, который вы указали в своем вопросе, я бы, вероятно, сделал что-то это это на java.

package Programs;

import java.math.BigDecimal;
import java.math.RoundingMode;

public class SquareRootInteger {

    public static boolean isPerfectSquare(long n) {
        if (n < 0)
            return false;

        long tst = (long) (Math.sqrt(n) + 0.5);
        return tst * tst == n;
    }

    public static void main(String[] args) {
        long iterator = 1;
        int precision = 10;
        long startTime = System.nanoTime(); //Getting systems time before calling the isPerfectSquare method repeatedly 
        while (iterator < 1000000000) {
            isPerfectSquare(iterator);
            iterator++;
        }
        long endTime = System.nanoTime(); // Getting system time after the 1000000000 executions of isPerfectSquare method
        long duration = endTime - startTime;
        BigDecimal dur = new BigDecimal(duration);
        BigDecimal iter = new BigDecimal(iterator);
        System.out.println("Speed "
                + dur.divide(iter, precision, RoundingMode.HALF_UP).toString()
                + " nano secs"); // Getting average time taken for 1 execution of method.

    }
}

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

UPDATE : - поскольку OP может быть неудобно с java, я добавил комментарии в код, чтобы передать идею более ясно. И для голосования вниз я был бы очень признателен, если бы я может получить конструктивную обратную связь о том, почему это было понижено. Спасибо!!

1
    Запишите значение времени до вашего массового расчета и значение после него. Разница заключается во времени выполнения.
  1. напишите сценарий оболочки, в котором вы будете запускать программу. И время бега ./xxx.sh-чтобы получить его, нужно время.
0