Foro de la JavaCup > Cambios javaCup: Optimización
Creo que esta modificación se refiere a controlar el tiempo o ciclos de cpu que consume una táctica cuando el framework llama al método execute de dicha táctica.
Si hay poco tiempo, las tácticas deberían ser menos perfectas porque tendrían menos tiempo para efectuar sus cálculos.
Alfonso
+1
Esta era una de las cosas q menos me gustaron de las 'normas'. Hablar de 'consumo excesivo' y permitir bucles de más de 10.000 vueltas para calcular el mejor tiro me parece un contrasentido.
Qué os parecería poner un timeout en la llamada al método 'execute' de las tácticas (en cada iteración)? algo suficientemente bajo como para q no se encallen los partidos en 'vivo'.
Entiendo q en diferentes máquinas tendremos tiempos de ejecución diferentes... pero es que creo que la gracia está en encontrar un buen algoritmo, no en usar la fuerza bruta (y q nadie se me ofenda, por favor)
kpacha
De acuerdo, pero hay que dejar bien especificadas algunas cuestiones.
1. El tipo de maquina en que se va a ejecutar el partido para tener una referencia porque no es lo mismo 50 mili segundos en un P4 que en un I7.
2. Aun así en determinadas iteraciones una táctica podría sobrepasar el umbral, creo que lo que se debe hacer en esos casos es simplemente interrumpir la ejecución de esa iteración (para la táctica infractora) y que esa táctica no ejecute ningún comando en dicha iteración.
3. El uso de hilos, en la edición anterior se dijo que podía hacerse uso de hilos, pero con esta modificación no se si es algo que se deba permitir, y de ser así hay que dejar explicito cuantos hilos puede crear cada táctica.
Saludos.
osorio
Respecto a los hilos, comentar que la idea que tenemos es que la próxima edición del torneo de javaCup se realice utilizando la web de javaLeague, que se apoya en el Google App Engine para ejecutar automáticamente los partidos en el lado del servidor, con lo que tendremos las "limitaciones" impuestas por Google. No están disponibles todas las clases del JRE (esta es la lista de las clases disponibles), creo que por esta parte no habría problemas, no se me ocurre una clase que no esté en esta lista y que fuese necesaria para hacer una táctica.
Pero si hay problemas con los hilos. Aunque aparezca en la lista la clase java.util.concurrent.Executor no se pueden utilizar, digamos, de cualquier manera, ya que provoca una excepción en tiempo de ejecución.
Aquí lo explican:
En las pruebas que estamos realizando efectivamente ocurre esta excepción, por lo que quizá en la normativa haya que explicitar claramente que no se usen hilos.
Alfonso
Pero eso si que puede ser una dificultad, no el hecho de no se puedan usar hilos por las tácticas, sino que el framework tampoco podría hacerlo. Entonces hay que pensar en un mecanismo que no sea usando hilos para controlar el tiempo de computo de cada iteración para cada táctica.
osorio
cierto, GAE no soporta threads. En esa plataforma hay q usar la cola de tareas y según las normas de la javaCup "d) No accede al sistema de archivos, a Internet o a otros recursos externos" así que el uso de hilos queda descartado totalmente.
volviendo al tema del timeout: siempre existe la solución tonta basada en guardar el timestamp previo a cada iteración y una vez completada la iteración validar el tiempo que ha tardado cada equipo en responder. Si en una iteración te pasas, tus comandos no entran en la lista de comandos a ejecutar. Algo como esto:
List<Command> comandosLocales = new LinkedList<Command>();
try {
long startTime = System.currentTimeMillis()
List<Command> comandosPropuestos = tacticaLocal.execute(spLocal);
if(System.currentTimeMillis() - startTime <= MAX_PROCESSING_TIME){
comandosLocales = comandoPropuestos;
} else {
// activar flag para evitar recuperación energía en la presente iteración
// el flag se desactiva en el método encargado de recuperar la energía
}
} catch (Exception e) {
logger.severe("Error al ejecutar tactica local: " + e.getMessage());
}
la elección de la constante MAX_PROCESSING_TIME sería la parte más delicada del asunto...
además, como se ve en el código propuesto, el infractor no debería recuperar energía en esa iteración pq no ha dejado quietos a los jugadores por propia voluntad.
es algo más rupestre y sigue consumiendo todo el tiempo que la táctica infractora quiera... pero ese equipo terminaría suficientemente penalizado como para que te salga más a cuenta chutar mal y rápido que procesar una barbaridad de trayectorias.
kpacha
creo que este tema es muy complicado, está bien que se controle el tiempo que puede utilizar cada táctica pero hay que garantizar que el desarrollador pueda saber con exactitud lo que puede hacer sino las tacticas serán mediocres buscando poder devolver comandos. Como saber si una táctica es óptima? Teniendo en cuenta que?
No se la respuesta pero si estoy seguro que esta que proponen no es
yoemny
Disculpar el retraso en dar señales de vida, me fue imposible ir más rápido con el desarrollo de javaLeague.
Acabo de poner otro post en el foro con el lanzamiento de la primera versión beta de javaLeague, donde todos los partidos se ejecutan en Google App Engine.
Respecto al tema que ocupa este hilo (optimización) se me ocurrió la siguiente idea. A ver que os parece.
En la clase Partido está añadido ahora lo siguiente:
List<Command> comandosLocales = new LinkedList<Command>();
try {
startTime = System.nanoTime();
spLocal.setStartTime(startTime);
comandosLocales = tacticaLocal.execute(spLocal);//envia la situacion del partido y obtiene los comandos de la tactica local
timeLocal = System.nanoTime() - startTime;
} catch (Exception e) {
logger.severe("Error al ejecutar tactica local: " + e.getMessage());
}
List<Command> comandosVisita = new LinkedList<Command>();
try {
startTime = System.nanoTime();
spVisita.setStartTime(startTime);
comandosVisita = tacticaVisita.execute(spVisita);//envia la situacion del partido y obtiene los comandos de la tactica visita
timeVisita = System.nanoTime() - startTime;
} catch (Exception e) {
logger.severe("Error al ejecutar tactica visita: " + e.getMessage());
}
En la clase GameSituations se ha añadido la variable
private long startTime; // Para obtener el tiempo utilizado en la ejecución de la táctica
y el método
/**
* Retorna el tiempo consumido en la ejecución de la táctica
* @return
*/
public long getTime() {
return System.nanoTime() - startTime;
}
que devolverá el tiempo consumido en la iteración por la táctica y podrá ser llamado en cualquier momento durante la ejecución de nuestra táctica.
La clave para penalizar a la táctica que consuma mucho sería, tal como comenta kpacha es ajustar el valor de MAX_PROCESSING_TIME
El problema es que este valor no puede ser constante, ya que dependiendo del equipo (procesaror, memoria, etc etc) en el que se ejecute el partido, debería tener un valor distinto adaptado a la capacidad de procesamiento del equipo.
Finalmente todos los partidos se van a ejecutar en el entorno de Google App Engine, por lo que se debería tomar como referencia el tiempo que tarda en ejecutarse la táctica en Google App Engine y calcular en base a ello el valor de MAX_PROCESSING_TIME a la hora de ejecutar el partido en el equipo en local mientras se desarrolla.
Existe una tarea programada en javaLeague que ejecuta un algoritmo de benchMark cada 15 minutos y guarda el resultado en una tabla. De igual manera, se ha añadido la clase BenchMark con ese mismo algoritmo en el framework javaCup y se ejecuta al inicio de cada partido, mostrando por consola el tiempo que tarda en ejecutar dicho algoritmo:
/**
*
*/
package org.javahispano.javacup.model.util;
/**
* @author adou
*
*/
public class BenchMark {
private double benchMark;
public BenchMark() {
long t1 = System.nanoTime();
int result = 0;
for (int i = 0; i < 1000 * 1000; i++) { // sole loop
result += sum();
}
long t2 = System.nanoTime();
benchMark = ((t2 - t1) * 1e-9);
}
private static int sum() {
int sum = 0;
for (int j = 0; j < 10 * 1000; j++) {
sum += j;
}
return sum;
}
/**
* @return the benchMark
*/
public double getBenchMark() {
return benchMark;
}
}
En esta imagen podéis ver una gráfica con los valores obtenidos en la ejecución del benchMark en Google App Engine.
Si vaís a http://javaleague.appspot.com/showBenchMark os devolverá un fichero csv con la fecha/hora de ejecución del benchMark y el tiempo empleado en la ejecución del algoritmo. No lo devuelve ordenado por fecha!
La idea es que calculando la media de ejecución del benchMark en Google podríamos calcular el tiempo máximo a permitir por iteración en local.
Tendríamos los siguientes valores:
MAX_PROCESSING_TIME_GAE: tiempo máximo de procesamiento de una iteración en Google App Engine.
PROCESSING_TIME_BENCHMARK_GAE: tiempo medio de procesamiento del benchMark en Google App Engine.
PROCESSING_TIME_BENCHMARK: tiempo de procesamiento del benchmark en local obtenido al iniciar un partido
y con estas variables, calculariamos el valor de MAX_PROCESSING_TIME al inicio de cada partido a ejecutar en local de forma transparente.
El único valor que tendríamos que definir de mano es
MAX_PROCESSING_TIME_GAE.
Este método no es preciso, cada ejecución del benchmark arroja un resultado distinto, tanto ejecutándolo en local como en Google App Engine (si veis la gráfica, en Google App Engine hay diferencias de hasta 4 segundos según el momento de ejecución).
El que haya tanta diferencia en la ejecución del benchMark en Google creo que se puede deber a varios factores:
- El propio algoritmo de benchMark. Es muy sencillo y seguramente habrá otros algoritmos que sirvan mejor para nuestro propósito.
- Servidores de Google App Engine. No sé cómo hace Google para ejecutar las tareas en sus servidores. Entiendo que la aplicación se ejecuta siempre en un servidor con similares características, pero igual no es siempre así.
- Cuenta gratuita en Google App Engine. Esto implica que tenemos una cuota de recursos asignada diariamente. No tengo claro si cuando andamos mal de cuota puede influir en el resultado en la ejecución del benchMark.
No es una solución perfecta, pero creo que nos puede llegar a valer si conseguimos unos resultados más estables.
¿ Qué os parece ?
sito
Finalmente no he encontrado una solución que me convenza para este tema.
Si os fijáis en el código de la clase partido, a la hora de iterar el partido se controla que la ejecución de las tácticas no supere el valor de maxTimeIter:
List<Command> comandosLocales = new LinkedList<Command>();
try {
startTime = System.nanoTime();
spLocal.setStartTime(startTime);
comandosLocales = tacticaLocal.execute(spLocal);//envia la situacion del partido y obtiene los comandos de la tactica local
timeLocal = System.nanoTime() - startTime;
if (timeLocal > maxTimeIter) // Se eliminan los comandos locales de esta iteración por superar el tiempo máximo permitido
comandosLocales.clear();
} catch (Exception e) {
logger.severe("Error al ejecutar tactica local: " + e.getMessage());
}
List<Command> comandosVisita = new LinkedList<Command>();
try {
startTime = System.nanoTime();
spVisita.setStartTime(startTime);
comandosVisita = tacticaVisita.execute(spVisita);//envia la situacion del partido y obtiene los comandos de la tactica visita
timeVisita = System.nanoTime() - startTime;
if (timeVisita > maxTimeIter) // Se eliminan los comandos visitantes de esta iteración por superar el tiempo máximo permitido
comandosVisita.clear();
} catch (Exception e) {
logger.severe("Error al ejecutar tactica visita: " + e.getMessage());
}
Pero este valor máximo de ejecución es igual a Long.MAX_VALUE, lo que equivale a no poner nada.
El caso es que antes de cada partido se ejecuta el benchMark y la idea era que teniendo unos valores de referencia, se calculase mediante una simple regla de tres el valor correspondiente.
No es un método perfecto, pero creo que podría valer para limitar de forma equilibrada el tiempo de ejecución de cada táctica.
El problema está en que ejecutando el frameWork en local el resultado del benchMark tiene sentido la primera vez que se ejecuta un partido, pero las siguientes ejecuciones el resultado es mucho menor del esperado.
Supongo que el problema está en que el benchMark utilizado no es muy bueno y de alguna manera se "cachean" los resultados.
No sé si finalmente esta solución puede funcionar, pero de momento en cada ejecución de los partidos en javaLeague se guarda el tiempo en nanosegundos empleado por cada táctica en cada iteración.
En la clase GameSituations se ha añadido el método
/**
* Retorna el tiempo consumido en la ejecución de la táctica
* @return
*/
public long getTime() {
return System.nanoTime() - startTime;
}
que retorna el tiempo consumido en la ejecución de la táctica. Falta el método que devuelva el tiempo máximo que puede consumir la táctica. No está hecho ya que de momento esta solución no está operativa.
Una vez terminada la ejecución del partido en javaleague, aparecerán al lado del partido dos iconos, uno para descargarse el partido para verlo en local y otro para descargarse el tiempo empleado por la táctica del usuario en cada iteración. Devuelve un fichero de texto donde cada línea es el tiempo empleado en cada iteración en nanosegundos. La primera línea de este fichero se corresponde con el tiempo que tardó en ejecutarse el benchMark justo antes de ejecutar el partido y supuestamente el tiempo máximo a emplear en la ejecución de la táctica, pero este último valor no se calcular y siempre se corresponde con Long.MAX_VALUE.
No sé si merece la pena seguir con esta idea porque igual no tiene sentido y complica en exceso la ejecución de las tácticas, pensando sobre todo en la gente nueva que quisiese empezar, pero bueno, seguiré buscando un benchMark que de mejores resultados.
Si alguien tiene alguna sugerencia y/o idea, será bienvenida.
Saludos,
Alfonso
En lo personal creo que no es el código de la tactica el que debería de llevar los hilos.
Creo que sería mejor que no hubiera iteraciones si no que el partido invocara a la clase tactica tantas veces como esta lo permita durante el tiempo del partido (que el framework fuera el que manejara los hijos ) este enfoque sería mas justo con las tacticas que son rapidas mientras que penalizaria de forma natural a las tacticas lentas.
gatsu
Esta es la explicación:
Otra historia que queda muy de lado es el de la optimización. Por mi vida laboral, es casi la parte más importante del trabajo, y quizá a veces lo lleve a todos los campos, pero tratándose de un 'concurso' de programación, es algo que no debería quedar en el olvido. Con las tácticas del año pasado, llegué a esperar casi un segundo a que ciertas tácticas hiciesen una sola iteración donde podían golpear el balón. ¿Por qué no limitar esto? ¿Por qué no hacer una medición y limitar la optimización? Entraría en juego otro aspecto muy importante y que haría equilibrar todo un poco. No sería el mejor el que más casos analizase e interpretase, sino que además debería hacerlo en un tiempo computacional razonable, al igual que un jugador tiene un tiempo limitado a la hora de tomar la decisión de un pase/tiro/lo que sea... Ahora la normativa es bastante vaga en este aspecto, puesto que refiere a las tácticas anteriores para ponerse en un lugar similar. También es verdad que me parece bastante raro que ciertas tácticas de este año se mantengan en los niveles de computación de años anteriores, pero eso es otra historia que creo que se debería tratar aparte.
Saludos.