domingo, enero 27, 2008

Optimización de código en Java

Hace poco descubrí algo que me dejó algo trastornando.

Java no realiza optimización de código (Con Java me refiero a javac). Increíble pero cierto.

Hace poco, en esos impulsos que no tengo idea de donde surgen me dieron ganas de hacer un pequeño lenguaje de programación. Una vez realicé uno que generaba código para Parrot usando SableCC, pero como suele suceder con las cosas que no se hacen con gusto, éste lenguaje de programación cumplía exclusivamente lo que pedía el profesor sin hacer ningún tipo de innovación.

Pues bien, en estos momentos no tengo claro que código generaré... He estado mirando otras opciones que me sugirieron y tal vez me decida por la VM de Lua o Ocaml. Pero también me pasó en algún momento por la cabeza generar para la JVM y pues estaba viendo bytecode y me dio por hacer una prueba sencilla para ver como optimizaba el código Java.

Un Ejemplo

Digamos que tenemos esto en Java

int a = 2;
int b = 0;
int c = 0;
for(int i = 0; i < 1000; i++){
b = a * a;
c += b;
}


Lo predecible... (lo que cualquier imbécil haría) sería sacar el b = a * a del for... Esta es de las técnicas de optimización de código mas elementales. Invariantes de for creo que se llama y javac no las hace!!!

aqui está el bytecode:


0: iconst_2 // int a = 2
1: istore_1
2: iconst_0 // int b = 0
3: istore_2
4: iconst_0 // int c = 0
5: istore_3
6: iconst_0 // for(int i = 0;
7: istore 4
9: iload 4
11: sipush 1000
14: if_icmpge 31 // i < 1000;
17: iload_1 // {b = a * a;
18: iload_1
19: imul
20: istore_2
21: iload_3 // c += b;}
22: iload_2
23: iadd
24: istore_3
25: iinc 4, 1 // i++)
28: goto 9


Otra técnica es "reducción de fuerza" es decir... la multiplicación por 2 se puede reemplazar por un corrimiento de bits... en fin esas son las cosas que se me ocurren.

Que Pasa?

Entonces teniendo claro el hecho de que "debe haber alguna buena razón para eso" me puse a leer por ahí y encontre dos versiones:

1. Alguien decía que la idea era delegar esas cosas al IDE... es decir, si tengo una "Tail recursion" eclipse sacaría una ventana y diria "desea reemplazar esto por código iterativo?".

Tiendo a pensar que puede funcionar con tail recursion... pero:

más código autogenerado = más verbose en el fuente = MÁS FEO

Mi intuición me dice que algunas optimizaciones se pueden hacer solo en bytecode. Cosas que impliquen reordenación a un bajo nivel... no se me ocurre un ejemplo.

2. Otra versión es que las optimizaciones se realizan en la máquina virtual.

Creo que algunas optimizaciones parten de asunciones de la semántica del lenguaje de arriba y la verdad sería problemático interoperabilidad con otros lenguajes con semánticas diferentes... Dichas asunciónes dejarían de ser válidas.

Me gustaría leer una verdadera respuesta en vez de perderme en mares de suposiciones e intuiciones mías. Al final tal vez solo el manual de referencia de la JVM me podría responder.

Nota Aparte:

Corrí el mismo código en gcc con -O1... gcc se "da cuenta" que al final el resultado es sumar 4 mil veces... y eso, como decía mi profesor de Cálculo, "casi siempre" da 4000. gcc reemplaza todo el for por un mov $4000.


Witchcraft... pero impresionante.

domingo, enero 20, 2008

In Defense of Java

Hacía bastante rato no me encontraba alguien que pensara en forma tan perpendicular a la forma como yo veo las cosas. Pues hace poco leí ésto

First of all: Java is one of the most successful languages ever by any metric you care to dream up. Number of lines code written in it. Number of programmers using it. Number of commercial projects using it. Or non-commercial projects, for that matter. Number of job offers. Number of universities teaching it. In all of these, Java would be in the top handful. THIS IS NOT A COINCIDENCE! It is just not the case that you alone know what’s going on and thousands of project managers and academics don’t. You may think that. If you do, you’re probably wrong.


Así que Cobol era un lenguaje genial? Ésto obviamente incurre en la falacia ad populum

Getting a language widely adopted is very, very, very hard.


Solo se necesitan millones de dolares de Sun.

.............

Pero bueno... luego leyendo otro de sus posts, en cierta forma entiendo que tipo de individuo es éste.

See, you can still not get away with pretending that ints can be added to lists. I see that every year when students try to write private List <int> myList;
even though you then proceed to apparently add ints to the list. In other words: To make sense of it all, you still have to understand the whole story, the primitive/object distinction, the wrapping, and the auto-boxing.


Yo no discutiré al respecto. He hablado de Java muchas veces mal y para que repetir lo mismo?

Java es MUY verbose... y si ante cualquier idea para solucionar lo verbose se dice "muy complicado, mis estudiantes nunca lo entenderían", se está diseñando para estúpidos. Que pasaría donde en la educación de los médicos se dijera la misma frase? estaríamos seguros visitando al médico?

sábado, enero 19, 2008

Lenguajes Innovadores

Hace poco leí un post de febuiles sobre lenguajes de programación innovadores. Cuando estaba comentando me di cuenta que tenía tanto que decir al respecto que en vez de ensuciar la pagina de él con un enoooorme comentario decidí mas bien escribir todo un post respuesta.

Decir:

# C++: Objetos con velocidad, sin alejarme mucho de C.
# Java: Objetos por todos lados, escalabilidad. Puedo confiar en el para grandes deployments.
# C#: ¿Integración con plataformas Microsoft?

Puede ser cierto, pero injusto cuando se dice que se trata de solo ésto y que en realidad no hay innovación. Para entender como cada lenguaje fué innovador hay que tener en mente el contexto y las ideas de sus creadores.

Respecto al contexto, C++ comenzó a desarrollarse en el 1979 y mas que parecerse a C buscaba compatibilidad (i.e) poder compilar codigo C en un compilador de C++. Pese a que la compatibilidad no es del 100%, esa tampoco era el objetivo. C++ pretendia mejorar la seguridad de tipos de C y hacer mas fácil el manejo de memoria (new en vez de malloc).

Si se hace un comparativo con el ejemplo simple de recorrer una colección con otros lenguajes (Digamos Ruby, Python) o un lenguaje funcional tal vez uno diga "C++ es verbose" o "que horrible no hacer fácilmente recorridos de colecciones".

Pero creo que tengo dos argumentos para decir porque pasa ésto.

1) C++ es mas viejo!?? obvio. Uno lo compara con lenguajes que tuvieron años de experiencias aprendidas de otros lenguajes y obviamente el resultado de dicha comparación resulta injusto. Python y Ruby fueron creados o empezaron su creación en 1993 y 1991 respectivamente. Pareciera que 10-15 años no es mucho pero en la computación si lo és. Uno se devuelve 10 desde la creación de C++ y en esa época ¡No se había hecho el primer estándar de C! era la época de programar en Assembler en una PDP. Si comparamos un salto de éste tipo es comprensible que tome 10-15 años pasar de hacer un for a un n.times{}.

2) C++ si brinda opciones para esos horribles for. Es solo cuestión de mirar algorithm de la STL. Hay construcciones for_each, transform, accumulate. Y si uno se sale del estándar se encuentra uno con Boost. Lambda expresiones, expresiones regulares y muchas otras cosas útiles.

# Innovación en C++

Del Primer lenguaje que tuve conocimiento que tuviera Templates fue C++. Probablemente no haya sido el primero. Sin embargo los templates de C++ sin importar si fueron una idea prestada permitieron:

1) Una nueva forma de Metaprogramación, código genérico. Incluso una vez vi como usar templates para hacer precálculo en compilación.
2) Los templates de C++ lograron ser una valiosa influencia para lenguajes como C# y Java.
3) STL. Una, IMHO, de las mejores librerías para manejar colecciones.

No puedo hablar mucho porque tengo que confesarlo, no se casi de C++.

# Innovación en Java

Siempre hay taaantas cosas malas para decir de Java, pero a veces unas cuantas buenas.

Un lenguaje de programación no es solo las estructuras sintácticas y semanticas... sino la implementación misma.

Mas que el compile once, run everywhere estan los desarrollos en la JVM que lo hicieron posible. Java mostró que la interpretación a nivel de Byte Code puede llegar a ser muy MUY rápida. Java hizo desarrollos importantes en Garbage Collection y una vez le escuché a un profesor que uno de estos desarrollos permitió incluso usar Java para algunas tareas de tiempo real.

La JVM permitió que se hicieran otro montón de lenguajes y re-implementaciones que aprovechan lo anterior. Scala, JRuby y Jython. En este sentido, la mera implementación de una VM eficiente como lo es la JVM resultó innovador.

# Innovación en C#

Nunca he programado en C# pero hay varias cosas innovadoras que leí en msdn de C# 3.0 y los ejemplos son sacados precisamente de ahí.

1. Query expressions.

Son expresiones integradas del lenguaje para hacer lo que uno hace usualmente con SQL.

cosas como éstas son posibles:

 
from c in customers
group c by c.Country into g
select new { Country = g.Key, CustCount = g.Count() }


Lo bacano es que he visto usar estas expresiones con simples arreglos y vectores. No solo con tablas o clases extrañas.

2. Otra forma de Lambda-exprs

No siempre se tiene que hacer algo nuevo... a veces basta con hacer distinto algo que ya se hace de una forma.

 
x => x + 1
//O también
x => { return x + 1; }


3. Inferencia de tipos.

Creo que no hay nada que decir al respecto.

martes, enero 15, 2008

Raytracing en F#

Bueno... por fin, después de pelear mucho con el sistema coordenado ya tengo unas primeras implementaciones de la parte de iluminación local.

Acá va una pequeña imagen.



Tengo serias dudas sobre el posicionamiento de los especulares en cada una de las esferas.

viernes, enero 11, 2008

Java Considered Harmful

Pues bien, ya muchas veces he discutido sobre "lo que está mal en la educación"... Muchas veces me he desquitado con mis clases de Sistemas distribuidos (alias Telemática 2) porque coincide con esta parte de un artículo que ha causado mucho revuelo.

The irresistible beauty of programming consists in the reduction of complex formal processes to a very small set of primitive operations. Java, instead of exposing this beauty, encourages the programmer to approach problem-solving like a plumber in a hardware store: by rummaging through a multitude of drawers (i.e. packages) we will end up finding some gadget (i.e. class) that does roughly what we want. How it does it is not interesting! The result is a student who knows how to put a simple program together, but does not know how to program. A further pitfall of the early use of Java libraries and frameworks is that it is impossible for the student to develop a sense of the run-time cost of what is written because it is extremely hard to know what any method call will eventually execute.


Él artículo está aquí:

jueves, enero 10, 2008

Piedra Papel o Tijera

Hace poco me encontré por casualidad, gracias a un enlace de Reddit (ya no lo encuentro), una página que ofrecía un software para simular Bots. Ésto incluía API y otro montón de cosas, todo ésto montado sobre Excel (PUAGGG). Dentro de los proyectos que habían el que mas me llamó la atención era uno llamado Scissors, Paper and Rock. Éste simulaba un ambiente donde unos bots se movían en forma aleatoria por un campo e iniciaban en posiciones aleatorias de éste. Lo único que cambiaba es que unos bots eran tijeras, otros rocas y otros papeles.

Si un bot Tijeras se topaba con un Papel, el papel se convertía en otro bot de tijeras... eso aplicaba para cualquier combinación de bots bajo las reglas usuales. Si en cambio 2 bots de la misma clase se encontraban no pasaba nada. Mas interesante que la imagen de unas tijeritas desplazándose por un mapa es tal vez la gráfica que el niño (si mal no recuerdo el que hizo ésto tenía 12 o 13 años) realizó de las poblaciones de dichos bots. Si uno piensa a la ligera se espera una gráfica super caótica o nada especial, sin embargo los efectos que cada población ejerce sobre las otras dos hace que la gráfica sea bien interesante.

Algo bueno de la ciencia es tal vez que todo resultado encontrado es sujeto de verificación. Yo realicé un experimento parecido al del niño este (ese niño si sabe divertirse) con algunas diferencias.

1) Como estoy aprendiendo F#, lo hice en F#.
2) Utilicé una matriz que iba recorriendo, mas a modo de automata celular... Dado que la matriz es bien dispersa resulta muy ineficiente.
3) Intente usar algo de teoría de Why Attribute Grammars Matters sin ningún éxito.
4) El grid no tiene bordes... es al estilo de un mapa de Karnaugh

En fin... sin más preámbulos aquí está la gráfica.



A diferencia de los resultados del niño, aqui cada "onda" va creciendo hasta que una población se queda sin bots.

Pero bueno. Mostraré algunas cositas del lenguaje bien sencillas.

Por ejemplo, si quiero definir Tijeras Roca y Papel, es tan sencillo como en Haskell.


type hand = Scissors | Rock | Paper


La función que decide quien gana es igual de fácil.

let rec who_wins i j = 
match i,j with
| Scissors,Paper -> Scissors
| Paper, Rock -> Paper
| Rock, Scissors -> Rock
| i, j when (i = j) -> i
| i, j -> who_wins j i


Sin embargo aún no me acostumbro a los aspectos de evaluación estricta de F#

Es decir... si en Haskell tenemos ésto:
a x = a x
iff a (x,y) = if a then x else y
x = iff True (2,a 3)

La función x termina. Porque con la evaluación perezosa no tenemos que saber cual es el valor de toda la tupla cuando se la pasamos a la función iff. En cambio en F#, tener éste equivalente:
let rec a x = a x
let iff a (x,y) = if a then x else y
let x = iff true (2,a 3)


Con evaluación estricta, tratamos de saber el valor de la tupla y en ese proceso nos quedamos en un loop infinito. En el código inicial para conocer la victoria tenía un código que hacía uso de una función iff. Por esto se llamaba a la función who_wins infinitamente y como resultado... stack overflow CHAAAN CHAAN CHAAAAAAAN.

jueves, enero 03, 2008

Raytracing en F#

Tengo que confesar que éstos primeros pasos han estado llenos de lectura, corrección de bugs y pensar como voy a hacer las cosas. Si midiera mi productividad por líneas de código (como muchas organizaciones hacen) podría decirse que es bien pobre. Pero bueno... hasta ahora he realizado poco del raytracer Sin embargo ya se pueden ver los primeros resultados:



Ésta imagen generada no tiene implementado el sombreado de Phong sinó que lo único que hace es para cada rayo, halla una lista con todas las intersecciones. de ésta lista saca la menor intersección. Para mostrar la expresividad de F# (aunque en general este poder puede ser atribuido a cualquier lenguaje funcional) podemos mostrar como hallo todas las intersecciones con todas las superficies. Pero primero entendamos algunas cuestiones de diseño.

Cada superficie es una interfaz. Similar (hay diferencias!) a lo que uno conoce como interfaz en Java, es básicamente el tipado de los métodos y atributos (en F#, no sé si en todo .Net diferencian éstos en valores, miembros y métodos). En el caso de las superficies solo existe un método y éste es intersección, dado un rayo este devuelve un tipo colisión. Para manejar el caso que no haya colisión esta se envuelve en el equivalente a la monada Maybe de Haskell, en F# este tipo es option:


let hits objs r = map ((|>) r) (map get_intersect objs)


Entendamos esto... primero la segunda parte get intersect es de tipo ISurface -> (ray-> hit) es decir, extrae el método del objeto... con map lo que se hace es que se aplica la función a todos los elementos de objs. generando una lista de funciones (ray-> hit).

Ahora bien, teniendo una lista de funciones queremos aplicarlas a un objeto.

El caso parecido sería dado [+1,*3,+3] queremos aplicárselas a 2 para obtener [3,6,5]... map en su forma convencional no nos sirve porque éste recibe una función y la lista, y en este caso las funciones están en la lista. Siendo así usamos el operador pipe (|>) el cual sería en Haskell algo como a -> (a -> b) -> b y se define como (|>) a b = b a

Pues bien eso es precisamente lo que está en la primera parte... tomamos lo que sea que está en la lista (la función) y se lo aplicamos a r.

El problema de ésta aproximación es que estamos realizando 2 maps... medí tiempos y en general me estaba dando que para hacer el render de la imagen anterior se demoraba alrededor de

00:00:01.0625000

Lo cual teniendo en cuenta que son solo 2 esferas y falta mucho por hacer decido hacer caso omiso de:

"Premature optimization is the root of all evil."
C.A.R. Hoare


Como arreglar ésto?

Composición de funciones!!


let hits objs r = map (get_intersect >> ((|>) r)) objs


Él operador (>>) es similar al operador (.) de Haskell. Y similar al concepto de composición de funciones de matemáticas discretas o Cálculo. las funciones de cada map las convierto en una sola y listo! Con lo cual pasa a demorarse:

00:00:00.8750000

En este par de muestras sin ninguna relevancia estadística obtengo 18%... pero mas o menos está entre el 8% y el 20%