RSS Atom
speed Posted at midnight, February 28th, 2009

La idea es comparar la velocidad de un programa en C contra la de el mismo programa (algoritmo) en Java

#include <stdio.h>  
int main(int argc, char* argv[]) {  
    long i;  
    long acc = 0;  
    for (i = 0; i < 1000000000; i++) {  
        if (i % 37 == 0 || i % 53 == 0) {  
            acc += i;  
        }  
    }  
    printf("%ld\n", acc);  
    return 0;  
}

public class vel {  
    public static void main(String[] argv) {  
        long i;  
        long acc = 0;  
        for (i = 0; i < 1000000000; i++) {  
            if (i % 37 == 0 || i % 53 == 0) {  
                acc += i;  
            }  
        }  
        System.out.println("" + acc);  
    }  
}  

$ gcc -o vel vel.c
$ javac vel.java
$ time ./vel
    22692504675420780
    real0m48.872s
    user0m48.059s
    sys0m0.064s
$ time java -d64 vel  
    22692504675420780  
    real0m57.900s  
    user0m56.656s  
    sys0m0.068s

C le gana a Java, pero, por muy poco tiempo; no se trata de "órdenes de magnitud" de diferencia. Ahora bien, el tiempo del programa en C es discutible; no he usado optimización. Al recompilar el programa con -O3, el tiempo de ejecución baja a 7 segundos, así que C gana, ahora sí, por un orden de magnitud.

A favor de Java hay que decir que el programa de prueba es muy sencillo; es posible que los tiempos de ejecución sean más parejos cuando los programas sean más complejos (de hecho, hay buena evidencia de que es así).

A manera de prueba, quité las líneas #include <stdio.h> y printf("%ld\\n", acc); del programa en C, y recompilé de nuevo con la máxima optimización disponible; el tiempo de ejecución cayó a 2 milésimas de segundo. Esto puede verse de 2 formas:

  • C puede ser increíblemente rápido, si el programa es suficientemente sencillo.

  • Sólo las cosas sencillas tienen un tiempo de ejecución en C sensiblemente menor respecto a otros lenguajes.

Varios de ustedes se preguntarán porqué defiendo a Java, cuando he dicho varias veces que es una mugre de lenguaje. Y de hecho, lo es; pienso que Java (como lenguaje), es horrible. Pero últimamente he aprendido (muy, muy por encima) cómo se ejecuta Java, y le he tomado respeto a la máquina virtual de Java.

Nótese que estoy hablando de java, y no de javac; la diferencia en velocidad no la hace el compilador, sino la JVM; los programas en Java se compilan a bytecode de la JVM, pero la JVM toma dicho bytecode y lo recompila en tiempo de ejecución. Sí, un JIT. Ése es el truco.

Usar un JIT permite hacer una variedad de optimizaciones que sencillamente no son posibles en tiempo de compilación; por ejemplo, ver qué secciones del programa se ejecutan frecuentemente, para recompilarlas a assembler. Y muchas (si no todas) las optimizaciones que puede hacer un JIT están disponibles para cualquier tipo de lenguaje, bien sea estático (como Java, C#) o dinámico (Python, Lua).

De hecho, a la larga, los lenguajes dinámicos podrán ser más veloces que los estáticos. Para ser más precisos, los lenguajes que permiten mejores abstracciones serán más rápidos que aquellos que no. El motivo de esto es que, al usar operaciones de "más alto nivel", por llamarlas de alguna forma, se delega el problema de optimizar el código. Por ejemplo, considere los siguientes fragmentos de código:

my_list = [slow_function(i) for i   in range(5000)]

for (i = 0; i < 5000; i++) {  
    my_list[i] = slow_function(i);  
}

No hay nada que impida que un futuro intérprete de Python (capaz de usar varios núcleos) vea ese código y decida usar varios hilos para ejecutar varias invocaciones a slow_function de manera simultánea. La velocidad de ejecución habría aumentado varias veces, y lo mejor es que no fue necesario modificar el código. Paralelismo gratuito, cortesía de la máquina virtual que ejecuta el programa.

Del otro lado, no hay mucho que hacer. Por supuesto que es posible hacer que el programa use varios hilos, pero sería necesario reescribir y recompilar el programa. Y, de nuevo, este es un ejemplo sencillo. La lección es: la generalidad da más espacio para la optimización.

Una metáfora (espero) adecuada sería pensar en que se tiene un empleado, que hace cosas por uno. Si le digo "multiplique este par de matrices", puede que le cueste algo de tiempo mirar cómo se hace, pero a manera que aparezcan mejores herramientas (una calculadora, Excel), él podrá hacer la operación más rápido. En cambio, si le digo "Toma el elemento A[1][1] y multiplícalo por B[1][1], y luego A[1][2] y...", él no tendrá opción de acelerar las cosas, aparte de ejecutar la secuencia de órdenes que le he dado más rápido.

Un JIT podría darse cuenta de que estoy multiplicando un par de vectores, y usar una instrucción especial del procesador para hacerlo. Se podría argumentar que un compilador también podría darse cuenta y hacer la misma optimización, pero, esto será más fácil de deducir (inducir?) si la operación solicitada es una operación general (haz este producto vectorial), que si se tiene una secuencia de pequeñas instrucciones (haz estos productos, acumúlalos). Y ahí es donde los lenguajes dinámicos hacen la gran diferencia.

Hay varios esfuerzos, y hay evidencia de que sirven. El mejor ejemplo es la JVM. Para Python, está (estuvo) Psyco, y está (estará?) PyPy. Para Lua se tiene LuaJIT. PyPy en particular es muy interesante.

UPDATE: Esta presentación sirvió como inspiración para este post.

Tags: c plus plus
A day with C++ templates Posted at midnight, January 23rd, 2009

File stuff.h

vector<pair<int, vector<pair<int, int>>>> v_hist_vars;
vector<pair<int, vector<pair<int, int>>>> h_hist_vars;
vector<pair<int, vector<pair<int, int>>>> d1_hist_vars;
vector<pair<int, vector<pair<int, int>>>> d2_hist_vars;

Compiler output

stuff.h:40: error: ISO C++ forbids declaration of vector with no type
stuff.h:40: error: expected ; before < token
stuff.h:41: error: ISO C++ forbids declaration of vector with no type
stuff.h:41: error: expected ; before < token
stuff.h:42: error: ISO C++ forbids declaration of vector with no type
stuff.h:42: error: expected ; before < token
stuff.h:43: error: ISO C++ forbids declaration of vector with no type
stuff.h:43: error: expected ; before < token

And so on. It should be std::vector... And (I actually don't know why) it is bad practice to put a using namespace yaddayadda; on a .h file. OK, whatever. It looks like it might cause namespace pollution, so don't spit on the face of your .h file users hiding a namespace usage thingie there. Second attempt.

std::vector<std::pair<int, std::vector<std::pair<int,int>>>> v_hist_vars;
std::vector<std::pair<int, std::vector<std::pair<int,int>>>> h_hist_vars;
std::vector<std::pair<int, std::vector<std::pair<int,int>>>> d1_hist_vars; 
std::vector<std::pair<int, std::vector<std::pair<int,int>>>> d2_hist_vars;

Compiler output

stuff.h:40: error: >> should be > > within a nested template argument list
stuff.h:40: warning: >> operator will be treated as two right angle brackets in C++0x
stuff.h:40: warning: suggest parentheses around >> expression
stuff.h:40: error: v_hist_vars was not declared in this scope
stuff.h:40: error: >> should be > > within a nested template argument list

It is funny that the compiler understands what I'm telling to it, but it still doesn't let me use that syntax.

Well, no, it ain't funny at all. Third attempt.

std::vector<std::pair<int, std::vector<std::pair<int, int> > > > v_hist_vars;
std::vector<std::pair<int, std::vector<std::pair<int, int> > > > h_hist_vars;
std::vector<std::pair<int, std::vector<std::pair<int, int> > > > d1_hist_vars;
std::vector<std::pair<int, std::vector<std::pair<int, int> > > > d2_hist_vars;

It isn't obvious, but the declaration takes 77 chars. And that is inside a class, so add the indentation for the class body and for the access specifier (at least 4 more chars). And all I wanted was a tree-like structure, without (re)implementing memory allocation, new data structures, and so on. Silly rabbit.

On another file, I got the following compilation error:

stuff.cpp:161: error: cannot convert std::vector<std::pair<int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >, std::allocator<std::pair<int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > > > > to int in initialization

I know it is my fault, but do you really have to call my mother names to tell me so? Who on earth can read that?

C++ : The Perl of static-typed languages.

C++ : the PDP-11 assembler that thinks it's an object system

C++ : As verbose as Java, and no garbage collection.

Well, at least in C++ you can have dynamic arrays of ints, and you don't have to fall back to a hack this ugly. Hint: even it you give it a catchy name, it will still suck. Oh, thanks for generating the code I would be forced to write because the language wasn't properly designed. And that will cause performance to suck so much that even you admit it. Meh.

Tags: c plus plus

Older posts