[C++/C#] Confronto prestazioni in allocazione dinamica

[vendettaaaaa]

Prima di tutto: non sono mosso dall'ansia da prestazioni, ma da pura curiosità

Ciao, scrivo un aggiornamento a proposito dell'altra mia discussione per sottoporvi un interessante quesito:
Kendall è stato molto disponibile e si è offerto di convertire la classe vettore (BbVector) in C#, per confrontare le prestazioni (mi ricordavo che proprio Kendall avesse detto che in C# l'allocazione dinamica è più veloce che in C++ e volevo verificare se, e di quanto ).
Abbiamo fatto un confronto, fra poco i risultati. Prima di tutto posto parte del codice (quello che ci interessa):

*===== BbVector in C++ =====*
BbVector.hpp

class BbVector
{
private:
	// ****************** Data
	double* myVector;	// Points to the 1st chunk of memory allocated to the vector, which remains unused because BbVector's index is 1-based; myVector == BbVector(0), unaccessible
	double* start;		// Points to the 1st accessible element of the vector, start == BbVector(1)
	double* avail;		// Points 1 past the last allocated element of the vector (see comments to grow() function)
	double* limit;		// Points 1 past the last chunk of memory allocated to the vector (see comments to grow() function)
	size_type mySize;	// Returns the no. of elements in the vector; mySize == avail - start

	// Allocator object to dynamically manage memory
	std::allocator<double> alloc;

	// ****************** Constructor functions
	void create();
	void create(size_type n, const double& val);
	void uncreate();

public:
	// ****************** Constructors
	BbVector() { create(); }
	explicit BbVector(int n, double val = 0.);
	
	// ****************** Destructor
	~BbVector() { uncreate(); }
	
	// Norms
	double normInf() const;
	double norm1() const;
	double norm2() const;
	double normM() const;
};

BbVector.cpp

// Construct a BbVector of size n, setting all elements to the value val
BbVector::BbVector(int n, double val)
{
	if (n <= 0)
		create();
	else
		create(n, val);
}

// Private function for memory management: create and empty BbVector
void BbVector::create()
{
	mySize = 0;
	myVector = 0;
	limit = avail = start = 0;
}

// Private function for memory management: create a BbVector by allocating n+1 doubles and setting their value to val
void BbVector::create(size_type n, const double& val)
{
	mySize = n;
	myVector = alloc.allocate(n + 1);
	start = myVector + 1;
	limit = avail = start + mySize;
	
	uninitialized_fill(start, limit, val);
}

// Private function for memory management: delete the current BbVector by destroying all doubles allocated into myVector and then deallocating such memory
void BbVector::uncreate()
{
	if (myVector) {
		iterator it = avail;
		
		while (it != myVector)
			alloc.destroy(--it);

//		cout << "About to deallocate " << limit - myVector << " double cells, whereas mySize = " << mySize << endl;
		alloc.deallocate(myVector, limit - myVector);
	}

	mySize = 0;
	myVector = 0;
	limit = avail = start = 0;
}

// Norms: self explanatory
double BbVector::normInf() const
{
	return get_max();
}

double BbVector::norm1() const
{
	double ret = 0.;

	for (int i = 1; i <= mySize; ++i)
		ret += abs(myVector[i]);

	return ret;
}

double BbVector::norm2() const
{
	double ret = 0.;

	for (int i = 1; i <= mySize; ++i)
		ret += myVector[i] * myVector[i];

	return sqrt(ret);
}

double BbVector::normM() const
{
	return mySize ? this->norm1() / mySize : 0.;
}

*===== BbVector in C# =====*

    class BbVector : IEnumerable<double>
    {
         // >>>> Fields <<<<
        private List<double> vector;

       // >>>> Constructors <<<<
        public BbVector()
        {
            vector = new List<double>();
        }

        public BbVector(int length, double value = 0d)
        {
            vector = new List<double>(length);
            for ( int i = 0; i < vector.Capacity; i++ ) {
				vector.Add(value);
            }
        }

        public double NormInf
        {
            get
            {
                return MaxValue;
            }
        }

        public double Norm1
        {
            get
            {
                if ( vector.Count == 0 ) {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach ( var item in vector ) {
                    norm += System.Math.Abs(item);
                }
                return norm;
            }
        }

        public double Norm2
        {
            get
            {
                if ( vector.Count == 0 ) {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach ( var item in vector ) {
                    norm += item * item;
                }
                return Math.Sqrt(norm);
            }
        }

        public double NormM
        {
            get
            {
                return vector.Count != 0 ? Norm1 / vector.Count : 0d;
            }
        }

Quindi, in breve: io ho creato una classe sulla falsa riga dello std::vector, che sfrutta un allocator per gestire l'heap; Kendall ha scelto di wrappare una List<double>. E si vede la comodità, ha scritto meno di metà righe di codice
Passiamo ai risultati: il confronto delle performance è effettuato misurato quanto tempo ci vuole a creare (e distruggere) 10M di volte un BbVector di 100 elementi:
*===== TEST CODE in C++ =====*

printf("THIS IS THE C++ VERSION!!\n\n");

ProcessorTimer myTimer;

for (int i = 0; i < 10000000; ++i)
{
	BbVector* a = new BbVector(100);
	delete a;
}
	
printf("I have initialized 10M BbVectors of size 100 in %E s\n\n", std::get<0>(myTimer.split_time()));

dove ProcessorTimer è una classe di supporto che sfrutta feature C++11 per misurare il tempo di esecuzione.
*===== TEST CODE in C# =====*

Console.WriteLine("THIS IS THE C# VERSION!!\n");

Stopwatch sw = new Stopwatch();
sw.Start();

for (int i = 0; i < 10000000; ++i)
    new BbVector(100);

Console.WriteLine("I have initialized 10M BbVectors of size 100 in {0} s\n", sw.Split());

dove Split è una mia estensione a Stopwatch.
I risultati di seguito:

Si vede che il ciclo di 10M di iterazioni, in cui semplicemente si crea un nuovo BbVector(100), in Release e senza debugger, è completato dal C# in 8.3s, mentre dal C++ in 1.2 (in realtà 1.8s circa).

Al che mi pareva tutto ok, ma poi Kendall m'ha fatto notare che questo codice:
*===== TEST CODE in C++ =====*

printf("THIS IS THE C++ VERSION!!\n\n");

BbVector* a;

for (int i = 0; i < 10000000; ++i)
{
	a = new BbVector[100];
	delete a;
}

*===== TEST CODE in C# =====*

Console.WriteLine("THIS IS THE C# VERSION!!\n");

BbVector[] a;

for (int i = 0; i < 10000000; ++i)
    a = new BbVector[100];

viene eseguito dal C# in 3 ms mentre dal C++ in 700 ms circa. E se anzichè BbVector[] a mettiamo double[] a, i risultati non cambiano.

Ricapitolando: pare che allocare 10M di volte un vettore di 100 BbVector vuoti, in C# sia istantaneo mentre in C++ richiede quasi un secondo; se invece allochiamo 10M di volte un BbVector di 100 elementi, la situazione si ribalta. Come mai?
Cioè...capisco benissimo che creare un vettore di 100 oggetti e un oggetto di 100 elementi sono operazioni diverse, ma quello che volevo capire è: cosa, in C#, rende così lenta la seconda operazione? Il fatto che sia stato usata una List<double>? Sembrerebbe che la parte che rallenta il tutto sia nel costruttore BbVector(int n, double val = 0d).
E poi, ci sono sicuramente altri modi per scrivere il BbVector in C#, ma per renderlo performante come in C++ come bisogna fare? Usare unsafe e i puntatori, manualmente?

Qualcuno con più esperienza mi potrebbe illuminare? Grazie per l'attenzione

[Vincenzo1968]

Iscritto. Per ora non ho tempo per effettuare prove ché sto preparando il contest 19(e poi va a finire come ieri che alla fine sono stanco e debbo rimandare). Ma iscritto.

In B4: ansia da prestazioni.

[idoido]

3 cose non ho capito nel codice C#

1) perché bbVector eredita IEnumerable

2) perché usare una List di double quando usare un array non aumenta le linee di codice o diminuisce la leggibilità.
si sa che fare un foreach su un List è più lento di fare un for su un array.

3) nei metodi Norm1 e Norm2 c'è un controllo se il vettore è vuoto, e non c'è nel codice C++

puoi mettere da qualche parte l'intero codice in C# per poterlo scaricare?

[AnonimoVeneziano]

Originariamente inviato da vendettaaaaa

Prima di tutto: non sono mosso dall'ansia da prestazioni, ma da pura curiosità
// Death star size post ...

Beh, facendo Vector[100] in C++ e poi delete chiami 100 volte il distruttore dell'oggetto, mentre creando un oggetto da 100 elementi chiami entrambi una sola volta.

Quando guardi al codice C# devi considerare due cose:

- Il C# è fortemente ottimizzato alla creazione e distruzione degli oggetti (come il Java). Il compilatore JIT si sforza incredibilmente nel cercare di rimuovere chiamate a costruttori quando non serve e non mi stupirei se lo facesse anche in questo caso. Inoltre non esistendo i distruttori questi non vengono chiamati, ma la liberazione delle risorse viene fatta attraverso il GC.

PS:A proposito di questo mi ricordo che alla mia uni venne un tipo di microsoft una volta parlando di game development in XNA con C#. La presentazione era la creazione di un piccolo gioco shooter a scorrimento verticale. Il gioco teneva tutti gli oggetti "Proiettili" in una lista e ad ogni rendering update doveva aggiornarne la posizione. Il presentatore ci disse che in C# la generazione di nuovi oggetti era così ottimizzata che era più veloce creare una nuova lista di nuovi oggetti proiettili con le posizioni aggiornate ed eliminare quella precedente (semplicemente assegnando la nuova lista creata coi proiettili aggiornati al reference della vecchia lista e lasciare al GC il resto) che ciclare sulla lista e aggiornare la posizione dei vari proiettili già esistenti

- Quando chiami "new" in C# non chiama direttamente l'allocatore del sistema operativo e non è neanche detto che allochi la memoria sullo heap. Il GC potrebbe ritornare della memoria già allocata in precedenza ma marcata come libera oppure allocare gli oggetti sullo stack se sono sufficientemente piccoli , evitando così l'overhead tipico di una chiamata a "new" del C++.

La creazione/distruzione degli oggetti C++ quindi è generalmente più costosa del C# e bisognerebbe evitarla il più possibile in cicli grossi come questo nel proprio design se si cerca la massima performance con questo linguaggio. Altrimenti ci sono dei trucchetti per renderla il meno costosa possibile allocando la memoria manualmente usando memory pools (facendo overload di new e delete) , cercando di ridurre all'osso di distruttori o allocando gli oggetti sullo stack.

Vorrei comunque farti notare un errore abbastanza grave nella seconda versione del tuo main che avrebbe anche potuto influire in parte sulle performance del tuo test:

printf("THIS IS THE C++ VERSION!!\n\n");

BbVector* a;

for (int i = 0; i < 10000000; ++i)
{
	a = new BbVector[100];
	delete a; <- ERRORE!
}

Quella delete in realtà è "delete [] a"

Cheers.

[[Kendall]]

Originariamente inviato da idoido

3 cose non ho capito nel codice C#

1) perché bbVector eredita IEnumerable

2) perché usare una List di double quando usare un array non aumenta le linee di codice o diminuisce la leggibilità.
si sa che fare un foreach su un List è più lento di fare un for su un array.

3) nei metodi Norm1 e Norm2 c'è un controllo se il vettore è vuoto, e non c'è nel codice C++

puoi mettere da qualche parte l'intero codice in C# per poterlo scaricare?

1) Perchè un vettore è per concezione stessa un oggetto enumerabile (associabile per concetto in tutto e per tutto ad un array), quindi reputavo giusto implementarne l'interfaccia.

2) L'utilizzo dell'array anzichè di una lista ridimensionabile era quello che avevo consigliato a Vendetta, però mi richiedeva una lista di questo tipo quindi ho dovuto usare List<T>. (Però, Vendetta, come ti scrivevo per mail, son ancora convinto che della mia ideaa).

3) L'ho aggiunto perchè la norma di un vettore esiste se il vettore ha per lo meno una dimensione. (tra l'altro, mi hai fatto notare che mi son dimenticato di inserire il controllo su NormM).

edit: Ecco il codice completo, con la proprietà NormM corretta:

namespace LinearAlgebra
{
    class BbVector : IEnumerable<double>
    {
        // >>>> Constructors <<<<
        public BbVector()
        {
            vector = new List<double>();
        }

        public BbVector(int length, double value = 0d)
        {
            vector = new List<double>(length);
            for ( int i = 0; i < vector.Capacity; i++ ) {
                vector.Add(value);
            }
        }

        public BbVector(double[] source)
        {
            vector = new List<double>(source.Length);
            foreach ( var item in source ) {
                vector.Add(item);
            }
        }

        public BbVector(IEnumerable<double> source)
        {
            vector = new List<double>();
            vector.AddRange(source);
        }


        // >>> Indexer & Properties <<<<
        public double this[int position] // 1-based
        {
            get { return vector[position - 1]; }
            set { vector[position - 1] = value; }
            // IndexOutOfRangeExceptions is automatically thrown by vector
        }

        public double MaxValue
        {
            get
            {
                if ( vector.Count == 0 ) {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double max = vector[0];
                for ( int i = 1; i < vector.Count; i++ ) {
                    if ( vector[i] > max ) { max = vector[i]; }
                }
                return max;
            }
        }

        public double MinValue
        {
            get
            {
                if ( vector.Count == 0 ) {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double min = vector[0];
                for ( int i = 1; i < vector.Count; i++ ) {
                    if ( vector[i] < min ) { min = vector[i]; }
                }
                return min;
            }
        }

        public double NormInf
        {
            get
            {
                return MaxValue;
            }
        }

        public double Norm1
        {
            get
            {
                if ( vector.Count == 0 ) {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach ( var item in vector ) {
                    norm += System.Math.Abs(item);
                }
                return norm;
            }
        }

        public double Norm2
        {
            get
            {
                if ( vector.Count == 0 ) {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach ( var item in vector ) {
                    norm += item * item;
                }
                return norm;
            }
        }

        public double NormM
        {
            get
            {
                if ( vector.Count == 0 ) {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                return Norm1 / vector.Count;
            }
        }


        // >>>> Methods <<<<
        public void Add(double value)
        {
            vector.Add(value);
        }

        public IEnumerator<double> GetEnumerator()
        {
            return vector.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable)vector).GetEnumerator();
        }

        public void Resize(int newSize)
        {
            vector = new List<double>(newSize);
            for ( int i = 0; i < vector.Capacity; i++ ) {
                vector.Add(0d); // Filled with 0
            }
        }

        public override string ToString()
        {
            if ( vector.Count == 0 ) {
                return "Empty BbVector!!";
            }
            else {
                StringBuilder vectorString = new StringBuilder();
                foreach ( var item in vector ) {
                    vectorString.AppendFormat("{0} ", item);
                }
                return vectorString.ToString();
            }
        }


        // >>>> Fields <<<<
        private List<double> vector;


    } // class BbVector


} // namespace LinearAlgebra

[[Kendall]]

Comunque Vendetta un simile ciclo non è poi così utile ai fini del bench, perchè comunque ogni linguaggio deve essere sfruttato per le sue peculiarità.
Il processo di allocazione dinamica È più veloce nel C# come nel Java per il semplice fatto che in questi ultimi la ram viene trattata bene o male come uno stack, mettendo le nuove istanze in coda alle vecchie direttamente e ripulendo e compattando il tutto quando entra in gioco il GC. Nel C++ invece causa allocazione e deallocazione manuale della memoria nella RAM si genera frammentazione quindi devono essere regolarmente eseguiti controlli per verificare che l'allocazione sia possibile o meno, e tutto ciò porta ad un rallentamento generale dell'operazione (la deallocazione invece è di per sè abbastanza veloce perchè la si fa su porzioni di ram della quale si conosce fin da subito l'indirizzo iniziale e finale).

Questo che vuol dire? Poco o niente, perchè comunque per l'aspetto puramente prestazionale il C++ è superiore e l'eccellere in singoli aspetti (come l'allocazione dinamica per il C#) non rende più veloci nel computo totale.

[[Kendall]]

Originariamente inviato da vendettaaaaa

Al che mi pareva tutto ok, ma poi Kendall m'ha fatto notare che questo codice:
*===== TEST CODE in C++ =====*

printf("THIS IS THE C++ VERSION!!\n\n");

BbVector* a;

for (int i = 0; i < 10000000; ++i)
{
	a = new BbVector[100];
	delete a;
}

*===== TEST CODE in C# =====*

Console.WriteLine("THIS IS THE C# VERSION!!\n");

BbVector[] a;

for (int i = 0; i < 10000000; ++i)
    a = new BbVector[100];

viene eseguito dal C# in 3 ms mentre dal C++ in 700 ms circa. E se anzichè BbVector[] a mettiamo double[] a, i risultati non cambiano.

Ricapitolando: pare che allocare 10M di volte un vettore di 100 BbVector vuoti, in C# sia istantaneo mentre in C++ richiede quasi un secondo; se invece allochiamo 10M di volte un BbVector di 100 elementi, la situazione si ribalta. Come mai?

In realtà Vendetta il mio esempio era riferito espressamente agli array di double, perchè nel caso che hai scritto qui sopra stiamo parlando di situazioni diverse tra loro.

Cioè...capisco benissimo che creare un vettore di 100 oggetti e un oggetto di 100 elementi sono operazioni diverse, ma quello che volevo capire è: cosa, in C#, rende così lenta la seconda operazione? Il fatto che sia stato usata una List<double>? Sembrerebbe che la parte che rallenta il tutto sia nel costruttore BbVector(int n, double val = 0d).
E poi, ci sono sicuramente altri modi per scrivere il BbVector in C#, ma per renderlo performante come in C++ come bisogna fare? Usare unsafe e i puntatori, manualmente?

Qualcuno con più esperienza mi potrebbe illuminare? Grazie per l'attenzione

Sicuramente il collo di bottiglia sta nell'utilizzo della List<> (e qui si torna al consiglio che ti davo di usare un array ), quello che non mi torna è che mi sembra fin troppo lento. Perchè una Lista rialloca la memoria nel caso in cui si sfori la capacità, ma in quel caso la capacità viene assegnata correttamente fin dall'inizio, quindi mi sembra strano che le chiamate ad Add(value) siano così lente.

[Vincenzo1968]

Il sorgente in C++ mi da problemi(con Visual Studio 2010):

1>------ Rebuild All started: Project: VendettaaaaaCpp, Configuration: Release Win32 ------
1>  main.cpp
1>main.cpp(83): error C2955: 'std::iterator' : use of class template requires template argument list
1>          C:\Programmi\Microsoft Visual Studio 10.0\VC\include\xutility(337) : see declaration of 'std::iterator'
1>main.cpp(83): error C2514: 'std::iterator' : class has no constructors
1>          C:\Programmi\Microsoft Visual Studio 10.0\VC\include\xutility(337) : see declaration of 'std::iterator'
1>main.cpp(85): error C2678: binary '!=' : no operator found which takes a left-hand operand of type 'std::iterator' (or there is no acceptable conversion)
1>          could be 'built-in C++ operator!=(double *, double *)'
1>          C:\Programmi\Microsoft Visual Studio 10.0\VC\include\system_error(425): or       'bool std::operator !=(const std::error_code &,const std::error_condition &)'
1>          C:\Programmi\Microsoft Visual Studio 10.0\VC\include\system_error(432): or       'bool std::operator !=(const std::error_condition &,const std::error_code &)'
1>          while trying to match the argument list '(std::iterator, double *)'
1>main.cpp(85): fatal error C1903: unable to recover from previous error(s); stopping compilation
========== Rebuild All: 0 succeeded, 1 failed, 0 skipped ==========

// Private function for memory management: delete the current BbVector by destroying all doubles allocated into myVector and then deallocating such memory
void BbVector::uncreate()
{
	if (myVector)
	{
		iterator it = avail; // <--- ERRORE
		
		while (it != myVector)
			alloc.destroy(--it);

//		cout << "About to deallocate " << limit - myVector << " double cells, whereas mySize = " << mySize << endl;
		alloc.deallocate(myVector, limit - myVector);
	}

	mySize = 0;
	myVector = 0;
	limit = avail = start = 0;
}

Poi non trova la funzione get_max:

double BbVector::normInf() const
{
	return get_max(); // <--- ERRORE 
}

Bisogna inserire qualche include file? Puoi postare il codice per intero?

[Vincenzo1968]

Anche il sorgente C# di Kendall mi da problemi(sempre Visual Studio 2010):

C:\Progetti Visual Studio\Progetti Visual Studio 2010\C#\MyProjects\Vendettaaaaa\Vendettaaaaa\Program.cs(151,9): error CS0305: Using the generic type 'System.Collections.Generic.IEnumerator<T>' requires 1 type arguments

Compile complete -- 1 errors, 2 warnings

        IEnumerator IEnumerable.GetEnumerator() // <--- ERRORE
        {
            return ((IEnumerable)vector).GetEnumerator();
        }

Ho questi using:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

[[Kendall]]

Originariamente inviato da Vincenzo1968

Anche il sorgente C# di Kendall mi da problemi(sempre Visual Studio 2010):

C:\Progetti Visual Studio\Progetti Visual Studio 2010\C#\MyProjects\Vendettaaaaa\Vendettaaaaa\Program.cs(151,9): error CS0305: Using the generic type 'System.Collections.Generic.IEnumerator<T>' requires 1 type arguments

Compile complete -- 1 errors, 2 warnings

Ho questi using:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

Devi aggiungere:

using System.Collections;

oppure utilizzare l'estensione completa quando utilizzi le interfacce IEnumerable e IEnumerator (nella versione non generica): System.Collection.IEnumerable e System.Collection.IEnumerator.

[Vincenzo1968]

Grazie mille, Kendall, ora funziona:



Questo è il codice completo:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

namespace LinearAlgebra
{
    class BbVector : IEnumerable<double>
    {
        // >>>> Constructors <<<<
        public BbVector()
        {
            vector = new List<double>();
        }

        public BbVector(int length, double value = 0d)
        {
            vector = new List<double>(length);
            for (int i = 0; i < vector.Capacity; i++)
            {
                vector.Add(value);
            }
        }

        public BbVector(double[] source)
        {
            vector = new List<double>(source.Length);
            foreach (var item in source)
            {
                vector.Add(item);
            }
        }

        public BbVector(IEnumerable<double> source)
        {
            vector = new List<double>();
            vector.AddRange(source);
        }


        // >>> Indexer & Properties <<<<
        public double this[int position] // 1-based
        {
            get { return vector[position - 1]; }
            set { vector[position - 1] = value; }
            // IndexOutOfRangeExceptions is automatically thrown by vector
        }

        public double MaxValue
        {
            get
            {
                if (vector.Count == 0)
                {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double max = vector[0];
                for (int i = 1; i < vector.Count; i++)
                {
                    if (vector[i] > max) { max = vector[i]; }
                }
                return max;
            }
        }

        public double MinValue
        {
            get
            {
                if (vector.Count == 0)
                {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double min = vector[0];
                for (int i = 1; i < vector.Count; i++)
                {
                    if (vector[i] < min) { min = vector[i]; }
                }
                return min;
            }
        }

        public double NormInf
        {
            get
            {
                return MaxValue;
            }
        }

        public double Norm1
        {
            get
            {
                if (vector.Count == 0)
                {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach (var item in vector)
                {
                    norm += System.Math.Abs(item);
                }
                return norm;
            }
        }

        public double Norm2
        {
            get
            {
                if (vector.Count == 0)
                {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach (var item in vector)
                {
                    norm += item * item;
                }
                return norm;
            }
        }

        public double NormM
        {
            get
            {
                if (vector.Count == 0)
                {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                return Norm1 / vector.Count;
            }
        }


        // >>>> Methods <<<<
        public void Add(double value)
        {
            vector.Add(value);
        }

        public IEnumerator<double> GetEnumerator()
        {
            return vector.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return ((IEnumerable)vector).GetEnumerator();
        }

        public void Resize(int newSize)
        {
            vector = new List<double>(newSize);
            for (int i = 0; i < vector.Capacity; i++)
            {
                vector.Add(0d); // Filled with 0
            }
        }

        public override string ToString()
        {
            if (vector.Count == 0)
            {
                return "Empty BbVector!!";
            }
            else
            {
                StringBuilder vectorString = new StringBuilder();
                foreach (var item in vector)
                {
                    vectorString.AppendFormat("{0} ", item);
                }
                return vectorString.ToString();
            }
        }

        static void Main(string[] args)
        {
            Console.WriteLine("THIS IS THE C# VERSION!!\n");

            Stopwatch sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < 10000000; ++i)
                new BbVector(100);

            //Console.WriteLine("I have initialized 10M BbVectors of size 100 in {0} s\n", sw.Split());
            Console.WriteLine("\nI have initialized 10M BbVectors of size 100 in {0}ms", sw.ElapsedMilliseconds);

        }

        // >>>> Fields <<<<
        public List<double> vector;


    } // class BbVector


} // namespace LinearAlgebra

/*
namespace Vendettaaaaa
{
    class BbVector 
    {
        private double MaxValue = 21;
        // >>>> Fields <<<<
        private List<double> vector;

        // >>>> Constructors <<<<
        public BbVector()
        {
            vector = new List<double>();
        }

        public BbVector(int length, double value = 0d)
        {
            vector = new List<double>(length);
            for (int i = 0; i < vector.Capacity; i++)
            {
                vector.Add(value);
            }
        }

        public double NormInf
        {
            get
            {
                return MaxValue;
            }
        }

        public double Norm1
        {
            get
            {
                if (vector.Count == 0)
                {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach (var item in vector)
                {
                    norm += System.Math.Abs(item);
                }
                return norm;
            }
        }

        public double Norm2
        {
            get
            {
                if (vector.Count == 0)
                {
                    throw new InvalidOperationException("The Vector is Empty!");
                }
                double norm = 0d;
                foreach (var item in vector)
                {
                    norm += item * item;
                }
                return Math.Sqrt(norm);
            }
        }

        public double NormM
        {
            get
            {
                return vector.Count != 0 ? Norm1 / vector.Count : 0d;
            }
        }

        static void Main(string[] args)
        {
            Console.WriteLine("THIS IS THE C# VERSION!!\n");

            Stopwatch sw = new Stopwatch();
            sw.Start();

            for (int i = 0; i < 10000000; ++i)
                new BbVector(100);

            //Console.WriteLine("I have initialized 10M BbVectors of size 100 in {0} s\n", sw.Split());
            Console.WriteLine("\nI have initialized 10M BbVectors of size 100 in {0}ms", sw.ElapsedMilliseconds);

        }
    }
}
*/

Questa è la macchina:

[vendettaaaaa]

Rispondo a ritroso:

Originariamente inviato da [Kendall]

In realtà Vendetta il mio esempio era riferito espressamente agli array di double, perchè nel caso che hai scritto qui sopra stiamo parlando di situazioni diverse tra loro.



Sicuramente il collo di bottiglia sta nell'utilizzo della List<> (e qui si torna al consiglio che ti davo di usare un array ), quello che non mi torna è che mi sembra fin troppo lento. Perchè una Lista rialloca la memoria nel caso in cui si sfori la capacità, ma in quel caso la capacità viene assegnata correttamente fin dall'inizio, quindi mi sembra strano che le chiamate ad Add(value) siano così lente.

Aaah ma ti riferivi alla versione C# quando parlavi degli array, ora tutto torna!
Cmq sia come dicevo capisco che stiamo facendo cose diverse, volevo solo capire quali operazioni fanno da collo di bottiglia nell'uno o nell'altro linguaggio! E a quanto pare le risposte stanno arrivando

Originariamente inviato da [Kendall]

Comunque Vendetta un simile ciclo non è poi così utile ai fini del bench, perchè comunque ogni linguaggio deve essere sfruttato per le sue peculiarità.
Il processo di allocazione dinamica È più veloce nel C# come nel Java per il semplice fatto che in questi ultimi la ram viene trattata bene o male come uno stack, mettendo le nuove istanze in coda alle vecchie direttamente e ripulendo e compattando il tutto quando entra in gioco il GC. Nel C++ invece causa allocazione e deallocazione manuale della memoria nella RAM si genera frammentazione quindi devono essere regolarmente eseguiti controlli per verificare che l'allocazione sia possibile o meno, e tutto ciò porta ad un rallentamento generale dell'operazione (la deallocazione invece è di per sè abbastanza veloce perchè la si fa su porzioni di ram della quale si conosce fin da subito l'indirizzo iniziale e finale).

Questo che vuol dire? Poco o niente, perchè comunque per l'aspetto puramente prestazionale il C++ è superiore e l'eccellere in singoli aspetti (come l'allocazione dinamica per il C#) non rende più veloci nel computo totale.

Ok inizio a capire. Cioè, non c'è molto da capire ma da sapere: il sistema di allocazione di memoria del C# è "smart" ed ottimizzato per la creazione di oggetti, mentre in C++ new non è smart ma fa sempre lo stesso mestiere di "forza bruta" cosa senza ottimizzazioni. Quindi creare un vettore di 100 elementi per 10M di volte (equivalente a 1 miliardo di chiamate a costruttore e distruttore) risulta ben più lento in C++.

Originariamente inviato da idoido

3 cose non ho capito nel codice C#

1) perché bbVector eredita IEnumerable

2) perché usare una List di double quando usare un array non aumenta le linee di codice o diminuisce la leggibilità.
si sa che fare un foreach su un List è più lento di fare un for su un array.

3) nei metodi Norm1 e Norm2 c'è un controllo se il vettore è vuoto, e non c'è nel codice C++

puoi mettere da qualche parte l'intero codice in C# per poterlo scaricare?

3) Beh nel codice C++ non serve: se il vettore è vuoto, mySize == 0 e i cicli for non partono neanche. Solo nel caso di normInf viene chiamata get_max che lancia un runtime_error se il vettore è vuoto. Cmq non preoccupatevene, non sono classi complete, per ora ho messo le basi strutturali senza pensare ad una gestione degli errori visto che le uso solo io per ora...precedenza alla parte algoritmica!

Originariamente inviato da AnonimoVeneziano

Beh, facendo Vector[100] in C++ e poi delete chiami 100 volte il distruttore dell'oggetto, mentre creando un oggetto da 100 elementi chiami entrambi una sola volta.

Quando guardi al codice C# devi considerare due cose:

- Il C# è fortemente ottimizzato alla creazione e distruzione degli oggetti (come il Java). Il compilatore JIT si sforza incredibilmente nel cercare di rimuovere chiamate a costruttori quando non serve e non mi stupirei se lo facesse anche in questo caso. Inoltre non esistendo i distruttori questi non vengono chiamati, ma la liberazione delle risorse viene fatta attraverso il GC.

PS:A proposito di questo mi ricordo che alla mia uni venne un tipo di microsoft una volta parlando di game development in XNA con C#. La presentazione era la creazione di un piccolo gioco shooter a scorrimento verticale. Il gioco teneva tutti gli oggetti "Proiettili" in una lista e ad ogni rendering update doveva aggiornarne la posizione. Il presentatore ci disse che in C# la generazione di nuovi oggetti era così ottimizzata che era più veloce creare una nuova lista di nuovi oggetti proiettili con le posizioni aggiornate ed eliminare quella precedente (semplicemente assegnando la nuova lista creata coi proiettili aggiornati al reference della vecchia lista e lasciare al GC il resto) che ciclare sulla lista e aggiornare la posizione dei vari proiettili già esistenti

- Quando chiami "new" in C# non chiama direttamente l'allocatore del sistema operativo e non è neanche detto che allochi la memoria sullo heap. Il GC potrebbe ritornare della memoria già allocata in precedenza ma marcata come libera oppure allocare gli oggetti sullo stack se sono sufficientemente piccoli , evitando così l'overhead tipico di una chiamata a "new" del C++.

La creazione/distruzione degli oggetti C++ quindi è generalmente più costosa del C# e bisognerebbe evitarla il più possibile in cicli grossi come questo nel proprio design se si cerca la massima performance con questo linguaggio. Altrimenti ci sono dei trucchetti per renderla il meno costosa possibile allocando la memoria manualmente usando memory pools (facendo overload di new e delete) , cercando di ridurre all'osso di distruttori o allocando gli oggetti sullo stack.

Vorrei comunque farti notare un errore abbastanza grave nella seconda versione del tuo main che avrebbe anche potuto influire in parte sulle performance del tuo test:

printf("THIS IS THE C++ VERSION!!\n\n");

BbVector* a;

for (int i = 0; i < 10000000; ++i)
{
	a = new BbVector[100];
	delete a; <- ERRORE!
}

Quella delete in realtà è "delete [] a"

Cheers.

Sì hai ragione, ho fatto un pasticcio di qualche tipo io (avendo il codice diviso in 3 solution), infatti in realtà senza le parentesi quadre il programma crasha proprio.
Ho rifatto i test e questi sono i risultati:

C++ non ci mette 700 ms a creare per 10M di volte un array di 100 BbVector vuoti (che casino ) bensì 8s e qualcosa e qua sì che si vede la differenza prestazionale col C# nella creazione nuovi oggetti...C# che ci mette 0.131s...
Al contrario, la creazione di 10M di BbVector con 100 elementi ribalta la situazione. Quindi quello che dite trova riscontro, e a questo punto: come mai è così lento il C#? E' colpa di List.Add (nel costruttore, il cui codice avete trovato nel primo post)?
Un'altra cosa a cui ho pensato: 10M di BbVector di 100 elementi non ci stanno nella RAM...non è che la pulizia dell'heap da parte del GC è la parte lenta? Parlo da ignorante...

@Vincenzo fra poco posto tutto il codice

[vendettaaaaa]

Qui il codice C++ completo; quello C# l'ha postato Kendall e cmq è easy da scrivere
Mi raccomando usatelo con giudizio

[Vincenzo1968]

Adesso compila ma ho qualche problemino con l'output:



EDIT: Ah no, scusate, visualizza il double in formato scientifico. Come non detto

La macchina è sempre questa:

[Vincenzo1968]

Modificato main così:

int main(int argc, char* argv[])
{

	printf("THIS IS THE C++ VERSION!!\n\n");

	double list[5] = {1., -5., 4., 53., -0.66};
	clock_t c_start, c_end;

	c_start = clock();

	BbVector bbV(5, list);

	BbVector bbA(5000000, 666.);
	
	bbA  = bbV;

	BbVector* d;

	for (int i = 0; i < 10000000; ++i)
	{
		d = new BbVector[100];
		delete[] d;
	}
	
	//printf("I have initialized 10M arrays of BbVectors of size 100 in %E s\n\n", std::get<0>(myTimer.split_time()));
	c_end = clock();

	printf("\nI have initialized 10M arrays of BbVectors of size 100 in  -> %5.5f s\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);


	BbVector* a;

	c_start = clock();

	for (int i = 0; i < 10000000; ++i)
	{
		a = new BbVector(100);
		delete a;
	}
	
	//printf("I have initialized 10M BbVectors of size 100 in %E s\n\n", std::get<0>(myTimer.split_time()));

	c_end = clock();

	printf("\nI have initialized 10M BbVectors of size 100 in -> %5.5f s\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);

	return 0;
}

[Vincenzo1968]

Riepilogo:




La macchina è questa:

[vendettaaaaa]

Originariamente inviato da Vincenzo1968

Riepilogo:




La macchina è questa:

Già che ci sei aggiungi la seconda prova nella versione C# e fai stampare il tempo in secondi
Cmq più o meno i conti tornano anche sulla tua macchina

Anch'io ho provato ad usare clock ma il ProcessorTimer mi sembra abbia più risoluzione. Al momento va usato in quel modo perchè split_time ritorna una tupla...ma volendo basta fargli ritornare un double!

[Vincenzo1968]

Originariamente inviato da vendettaaaaa

Già che ci sei aggiungi la seconda prova nella versione C# e fai stampare il tempo in secondi
Cmq più o meno i conti tornano anche sulla tua macchina

Anch'io ho provato ad usare clock ma il ProcessorTimer mi sembra abbia più risoluzione. Al momento va usato in quel modo perchè split_time ritorna una tupla...ma volendo basta fargli ritornare un double!

La seconda prova? Nel Codice C#?

Datemi i sorgenti e vi faccio le verifiche. Per il momento sto facendo i benchmark per Lucene, Indri e Zettair(Contest 19).

[Vincenzo1968]

Ah una cosa: questa è la mia macchina vecchia. Di la ho la macchinina nuova con Windows 8 e Linux Ubuntu 12.10 a 64 bit. In questa vecchia macchinina invece ho Windows XP e Linux gNewSense a 32 bit.

Più tardi prendo i tempi anche sulla macchina nuova.

EDIT: Vabbuo', il tempo in secondi, questo è facile:

//Console.WriteLine("\nI have initialized 10M BbVectors of size 100 in {0}ms", sw.ElapsedMilliseconds);
Console.WriteLine("\nI have initialized 10M BbVectors of size 100 in {0} s.", (double)sw.ElapsedMilliseconds/(double)1000);

[Vincenzo1968]

I tempi presi sulla macchina nuova compilando entrambe le applicazioni a 64 bit con Visual Studio 2012: