invertir - listas con arreglos c#

No se puede reproducir: Ventajas del rendimiento de C++ Vector sobre el rendimiento de la lista C#

Question

En la conferencia BUILD de Microsoft, Herb Sutter explicó que C ++ tiene "Real Arrays" y que los lenguajes C # / Java no tienen el mismo tipo.

Fui vendido en eso. Puede ver la charla completa aquí http://channel9.msdn.com/Events/Build/2014/2-661

Aquí hay una instantánea rápida de la diapositiva donde describió esto. http://i.stack.imgur.com/DQaiF.png

Pero quería ver cuánta diferencia voy a hacer.

Así que escribí programas muy ingenuos para las pruebas, que crean un gran vector de cadenas de un archivo con líneas que van desde 5 a 50 caracteres.

Enlace al archivo:

www (dot) dropbox.com/s/evxn9iq3fu8qwss/result.txt

Luego accedí a ellos en secuencia.

Hice este ejercicio tanto en C # como en C ++.

Nota: Hice algunas modificaciones, eliminé la copia en los bucles como se sugiere. Gracias por ayudarme a entender los arreglos reales.

En C # utilicé List y ArrayList porque ArrayList está en desuso a favor de List.

Aquí están los resultados en mi computadora portátil dell con procesador Core i7:

count       C# (List<string>)   C# (ArrayList)     C++   

1000           24 ms              21 ms             7 ms       
10000         214 ms             213 ms            64 ms     
100000  2 sec 123 ms       2 sec 125 ms           678 ms    

Código C #:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;
namespace CSConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            int count;
            bool success = int.TryParse(args[0], out count);

            var watch = new Stopwatch();
            System.IO.StreamReader isrc = new System.IO.StreamReader("result.txt");

            ArrayList list = new ArrayList();
            while (!isrc.EndOfStream)
            {
                list.Add(isrc.ReadLine());
            }
            double k = 0;
            watch.Start();
            for (int i = 0; i < count; i++)
            {
                ArrayList temp = new ArrayList();
                for (int j = 0; j < list.Count; j++)
                {
                   // temp.Add(list[j]);
                    k++;
                }
            }

            watch.Stop();
            TimeSpan ts = watch.Elapsed;

            //Console.WriteLine(ts.ToString());
            Console.WriteLine("Hours: {0} Miniutes: {1} Seconds: {2} Milliseconds: {3}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds);
            Console.WriteLine(k);
            isrc.Close();
        }


    }
}

Código C ++

#include "stdafx.h"
#include <stdio.h>
#include <tchar.h>

#include <vector>
#include <fstream>
#include <chrono>
#include <iostream>
#include <string>

using namespace std;

std::chrono::high_resolution_clock::time_point time_now()
{
    return std::chrono::high_resolution_clock::now();
}

float time_elapsed(std::chrono::high_resolution_clock::time_point const & start)
{

    return std::chrono::duration_cast<std::chrono::milliseconds>(time_now() - start).count();
    //return std::chrono::duration_cast<std::chrono::duration<float>>(time_now() - start).count();
}


int _tmain(int argc, _TCHAR* argv [])
{
    int  count = _wtoi(argv[1]);

    vector<string> vs;
    fstream fs("result.txt", fstream::in);
    if (!fs) return -1;

    char* buffer = new char[1024];
    while (!fs.eof())
    {
        fs.getline(buffer, 1024);
        vs.push_back(string(buffer, fs.gcount()));
    }
    double k = 0;
    auto const start = time_now();
    for (int i = 0; i < count; i++)
    {
        vector<string> vs2;
        vector<string>::const_iterator iter;
        for (iter = vs.begin(); iter != vs.end(); iter++)
        {
            //vs2.push_back(*iter);
            k++;
        }
    }

    auto const elapsed = time_elapsed(start);
    cout << elapsed << endl;
    cout << k;
    fs.close();
    return 0;
}

Answer 1

Las diferencias encontradas por su programa de ejemplo no tienen nada que ver con las listas o su estructura.

Es porque en C #, las cadenas son un tipo de referencia, mientras que en el código C ++, las está utilizando como un tipo de valor.

Por ejemplo:

string a = "foo bar baz";
string b = a;

Asignar b = a es simplemente copiar el puntero.

Esto sigue a través de listas. Agregar una cadena a una lista de C # es simplemente agregar un puntero a la lista. En su bucle principal, creará N listas, todas las cuales solo contienen punteros a las mismas cadenas.

Sin embargo, debido a que está utilizando cadenas por valor en C ++, tiene que copiarlas cada vez.

vector<string> vs2;
vector<string>::const_iterator iter;
for (iter = vs.begin(); iter != vs.end(); iter++)
{
   vs2.push_back(*iter); // STRING IS COPIED HERE
}

Este código está haciendo copias de cada cadena. Terminas con copias de todas las cadenas y usarás mucha más memoria. Esto es más lento por razones obvias.

Si reescribe el bucle como sigue:

vector<string*> vs2;
for (auto& s : vs)
{
    vs2.push_back(&(s));
}

Entonces ahora estás creando listas de punteros, no listas de copias y estás en pie de igualdad con C #.

En mi sistema, el programa C # se ejecuta con N de 1000 en aproximadamente 138 milisegundos , y el C ++ se ejecuta en 44 milisegundos , una clara victoria para C ++.

Comentario:

Uno de los principales beneficios de los vectores C ++ según la imagen de la hierba sutter, es que el diseño de la memoria puede ser contiguo (es decir, todos los elementos están pegados uno al otro en la memoria). Nunca verá este trabajo con una std::string sin embargo, ya que las cadenas requieren una asignación de memoria dinámica (no puede pegar una carga de cadenas una al lado de la otra en una matriz porque cada cadena tiene una longitud diferente)

Esto le daría un gran beneficio si quisiera iterar rápidamente a través de todos ellos, ya que es mucho más amigable con los cachés de la CPU, pero la desventaja es que tiene que copiar todos los elementos para incluirlos en la lista.

Aquí hay un ejemplo que lo ilustra mejor:

Código C #:

class ValueHolder {
    public int tag;
    public int blah;
    public int otherBlah;

    public ValueHolder(int t, int b, int o)
    { tag = t; blah = b; otherBlah = o; }
};

static ValueHolder findHolderWithTag(List<ValueHolder> buffer, int tag) {
    // find holder with tag i
    foreach (var holder in buffer) {
        if (holder.tag == tag)
            return holder;
    }
    return new ValueHolder(0, 0, 0);
}

static void Main(string[] args)
{
    const int MAX = 99999;

    int  count = 1000; // _wtoi(argv[1]);
    List<ValueHolder> vs = new List<ValueHolder>();
    for (int i = MAX; i >= 0; i--) {
        vs.Add(new ValueHolder(i, 0, 0)); // construct valueholder with tag i, blahs of 0
    }

    var watch = new Stopwatch();
    watch.Start();

    for (int i = 0; i < count; i++)
    {
        ValueHolder found = findHolderWithTag(vs, i);
        if (found.tag != i)
            throw new ArgumentException("not found");
    }

    watch.Stop();
    TimeSpan ts = watch.Elapsed;
    Console.WriteLine("Hours: {0} Miniutes: {1} Seconds: {2} Milliseconds: {3}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds);
}

Código C ++:

class ValueHolder {
public:
    int tag;
    int blah;
    int otherBlah;

    ValueHolder(int t, int b, int o) : tag(t), blah(b), otherBlah(o) { }
};

const ValueHolder& findHolderWithTag(vector<ValueHolder>& buffer, int tag) {
    // find holder with tag i
    for (const auto& holder : buffer) {
        if (holder.tag == tag)
            return holder;
    }
    static ValueHolder empty{ 0, 0, 0 };
    return empty;
}

int _tmain(int argc, _TCHAR* argv[])
{
    const int MAX = 99999;

    int  count = 1000; // _wtoi(argv[1]);
    vector<ValueHolder> vs;
    for (int i = MAX; i >= 0; i--) {
        vs.emplace_back(i, 0, 0); // construct valueholder with tag i, blahs of 0
    }

    auto const start = time_now();
    for (int i = 0; i < count; i++)
    {
        const ValueHolder& found = findHolderWithTag(vs, i);
        if (found.tag != i) // need to use the return value or compiler will optimize away
            throw "not found";
    }

    auto const elapsed = time_elapsed(start);
    cout << elapsed << endl;
    return 0;
}

Ya sabemos por la pregunta original que crear un grupo de listas duplicadas sería mucho más rápido en C # que en C ++, pero ¿qué hay de buscar en la lista?

Ambos programas solo están haciendo un estúpido escaneo de lista lineal en un simple intento de mostrar esto.

En mi PC, la versión C ++ se ejecuta en 72 ms y la C # one toma 620 ms . ¿Por qué aumenta la velocidad? Debido a las "matrices reales".

Todos los ValueHolders C ++ están pegados uno al lado del otro en el std::vector . Cuando el bucle quiere leer el siguiente, esto significa que probablemente ya esté en el menú de la CPU.

Los C # ValueHolders están en todo tipo de ubicaciones de memoria al azar, y la lista solo contiene punteros a ellos. Cuando el bucle quiere leer el siguiente, es casi seguro que no está en la memoria caché de la CPU, así que tenemos que ir a leerlo. El acceso a la memoria es lento, por lo tanto, la versión C # tarda casi 10 veces más.

Si cambia el ValueHolder de C # de la class a la struct , entonces la Lista de C # puede pegarlos en la memoria, y el tiempo se reduce a 161 ms . Pero ahora tiene que hacer copias cuando se está insertando en la lista.

El problema para C # es que hay muchas situaciones en las que no puedes o no quieres usar una estructura, mientras que en C ++ tienes más control sobre este tipo de cosas.

PD: Java no tiene estructuras, por lo que no puedes hacer esto en absoluto. Estás atascado con el 10x como versión hostil de caché lento

Answer 2

Mientras que C # string y C ++ std::string comparten un nombre, y ambos son colecciones ordenadas de tipos de caracteres, de lo contrario son muy diferentes.

std::string es un contenedor mutable, la string C # es inmutable. Esto significa que los datos en dos string C # se pueden compartir: al copiar una string C # se duplica un puntero (también conocido como referencia), y se realiza un trabajo de administración de por vida. Al duplicar una std::string copian los contenidos (copia en escritura C ++ estándar std::string no es legal).

Para crear un conjunto más similar de código C ++, almacene std::shared_ptr<const std::string> en su vector s. Y cuando rellene los vector duplicados, asegúrese de copiar solo los punteros inteligentes. Ahora tiene punteros (inteligentes) para datos inmutables, como C #.

Tenga en cuenta que esto mejorará el rendimiento de la copia probablemente en C ++, pero hará que la mayoría de las demás operaciones sean más lentas (si desea editar la std::string , ahora debe copiar todo, luego modificar la copia y leer hace una diferencia de puntero adicional) ).

struct immutable_string {
  immutable_string() = default;
  immutable_string(const&) = default;
  immutable_string(&&) = default;
  immutable_string& operator=(const&) = default;
  immutable_string& operator=(&&) = default;

  immutable_string( std::string s ):data( std::make_shared<std::string>(std::move(s)) ) {}

  std::string const& get() const { if (data) return *data; return *empty_string(); }
  std::string get() && {
    if (!data) return {};
    if (data->use_count()==1) return std::move( const_cast<std::string&>(*data) );
    return *data;
  }
  template<class... Args>
  void emplace( Args&&... args ) {
    data = std::make_shared<std::string>(std::forward<Args>(args)...);
  }
  template<class F>
  void modify( F&& f ) {
    std::string tmp = std::move(*this).get();
    std::forward<F>(f)(tmp);
    emplace(std::move(tmp));
  }
private:
  std::shared_ptr<const std::string> data;
  static std::shared_ptr<const std::string> empty_string() {
    static auto nothing = std::make_shared<const std::string>();
    return nothing;
  }
};

Esto nos da VACA. Para editar, llame a immutable_string s; s.modify( [&](std::string& s){ immutable_string s; s.modify( [&](std::string& s){ código va aquí }); .