c++ - pseudocodigo - programacion android pdf 2018

Cómo encontrar la eficiencia en tiempo de ejecución de un código C++

Question

Estoy tratando de encontrar la eficiencia de un programa que he publicado recientemente en stackoverflow.

Cómo eliminar de manera eficiente elementos de un vector dado otro vector

Para comparar la eficiencia de mi código con otras respuestas, estoy usando el objeto chrono .

¿Es una forma correcta de verificar la eficiencia del tiempo de ejecución?

Si no, entonces por favor sugiera una manera de hacerlo con un ejemplo.

Código de Coliru

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <ctime>
using namespace std;

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    if(!vDestination.empty() && !vSource.empty())
    {
        for(auto i: vSource) {
            vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end());
        }
    }
}

int main() {
    vector<int> v1={1,2,3};
    vector<int> v2={4,5,6};
    vector<int> v3={1,2,3,4,5,6,7,8,9};
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    remove_elements(v3,v1);
    remove_elements(v3,v2);
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now();
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl;
    for(auto i:v3)
        cout << i << endl;
    return 0;
}

Salida

Time difference = 1472
7
8
9

Answer 1

¿Es una forma correcta de verificar la eficiencia del tiempo de ejecución?

Parece que no es la mejor manera de hacerlo. Veo las siguientes fallas en tu método:

1. Los valores están ordenados. La predicción de rama puede exponer efectos ridículos cuando se prueban valores ordenados frente a valores no clasificados con el mismo algoritmo. Posible solución: pruebe en ordenados y no clasificados y compare los resultados.
2. Los valores están codificados. La memoria caché de la CPU es una cosa complicada y puede introducir diferencias sutiles entre las pruebas en valores codificados y los de la vida real. En un mundo real, es poco probable que realice estas operaciones en valores codificados, por lo que puede leerlos desde un archivo o generar valores aleatorios.
3. Muy pocos valores. El tiempo de ejecución de su código es mucho menor que la precisión del temporizador.
4. Ejecutas el código una sola vez. Si soluciona todos los demás problemas y ejecuta el código dos veces, la segunda ejecución puede ser mucho más rápida que la primera debido al calentamiento de la caché: las ejecuciones posteriores tienden a tener menos errores de caché que la primera.
5. Ejecuta el código una vez en datos de tamaño fijo. Sería mejor ejecutar pruebas de lo contrario correctas al menos cuatro veces para cubrir un producto cartesiano de los siguientes parámetros:
   • Datos ordenados vs. sin clasificar
   • v3 adapta a la memoria caché de la CPU y el tamaño de v3 excede la memoria caché de la CPU. También considere los casos en que (v1.length() + v3.length()) * sizeof(int) ajusta al caché o no, (v1.length() + v2.length() + v3.length()) * sizeof(int) ajusta al caché o no, y así sucesivamente para todas las combinaciones.

Answer 2

Los mayores problemas con su enfoque son:

1) El código que estás probando es demasiado corto y predecible. Debe ejecutarlo al menos unos pocos miles de veces para que haya al menos unos cientos de milisegundos entre las mediciones. Y necesita hacer que el conjunto de datos sea más grande y menos predecible. En general, los cachés de CPU realmente hacen mediciones precisas basadas en datos de entrada sintéticos en PITA.

2) El compilador es libre de reordenar su código . En general, es bastante difícil asegurar que el código que está cronometrando se ejecutará entre las llamadas para verificar la hora (y nada más, en realidad). Por un lado, puede reducir la optimización, pero por el otro desea medir el código optimizado.

Una solución es desactivar la optimización de todo el programa y colocar las llamadas de tiempo en otra unidad de compilación.

Otra solución posible es utilizar una cerca de memoria alrededor de su prueba, por ejemplo,

    std::atomic_thread_fence(std::memory_order_seq_cst);

(requiere #include <atomic> y un compilador compatible con C ++ 11).

Además, es posible que desee complementar sus mediciones con los datos del generador de perfiles para ver qué tan eficientemente se utilizan los cachés L1 / 2/3, los cuellos de botella en la memoria, la tasa de retiro de instrucciones, etc. Desafortunadamente, la mejor herramienta para Intel x86 es comercial (vtune). pero en AMD x86 una herramienta similar es gratuita (codeXL).

Answer 3

Podría considerar usar una biblioteca de evaluación comparativa como Celero para hacer las mediciones por usted y lidiar con las partes difíciles de las mediciones de rendimiento, mientras permanece concentrado en el código que está tratando de optimizar. Hay ejemplos más complejos disponibles en el código que he vinculado en la respuesta a su pregunta anterior ( Cómo eliminar elementos de un vector de manera eficiente y en otro ), pero un caso de uso simple se vería así:

BENCHMARK(VectorRemoval, OriginalQuestion, 100, 1000)
{
    std::vector destination(10000);
    std::generate(destination.begin(), destination.end(), std::rand);
    std::sample(destination.begin(), destination.end(), std::back_inserter(source), 
        100, std::mt19937{std::random_device{}()})    

    for (auto i: source)
        destination.erase(std::remove(destination.begin(), destination.end(), i), 
            destination.end());    
}