Posted by
chochos on Oct 20, 2011 in
Scala |
0 commentsHace mucho tiempo, implementé un codificador para Base 64 en Java. El algoritmo es relativamente simple: consiste en codificar 3 bytes como 4 caracteres de texto, tomados de un alfabeto de 64 posibles caracteres (de ahí el nombre). El alfabeto está compuesto de las letras A a la Z mayúsculas y luego minúsculas, los dígitos y los signos + y /. Existe además un símbolo especial = para indicar la ausencia de datos, cuando se codifica un bloque de menos de 3 bytes.
Cuando lo implementé en Java, lo primero que hice fue definir el alfabeto, como un arreglo de char Para ello, dentro de la clase que iba a contener los dos métodos (codificar y decodificar), hice esto:
public class Base64 {
private static char[] HEX_CHARS = new char[]{
'0', '1', '2', '3', '4', '5', '6', '7',
'8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
};
/** El arreglo de 64 caracteres que componen el 'alfabeto' de base 64. */
static final char[] B64_CHARS = new char[64];
static {
for (int i = 0; i < 26; i++) {
B64_CHARS[i] = (char)(i + 65);
}
for (int i = 26; i < 52; i++) {
B64_CHARS[i] = (char)(i + 71);
}
for (int i = 52; i < 63; i++) {
B64_CHARS[i] = (char)(i - 4);
}
B64_CHARS[62] = '+';
B64_CHARS[63] = '/';
}
}
Es decir, en el static de la clase, que se ejecuta cuando se carga la misma, es donde lleno el arreglo de 64 caracteres. Estoy consciente de que bien podría simplemente tener la cadena “ABCDEF…xyz0123…9+/”, pero no lo tengo por dos razones: Primero, qué flojera teclearla y segundo, tendría que hacer pruebas más rigurosas para verificar que no me equivoqué al teclearla. O revisarla manualmente o pedirle a alguien más que lo haga. Qué padre, tener que revisar que una cadena vaya de la A a la Z, etc. Qué bueno que tenemos computadoras que puedan generar esos datos por nosotros.
Ahora, para codificar un arreglo de bytes como texto en base64, lo que hacemos es codificar bloques de 3 bytes, cada uno de los cuales resulta en 4 caracteres, porque se separan los 3 bytes, que son 3 grupos de 8 bits, para un total 24 bits, en 4 bloques de 6 bits; con 6 bits se pueden representar números del 0 al 63, y los representaremos con un caracter del alfabeto que ya definimos. El último bloque puede contener menos de 3 bytes (puede estar vacío, en cuyo caso no se hace nada, o tener 1 ó 2 bytes), por lo que se trata de manera especial:
- Un bloque vacío (0 bytes) se representa con una cadena vacía
- Un bloque de un byte requiere 2 caracteres (6 bits en un caracter y 2 bits en el siguiente
- Un bloque de dos bytes requiere 3 caracteres (6 bits en el primer caracter, 6 en el segundo, y los últimos 4 bits van al tercer caracter)
En los últimos dos casos, faltan caracteres para tener un bloque de 4; lo que se hace es rellenarlo con =. De modo que un bloque de un byte tendrá terminación == y un bloque de dos bytes tendrá un = al final.
Pues bien, podemos hacer la implementación en Java usando un StringBuilder en donde vamos a poner el texto. El método para codificar debe recibir un arreglo de bytes, y podemos recibir también el índice inicial donde debemos empezar a codificar y el número de bytes que debemos codificar. Esto nos permite codificar un segmento de un arreglo y no solamente arreglos enteros.
ADVERTENCIA: El siguiente código contiene operaciones directas sobre bits, tales como bitwise-and, bitwise-or, y bitshifts, por lo que se recomienda verlo acompañado de un programador Senior.
public static String base64Encode(byte[] input, int start, int len) {
//Le ponemos capacidad inicial
StringBuilder buf = new StringBuilder((input.length * 4) / 3);
//Leemos de tres en tres, escribimos de cuatro en cuatro
int end = start + len;
for (int i = start; i < end; i += 3) {
int indice = -1;
int uno = 0, dos = 0, tres = 0;
//Los bytes van del -128 al 127, pero hay que convertirlos a valores del 0 al 255
uno = input[i] & 0xff;
//tomar los primeros seis bits del primer byte
buf.append(B64_CHARS[uno >> 2]);
//Los ultimos dos bits van al siguiente caracter
indice = (uno & 0x03) << 4;
if (i + 1 < len) {
//Leer el segundo byte y pasarlo a positivo
dos = input[i + 1] & 0xff;
//Contar tambien los primeros 4 bits del segundo byte
indice |= (dos & 0xf0) >> 4;
}
buf.append(B64_CHARS[indice]);
//Leer el tercer byte y pasarlo a positivo
if (i + 2 < len) {
tres = input[i + 2] & 0xff;
//Los ultimos 4 del segundo y los primeros 2 del tercero
indice = ((dos & 0x0f) << 2) | ((tres & 0xC0) >> 6);
buf.append(B64_CHARS[indice]);
//los ultimos 6 del tercero
indice = tres & 0x3f;
buf.append(B64_CHARS[indice]);
} else if (i+2 == len) {
indice = (dos & 0x0f) << 2;
buf.append(B64_CHARS[indice]);
buf.append("=");
}
if (i + 1 >= len) {
buf.append("==");
} else if (i >= len) {
buf.append("=");
}
}
return buf.toString();
}
A ver… ¿no dije que era un algoritmo relativamente sencillo? ¿Por qué 27 líneas de código entonces? Este es uno de los problemas de la programación en estilo imperativo… estamos expresando exactamente no sólo lo que se tiene que hacer, sino cómo se tiene que hacer. Y cada condición especial (lo del último bloque, que si mide un byte, o dos, o tres) hay que considerarla y manejarla de manera especial.
Muy probablemente este código se pueda simplificar. Lo que no me gusta mucho, es que aunque yo mismo lo escribí, lo veo y ya no quiero ni moverle; no es obvio si es optimizable o simplificable, dónde puedo quitar código, cómo refactorizarlo, etc.
El decodificador de plano ya mejor ni lo pongo, es todavía más código, y son puras líneas muy cortas. Incluso tiene breaks. No estoy orgulloso de esas 35 líneas (efectivas) de código. Pero al igual que el método para codificar, tampoco encuentro la manera de simplificarlo.
Eso sí, este código es muy rápido. Se tarda entre 280 y 320 milisegundos en codificar 10MB de datos. No lo hice para codificar bloques tan largos de código, de hecho este código se usa en la práctica para codificar bloques de menos de 2KB, pero potencialmente muchos bloques cortos, por lo que sí es importante el performance. Este es uno de esos raros casos en que la manera en que manipulamos los bytes directamente nos puede dar un mejor performance.
Ahora en Scala
A manera de ejercicio, decidí implementar ahora el codificar Base 64 en Scala. Algo que me gustó desde el principio fue la manera en que puedo definir el alfabeto:
object Base64 {
val chars = ('A' to 'Z') ++ ('a' to 'z') ++ ('0' to '9') :+ '+' :+ '/'
}
Es decir, el rango de caracteres A-Z, concatenado con el rango de caracteres a-z, con los dígitos y luego con los dos símbolos adicionales. El operador ++ es un método de las listas de Scala, para concatenar dos listas, y el método :+ es para crear una nueva lista que trae el nuevo elemento al final.
En Scala, todo es un objeto. Por lo tanto, los arreglos de bytes son objetos, y tienen muchos de los métodos de las colecciones de Scala, por ejemplo para particionar o para obtener un sub-arreglo. Por lo tanto, el método para codificar no necesita que le indiquemos índice inicial y final, porque simplemente podemos obtener primero el sub-arreglo que queremos codificar y pasar eso al método. Y otra cosa: aprovechemos los beneficios de la programación funcional, y el estilo declarativo. Simplemente tengo que indicar a grandes rasgos, lo que quiero hacer, y luego voy implementando las partes más pequeñas. El algoritmo expresado de manera lineal es:
Tomar bloques de 3 bytes, y generar bloques de 4 caracteres, para formar una cadena al final.
Esto expresado en Scala puede ser así (aunque no tengamos todo lo necesario ahorita):
bytes grouped 3 map encodeBlock flatten
Lo anterior puede funcionar, si bytes es un arreglo o lista o secuencia o lo que sea de bytes, porque a las colecciones en Scala les podemos pedir que nos den un iterador que tome grupos de N elementos. Entonces bytes grouped 3 nos dará un iterador para poder procesar grupos de 3 bytes. Si al final hay menos de 3 bytes, nos devuelve lo que queda (el último grupo puede ser más corto). Los iteradores también tienen la función map, a la que podemos pasarle una función que reciba un elemento y devuelva otra cosa, y entonces el iterador termina devolviendo los elementos que resultaron de cada invocación a la función. En este caso me inventé una función llamada encodeBlock, que me imagino que debe recibir un bloque de 3 bytes y nos debe devolver ya sea una cadena, o una lista o algo con 4 caracteres. Por lo tanto al final tendremos una lista de listas, y entonces el método flatten nos sirve para convertirla en una lista plana; lo que hace flatten cuando tienes una lista de listas por ejemplo, es que extrae los elementos de las listas internas y devuelve una lista ya plana, con los elementos de cada una; es decir:
List(List(1,2,3), List(4,5), List(6)).flatten == List(1,2,3,4,5,6)
Y bueno, al final hay que hacer una cadena con esa colección de caracteres, pero lo más importante es que hay que implementar ese encodeBlock, el método que codifica un bloque de 1 a 3 bytes. La manera en que lo implementé fue como una función dentro del método encode, porque no le sirve a nadie fuera de ese método:
def encode(a:Seq[Byte]):String = {
def encodeBlock(seg:Seq[Byte]) = {
//El primer caracter son los primeros 6 bits del primer byte
val c0 = (seg(0) & 0xff) >> 2
//El segundo caracter son los últimos 2 bits del primer byte y los 4 primeros bits del segundo byte (si existe)
val c1 = ((seg(0) & 3) << 4) | (if (seg.size > 1) {
(seg(1) & 0xf0) >> 4
} else 0)
//El tercer caracter son los últimos 4 bits del segundo byte y los primeros 2 bits del tercer byte (si existe)
val c2 = (if (seg.size > 1) {
(seg(1) & 0xf) << 2
} else -1) | (if (seg.size > 2) {
(seg(2) & 0xf0) >> 6
} else if (seg.size > 1) 0 else -1)
//Y el cuarto caracter son los últimos 6 bits del tercer byte (si existe)
val c3 = if (seg.size > 2) (seg(2) & 0x3f) else -1
//Al final devolvemos una lista de caracteres
//Los primeros dos siempre vienen,
List[Char](chars(c0), chars(c1),
//Pero el tercero y cuarto pueden ser "=" si no hay más bytes
if (c2 >=0) chars(c2) else '=', if (c3 >= 0) chars(c3) else '=')
}
//Al final hacemos lo que ya había explicado, y a la lista resultante le invocamos mkString que nos da una cadena con los elementos (que son caracteres)
(a grouped 3 map encodeBlock flatten) mkString
}
14 líneas de código. La mitad del equivalente en Java. ¿Dónde estuvo el ahorro? Pues una buena parte es debido a la facilidad que tienen las colecciones para procesar datos; eso de grouped 3 nos ahorra tener un ciclo donde tomemos los bytes de 3 en 3. Y luego el map encodeBlock es para pasarle cada grupo de 3 (o menos) bytes a la función encodeBlock; luego aplanamos esas listas internas para tener una sola y construimos una cadena con eso.
Dentro de la función encodeBlock, seguimos teniendo varios if’s, pero la ventaja es que en Scala el if nos devuelve un valor; if (x) a else b es una función que nos va a devolver a si se cumple la condición x o b si no se cumple. Por eso es que están alrevés del código en Java (en Java primero tengo if y dentro de los bloques hago la asignación a variables; en Scala tengo los if dentro de la asignación a los valores).
Muy bonito, pero… esta versión en Scala procesa los mismos 10MB en 6 segundos. Se tarda 30 veces más que la versión en Java.
Primera optimización: Podemos hacer que encodeBlock devuelva una cadena, y entonces no tenemos que aplanar la colección final, solamente concatenar todas las cadenas. Entonces en vez de List[Char](...), la última línea de encodeBlock es Array[Char](...) mkString. Y la llamada se hace a grouped 3 map encodeBlock mkString (quitamos el flatten). Con esto bajamos el tiempo a 3.7 segundos (unas 12 veces más que la versión en Java; me parece que sigue siendo inaceptable pero ya no está tan grave como los 6 segundos anteriores).
Y de hecho, si en vez de mkString, construimos un String al final de encodeBlock: new String(Array[Char](...)), el tiempo baja a 3 segundos. De modo que tal vez la lentitud está en la conversión de datos…
Analizando el código con ayuda del IDE y unos cuantos println, puedo ver que el alfabeto es un Vector de Scala. Si lo convierto a un Array, el tiempo de ejecución baja entre 50 y 100 milisegundos, que no es significativo. Pero si lo convierto a String y utilizo directamente charAt para obtener los caracteres que necesito, el tiempo baja casi 300 milisegundos, quedando en 2.7 segundos.
Después de estar experimentando con varias opciones, ese tiempo fue el menor que pude lograr. La versión de Scala tarda 10 veces el tiempo que la de Java. Como mencioné anteriormente, este es uno de esos algoritmos en los que sí se tiene un beneficio muy notorio al poder manejar los tipos nativos de Java y hacer las operaciones de bits directamente. No es el caso típico de una aplicación; es de hecho el caso marginal en el que conviene tener el código en Java, por el performance.
Ya solamente para completar el código, dejo el método para decodificar:
def decode(s:String):Seq[Byte]={
val s0 = s filter { Character.isWhitespace(_) }
require(s0.length % 4 == 0, "Longitud inválida, debe ser múltiplo de 4")
def decodeBlock(seg:String)={
val (s1, s2, s3) = (seg(1), seg(2), seg(3))
val b0 = (chars.indexOf(seg(0)) << 2) | (chars.indexOf(s1) >> 4)
if (s2 == '=') {
Seq(b0.toByte)
} else {
val b1 = (chars.indexOf(s1) << 4) | (chars.indexOf(s2) >> 2)
if (s3 == '=') {
Seq(b0.toByte, b1.toByte)
} else {
val b2 = (chars.indexOf(s2) << 6) | chars.indexOf(s3)
Seq(b0.toByte, b1.toByte, b2.toByte)
}
}
}
s0 grouped 4 flatMap decodeBlock toSeq
}
15 líneas de código. Ya no hice benchmark, pero seguramente será también órdenes de magnitud más lento que la versión en Java.
Conclusión
Con todo eso, no trato de decir que Java sea mejor, o que Scala sea mejor o peor, o que sea lento en general, etc. La JVM me parece una excelente plataforma, y dentro de ella, me parece que Java es un buen lenguaje para implementar algoritmos intensivos donde el desempeño es muy importante y depende directamente del lenguaje. Pero cuando desarrollamos aplicaciones, la mayor parte del código no es más rápido o lento por estar haciendo cosas como este ejemplo; de hecho, por las abstracciones que ya es necesario manejar para poder administrar la complejidad de una aplicación común hoy día, no habrá mucha diferencia entre manejarlo en uno u otro lenguaje, en lo que a performance se refiere; pero sí hay mucha diferencia en la legibilidad del código, que depende mucho de la expresividad, sintaxis, simpleza, etc del lenguaje que se utilice.
Es por ello que creo que Java es una buena opción para implementar este tipo de algoritmos, pero Scala y Groovy, JRuby, etc son mucho mejores opciones para desarrollo general de aplicaciones. Tal vez en un futuro no muy lejano, Java se convierta en el lenguaje de infraestructura de la JVM, y solamente se utilice para este tipo de cosas, así como en otras plataformas se utiliza todavía C para este tipo de algoritmos y se le pone una interfaz para un lenguaje de más alto nivel.
