Muchas veces nos hemos encontrado con la necesidad de realizar mediciones de rendimiento en el código, ya sea medir el tiempo de duración de un proceso, función, etc. Desde c++11 se ha incorporado una librería estándar llamada chrono. Esta librería es bastante útil porque permite calcular la duración de bloques de código tomando referencias de tiempo para posteriormente realizar la diferencia y obtener la duración con bastante granularidad.

Dicha librería puede ser un poco engorrosa de trabajar debido al boilerplate que debemos escribir para acceder a los timestamps del reloj, los tipos de cada variable, etc. Podemos hacer uso de la declaración de variables con auto y así evitar tener que escribir todos los tipos.

Además, si metemos los lambdas en la ecuación, podemos tener nuestra propia librería para realizar mediciones de cualquier parte del código de una forma bastante simple y sencilla. Vamos al código =)

template <class Duration, class Function>
auto measure(Function func)
{
    auto start = std::chrono::high_resolution_clock::now();
    func();
    auto stop = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<Duration>(stop - start).count();
}

auto code_to_measure = []() {
    //long running operation
};

auto duration_ms = measure<std::chrono::milliseconds>(code_to_measure);
auto duration_nanoseconds = measure<std::chrono::nanoseconds>(code_to_measure);
auto duration_microseconds = measure<std::chrono::microseconds>(code_to_measure);
//the other time units

Donde std::chrono::milliseconds es un tipo de esta lista

Búsqueda binaria vs Búsqueda lineal

Como ejemplo tomaremos el caso de búsqueda binaria contra búsqueda lineal. Compilando con todas las optimizaciones. Nota: Se puede compilar desde c++17

g++ -Wall -O3 -std=c++20 main.cc -o main.out

include <iostream>
#include <vector>
#include <chrono>
#include <algorithm> //for generate_n

using namespace std;;

template <class Duration, class Function>
auto measure(Function func)
{
    auto start = std::chrono::high_resolution_clock::now();
    func();
    auto stop = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<Duration>(stop - start).count();
}

int recursive_binary_search(const int num_to_search, 
                  const std::vector<int>& vector,
                  int left,
                  int right) {
    const int mid = left + (right - left) / 2;
    if (right >= left) {
        if (vector[mid] == num_to_search) {
            return mid;
        }
        else if (vector[mid] > num_to_search) {
            return recursive_binary_search(num_to_search, vector, left, mid - 1);
        }
        else if (vector[mid] < num_to_search) {
            return recursive_binary_search(num_to_search, vector, mid + 1, right);
        }
    }
    return -1;
}

int iterative_binary_search(const int num_to_search,
                            const std::vector<int>& vector,
                            int left,
                            int right)
{
    while (right >= left) {
        int mid = left + (right - left) / 2;
        if (vector[mid] == num_to_search) {
            return mid;
        }
        else if (vector[mid] > num_to_search) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    return -1;
}

int main(void)
{
    const int MAX_LEN = 50'000;
    const int NUM_TO_SEARCH = 40'000;
    std::vector<int> vector;

    int i = 0;
    std::generate_n(std::back_inserter(vector), MAX_LEN, [&]() {
            return i++;
    });

    auto perf_recursive_binary_search = [=]() {
        const std::string fname = "perf_recursive_binary_search";
        int index = recursive_binary_search(NUM_TO_SEARCH, vector, 0, vector.size());
        if (index < 0) {
            std::cout << fname << " error" << std::endl;
            return;
        }
        //std::cout << fname << " index= " << index << std::endl;
    };

    auto perf_iterative_binary_search = [=]() {
        const std::string fname = "perf_iterative_binary_search";
        int index = iterative_binary_search(NUM_TO_SEARCH, vector, 0, vector.size());
        if (index < 0) {
            std::cout << fname << " error " << std::endl;
        }
        //std::cout << fname << " index = " << index << std::endl;
    };
    
    auto perf_linear_search = [=]() {
        const std::string fname = "perf_linear_search";
        int index = 0;
        bool found = false;
        for (auto number: vector) {
            if (number == NUM_TO_SEARCH) {
                found = true;
                break;
            }
            index++;
        }
        if (!found) {
            std::cout << fname << " error" << std::endl;
        }
        else {
            //std::cout << fname << " index=" << index << std::endl;
        }
    };

    auto perf_std_binary_search = [&]() {
        bool found = std::binary_search(vector.begin(), vector.end(), NUM_TO_SEARCH);
        if (!found) {
            std::cout << "no found" << std::endl;
        }
    };

    //using microseconds = std::chrono::microseconds;
    using nanoseconds = std::chrono::nanoseconds;

    auto duration = measure<nanoseconds>(perf_recursive_binary_search);
    std::cout << "=> recursive_binary_search took " << duration << "
    nanoseconds" << std::endl;

    duration = measure<nanoseconds>(perf_linear_search);
    std::cout << "=> perf_linear_search took " << duration << " nanoseconds" << std::endl;

    duration = measure<nanoseconds>(perf_iterative_binary_search);
    std::cout << "=> iterative_binary_search took " << duration 
    << " nanoseconds" << std::endl;

    duration = measure<nanoseconds>(perf_std_binary_search);
    std::cout << "=> perf_std_binary_search took " << duration 
    << " nanoseconds" << std::endl;

    return 0;
}

Que da como resultado en gcc:

=> recursive_binary_search took 3354 nanoseconds
=> iterative_binary_search took 834 nanoseconds
=> perf_std_binary_search took 357 nanoseconds
=> perf_linear_search took 31742 nanoseconds

Y en clang:

clang -Wall -O3 -std=c++20 main.cc -o main.out

=> recursive_binary_search took 1960 nanoseconds
=> iterative_binary_search took 1062 nanoseconds
=> perf_std_binary_search took 347 nanoseconds
=> perf_linear_search took 24411 nanoseconds