¿Seguro que es el mejor algoritmo?

Cambiamos un poco de tema. En Think you’ve mastered the art of server performance? Think again. el análisis del coste de una solución cuando empiezan a entrar diversos factores que afectan a cómo la teoría interpreta los resultados.

Por ejemplo, algunas suposiciones puede ser importante:

A quick browse of the mental catalog flipped up the binary-heap card, which not only sports an O(log2(n)) transaction performance, but also has a meta-data overhead of only a pointer to each object—which is important if you have 10 million+ objects.

La memoria virtual:

It took quite some time before virtual memory took hold, but today all general-purpose, most embedded, and many specialist operating systems use VM to present a standardized virtual machine model (i.e., POSIX) to the processes they herd.

Y como seguimos ignorándola a la hora de medir teóricamente algunas cosas:

The fact is, however, 46 years later most CS-educated professionals still ignore VM as a matter of routine. This is an embarrassment for CS as a discipline and profession, not to mention wasting enormous amounts of hardware and electricity.

Por eso,

What good is an O(log2(n)) algorithm if those operations cause page faults and slow disk operations? For most relevant datasets an O(n) or even an O(n^2) algorithm, which avoids page faults, will run circles around it.

Por eso, nosotros siempre recomendamos medir teóricamente para tener una idea de por donde van los tiros. Pero luego probar con nuestros sistemas reales y con los datos de verdad, para estar seguros de que los resultados teóricos se mantienen.
Y, por supuesto, esto nos da pistas de por qué es importante saber de hardware, del sistema y tratar de estar al día en muchos de estos temas.

Divertido, ¿no?

Siempre hay sitio para la optimización

La optimización del código que se ejecuta en nuestros programas es un tema clave (y con el que hay que tener cuidado sobre todo antes de tiempo).
Por eso me gustó leer A Python Optimization Anecdote donde nos cuentan los pasos seguidos para mejorar una función para evitar Cross-Sie scripting en Dropbox.

En resumen: probar, medir (y para eso hay que tener casos de prueba *nuestras pruebas, nuestros datos*) y ver cómo afecta a nuestro código con nuestros datos los cambios que hagamos:

Conclusions
The first, most basic conclusion is that the basic facts of Python
optimization inline functions, use implicit loops, move computation into C
if possible are perfectly valid. Another fact: Python dictionaries are
*fast*. The WHITELIST set and the CACHE_HTML_ESCAPES dict both rely on the
superb hash table implementation for their performance gains.

Other “common wisdom”, like using locals instead of globals, yields
relatively little gain.

Optimizing inner loops in a high-level loops requires lots of trial and
error. It was absolutely amazing that moving to string concatenation from
string interpolation gave such a huge boost to performance.

Finally, measurement is key. It was measurement that told us that HTML
escaping was slow to begin with; and without measuring performance, we
would never have guessed that string interpolation was so slow.

¿Por qué GNU grep es rápido?

La respuesta en why GNU grep is fast y lo explica haciendo referencia a los aspectos técnicos pero sin meterse mucho en los detalles.

Esencialmente:
Se utiliza el algoritmo de Boyer-Moore, que tiene como ventaja que evita mirar los bytes uno a uno, porque es capaz de evitar algunos basándose en información sobre lo que se busca (letra final, tamaño y aprovechándolo para dar saltos más grandes).
Pocas operaciones sobre cada byte de los que realmente se miran.

Además, el bucle interno está ‘desenrollado‘, lo que le evita algunas operaciones extra (las de control del propio bucle, claro). También evita pensar en líneas (salvo cuando ‘cree’ que ha podido encontrar lo que buscaba y trata de gestionar mejor la memoria para que la lectura sea más eficiente.
¿Alguien se anima a echarle un ojo al código?

GPU, cálculos y descubrimiento de claves

Ya hemos hablado alguna vez de utilizar GPUs (procesadores gráficos) para cálculos generalistas (por ejemplo en Utilización de GPUs para análisis de claves).

En GPU y cracking, que tarjeta me compro aparecen algunos propios y otros de Ivan Golubev (More speed estimations con comparativas de velocidad y precio para distintas tarjetas, con algunas pruebas.