C++ seems faster than C at summing big arrays!!

Forewords

I'm some sort of self-taught programer, so it is expected that my methods and algorithms aren't state of the art optimized to best design practices and improved performance. I made the code without thinking on but doing the tast and leaving aside the code optimization and all that stuff.

The result here is just what I have found. I think that sitting and optimizing code could turn tables, but, not anyone is capable of efficiently write code (a.k.a. optimizing it for best performance), specially if you are a scientist coding (and not a computer scientist).

Motivation

For several months I've been wondering whether C or C++ is more efficient at doing science related tasks. As far as I know, the most common tasks in science involve linear algebra, and one of the simplest tasks is the sum of vectors. Given that I'm preparing some study materials I've decided to test it out and here is what i've found so far.

C++ seems faster than C at summing big arrays of integers

I made codes that compares the performance between regular C arrays (also C++ valid arrays) and STL arrays (exclusive of C++) by taking two random vectors up to 200000 components as input from a file.

One program run consist of,

• Read a 1000 components of two random vectors from a given file.
• Sum component to component the couple of vectors read. Report the number of components and the milliseconds it took for the whole process to standard output.
• Increase the number of components by 1000, then repeat the read-sum-report procedure stated above.
• Repeat increasing size until the vectors reach 200000 components.

The codes are available here

Results

Well, using my unoptimized algorithm it seems that C++ is indeed a little bit faster than C.
The time-to-completion was measured 300 times on the same machine, the resulting run-times where averaged to compensate the effects of anyother processes running.
A fitting to linear functions seemed suitable for the resulting data. The blue marks on the graph represent C++ run-times whilst purple marks represent those of C.
The fitting was made using gnuplot with the fit function: f(x) for C and g(x) for C++ (details below)

Fitting for C with f(x)

f(x)=A*x+B

The relevant output of the fitting was


After 8 iterations the fit converged.
final sum of squares of residuals : 68.4475
relative change during last iteration : -1.00902e-13

degrees of freedom (FIT_NDF) : 197
rms of residuals (FIT_STDFIT) = sqrt(WSSR/ndf) : 0.589448
variance of residuals (reduced chisquare) = WSSR/ndf : 0.347449

Final set of parameters Asymptotic Standard Error
======================= ==========================
A = 0.000385433 +/- 7.274e-07 (0.1887%)
B = 1.36903 +/- 0.08389 (6.127%)


Fitting for C++ with g(x)


function used for fitting: g(x)
g(x)=C*x+D

After 8 iterations the fit converged. q
final sum of squares of residuals : 48.4348
relative change during last iteration : -1.78975e-14

degrees of freedom (FIT_NDF) : 197
rms of residuals (FIT_STDFIT) = sqrt(WSSR/ndf) : 0.495845
variance of residuals (reduced chisquare) = WSSR/ndf : 0.245862

Final set of parameters Asymptotic Standard Error
======================= ==========================
C = 0.000367315 +/- 6.119e-07 (0.1666%)
D = 1.16317 +/- 0.07056 (6.067%)


Conclusions

At the beginning, the execution times of both languages are undistinguishable but it seems that C++ has better performance than C as the size of the vectors increase. It could be a matter of design, more test with different algorithms should be performed.

The difference between the fitted curves is the linear function
D(x) = f(x) - g(x) = 0.000018118*x-0.20586
Clearly when N=10 000 000 the difference between runtimes would be of just 17.91214 ms so whats the point of using C++ over C if the performance difference would be so small? Well, because of Object Oriented Programming, that's why. Besides, the C++ std::array are expected to be optimized over the regular int array[] of C.

Conozcamos la STL (Standard Template Library) de C++ - Primera entrega: std::map - Parte 2 de 2

Introducción

Mucha personas (como yo en el pasado cercano) ignorarán el poder oculto detrás de las siglas STL. Se trata de nada más ni nada menos que una de las "cosas" que convierte a C++ en uno de los lenguajes de programación más poderosos. La STL o Standard Template Library 

La STL proporciona una colección de estructuras de datos contenedoras y algoritmos genéricos que se pueden utilizar con éstas.

(Mirar por ejemplo http://decsai.ugr.es/~jfv/ed1/c++/cdrom4/paginaWeb/stl.htm)

Dada la extensión que pretendía dar a este tema, decidí dividirlo en dos entradas independientes y complementarias.

La primera parte de esta entrega (disponible aquí) consiste en la implementación del contenedor std::map con los tipos de datos incluidos en el estándar de C++.

En la segunda parte (este post) abordaré la implementación del contenedor std::map haciendo uso de una clase propia, es decir, una clase que hemos hecho nosotros mismos, tal como lo ilustramos en una entrega previa, donde hemos definido una clase para la manipulación de vectores.

Usando std::map con una clase propia

Supongamos ahora que creamos una clase y queremos usarla en una variable tipo std::map. Para tal fin es necesario crear un criterio de comparación, específicamente, es necesario definir el operador< dentro de nuestra clase, puesto que std::map se basa en el para realizar el ordenamiento.
En una entrega previa hemos definido una clase para la manipulación de vectores y hemos definido el operador< dentro de la misma tal como lo requiere el std::map.

La clase cVector y su código de implementación pueden descargarse usando este enlace.
Mirando el código de ejemplo:


#include <iostream>
#include <map>
#include "cVector.hpp"

int main(void)
{

    cVector I_vector;
    cVector J_vector;
    cVector K_vector;
 
/*
Aqui implementamos un mapa que contiene elementos de la clase cVector,
No debe representar problemas puesto que el operador< ha sido definido para la clase
como puede verse en cVector.hpp
*/

    std::map<int,cVector> mi_mapav;
 
    I_vector.colocarCoordenadas(1,0,0);
    J_vector.colocarCoordenadas(0,2,0);
    K_vector.colocarCoordenadas(0,0,3);

 
mi_mapav[0]=I_vector;
mi_mapav[1]=J_vector;
mi_mapav[2]=K_vector;

    std::cout << "Producto punto entre I y K " << I_vector*K_vector << std::endl;
 
    std::cout << "La magnitud de la suma vectorial entre I y J " << (I_vector+J_vector).normaVector() << std::endl;
 
    if( (I_vector+J_vector)<K_vector)
    {
std::cout << "La magnitud de I + J es menor que la de K " << std::endl;
}
else
{
std::cout << "La magnitud de I + J es mayor que la de K " << std::endl;
}

for(int i=0;i<1;i++)
{
std::cout << "Usando el std::map tenemos la norma de la suma de vectores consecutivos" << (mi_mapav[i]+mi_mapav[i+1]).normaVector() << std::endl;

}
}


Conozcamos la STL (Standard Template Library) de C++ - Primera entrega: std::map - Parte 1 de 2

Introducción

Mucha personas (como yo en el pasado cercano) ignorarán el poder oculto detrás de las siglas STL. Se trata de nada más ni nada menos que una de las "cosas" que convierte a C++ en uno de los lenguajes de programación más poderosos. La STL o Standard Template Library 

La STL proporciona una colección de estructuras de datos contenedoras y algoritmos genéricos que se pueden utilizar con éstas.

(tomado de aquí: http://decsai.ugr.es/~jfv/ed1/c++/cdrom4/paginaWeb/stl.htm)

En esta entrega trataré de ilustrar el uso del contenedor map, a través de algunos ejemplos prácticos.

Dada la extensión que pretendía dar a este tema, decidí dividirlo en dos entradas independientes y complementarias.
La primera  parte de esta entrega (es decir, este post) consiste en la implementación del contenedor std::map con los tipos de datos incluidos en el estándar de C++.
En la segunda parte (disponible aquí) abordaré la implementación del contenedor std::map haciendo uso de una clase propia, es decir, una clase que hemos hecho nosotros mismos, tal como lo ilustramos en  una entrega previa, donde hemos definido una clase para la manipulación de vectores.

Contenedor std::map de la STL

Generalidades del contenedor std::map

Uno de esos contenedores incluidos en la STL corresponde a map, un contenedor de datos donde cada uno posee una clave(key en inglés) que lo identifica. Para utilizar map es necesario incluirlo en la cabecera de nuestro código fuente:

#include<map>

De esta manera, es posible hacer el llamado

std::map<tipo_variable_1 clave,tipo_variable_2 valor, criterio_comparación_clave> variable_map;

 De esta manera, se puede declarar una varible tipo map, en este caso: variable_map. Esta definición parece un poco ambigua de entender, pero todo es más claro en cuanto se entiende que la variable map lo que hace es etiquetar con la variable clave lo que contiene la variable valor. Para realizar el ordenamiento, el contenedor map utiliza un criterio de comparación basándose en alguna operación de comparación, específicamente, usando el operador< definido para del tipo_variable_1, es por esta razón que el operador< debe estar definido para el tipo de variable utilizado como clave.
Para realizar la asignación de valores a nuestro mapa, basta con escribir

variable_map[valor_tipo_variable_1]=valor_tipo_variable_2;

Para ver claramente lo que acabo de exponer, observemos el siguiente ejemplo (código c++, obviamente)



#include<iostream>
#include<string>
#include<map>


int main(void)
{
        std::map<int /*indice o clave*/, std::string /*contenido*/> mi_mapa;

       std::string palabra;

        for(int i(0);i<5;i++)
        {
                std::cout << "Ingrese una palabra: " << std::endl;
                std::cin>>palabra;
                mi_mapa[i]=palabra;
        }


        for(i=0;i<5;i++)
        {
                std::cout << "Palabra almacenada con clave " << i << " es " << mi_mapa[i] << std::endl;
        }
}


Vemos que en el ejemplo hemos usado map como si se tratase de un array. Sin embargo, la diferencia sustancial es que la información se ha guardado de manera ordenada en función del valor de i. Este comportamiento no es visible a simple vista, puesto que el orden de entrada de los datos ya están ordenados, pero considere el siguiente ejemplo

#include<iostream>
#include<string>
#include<map>

int main(void)
{
        std::map<int /*indice o clave*/, std::string /*contenido*/> mi_mapa;
        std::string palabra;
        int numero;


        for(int i(0);i<5;i++)
        {
                std::cout << "Ingrese un número: " << std::endl;
                std::cin >> numero;

                std::cout << "Ingrese una palabra: " << std::endl;
                std::cin >> palabra;


                mi_mapa[numero]=palabra;
        }


        for(i=0;i<5;i++)
        {
                std::cout << "Palabra almacenada con clave " << i << " es " << mi_mapa[i] << std::endl;
        }

}

En este caso, vemos que para cada valor no repetido de i, se muestra un valor de palabra. es decir, que para cada int i, se ha asignado una variable std::string. Este uso sigue siento familiar con el uso de los arrays. Podemos probar cambiando los tipos de variable en la definición de la variable tipo map. Considere el siguiente ejemplo

#include<iostream>
#include<string>
#include<map>

int main(void)
{
        std::map<std::string /*indice_palabra*/,int /*indice_numero*/> mi_mapa;
        std::string palabra;
        int numero;

        mi_mapa["hola"]=10;
        mi_mapa["alfabeto"]=5;
        mi_mapa["zoo"]=0;
        mi_mapa["a"]=3;
        mi_mapa["marmota"]=9;


        std::cout << " La palabra \"alfabeto\" tiene asignado el número " << mi_mapa["alfabeto"] << std::endl;
        std::cout << " La palabra \"a\" tiene asignado el número " << mi_mapa["a"] << std::endl;

        std::cout << " La palabra \"hola\" tiene asignado el número " << mi_mapa["hola"] << std::endl;
        std::cout << " La palabra \"marmota\" tiene asignado el número " << mi_mapa["marmota"] << std::endl;



}

A cada std::string se ha asignado un valor numérico tipo int, de esta manera, los llamados a cada int se realizan mediante el std::string correspondiente a su clave.

Considere ahora el siguiente ejemplo

#include<iostream>
#include<string>
#include<map>

int main(void)
{
        std::map<std::string /*indice_palabra*/,int /*indice_numero*/> mi_mapa;
        std::string palabra;
        int numero;


        for(int i(0);i<5;i++)
        {
                std::cout << "Ingrese un número: " << std::endl;
                std::in >> numero;

                std::cout << "Ingrese una palabra: " << std::endl;
                std::in >> palabra;


                mi_mapa[palabra]=numero;
                std::cout << " La palabra << palabra << " tiene asignado el número " << mi_mapa[palabra] << std::endl;

        }

}

En este caso, a cada palabra ingresada por el usuario, se ha asignado un valor numérico también ingresado por el usuario. El ordenamiento se hace según el operador< definido en la clase std::string.