El regreso de los discos RAM (RAM disks)

Un artículo reciente menciona que es posible mejorar el rendimiento de los Chromebooks con un simple cambio que no toma más de 30 segundos (link).

Al aplicar este cambio, se activa un feature llamado zram dentro de ChromeOS (ChromeOS y Android son Linux, no sé por qué Google trata de ocultar esto), que activa una partición de swap creada en un block device en memoria, que además comprime los bloques para que ofrezca mayor capacidad.

Me pareció un concepto interesante, principalmente por el tema de la compresión de los datos, y veo que puede ser aplicado dentro de Linux y de Android también, resolviendo el problema de las computadoras o handsets que tienen poca memoria RAM.

Esta es una solución que muestra dos conceptos unidos: el RAM disk (que en este artículo mencionan que es para cuando uno tiene más de 6GB de RAM) y la compresión de datos, que resulta entonces en un buen feature para equipos con limitaciones de memoria.

En el caso de Android, el manejador de memoria no puede activar pagineo por demanda, al no contar con almacenamiento secundario de forma permanente.  Esto es principalmente porque las memorias externas pueden ser extraídas en cualquier momento, y además sufren de desgaste por constantes ciclos de lectura y escritura.  Una solución de pagineo hacia la RAM con compresión viene a mejorar el rendimiento de un sistema operativo que su diseño fue orientado hacia el uso de memoria virtual.

Para el caso de iOS, el documento de Memory Usage Performance Guidelines de Apple menciona que no utiliza ningún tipo de swap o pagineo.

Música: The Police Live!
Libro: Ready Player One

Forma simple de transferir contactos de un dispositivo iOS a un Android usando iCloud y Google Contacts

Después de vivir en el mundo iOS, entré a la tierra de Android con una tableta Nexus 7.   Esto más que todo por curiosidad, y para comenzar a desarrollar el tema de sistemas operativos móviles en el curso que doy.

 Voy a documentar una forma rápida de transferir los contactos de un iPhone o iPad hacia cualquier Android:

1) Para comenzar, se necesita que el dispositivo iOS esté sincronizado con iCloud, y que los contactos estén sincronizados hacia iCloud.  Esto se puede hacer desde el iOS 5.

2) Cuando ya los contactos están sincronizados entre el dispositivo iOS e iCloud, entonces se ingresa al web site www.icloud.com y se ingresa con la clave de su Apple ID.

3) En la parte de Contactos de la página web de iCloud, se ingresa y se seleccionan todos los contactos que se quieren transferir (forma rápida para todos: ir al grupo de Todos los Contactos y luego marcarlos todos con shift-click).

4) Luego de marcar los contactos, darle click al ícono de engranaje y luego seleccionar la opción de Exportar a vCard.  Esto creará un archivo que puede descargar en donde desee.  Con esto terminamos la parte de iCloud.

5) Ingresar ahora a su cuenta de Google (Gmail, Plus, etc.).  Al estar dentro, puede abrir otro tab para entrar a http://www.google.com/contacts ya con la información de su cuenta.

6) En la pantalla de Google Contacts, darle click al botón de Más u Opciones y luego seleccionar la opción Importar.   Ingresar el archivo que guardó en el paso 4, y con eso se importarán los contactos a su cuenta de Google.

7) En unos minutos, el dispositivo Android recibirá los contactos en su aplicación interna.

Esta técnica funciona en general para cualquier libreta de contactos/organizador que soporte importar vCards.

La principal desventaja de esta forma es que no sincroniza los contactos.  Es decir que si se agrega un contacto en cualquiera de los dos dispositivos, esto no se copia al otro, sin tener una aplicación adicional.  Hay muchas en los respectivos App Stores, las que generalmente son de pago.

Programando el control remoto LG AKB35840202

Una breve nota mental, por si se me vuelve a desprogramar el control remoto del DVD player LG:

Para usarlo como control de TV, dejar presionado el botón de Power y luego presionar:

8 ó 9 para televisiones Sony

Más información  aquí

Diseño de un generador de código objeto

El generador de código objeto puede considerarse como la penúltima fase de un compilador, la cual se encarga de tomar como entrada el código intermedio generado por el front-end, y producir código objeto de la arquitectura target para luego entrar en la fase de optimización de código.

Para el generador de código objeto, se puede asumir que el front-end ha hecho los análisis léxico y sintáctico, y ha traducido a una representación intermedia suficientemente detallada (LLVM?), en la que los valores de los nombres que aparecen en código intermedio pueden ser representados por cantidades que la máquina objeto puede manejar directamente. Además, se supone que se hecho el chequeo de tipos necesario y se han detectado los errores semánticos. Por lo tanto, la fase de generación de código trabaja bajo el supuesto que su entrada no contiene errores.

La salida del generador de código consiste en el programa objeto. Existe un variedad de formas para el código objeto : lenguaje de máquina absoluto (imagen de memoria), lenguaje de máquina relocalizable (.OBJ en Intel Relocatable Format, ELF, etc.), lenguaje ensamblador o incluso otro lenguaje de programación.

La naturaleza del conjunto de instrucciones de la máquina objeto determina la dificultad de la selección de instrucciones. Es importante que el conjunto de instrucciones sea uniforme y completo, para generar reglas fáciles de traducción, por ejemplo : una arquitectura como la de Intel x86 permite que los compiladores tengan reglas bien definidas y cortas para casi todas las operaciones, mientras que una máquina RISC como el SPARC no posee un conjunto de instrucciones completo (desventaja para el constructor de compiladores, ventaja para los usuarios) y hace que la generación de código sea muy compleja. Otras arquitecturas, como la de MIPS, presenta un problema aparte, puesto que requiere que se reordene el código de ciertas maneras y se evite el uso de ciertas instrucciones para evitar hazards en el pipeline.

Otra de las consideraciones a tener para el generador de código consiste en la asignación de registros. Los registros son los elementos más valiosos y escasos en la fase de generación de código, puesto que el CPU solamente puede procesar datos que se encuentren en registros. Además, las instrucciones que implican operandos en registros son más cortas y rápidas que las de operandos en memoria. El uso de registros se divide generalmente en dos subproblemas :


1)Durante la asignación de registros, se selecciona el conjunto de variables y/o constantes que residirán en los registros en un momento del programa.
2)Durante una fase posterior a la anterior, se escoje el registro específico en el que residirá una variable.

Es muy difícil encontrar una asignación óptima de registros a variables. Matemáticamente, el problema es NP-completo. Este problema se complica todavía más debido a restricciones de hardware, de sistema operativo o ambos. Puede ser que el conjunto de instrucciones de la máquina no sea ortogonal (problema que existe en los x86 pero no en los Power por ejemplo). Algunas máquinas además requieren para ciertas operaciones el uso de un conjunto de registros para algunos operandos y resultados.

Ejemplo de un analizador sintáctico escrito en Bison/Yacc

Acabo de subir a Slideshare un documento conteniendo un ejemplo completo de un analizador sintáctico (parser) escrito en Bison.

Analizador sintáctico de Pascal escrito en Bison

View more documents from Egdares Futch.

Apuntes de Compiladores

Regresando al tema principal del blog, he posteado en Slideshare los apuntes de clase que usé para el curso de Compiladores durante un buen tiempo. Están incompletos, pero si encuentro más, los scanneo y los pongo también.

El contenido está basado en los libros clásicos del Dragón 1a. edición (Aho, et.al.) y el Tigre (Appel). Las notas como tal son para uso libre de cualquier persona interesada en estos temas. Espero que sean de provecho.

Los contenidos son: Conversión de NFA a DFA, Minimización de estados de un DFA, Parsing Top-Down Recursivo y No Recursivo, Parsing Bottom-Up, Construcción de tablas LR(0), SLR, LALR, Traducción dirigida por sintaxis, Evaluación de atributos en parsers LR (Por stack), Atributos heredados en parsers LR, Máquinas abstractas de stack, Entorno de run-time, Organización de la memoria, Stack frames y paso de parámetros, Generación de código para declaraciones, Generación de código para asignaciones, Manejo de índices en arreglos, Generación de código para expresiones booleanas, Generación de código en statements de control de flujo, Backpatching.

Puede ver el PDF del documento completo en Slideshare:

Apuntes del Curso de Compiladores

View more documents from Egdares Futch.

Compresión de datos: ¿cómo funciona?

Regresando al blog después de un montón de tiempo....(siempre digo eso).

Conversando sobre esto, una persona me dijo que la compresión de datos era algo que ya no era tan relevante, porque las capacidades de almacenamiento disponibles para cualquiera eran más que suficiente: llaves USB de 16 gigabytes, iPods de 120 gigabytes, discos de 1 terabyte, ¡o más! Sin embargo, considero que la compresión de datos tiene importancia aún, especialmente para nuestra comunicación en línea, aumentando la eficiencia de nuestros equipos.

Estamos acostumbrados a hablar de información que ha sufrido procesos de Compresión con Pérdidas (en inglés: Lossy Compression): los archivos MP3, que se comprimen por medio de algoritmos que modelan la percepción de frecuencias sonoras del oído humano, o las imágenes JPEG que se reducen en tamaño por medio de degradaciones en la calidad o fidelidad de las mismas.

En cambio, la Compresión sin Pérdidas (en inglés: Lossless Compression) reduce el tamaño de la información sobre la que trabaja, sin tener pérdida de fidelidad o contenido. Para todos son muy conocidos los archivos .ZIP, o .RAR. En ellos se obtiene como resultado algo de menor tamaño, que puede ser reintegrado a su versión original conservando todo el contenido sin ninguna pérdida: ¡es casi como ir en contra de las leyes de la física!

Para comenzar a explorar el tema de compresión, vamos a analizar el algoritmo de Huffman, creado en los años 50, ya que ésta es una de las técnicas de Compresión sin Pérdidas que usualmente se discuten para introducir el tema, tanto por su relativa sencillez, pero brillante concepto, así como su falta de protección por patentes.  La leyenda (en Wikipedia) dice que este algoritmo fue creado como la respuesta a una tarea de la universidad.

El algoritmo está basado en el concepto que los símbolos más frecuentes deberían estar codificados con menos bits que los menos frecuentes, logrando así una reducción en la cantidad de bits totales del mensaje o documento a comprimir. En el caso de textos en español por ejemplo, las letras a y e son más frecuente que la letra r, por lo que si le asignamos menos bits a esas letras que los 8 normales de un carácter ASCII, podríamos reducir el espacio requerido para almacenar el contenido.

La codificación Huffman entonces formaliza este concepto relacionando el número de bits asociados a un símbolo a la probabilidad de ocurrencia del mismo. En este artículo veremos la forma estática del algoritmo, que requiere tener una tabla de probabilidades calculada antes de comenzar a comprimir los datos. Esta tabla puede ser calculada en base a suposiciones iniciales (por ejemplo, una tabla de frecuencias de textos en español o inglés, dependiendo del lenguaje), o se puede generar directamente de los datos que se desean comprimir, recorriendo el contenido y haciendo un conteo simple de la ocurrencia de los símbolos.

Con esta información, el procedimiento de compresión puede comenzar a construir un árbol binario que codifica esta información de probabilidades, insertando nodos dentro del árbol, de forma de poner en las hojas más alejadas de la raíz, los símbolos menos probables. De esa manera, al completar este proceso de inserción, se tendrá un árbol con las hojas representando los símbolos, y nodos interiores que solamente sirven para diferenciar los niveles. El recorrido del árbol, etiquetando los arcos izquierdos con un 0 y los derechos con un 1, producen las palabras de código Huffman, con bits mínimos.

La Figura 1 ilustra este proceso. Como primera actividad, estamos generando el conteo de frecuencias del string de entrada “bcbbbbbbaacaabbcade” de 19 caracteres de largo. Esto ocuparía 19*8=152 bits de espacio para representarse normalmente en ASCII. Del conteo de caracteres, vemos que el más frecuente es el carácter b, luego el a, y así sucesivamente. Los menos frecuentes son los caracteres d y e.

 

Es posible ahora crear el árbol Huffman de la siguiente manera:

• Paso 1: Seleccione los dos símbolos con la menor probabilidad
• Paso 2: Cree un nuevo nodo como padre de los dos símbolos de menor probabilidad
• Paso 3: Asignar al nuevo nodo una probabilidad igual a la suma de sus hojas
• Paso 4: Repita el paso 1 hasta que ya solamente quede un nodo sin padre, el cual se agregará a la raíz

 El código Huffman para cada símbolo se obtiene ahora caminando hacia cada uno de ellos, con los vértices izquierdos etiquetados con un 0, y los derechos con un 1. En este momento, ya se puede proceder a emitir los códigos leyendo cada símbolo, y produciendo el valor para cada uno de ellos. Es de notar que solamente hay códigos Huffman para las hojas del árbol. Los nodos interiores no contienen información.

En el ejemplo, el string original queda ahora conformado por los siguientes códigos (separados por guiones): “0-101-0-0-0-0-0-0-11-11-101-11-11-0-0-101-11-1001-1000” que suman en total 36 bits, equivalentes a una compresión de 36/152=23% del tamaño original.

El proceso de decompresión ocurre a la inversa: se lee el input un bit a la vez y se emite un símbolo recorriendo el árbol, al llegar a la hoja correspondiente.

Para lograr la implementación de este algoritmo, debe considerarse el anexar la tabla de frecuencias (o tenerla fija, ya precalculada) para lograr la decompresión, así como enviar el número de símbolos del input, para tener el parámetro de parada del algoritmo, ya que el decompresor no puede saber precisamente dónde termina la entrada.

Es posible también conseguir ejemplos de código en diversos lenguajes en Internet, y la Wikipedia tiene múltiples links al respecto.

Aún cuando no se vaya a implementar, es interesante conocer los detalles internos del funcionamiento de este tipo de algoritmo.

Una pregunta de análisis: ¿qué pasaría con el input, si por fallas en la transmisión un solo bit se enviara erróneo?

Referencias usadas:

Apiki, Steve. “Lossless Data Compression”. Byte, marzo 1991.

Música:

The Beatles Stereo Box Set, Is there anybody out there? The Wall Live

TV:

Glee, Fringe S2, American Family