2017-11-27 16:25 GMT+01:00 Jesus Cea <j...@jcea.es>: > On 27/11/17 10:29, Francesc Alted wrote: > > Lo único que se me ocurre es que, para minimizar el uso de memoria uses > > compresión para tus bloques binarios (dices que te llegan ordenados > > numéricamente, así que seguro que se pueden obtener buenos ratios de > > compresión). > > En realidad la compresión es mínima y no compensa. Son valores > aleatorios de 256 bits. Aunque estén ordenados de forma numérica, la > ganancia es mínima. > > Por ejemplo, un grupo típico tiene 256000 valores. Como cada valor tiene > 256 bits, eso supone que cada fragmento de 1000 valores consecutivos > empieza con el mismo byte. Dividiendo esa tabla de 256000 valores en 256 > tablas de 1000 valores cada una, ocupando cada entrada 31 bytes en vez > de 32 (porque el primer byte es implícito), la ganancia es de 32->31 > bytes, es decir, apenas un 3%. Algo es algo, es verdad. Pero no sé si me > compensa picar código para ganar un 3%. >
Correcto, un 3% es demasiado poco. Sin embargo, antes de decidir si tu conjunto comprime bien o no, nunca está de más hacer una prueba. Lo que me hacía pensar en que tus datos podrían ser comprimibles es precisamente lo que decías de que los valores te llegaban ordenados, y sé que eso puede afectar mucho al ratio de compresión. Por ejemplo, usando un conjunto de números aleatorios de 1 millón de enteros de 64 bits (en total 8 MB) se tiene: In [1]: import numpy as np In [2]: import blosc In [3]: b = np.random.randint(1000*1000, size=1000*1000) In [4]: %time len(blosc.compress(b)) CPU times: user 40.4 ms, sys: 5.15 ms, total: 45.5 ms Wall time: 13.3 ms Out[4]: 2878893 In [5]: b.sort() In [6]: %time len(blosc.compress(b)) CPU times: user 16.6 ms, sys: 434 µs, total: 17.1 ms Wall time: 4.71 ms Out[6]: 765295 lo que significa que la compresión de series numéricas ordenadas funciona mucho mejor (6x mejor en este caso, para un cratio de más de 17x sobre los datos sin comprimir). Esto es así porque Blosc hace uso de filtros especiales (llamados shufflers) para poner los bytes más significativos juntos, y por tanto reduciendo (normalmente) la entropía. Eso no quiere decir que esto se vaya a cumplir para tus datos pero como me gusta decir, no hay sustituto para una prueba ;) > > Además, si uso algo tipo "cuckoo hashing", no puedo aplicar esa > compresión en memoria, que es donde la necesitaría (para paginar lo > mínimo posible). > > > Para las búsquedas puedes continuar usando hashes cuckoo, > > pero sólo guardando las claves, no los valores > > Es cierto, no lo he explicado: Estoy usando esto para "conjuntos", no > para "diccionarios". Es decir, solo hay claves, no hay valores :). Pero > buen apunte para otra ocasión. > Vale, lo hab í a entendido mal ; en ese caso los hashes cuckoo no serán muy útiles. Sin embargo, la otra aproximación que apuntas, la del filtro cuckoo, al usar fingerprints mucho más cortos, sí que podría funcionar ya que aunque el número de falsos positivos sea un poco alto, la alta velocidad de decompresión de Blosc permite una verificación bastante rápida en la estructura de los conjuntos de claves comprimidos (todo esto suponiendo que la compresión funcione bien para tu caso). Bueno, ya nos contarás cual ha sido tu decisión; nos has dejado intrigados :) Francesc > > > clase de acceso de manera muy eficiente a través de la llamada > > `blosc_getitem()` > > Valoré Blosc brevemente, pero considero que mis datos son > "incompresibles" en RAM. Estoy más interesado en la parte de la > estructura de datos a utilizar para que las búsquedas sean eficientes > considerando que tengo poca RAM, no hay localidad de acceso en las > búsquedas (los datos que se buscan son aleatorios y no hay correlación > entre ellos) y puedo necesitar paginar al SWAP. Por eso estoy tan > interesado en reducir al mínimo los accesos a páginas diferentes de 4096 > bytes (La unidad de paginación). Los haskes cuckoo me garantizan un > máximo de dos accesos por búsqueda en el peor de los casos. Posiblemente > no sea mejorable y, básicamente me interesa que alguien me diga "pues > estás equivocado, Jesús, mírate el algoritmo XXX, que te garantiza un > único acceso a página". > > De hecho en este caso existe una posibilidad más: Como los datos son > aleatorios y "bien repartidos", podría hacer una búsqueda "estimativa" > en plan: "me da en la nariz que el valor, si existe, está en esta zona" > y buscar directamente allí. Las búsquedas dentro de una página de 4096 > bytes las considero "gratis". Lo que duele es la paginación. 4096 bytes > me dan para 128 entradas. Mirarlas una a una es "gratis" comparado con > tocar el disco duro. > > Esto ya lo había pensado, pero lo cierto es que por necesidades del > sistema no puedo basarme en que los datos estén "bien repartidos". Ahora > mismo lo están, pero no es un requerimiento de diseño y puede no > cumplirse en el futuro. Necesito algo capaz de sobrevivir a "sesgos". > > Otra posibilidad sería tener una tabla con el primer primer registro de > cada página de 4096 bytes. Es decir, 32 bytes por cada 128 registros > (4kbytes). Si mi conjunto tiene 2560000 entradas, son 2000 páginas de > 4096 bytes. Puedo tener un índice de 2000 entradas (64000 bytes, 16 > páginas de 4096 bytes). La búsqueda en el índice es binaria y podría > tocar 4 páginas, pero es razonable pensar que un índice de 64Kbytes sí > lo puedo mantener en RAM, incluso con un "MAP_LOCKED" o "mlock()". > > Claro que el problema es que mis datos no miden 256000 entradas. Son > docenas de conjuntos, cada uno con 256000 entradas. No estamos hablando > de 64 kbytes en RAM para el índice, sino 64*número de conjuntos, y ese > numero de conjuntos va por los cientos y subiendo. > > En fin, el asunto es engañosamente sencillo. > > De momento va ganando el cuckoo hashing. Es una estructura sencilla y me > garantiza un máximo de dos accesos a página, por muy grandes o muy raros > que sean mis datos. > > Mi esperanza es que alguien me sugiera algo mejor :-). > > Para uno de los modos de uso del sistema, el que más me importa, estoy > valorando usar "filtros cuckoo", tolerando un pequeño nivel de falsos > positivos, del orden del UNO por millón. Sigo teniendo dos accesos por > búsqueda, pero como ahora la estructura es más pequeña es más factible > que el número de accesos al SWAP se reduzca (recordemos que lo que me > penaliza es la paginación, las búsquedas en memoria las considero > gratis). Esto complicaría ese caso de uso porque ahora podría tener > falsos positivos, lo que supone que una vez por millón de accesos voy a > ir a buscar el dato a un servidor, me va decir que no está ahí y luego > tengo que hacer un acceso al servidor "por defecto". Ese "error" es muy > costoso en recursos y tiempo, pero si solo ocurre una vez por millón de > accesos, el coste amortizado es bajo. > > Decisiones, decisiones... > > Gracias por responder, Francesc. Buen aporte. > > -- > Jesús Cea Avión _/_/ _/_/_/ _/_/_/ > j...@jcea.es - http://www.jcea.es/ _/_/ _/_/ _/_/ _/_/ _/_/ > Twitter: @jcea _/_/ _/_/ _/_/_/_/_/ > jabber / xmpp:j...@jabber.org _/_/ _/_/ _/_/ _/_/ _/_/ > "Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/ > "My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/ > "El amor es poner tu felicidad en la felicidad de otro" - Leibniz > > > _______________________________________________ > Python-es mailing list > Python-es@python.org > https://mail.python.org/mailman/listinfo/python-es > > -- Francesc Alted
_______________________________________________ Python-es mailing list Python-es@python.org https://mail.python.org/mailman/listinfo/python-es
