Impossibile riprodurre: C++ Vantaggi delle prestazioni vettoriali rispetto a C# Prestazioni degli elenchi

Question

Alla conferenza BUILD di Microsoft Herb Sutter ha spiegato che C++ ha "Real Arrays" e che i linguaggi C#/Java non hanno lo stesso tipo.

Sono stato venduto su quello. Puoi guardare il discorso completo qui http://channel9.msdn.com/Events/Build/2014/2-661

Ecco una rapida istantanea della diapositiva in cui ha descritto questo. http://i.stack.imgur.com/DQaiF.png

Ma volevo vedere quanta differenza potrei fare.

Così ho scritto programmi molto ingenui per i test, che creano un grande vettore di stringhe da un file con righe che vanno da 5 caratteri a 50 caratteri.

link al file:

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

Allora io li accede in sequenza.

Ho fatto questo esercizio sia in C# che in C++.

Nota: ho apportato alcune modifiche, rimosso la copia nei loop come suggerito. Grazie per avermi aiutato a capire i veri array.

In C# ho usato sia List che ArrayList perché ArrayList è deprecato in favore di List.

Ecco i risultati sul mio portatile Dell con processore 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  

---

codice 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(); 
     } 


    } 
} 

---

codice 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

Le differenze rilevate dal programma di esempio non hanno nulla a che fare con le liste o la loro struttura.

È perché in C# le stringhe sono un tipo di riferimento, mentre nel codice C++ le si utilizza come un tipo di valore.

Ad esempio:

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

Assegnazione b = a semplicemente copiando il puntatore.

Segue attraverso gli elenchi. Aggiungere una stringa a un elenco C# è solo aggiungere un puntatore all'elenco. Nel tuo ciclo principale, crei N liste, tutte contenenti solo puntatori alle stesse stringhe.

Poiché si utilizzano stringhe in base al valore in C++, tuttavia, è necessario copiarle ogni volta.

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

Questo codice esegue effettivamente le copie di ogni stringa. Finisci con le copie di tutte le stringhe e userai molta più memoria. Questo è più lento per ovvi motivi.

Se si riscrive il ciclo nel modo seguente:

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

Allora stai ora la creazione di liste-di-puntatori non liste-di-copie e sono in condizioni di parità con C#.

Sul mio sistema, il programma C# corre con N 1000 in circa 138 millisecondi , e le piste da C++ a uno 44 millisecondi, una chiara vittoria per C++.

---

Commento:

Uno dei principali vantaggi di vettori C++ secondo l'immagine di erbe di Sutter, è che il layout di memoria può essere contigui (vale a dire tutti gli elementi sono bloccati l'uno accanto all'altro in memoria). Non sarai mai vedere questo lavoro con un std::string tuttavia, come stringhe richiedono allocazione dinamica della memoria (non si può attaccare un carico di stringhe uno accanto all'altro in una matrice, poiché ogni stringa ha una lunghezza diversa)

Questo sarebbe Dare un grande vantaggio se si desidera eseguire una rapida iterazione di tutti loro, poiché è molto più amichevole delle cache della CPU, ma il compromesso è che è necessario copiare tutti gli elementi per inserirli nell'elenco.

Ecco un esempio che illustra meglio è:

C# Codice:

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); 
} 

codice 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; 
} 

Sappiamo già dalla domanda originale che la creazione di un gruppo di liste duplicati sarebbe molto più veloce in C# che in C++, ma che dire invece di cercare la lista?

Entrambi i programmi eseguono semplicemente una scansione di lista lineare stupida in un semplice tentativo di mostrare questo.

Sul mio PC, la versione C++ viene eseguito in 72ms e C# si prende 620ms. Perché la velocità aumenta? A causa dei "veri array".

Tutti i C++ ValueHolders sono bloccati uno accanto all'altro nel std::vector. Quando il loop vuole leggere il prossimo, questo significa che è molto probabilmente già nel CPU cacue.

I C# ValueHolders si trovano in tutti i tipi di posizioni di memoria casuale e l'elenco contiene solo dei puntatori. Quando il ciclo vuole leggere il prossimo, è quasi certamente non nella cache della CPU, quindi dobbiamo andare a leggerlo. L'accesso alla memoria è lento, quindi la versione C# richiede circa 10 volte di più.

Se si cambia il C# ValueHolder class-struct, poi la C# elenco può attaccare tutti accanto a vicenda nella memoria, e il tempo scende a 161ms. Ma ora deve fare delle copie quando stai inserendo nella lista.

Il problema per C# è che ci sono molte situazioni in cui non puoi o non vuoi usare una struct, mentre in C++ hai più controllo su questo tipo di cose.

PS: Java non ha strutture, quindi non è possibile farlo affatto. Sei bloccato con il 10x come versione ostile della cache lenta

Answer 2

Mentre C# string e C++ std::string condividono un nome, ed entrambe sono raccolte ordinate di tipi di caratteri, diversamente sono molto diverse.

std::string è un contenitore mutabile, C# 's string è immutabile. Ciò significa che i dati in due C# string possono essere condivisi: la copia di un C# string duplica un puntatore (noto anche come riferimento) e fa funzionare la gestione a vita. La duplicazione di un std::string copia il contenuto (copia su scrittura C++ std::string non è legale).

Per creare un set più simile di codice C++, memorizzare std::shared_ptr<const std::string> nei tuoi vector s. E quando inserisci il duplicato vector s, assicurati di copiare solo i puntatori intelligenti. Ora hai puntatori (intelligenti) a dati immutabili, proprio come C#.

Si noti che ciò migliorerà le prestazioni di copia probabilmente in C++, ma rallenterà la maggior parte delle altre operazioni (se si desidera modificare lo std::string ora è necessario copiare l'intero elemento, quindi modificare la copia e leggere fa un puntatore aggiuntivo dereference).

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; 
    } 
}; 

questo ci dà COW. Per modificare, chiamare il codice immutable_string s; s.modify([&](std::string& s){qui va});.