Un caso interesante de Scala vs. Java

Hace 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.

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

La nota curiosa es que Java

La nota curiosa es que Java soporta muy bien el estilo imperativo/procedural porque fue diseñado precisamente para facilitar la transición de los programadores que estaban en lenguajes no orientados a objetos hacia el paradigma OO ( y parecer familiar a los de C++ ).

De hecho el parecer familiar al paradigma reinante es una característica deseable en el diseño de los lenguajes de programación y ahí viene el reto para crear algo diferente que sea aceptado. Al hacerlo totalmente diferente se corre el riesgo de poca adopción por muy bueno que sea el lenguaje y el lenguaje muere.

Scala hizo exactamente lo mismo, soportar el paradigma OO para atraer a los programadores hacia el paradigma funcional y no creo estar muy errado al decir que ha tenido éxito en hacerlo, aunque el "market share" sigue siendo muy muy bajo.

Me pregunto como se vería la misma implementación en un lenguaje de programación orientado a objetos puro ( por ejemplo Smalltalk )

+1 por el detalle en la explicación @ezamudio

Imagen de bferro

Criminal la ADVERTENCIA de @ezamudio

Muy buen post el de Enrique y muy criminal la Advertencia:
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.

Por supuesto que es una broma lo que acabo de escribir, pero retomando nuevamente la seriedad, pienso que la manipulación a nivel de bits es un conocimiento obligado para los bebés, los juniors, los seniors y los de la tercera edad. Es un conocimiento básico de computación y realmente sencillo, si se "agarra al toro por los cuernos".
Con respecto a las consideraciones de Enrique sobre Java como lenguaje para infraestructura , no coincido con eso aunque por supuesto acepto las bondades de Scala para resolver muchas cosas de una manera menos dolorosa. Soy de los que piensa que es un lenguaje obligado para los que ya llevan tiempo en Java, y estoy seguro que con su uso se fortalece el conocimiento del paradigma de orientación a objetos y por supuesto el funcional.
Me tomo el atrevimiento de un par de aclaraciones:
Es necesario distinguir entre secuencias indexadas y secuencias lineales. Los rangos son secuencias indexadas con tiempo de acceso constante mientras que las listas son secuencias lineales con tiempo lineal de acceso. Las colecciones en Scala lo hacen explícito definiendo traits diferentes, lo que es una gran ventaja y ayuda a la comprensión del problema.

Imagen de ezamudio

Optimizar

Entonces crees que se pueda optimizar el desempeño utilizando una colección distinta de entrada, en vez de Seq[Byte]?

Lo de los bits por supuesto fue broma, haciendo referencia a que hace una semanas había un post por aquí donde se discutía acerca de ese tipo de operadores y algunos preguntaban si alguien los había usado en la vida real... de hecho estuvimos ambos participando.

Imagen de Algus Dark

Wow!

Interesantísimo post, la verdad es que ya soy fan de los posts de ezamudio. Apenas he despertado en el mundo de JAVA, acabo de salir de la universidad y trabajo programando en JAVA pero son cosas sencillas (J2EE). Me agrada ver cosas que no entiendo, porque me dan muchas ganas de aprenderlo y he ahí cuando la curiosidad no mata al gato.

Sobre los operadores de bits los usé en la escuela un semestre y en el trabajo sólo una vez. Pero nunca deja de ser divertido. Gracias por el post, me ha sorprendido las bondades de SCALA, un lenguaje que quisiera aprender.

Hey, aprovecho el post para que me recomienden un buen libro. Si está en inglés mucho mejor.

Imagen de ezamudio

El de Venkat

Este es muy buena opción porque es de los más cortos de Scala, muy bien explicado, y pues el autor ya nos honró dando una plática para javaMexico.

Imagen de Algus Dark

Gracias!

Gracias Ezamudio, está barato, se puede comprar por Paypal y me gustó mucho cómo Venkat hizo su presentación en SG conference.
Saludos!

Re: Optimizar

My bad! :P

Jajajaja...pues sería chido tener un profe en la universidad cómo @ezamudio o cómo @bferro; en mi universidad el plan de estudios no estuvo tan "programming from scratch". Empezamos con lógica, de ahí nos pasaron a programación estructurada (en C#, lo que me hizo exclamar un "WTF?"); de ahí nos movieron a OOP (con C# también, ahora no suena descabellado), de ahí nos pasaron a Java (era el curso de "programación avanzada"), nos dieron después estructura de datos (la mejor materia que vi), luego nos dieron programación web.

En si, cómo programación no estuvo tan bien hecho el programa, creo que si debimos haber visto programación de binario, de hecho yo no me hubiera enterado (ni dado curiosidad) de no ser porqué en el código de un compañero de trabajo vi que hacía cosas parecidas a: uno = input[i] & 0xff;, pero él [mi compañero de trabajo] si que lo usa en su día a día (es ingeniero en electrónica).

De hecho, hasta el momento no me he visto en la necesidad de usar bits directamente, aunque si que me gustaría aprender y comprender al 100% el código que @ezamudio ha posteado.

En fin, palabras de un novato con ganas de aprender :D

Otra opción

¡Muy buen artículo! (perdón que resucite posts viejos, pero estoy leyendo tu blog recién descubierto)
Me gusta la idea de java como lenguaje de bajo nivel...antes era C para velocidad y java para facilidad, ahora es java para velocidad y ¿scala? para facilidad...no se, ceylon me gusta mas.

Me da la impresión de que has encarado el algoritmo en java de una manera compleja desde el principio...Cuando uno quiere pasar "a mano" a base64, ¿como hace? Toma los bytes de a tres, y escribe bit a bit en un papel, y agrupa de a 6...si hago eso en java me queda algo asi:

public static String base64Encode2(byte[] input, int start, int len) {
        StringBuilder buf = new StringBuilder((input.length * 4) / 3);
        for (int i = start; i < start + len; i += 3) {

                int todojunto = (input[i] & 0xff) << 16; //lo leo positivo y lo llevo al principio del int
                if (i + 1 < len) todojunto |= (input[i + 1] & 0xff) << 8; //lo leo positivo y lo llevo al medio del int
                if (i + 2 < len) todojunto |= (input[i + 2] & 0xff);    //lo leo positivo y lo dejo al final del int  

                int byte0 = (todojunto & 0xfc0000) >> 18; //leo los primeros 6 y los llevo al origen
                int byte1 = (todojunto & 0x3f000) >> 12;  //leo los segundos 6 y los llevo al origen
                int byte2 = (todojunto & 0xfc0) >> 6; //etc
                int byte3 = todojunto & 0x3f;

                buf.append(B64_CHARS[byte0]);
                buf.append(B64_CHARS[byte1]);
                if (i + 1 < len) buf.append(B64_CHARS[byte2]);
                else buf.append("=");
                if (i + 2 < len) buf.append(B64_CHARS[byte3]);
                else buf.append("=");
        }
        return buf.toString();
}

son 17 lineas bastante legibles en java, que se podrían resumir un poco mas haciendo trampa (if y else en la misma línea ) o ahorrando las variables byteX ..pero eso para mi gusto lo haría muy poco claro. La perfomance es parecida, y parece andar bien.
Igualmente aplicando esta idea la versión scala tambien sería mas breve, estimo...lo tengo que probar.