¡Felices Fiestas!

La maldición de la Callback de jade cómo escribir una Callback en C

Hoy vamos a hablar de un tema un poco especial, las funciones callback. ¿Porqué especiales? Bueno, para empezar, en la biblia del C (el K&R) nunca se habla del argumento, así que un radical C-ista también podría afirmar que "¡las callback no existen!". En realidad, en el K&R se habla ampliamente de los tíos de las callback, es decir, los punteros a función (de los cuales las callback son un caso especial): entonces las callback existen.

No voy a escribir un tratado sobre el uso de las callback (ya puedo escuchar vuestros suspiros de alivio), ni voy a explicar cómo, cuándo, por qué, y (especialmente) si usarlas: hay muchas fuentes en la red interesantes y bien escritas. Eventualmente, sería bueno escribir un post sobre sus tíos, pero dado el tema muy complicado y el probable malestar estomacal que me vendría escribiéndolo, lo aplazo a una fecha futura (para ser claros: incluso Kernighan y Ritchie hablando de Pointers to Functions han titulado el capítulo 5.12 del K&R "Complicated Declarations", y si eran complicadas para ellos...).

¿De qué vamos a hablar entonces? Bueno, yo (como muchos otros, supongo) he usado muchas veces las callback, y he leído código que las usaba (código que era, en la mayoría de los casos, ilegible y difícil de interpretar en relación directamente proporcional a la frecuencia de utilización de las callback, sigh). Y bien, hasta el día en el que escribí una aplicación completa (o sea he escrito, además de la callback, la función a la que pasarla) no me he dado cuenta de algunos detalles ocultos. Por supuesto, si para vosotros las callback no tienen detalles ocultos, podéis dejar de leer lo siguiente y nos vemos en el próximo post.

¿Todavía estáis aquí? Vale, antes de empezar vamos a ver una definición de las callback tomada textualmente de Wikipedia: "una función que se usa como argumento de otra función", y yo agregaría: "y, con frecuencia y/o normalmente, la función llamante es una función de librería". El ejemplo más clásico y conocido citado en literatura es relativo al uso de qsort():

// funzione callback de comparación para la qsort()
static int cbCmpFunc(const void *elem_a, const void *elem_b)
{
    return *(int*)elem_a > *(int*)elem_b;
}

// main
int main(void)
{
    int array[] = {34,12,32,9,10,72,82,23,14,7,94};
    int nelems = sizeof(array) / sizeof(int);

    // ejecuto sort array con qsort()
    qsort(array, nelems, sizeof(int), cbCmpFunc);

    // enseño resultados
    int i;
    for (i = 0; i < nelems; i++)
        printf("%d - ", array[i]);
    printf("\n");

    // salgo
    return 0;
}

La qsort() es una función de libc que implementa el algoritmo de ordenación quicksort, y requiere una función de callback que especifique el tipo de ordenación deseado. Estamos, por tanto, en un caso clásico: qsort() es una función de libreria, y nosotros, a nivel local, la usamos pasándole una callback que, en nuestro ejemplo, se utiliza para ordenar en orden ascendente los números del array.

Y ahora vamos al grano: en otros tiempos, cuando no era fácil como ahora encontrar documentación y ejemplos, se me ocurría leer y escribir código como el que se muestra arriba y me preguntaba (quizás sólo inconscientemente): "pero de donde salen los parámetros elem_a y elem_b de cbCmpFunc()? " y otra vez: "Si llamo a la callback y no le paso explícitamente parámetros, cómo funciona todo?" Bueno, como descubrí más tarde, yo estaba pensando invirtiendo la relación causa-efecto: no era yo quien llamaba la callaback, ¡era la qsort() que la llamaba! Vale, me avergüenza un poco tener que contar una conclusión tan perogrullada, pero, efectivamente, lo comprendí a fondo solo el día en que necesité escribir una función de librería que utilizaba una callback. Claro, ahora con toda la información en la red es mucho más fácil ...

Así que para aclarar, vemos un ejemplo completo (NOTA: el ejemplo se podría escribir todo en un file, pero, como se muestra en los comentarios apropiados debería ser dividido en tres file en un proyecto real):

/* parte que tendría que estar en el file mysort.h
*/
// prototipos para mySort()
typedef int (*mycallback)(int, int);
void mySort(int *array, int nelems, mycallback cmpFunc);

/* parte que tendría que estar en el file mysort.c
 */
// mySort() - función de sort que usa el algoritmo bubblesort
void mySort(int *array, int nelems, mycallback cmpFunc)
{
    // loop sobre todos los elementos de array
    while (nelems > 0) {
        // loop interno con decremento longitud
        int i;
        for (i = 0; i < (nelems -1); i++) {
            // ejecuto callback de comparación
            if (cmpFunc(array[i], array[i + 1])) {
                // eseguo swap di array[i] e array[i+1]
                int temp = array[i];
                array[i] = array[i + 1];
                array[i + 1] = temp;
            }
        }

        // decremento nelems
        nelems--;
    }
}

/* parte que tendría que estar en el file mymain.c
*/
// cbCmpFunc() - función de comparación
static int cbCmpFunc(int elem_a, int elem_b)
{
    return elem_a > elem_b;
}

// main
int main(void)
{
    int array[] = {34,12,32,9,10,72,82,23,14,7,94};
    int nelems = sizeof(array) / sizeof(int);

    // ejecuto sort array
    mySort(array, nelems, cbCmpFunc);

    // enseño resultados
    int i;
    for (i = 0; i < nelems; i++)
        printf("%d - ", array[i]);
    printf("\n");

    // salgo
    return 0;
}

Como podéis ver es muy similar al ejemplo de la qsort(), pero, en lugar de utilizar una función de la libc, se utiliza una función de ordenación escrita ad-hoc, la mySort(). Para este ejemplo he utilizado, para no complicar demasiado el código, un algoritmo de tipo bubblesort, que es (lo sé) un asco, pero, para hacer una prueba sencilla es mas que suficiente. Como notaréis es la mySort(), la que se encarga de escribir los argumentos para la callback, procesando correctamente los otros parámetros que se pasan (array y nelems), y así, mágicamente, aparecen los valores en elem_a y elem_b.

¿Qué os parece? Sí, un poco ingenuo (tal vez), pero que levante la mano quien nunca tuvo dudas en su historia de programador (uhmm... veo pocas manos levantadas). Y si este post ha servido para ampliar el conocimiento sólo a uno de mis lectores estoy super-feliz. Y para los otros, aquellos que ya lo sabían todo de las callback: porque habéis llegado igualmente al final del post?

Hasta el próximo post.

Érase una vez la Optimización cómo optimizar el codigo en C

To be, or not to be, that is the question: Whether 'tis Nobler in the mind to suffer... oops, tal vez me he equivocado de blog. Este no es el blog de literatura Inglesa? Este es un blog sobre programación en C? De acuerdo, ya que estoy, solo hay que cambiar un poco la pregunta: Optimizar, o no optimizar, esa es la pregunta...

La pregunta realmente es: "Cuando escribo código tengo que hacerlo de una manera natural, o más bien instintiva (bueno, siempre y cuando se posee el instinto del programador...) o debo seguir líneas un poco abstrusas y herméticas para que el programa sea más eficiente?" Y, por supuesto, no estoy hablando de algoritmos: en este caso, está claro que un buen algoritmo es mejor que uno malo. Estoy hablando en términos de instrucciones y grupos de instrucciones.

Hagamos una premisa: ya no estamos en el año de la pera. Y considerando esto tenemos que comportarnos/actuar. Antiguamente, los ordenadores eran (respecto a los de ahora) lentos y con pocos recursos, y los compiladores eran mucho más sencillos de los actuales. Y, entonces, utilizando la palabra mágica register se podía acelerar un loop y, consiguiendo escribir un código reducido al máximo omitiendo cualquiera operación (presuntamente) superflua, se obtenían programas mucho más eficientes. ¿Y ahora? ¿Aún tiene sentido escribir código de esta manera? El compilador realmente necesita nuestra ayuda?

El asunto es complejo, y creo que necesitaremos más de un post. En este, para empezar, analizaremos un ejemplo sencillo (?), La optimización de un loop, que es, por supuesto, una parte (de hecho, La Parte) critica para el rendimiento de un programa. Comencemos:

// myFunc1()
// versión con multiplicación, array e índice
int myFunc1(int array[], int nelems)
{
    int i;
    for (i = 0; i < nelems; i++)
        array[i] = i * 2;
}

La función es muy simple, pero contiene un bucle, y si nelems es muy grande podría llegar a ser costoso. Probemos a optimizarla usando dos técnicas: la Strength Reduction y ​​la Induction Variable: Vamos a ver lo que podemos lograr a través de varios pasos:

// myFunc2()
// versión con incremento en lugar de multiplicación
int myFunc2(int array[], int nelems)
{
    int i, incr;
    for (i = 0, incr = 0; i < nelems; i++) {
        array[i] = incr;
        incr += 2;
    }
}

// myFunc3()
// versión con incremento y pointer en lugar de array
int myFunc3(int array[], int nelems)
{
    int *ptr = array;
    int i, incr;
    for (i = 0, incr = 0; i < nelems; i++, ptr++) {
        *ptr = incr;
        incr += 2 ;
    }
}

// myFunc4()
// versión con incremento, pointer y sin indice
int myFunc4(int array[], int nelems)
{
    int *ptr = array;
    int limit = nelems * 2;
    int incr;
    for (incr = 0; incr < limit; incr += 2, ptr++)
        *ptr = incr;
}

Según lo prometido y dicho, en este post no quiero limitarme a proponer técnicas de optimización sin proporcionar datos, así que he escrito un programa de prueba y, en mi ordenador, con un valor de nelems lo suficientemente grande (0xFFFFFFF) los resultados son los siguientes:

- compilación sin optimización
myFunc1 - Tiempo transcurrido: 1.720000 segundos.
myFunc2 - Tiempo transcurrido: 1.340000 segundos.
myFunc3 - Tiempo transcurrido: 1.160000 segundos.
myFunc4 - Tiempo transcurrido: 0.920000 segundos.

Por lo tanto, parece que las técnicas de optimización funcionan. Vamos a probar de compilar optimizando, o sea, dejamos que se ocupe el compilador: usaremos la opción -O2 de GCC. Veamos los nuevos resultados:

- compilación con optimización (-O2)
myFunc1 - Tiempo transcurrido: 0.940000 segundos.
myFunc2 - Tiempo transcurrido: 0.540000 segundos.
myFunc3 - Tiempo transcurrido: 0.540000 segundos.
myFunc4 - Tiempo transcurrido: 0.540000 segundos.

Ohhh, qué sorpresa! Parece que el compilador es mejor que nosotros! Con la opción-O2, la versión sin optimizar (myFunc1) se comporta más o menos como la que hemos optimizado nosotros (myFunc4) sin utilizar -O2. No es una sorpresa: simplemente significa que el compilador ha hecho (probablemente) nuestras optimizaciones manuales. También notamos que, utilizando cualquiera de las versiones optimizadas manualmente, el compilador es capaz de añadir un plus adicional de mejora.

Sólo para confundirnos más las ideas, vamos a hacer otro test, sustituyendo la multiplicación por dos con un Shift Lógico:

/ myFunc2Bis()
// versión con shift lógico en lugar de multiplicación
int myFunc2Bis(int array[], int nelems)
{
    int i;
    for (i = 0; i < nelems; i++)
        array[i] = i << 1;
}

Y vemos la velocidad sin la optimización del compilador:

- compilación sin optimización
myFunc2Bis - Tiempo transcurrido: 0.950000 segundos.

Mira, parece que con usando solo el shift logico se consigue el mismo resultado que se obtiene aplicando todas las técnicas ilustradas (myFunc4). Y si además utilizamos la opción -O2, ¿qué pasa?

- compilación con optimización (-O2)
myFunc2Bis - Tiempo transcurrido: 0.540000 segundos.

obtenemos el mismo resultado optimizado que hemos visto arriba.. Tal vez hemos descubierto el secreto del compilador...

La primera conclusión (pero seguirán otros capítulos): merece la pena transformar un código legible y claro como el de myFunc1() en uno mucho más críptico, como el de myFunc4(), simplemente porque no confiamos en el compilador? O bien, podría añadir, porque somos tan presuntuosos como para pensar que podemos hacerlo mejor que el compilador? Repito: ya no estamos en el año de la pera, y considerando esto tenemos que actuar.

Por lo visto hasta ahora, parece que la única ayudita manual que podemos dar es usar (cuando sea posible, y sólo en los puntos realmente críticos) shift logicos en lugar de multiplicaciones. En este caso, recomiendo añadir un comentario, para evitar las maldiciones de los que leen nuestro código. Y si estáis impacientes de descubrir otras informaciones útiles en la optimización, y no queréis esperar mis próximos episodios (traidores!), os sugiero la habitual ronda en Google, o leer directamente un excelente artículo (en Italiano, lo siento) del igualmente excelente Carlo Pescio.

Volveré sobre el tema, intentando agregar datos reales y trabajo de pruebas (¡habéis visto que he cumplido mi promesa!) a los estudios sólo teóricos disponibles en la red. Y si no, ¿qué hago aquí?

Hasta el próximo post.