Entradas por: LaNsHoR

Sé lo que estás mirando

Publicado por LaNsHoR el 10/09/2013 en Bases de Datos, Problemas | 10 comentarios

Aquí el va el primer problema de algunos que iré proponiendo. Yo publicaré mi solución en unos días (4… o 5), dejando así un tiempo prudente ;]

/* si sois hábiles, no debería llevaros más que unos pocos minutos; pero en cualquier caso la velocidad no significa nada, lo importante es llegar a una buena solución; -es sobre todo un ejercicio mental, de diseño – */

Es muy sencillo pero, como nota, os diré que cuando vi la implementación de esto mismo en un proyecto grande… casi me echo a llorar.

***

Fue una de las primeras cosas que tuve que resolver hace algunos años para LoG85. Se trata de diseñar un fragmento del esquema de una base de datos para guardar, para cada usuario, qué publicaciones ha visitado y cuáles no. Las publicaciones pueden ser fotos, entradas, comentarios… lo que queráis, es lo de menos.

De partida tenemos una tabla usuarios y otra publicaciones, con los campos y restricciones que queráis; tenéis que conseguir que en la base de datos se guarden qué publicaciones han sido visitadas por qué usuarios. Tenéis libertad absoluta para crear o reformar tablas, escribir código, diseñar cachés… la película que queráis. Lo importante es que el sistema tiene que ser elegante (sencillo, claro, eficiente) y escalable (el número de usuarios y de publicaciones, así como su relación, puede crecer ad infinitum). Y por supuesto en todo momento la bd ha de encontrarse en un estado coherente; manteniendo la integridad referencial.

Si dais la solución en prosa, aseguraos de que todo está bien especificado 😉

*** SOLUCIÓN ***

¡Gracias a todos los que habéis participado! Bien vía comentarios, bien vía email o teléfono. Comento un poco las respuestas:

Todas las soluciones se han centrado en crear una tabla que representa la relación entre publicaciones y usuarios; las entradas de esta tabla nueva guardan qué usuarios han visitado qué publicación. Han habido diferentes versiones en las que se guardaban fechas, número de visitas, etc. Pero en cualquier caso, la versión básica de esta tabla, que sólo contendría dos claves ajenas a las primarias de las tablas usuarios y publicaciones, valdría (la primaria de la nueva tabla sería una composición de las dos ajenas).

Esta es la solución “trivial” que funciona. Pero no cumple uno de los objetivos del enunciado; no es escalable.

Primero, hablaremos de volumen; en un proyecto mediano que tenga unos 20.000 usuarios, es fácil que en pocos meses esos usuarios hayan visto una media de 1.000 publicaciones (fotos, tweets, entradas… lo que sea). Esto significa que nuestra tabla auxiliar tendrá 20.000.000 de filas. Y lo que es peor, crece geométricamente conforme aumenta el número de publicaciones y usuarios; a n*m. En pocos años tendremos una tabla con varios cientos de millones de filas, sólo para almacenar quién ha visto qué.

Aunque SGBD’s grandes tipo MySQL, MariaDB, Oracle… se comportan relativamente bien con tablas grandes, también tenemos que contemplar la posibilidad de que nuestra aplicación pueda correr sobre sistemas de gestión de bases de datos más modestos como SQLite. No sólo eso, para tener una velocidad aceptable es imprescindible tener los segmentos de las tablas más utilizados cacheados en RAM; con tablas tan grandes estamos invalidando la caché casi en cada consulta; llegado cierto punto límite en el que la tabla no quepa en memoria el rendimiento bajará de golpe varios órdenes de magnitud. Un diseño como este puede ser la diferencia entre que una aplicación vaya como un rayo en un hosting compartido o requiera un servidor dedicado entero para medio-funcionar. Y por supuesto, no podríamos ni plantearnos usar un sistema de instancias virtuales tipo Amazon, donde pagamos por consumo de memoria y ciclos de CPU.

La información mínima:

Este problema es peligroso porque es trivial encontrar una solución que “funciona”. Es fácil comformarse. Funciona en un “programa juguete” de estar por casa; pero muere en un entorno real. Tampoco hay una solución directa, dado que la información que tenemos que almacenar es esta y aparentemente no podemos reducirla más.

¿No podemos?

En realidad sí, y aquí está la magia.

Mi solución es usar una tabla “views” para las relaciones de esta forma:

La idea es la siguiente: lo más probable que es un usuario visualice muchas publicaciones con ids consecutivos (fotos de un album, respuestas de una entrada, entradas consecutivas, etc). Aún en el caso de que por la naturaleza de nuestra aplicación esta estadística no fuera cierta, más adelante veremos como forzar a que así sea.

Sabiendo esto, podemos explotar esta característica para almacenar segmentos de ids visitados, con un inicio y un final. Es decir, guardamos cosas como “el usuario 34 ha visitado todas las publicaciones de la 7 a la 10”.

A esto, añadimos un pequeño algoritmo de inserción, el consumo de CPU en la inserción es despreciable frente al consumo de CPU que supone consultas en una tabla cargada; además la inserción será una operación poco habitual.

Consulta para saber si una publicación ha sido visitada:

select true from views where id_user=$id_user and
secuence_start<=$id_post and secuence_end>=$id_post;

Algoritmo de inserción:

1) Comprobar si la publicación ya ha sido leída con la consulta anterior. Si es así, terminamos aquí.

2) Ejecutar:

update views set secuence_start=$id_post where
id_user=$id_user and secuence_start=$id_post+1;

Es decir, si queremos insertar como vista la publicación 6, y tenemos un segmento que empieza en la 7 para ese usuario, simplemente cambiamos el 7 por un 6.

El driver nos devuelve el número de filas cambiadas después de la operación, si es uno (se ha encontrado un segmento que cambiar), vamos al paso 2A. Si es cero, saltamos al 3.

2A) Comprobamos si el nuevo inicio de segmento es inmediatamente posterior a un final de segmento. Esto implica fusionar y desfragmentar segmentos que deben ser uno solo.

select secuence_start from views where id_user=$id_user
and secuence_end=$id_post-1;

Guardamos el resultado en una variable $tmp. Si $tmp tiene valor (hay resultado), actualizamos el segmento siguiente y eliminamos el que quedará con información redundante:

update views set secuence_start=$tmp where id_user=$id_user
and secuence_start=$id_post;

delete from views where id_user=$id_user and
secuence_start=$tmp and secuence_end=$id_post-1;

Hemos terminado nuestra inserción y fusión 🙂

3) Ejecutar:

update views set secuence_end=$id_post where
id_user=$id_user and secuence_end=$id_post-1;

Es lo mismo que la operación anterior, pero para los finales de segmento. Preguntamos al driver el número de filas modificadas. Si es uno, pasamos a 3A, si no a 4.

3A) Repetimos las operaciones en 2A por el mismo motivo, adaptadas a una inserción de final de segmento.

select secuence_end from views where id_user=$id_user
and secuence_start=$id_post+1; --guardado en variable tmp

update views set secuence_end=$tmp where id_user=$id_user and
secuence_end=$id_post;

delete from views where id_user=$id_user and
secuence_start=$id_post+1 and secuence_end=$tmp;

Terminada la inserción y fusión.

4) Llegados a este punto, no hay ningún segmento para el que nuestra entrada vaya a formar parte.

Ejecutamos:

insert into views values($id_user,$id_post,$id_post);

Y fin.

En cuanto pueda os pondré números reales de lo que supone realmente este algoritmo en rendimiento y reducción de tablas; basándome en la bd de log85 😉

¿Cómo llegué a esta solución?

Esto es lo más importante; la verdadera lección de este problema. A menudo tenemos que trabajar con cantidades enormes de información que no podemos comprimir en base a su grado de entropía usando métodos tradicionales.

Pero, como mentes inteligentes y cumbres del pensamiento abstracto que somos (nos queremos), debemos aprovechar nuestra condición humana para encontrar patrones y características que vuelvan a esa información vulnerable. Ya no en almacenamiento; en procesamiento cualquier “información sobre la información” que nos restrinja de una entrada de palabras aleatorias puede marcar la diferencia entre encontrar un algoritmo que se ejecute en 100ms, o tener que usar otro “default” que necesitará, literalmente, varios cientos años para darnos una respuesta.

Esta es sólo una idea. Puede mejorarse sobre la misma base y forzar la estadística para que los ids de lo que ven los usuarios sean más secuenciales. Por ejemplo; las entradas pueden tener ids como 100, 200, 300, 400… y los comentarios a las entradas como unidades sumadas a la id de la entrada: 101, 102, 103… así al ver entradas y comentarios tenemos un buen segmento asegurado. Esto no significa un límite de 100 comentarios por entradas. Cuando nos quedemos sin ids para la secuencia podremos romperla… al fin y al cabo, lo único importante de un id es que sea único (no necesariamente secuencial). Podéis jugar con esto para reducir la fragmentación entre ids de lo que realmente se ve.

Si lo probáis, veréis como la mejora con esta solución es espectacular. Espero que os haya gustado 🙂

Intersección Rayo-Triángulo

Publicado por LaNsHoR el 04/09/2013 en Computación Gráfica | 0 comentarios

Hagamos un poco de abstract:

La intersección rayo-triángulo en R3 es un problema clásico que a menudo nos encontramos cuando buscamos soluciones a un sistema que depende de la topología de una malla triangular que interactúa con otra entidad en la escena. Especialmente en aplicaciones y variaciones de raytracing tipo mapeado fotónico; esto es, para renders offline.

frame de  Big Buck Bunny, renderizado con Blender

Hay muchas técnicas para calcularla, una casi omnipresente y eternamente recomendada es la Intersección Rayo-Triángulo Rápida de Mínimo Almacenamiento de Moller y Trumbore (conocida como MT97); basada en el cambio de coordenadas baricéntricas del triángulo en cuestión.

El paper del último link de MT97 explica bien el algoritmo y proporciona una implementación. Probablemente, es la que necesitáis para vuestro problema.

¿Probablemente?

Lo mejor de MT97 es que nos da una valiosa lección de filosofía. Su defecto, como el de tantas cosas en la vida, es el de su adopción masiva sin planteamiento.

Más que en ningún otro sitio, en este tipo de problemas hay que ser especialmente crítico; sobretodo en las líneas clave que van a suponer más del 70% del código de ejecución (no fuente) del programa.

Así, hace algunos años cuando me encontré con la necesidad de implementar una solución para calcular la intersección rayo/triángulo hice una comparativa (cosas de la intuición) entre MT97 y mi opción alternativa. Sorprendentemente encontré que para mi problema era mucho más rápida (computacionalmente) esta última.

La primera ventaja que intuí antes de hacer la prueba venía por su naturaleza paralelizable. Programándola usando instrucciones SSE y registros XMM* en gran parte del proceso obtenía hasta tres operaciones por instrucción.

El algoritmo es el siguiente:

Se puede demostrar matemáticamente que si la suma de las tres áreas de los formados es igual a la del original, entonces el punto de intersección está dentro del original. Dando como trivial el punto 1, nuestro problema se reduce pues a calcular el área de un triángulo en R3.

La función implementada y con comentarios en español quedaría:

/*
Los registros XMM* son de 128bits, utilizo 4 floats
para llenarlos en una estructura V4.
*/
struct V4
{
   float a;float b;float c;float d;
   V4(float x=0){a=b=c=d=x;}
   V4(float x, float y, float z, float i){a=x;b=y;c=z;d=i;}
};
/* P*: Vértice *(x,y,z) - R: Resultado */
void inline AreaOfATriangle(V4& P1, V4& P2, V4& P3, V4& R)
{
   V4 DIV(0.5);
   //Nota: Las coordenadas .d deben ser 0
   //TODO: Setear a 0 estos últimos 32bits para P1, P2 y P3
      asm volatile
      (
      "MOVUPS %0, %%XMM1\n\t"     //Sube x,y,z de P1 a XMM1
      "MOVUPS %1, %%XMM2\n\t"     //Sube x,y,z de P2 a XMM2
      "MOVUPS %2, %%XMM3\n\t"     //Sube x,y,z de P3 a XMM3
      "MOVUPS %%XMM2, %%XMM4\n\t" //Copia P2 en XMM4
      "SUBPS  %%XMM1, %%XMM4\n\t" //Resta P2-P1 (XMM4)
      "MOVUPS %%XMM3, %%XMM5\n\t" //Copia P3 en XMM5
      "SUBPS  %%XMM1, %%XMM5\n\t" //Resta P3-P1 (XMM5)
      //--- Producto vectorial de P2P1 y P3P1 (determinante 3x3)
      "PSHUFD $0xC9, %%XMM4, %%XMM6\n\t" //P2P1 en XMM6 (Y,Z,X)
      "PSHUFD $0xC9, %%XMM5, %%XMM7\n\t" //P3P1 en XMM7 (Y,Z,X)
      "MULPS  %%XMM4, %%XMM7\n\t" //P2P1 * P3P1(Y,Z,X)
      "MULPS  %%XMM5, %%XMM6\n\t" //P3P1 * P2P1(Y,Z,X)
      "SUBPS  %%XMM7, %%XMM6\n\t" //Resta XMM6 y XMM7
      //--- Módulo del vector resultado
      "MOVUPS %%XMM6, %%XMM7\n\t" //Resultado a XMM7
      "MULPS  %%XMM6, %%XMM7\n\t" //Cuadrado de componentes XMM7
      "HADDPS %%XMM7, %%XMM7\n\t" //Suma parcial de coordenadas
      //... (A+B,C+D,A+B,C+D)
      "HADDPS %%XMM7, %%XMM7\n\t" //Fin la suma
      //... ((A+B)+(C+D),...)
      "SQRTPS %%XMM7, %%XMM7\n\t" //Raíz cuadrada del resultado
      "MOVUPS %3, %%XMM6\n\t"     //Sube 0.5 a XMM6
      "MULPS  %%XMM6, %%XMM7\n\t" //Divide el resultado entre 2
      "MOVUPS %%XMM7, %4"         //Pone el resultado en R {R(0)}
      :"=m"(P1), "=m"(P2), "=m"(P3), "=m"(DIV), "=m"(R)
      :"m"(R)
      );
      return;

Como siempre lo mejor es hacer pruebas en las máquinas que vayan a ejecutar el código. Gran parte de la mejora en velocidad viene del hecho de reducir los accesos a memoria (todo lo que sea pasearse por el bus de la placa base es siempre como subirse a una tortuga…) y no salir de los registros de la CPU.

De esto hace ya algunos años, la extensión SSE4.2 incluye una instrucción para calcular el producto vectorial (nos ahorramos 5 instrucciones en el código dado). Si la integráis con la intersección plano/triángulo y la adaptáis a una CPU contemporánea de gama alta, vuestro raytracer podrá casi volar… 😉

$blog->run();

Publicado por LaNsHoR el 30/08/2013 en Citas | 0 comentarios

Carl Sagan