Estoy enseñando Introducción a Ciencias de la Computación II (mejor conocida como ICC-2) por primera vez en mi vida, en gran medida por un ligero error administrativo. La verdad es que me estoy divirtiendo como enano (al parecer, tristemente disfruto yo más el curso que mis alumnos), y entre las cosas divertidas que decidí hacer fue el darle a mis alumnos la oportunidad de hacer las prácticas en C (en lugar de Java) por un punto extra durante el curso, o medio si hacen al menos la mitad. Desafortunadamente, ninguno de mis alumnos me ha entregado una práctica escrita en C.
Como sea, para poder dejarles las prácticas en C a mis alumnos, primero tengo que hacerlas yo, y eso es en gran medida la razón de que me esté divirtiendo tanto. Por supuesto también hago las prácticas en Java; como ICC-2 es en gran parte estructuras de datos, esto también significa ver las características novedosas de Java, como son iteradores y genéricos. Lo cual también es muy divertido; especialmente cuando puedo comparar los dos lenguajes en cosas como velocidad de ejecución.
Como es necesario siempre que uno ve arreglos y listas, les dejé a mis estudiantes que programaran QuickSort y MergeSort. Yo recuerdo que como estudiante tuve que programar esos algoritmos al menos tres veces: la primera en ICC-2, la segunda en Análisis de Algoritmos, y ahora sí que como dice la canción, la tercera por placer. También recuerdo claramente que QuickSort me parecía el mejor de ambos algoritmos; la inocencia de tener veinte años, supongo.
Total que implementé ambos algoritmos en C y en Java, y me llevé una sorpresa con los resultados. Voy a relatar lo que resultó de investigar porqué las diferencias en velocidades, que la verdad yo no termino de entender.
Aquí está QuickSort en Java:
public static void swap(T[] a, int i, int j) {
if (i == j)
return;
T t = a[j];
a[j] = a[i];
a[i] = t;
}
public static < T extends Comparable < T > >
void quickSort(T[] a) {
quickSort(a, 0, a.length-1);
}
private static < T extends Comparable < T > >;
void quickSort(T[] a, int ini, int fin) {
if (fin - ini < 1)
return;
int i = ini + 1, j = fin;
while (i < j)
if (a[i].compareTo(a[ini]) > 0 &&
a[j].compareTo(a[ini]) < = 0)
swap(a, i++, j--);
else if (a[i].compareTo(a[ini]) <= 0)
i++;
else
j--;
if (a[i].compareTo(a[ini]) > 0)
i--;
swap(a, ini, i);
quickSort(a, ini, i-1);
quickSort(a, i+1, fin);
}
Y aquí está en C:
inline static void
swap(void** a, int i, int j)
{
if (i == j)
return;
void* t = a[i];
a[i] = a[j];
a[j] = t;
}
void
quicksort(void** a, int n, func_compara f)
{
quicksort_aux(a, 0, n-1, f);
}
static void
quicksort_aux(void** a, int ini, int fin, func_compara f) {
if (fin - ini < 1)
return;
int i = ini + 1, j = fin;
while (i < j)
if (f(a[i], a[ini]) > 0 &&
f(a[j], a[ini]) < = 0)
swap(a, i++, j--);
else if (f(a[i], a[ini]) <= 0)
i++;
else
j--;
if (f(a[i], a[ini]) > 0)
i--;
swap(a, ini, i);
quicksort_aux(a, ini, i-1, f);
quicksort_aux(a, i+1, fin, f);
}
(En mi blog el código aparece bonito con destacamiento de sintaxis; no sé cómo aparecerá en RSS, pero dudo que bonito.)
Con el código así, la versión en Java necesita 33.4 segundos (en promedio en mi máquina) para ordenar un arreglo de un millón (1,000,000) de elementos aleatorios. Sin optimizaciones, la versión en C tarda 114.7 segundos; lo cual es una diferencia brutal, si me permiten decirlo. Con la mejor optimización (-O3; el resultado es idéntico a -Ofast), esta velocidad baja a 44.85 segundos; mucho mejor, pero de cualquier forma más lento que con Java.
La versión en C utiliza void** como tipo del arreglo, y recibe un apuntador a función f justamente para emular los genéricos de Java; la idea es que el QuickSort de C pueda ordenar arreglos de cualquier tipo de elemento. Nada más por completez, incluyo la definición del tipo func_compara, así como la implementación usada para estas pruebas:
typedef int (*func_compara) (const void* a,
const void* b);
int
compara_enteros(const void* a, const void* b)
{
int aa = *((int*)a);
int bb = *((int*)b);
return aa - bb;
}
Mi primera impresión fue que estos “genéricos” en C (altamente basados en la biblioteca GLib) le estaban dando en la madre a la velocidad de ejecución de mi implementación en C. El andar siguiendo los apuntadores, sacar el valor de las referencias en compara_enteros, y los castings probablemente eran la razón (pensaba yo) de que mi versión en C fuera (ligeramente) más lenta que la de Java. Así que hice trampa y volví a implementar QuickSort, pero esta vez nada más para enteros:
inline static void
swap_int(int* a, int i, int j)
{
if (i == j)
return;
int t = a[i];
a[i] = a[j];
a[j] = t;
}
void
quicksort_int(int* a, int n)
{
quicksort_int_aux(a, 0, n-1);
}
static void
quicksort_int_aux(int* a, int ini, int fin) {
if (fin - ini < 1)
return;
int i = ini + 1, j = fin;
while (i < j)
if (a[i] > a[ini] &&
a[j] < = a[ini])
swap_int(a, i++, j--);
else if (a[i] <= a[ini])
i++;
else
j--;
if (a[i] > a[ini])
i--;
swap_int(a, ini, i);
quicksort_int_aux(a, ini, i-1);
quicksort_int_aux(a, i+1, fin);
}
No muy sorprendentemente, esta versión le partió completamente su madre a la de Java: tarda en promedio 6.35 segundos. Hago notar que los elementos del arreglo son generados aleatoriamente; por lo que el escoger un pivote aleatorio entre ini y fin no serviría (en teoría) de nada. Ciertamente no marcó ninguna diferencia en mis pruebas.
Aunque esta versión es bastante rápida, estaba haciéndo muchísima trampa. De nada (o muy poco) me sirve un QuickSort rapidísimo, si voy a tener que reimplementarlo cada vez que cambie el tipo de mis arreglos. Así que me puse a pensar cómo mejorar una versión “genérica” en C. La respuesta es que sí se puede, pero es bastante feo desde mi punto de vista.
La idea es sencillamente utilizar aritmética de apuntadores, y al intercambiar elementos el copiarlos usando la memoria:
inline static void
swap_memcpy(void* a, int i, int j, size_t s, void* t)
{
if (i == j)
return;
memcpy(t, a+(i * s), s);
memcpy(a+(i * s), a+(j * s), s);
memcpy(a+(j * s), t, s);
}
void
quicksort_memcpy(void* a, int n, size_t s, func_compara f)
{
void* t = malloc(s);
quicksort_memcpy_aux(a, 0, n-1, f, s, t);
free(t);
}
static void
quicksort_memcpy_aux(void* a, int ini, int fin,
func_compara f, size_t s, void* t) {
if (fin - ini < 1)
return;
int i = ini + 1, j = fin;
while (i < j)
if (f(a+(i*s), a+(ini*s)) > 0 &&
f(a+(j*s), a+(ini*s)) < = 0)
swap_memcpy(a, i++, j--, s, t);
else if (f(a+(i*s), a+(ini*s)) <= 0)
i++;
else
j--;
if (f(a+(i*s), a+(ini*s)) > 0)
i--;
swap_memcpy(a, ini, i, s, t);
quicksort_memcpy_aux(a, ini, i-1, f, s, t);
quicksort_memcpy_aux(a, i+1, fin, f, s, t);
}
Esta versión es superior a la de void** ya que puedo pasarle un arreglo de tipo int* directamente, y funciona sin problema; la versión void** necesita por fuerza que le pase un arreglo de apuntadores al tipo que me interesa; en otras palabras, tengo que pasarle un int**, y además tengo que hacerle cast a void**. Además de esto (que no es poco), es más rápido que la primera versión en C, y más rápido que la versión en Java. No por mucho, pero más rápido: tarda 27.5 segundos con un millón de elementos.
Por lo demás, está bastante fea; necesito por fuerza el tamaño del tipo que me interesa ordenar (porque el arreglo lo veo como un chorizo enorme de bytes), y por lo mismo para intercambiar elementos del arreglo debo utilizar memcpy, además de que cargo por todas partes un pedazo de memoria t para guardar el valor temporal durante el intercambio; la alternativa hubiera sido usar variables globales (the horror!), o solicitar y liberar memoria en cada intercambio de variables.
Hasta aquí estaba más o menos satisfecho: ya tenía una versión “genérica” en C que era más rápida que la de Java (aunque desde mi punto de vista la solución sea bastante fea), pero entonces se me ocurrió que estaba siendo muy injusto: si hice una versión tramposa para C (la que sólo sirve para enteros), debería hacer una versión tramposa para Java también. Así que eso hice:
public static void swap(int[] a, int i, int j) {
if (i == j)
return;
int t = a[j];
a[j] = a[i];
a[i] = t;
}
public static void quickSort(int[] a) {
quickSort(a, 0, a.length-1);
}
private static void quickSort(int[] a, int ini, int fin) {
if (fin - ini < 1)
return;
int i = ini + 1, j = fin;
while (i < j)
if (a[i] > a[ini] &&
a[j] < = a[ini])
swap(a, i++, j--);
else if (a[i] <= a[ini])
i++;
else
j--;
if (a[i] > a[ini])
i--;
swap(a, ini, i);
quickSort(a, ini, i-1);
quickSort(a, i+1, fin);
}
Esta versión tarda 2.26 segundos en ordenar un arreglo de un millón de elementos, lo que la hace casi tres veces más rápida que la versión tramposa de C. ¿Por qué ocurre esto? Sinceramente, no tengo idea; lo único que se me ocurre es que con 1,000,000 recursiones, el compilador Just-In-Time (JIT) de Java alcanza a optimizar algo durante la ejecución del programa que la versión en C no puede. Yo no veo otra alterantiva; pero me encantaría oír teorías.
Sólo un pequeño dato para terminar con QuickSort; hice otra versión tramposa en C para el tipo long, y ésta corre en 4.35 segundos, lo que la sigue haciendo más lenta que la de Java, pero más rápida que la de enteros (int) en C. ¿A lo mejor porque mi máquina es arquitectura AMD64? Una vez más, no tengo idea; pero sí me gustaría saber qué carajo hace la JVM para ser tan rápida.
Los enigmas no terminaron ahí, porque también implementé MergeSort en Java y C. Primero les enseño mis estructuras de datos en ambos lenguajes; estas son mis listas en Java:
public class Lista< T > implements Iterable< T > {
protected class Nodo< T > {
public T elemento;
public Nodo< T > siguiente;
public Nodo< T > anterior;
}
protected Nodo< T > cabeza;
protected Nodo< T > rabo;
public void agregaFinal(T elemento) { ... }
public void agregaInicio(T elemento) { ... }
...
}
Ignoren el Iterable; es sólo para poder recorrer la lista con el foreach de Java. Las listas en C siguen el modelo estructurado en lugar del orientado objetos; por lo tanto en C lidiamos con los nodos directamente (mientras en Java siempre están ocultos al usuario):
struct lista
{
void* elemento;
struct lista* siguiente;
struct lista* anterior;
};
struct lista* lista_agrega_final (struct lista* lista,
void* elemento);
struct lista* lista_agrega_inicio (struct lista* lista,
void* elemento);
Por su puesto para su práctica mis alumnos tuvieron que implementar más cosas; pero nada de eso es relevante para lo que discuto aquí. Mi implementación de MergeSort en Java (para estas listas) fue la siguiente:
private static < T extends Comparable< T >> Lista< T >
merge(Lista< T > li, Lista< T > ld) {
Lista< T > l = new Lista< T >();
Lista< T >.Nodo< T > nli = li.cabeza;
Lista< T >.Nodo< T > nld = ld.cabeza;
while (nli != null && nld != null) {
if (nli.elemento.compareTo(nld.elemento) < 0) {
l.agregaFinal(nli.elemento);
nli = nli.siguiente;
} else {
l.agregaFinal(nld.elemento);
nld = nld.siguiente;
}
}
while (nli != null) {
l.agregaFinal(nli.elemento);
nli = nli.siguiente;
}
while (nld != null) {
l.agregaFinal(nld.elemento);
nld = nld.siguiente;
}
return l;
}
public static < T extends Comparable< T >> Lista< T >
mergeSort(Lista< T > l) {
int n = l.longitud();
if (n == 1)
return l;
Lista< T > li = new Lista< T >();
Lista< T > ld = new Lista< T >();
int i = 0;
Iterator< T > iterador = l.iterator();
while (i++ < n/2)
li.agregaFinal(iterador.next());
while (i++ <= n)
ld.agregaFinal(iterador.next());
li = mergeSort(li);
ld = mergeSort(ld);
return merge(li, ld);
}
La versión en C es la que sigue:
static struct lista*
merge(struct lista* li, struct lista* ld, func_compara f)
{
struct lista* l = NULL;
struct lista* ii = li;
struct lista* id = ld;
while (ii != NULL && id != NULL) {
if (f(ii->elemento, id->elemento) < 0) {
l = lista_agrega_inicio(l, ii->elemento);
ii = ii->siguiente;
} else {
l = lista_agrega_inicio(l, id->elemento);
id = id->siguiente;
}
}
while (ii != NULL) {
l = lista_agrega_inicio(l, ii->elemento);
ii = ii->siguiente;
}
while (id != NULL) {
l = lista_agrega_inicio(l, id->elemento);
id = id->siguiente;
}
struct lista* tmp = lista_reversa(l);
lista_libera(l);
return tmp;
}
struct lista*
mergesort(struct lista* l, func_compara f)
{
int n = lista_longitud(l);
if (n == 1) {
struct lista* uno =
lista_agrega_inicio(NULL, l->elemento);
return uno;
}
struct lista* li = NULL;
struct lista* ld = NULL;
int i = 0;
struct lista* tmp = l;
while (i++ < n/2) {
li = lista_agrega_inicio(li, tmp->elemento);
tmp = tmp->siguiente;
}
while (i++ < = n) {
ld = lista_agrega_inicio(ld, tmp->elemento);
tmp = tmp->siguiente;
}
tmp = lista_reversa(li);
lista_libera(li);
li = tmp;
tmp = lista_reversa(ld);
lista_libera(ld);
ld = tmp;
tmp = ordenamientos_mergesort(li, f);
lista_libera(li);
li = tmp;
tmp = ordenamientos_mergesort(ld, f);
lista_libera(ld);
ld = tmp;
tmp = merge(li, ld, f);
lista_libera(li);
lista_libera(ld);
return tmp;
}
Dado que una "lista" es realmente un nodo de la lista (siguiendo el modelo utilizado por GLib), no tengo guardado en nigún lado el rabo de la lista; por eso agrego elementos al inicio, y cuando termino la volteo. Hice mis pruebas de nuevo con 1,000,000 elementos, y lo primero que me sorprendió fue que fuera tan rápido en comparación con QuickSort; yo recordaba que cuando los implementé en mi carrera, la diferencia no era tanta. A lo mejor ahora programo mejor.
La versión en Java tarda (en promedio) 2.25 segundos; la versión en C 4.8, más del doble. Esta vez ya estaba preparado y no me sorprendió tanto, y de inmediato pensé que una obvia optimización es cargar el rabo de cada lista, y así poder agregar elementos al final en tiempo constante, sin tener que preocuparme de voltearla después. Para eso creé esta estructura de datos:
struct dlista {
struct lista* cabeza;
struct lista* rabo;
int longitud;
};
void dlista_agrega_final(struct dlista* dl, void* elemento);
void dlista_agrega_inicio(struct dlista* dl, void* elemento);
Pude entonces simplificar mi versión de MergeSort:
static struct dlista*
merge(struct dlista* dli, struct dlista* dld, func_compara f)
{
struct dlista* dl = dlista_nueva();
struct lista* ii = dli->cabeza;
struct lista* id = dld->cabeza;
while (ii != NULL && id != NULL) {
if (f(ii->elemento, id->elemento) < 0) {
dlista_agrega_final(dl, ii->elemento);
ii = ii->siguiente;
} else {
dlista_agrega_final(dl, id->elemento);
id = id->siguiente;
}
}
while (ii != NULL) {
dlista_agrega_final(dl, ii->elemento);
ii = ii->siguiente;
}
while (id != NULL) {
dlista_agrega_final(dl, id->elemento);
id = id->siguiente;
}
return dl;
}
struct dlista*
mergesort(struct dlista* dl, func_compara f)
{
int n = dl->longitud;
if (n == 1) {
struct dlista* uno = dlista_nueva();
dlista_agrega_final(uno, dl->cabeza->elemento);
return uno;
}
struct dlista* dli = dlista_nueva();
struct dlista* dld = dlista_nueva();
int i = 0;
struct lista* tmp = dl->cabeza;
while (i++ < n/2) {
dlista_agrega_final(dli, tmp->elemento);
tmp = tmp->siguiente;
}
while (i++ < = n) {
dlista_agrega_final(dld, tmp->elemento);
tmp = tmp->siguiente;
}
struct dlista* tmp2;
tmp2 = mergesort(dli, f);
dlista_libera(dli);
dli = tmp2;
tmp2 = mergesort(dld, f);
dlista_libera(dld);
dld = tmp2;
tmp2 = merge(dli, dld, f);
dlista_libera(dli);
dlista_libera(dld);
return tmp2;
}
Esta nueva versión corre en 2.72 segundos; mucho más cerca a la versión de Java, pero todavía más lenta. Lo único extra que se me ocurrió que podía hacer era eliminar el manejo de memoria; pensando que tal vez Java es más rápido (en este caso) porque puede diferir el liberar memoria hasta después de correr el algoritmo. Así que quité las llamadas a la función dlista_libera tratando de emular como sería tener recolector de basura, y por supuesto el algoritmo corrió ahora más lento: 2.92 segundos. ¿A lo mejor con 1,000,000 de elementos consigo forzar que Linux pase memoria al swap? No tengo idea; pero la verdad lo dugo: tengo 4 Gb de memoria, y no vi que el foquito de mi disco duro se prendiera.
Todos estos resultados pueden atribuirse a errores del programador (dícese, yo), pero honestamente no creo estar haciendo nada obviamente mal. Mi teoría favorita (y de hecho la única) es que el compilador JIT de la JVM está haciendo algo de magia que el simple ensamblador optimizado de C no puede; lo cual sería una muesta feaciente e innegable de las ventajas que pueden tener los lenguajes de programación que compilan para una máquina virtual altamente optimizada. Sumado a que es mucho más sencillo programar todas estas estructuras de datos si uno no tiene que preocuparse de manejar la memoria, y además con la fuerte (y desde mi punto de vista muy bonita) tipificación de datos que ofrecen los genéricos en Java, la verdad no vería por qué alguien escogería C sobre Java para programar cosas que tengan que repetir una misma tarea cientos de miles de veces.
Por supuesto es un experimento sólo en mi máquina, y en estos días 1,000,000 de elementos me suena a que ya no es realmente tanto. Con 10,000,000 de elementos, la versión en C tardó 36.32 segundos, y la versión en Java tardó 41.98 segundos; además de que tuve que aumentarle el tamaño al heap de la máquina virtual de Java a 4 Gb. Si lo aumentaba a 2 Gb, tardaba 54.99 segundos; en ambos casos el foquito de mi disco duro se prendió. En uso de memoria, sin duda C sigue siendo mucho superior (al costo de que uno tiene que andar manejándola a mano).
De cualquier forma, es impresionante lo rápido que es Java hoy en día; cuando yo lo comencé a aprender (el siglo pasado), todavía muchísima gente se quejaba de lo lento que era. Ahora yo (que no tengo poca experiencia programando) no puedo hacer que una versión en C del mismo algoritmo le gane.
En nuestras vidas profesionales lo más probable es que mis alumnos y yo no tengamos que implementar ninguno de estos algoritmos nunca; lo más seguro es que ya existirá una versión suficientemente buena y suficientemente optimizada disponible, lo que haría medio inútil que la implementáramos de nuevo. Sin embargo, me parece importante que un computólogo las implemente aunque sea una vez en su vida, y entienda cómo funcionan y cómo podrían utilizar una versión personalizada para algún obscuro problema que se encuentren.
Y ahora tengo que trabajar en mis algoritmos para árboles binarios.
Imprimir entrada
