PDF de programación - Compartiendo memoria. Eficientemente.

Imágen de pdf Compartiendo memoria. Eficientemente.

Compartiendo memoria. Eficientemente.gráfica de visualizaciones

Actualizado el 21 de Marzo del 2018 (Publicado el 11 de Marzo del 2018)
451 visualizaciones desde el 11 de Marzo del 2018
4,0 MB
54 paginas
Creado hace 4a (23/11/2016)
Compartiendo memoria.

Eficientemente.

Claudio Daniel Freire

PyConAr Bahía Blanca 2016





Python
(a veces)





Python
(a veces)





Python

Python
(a veces)

CPU





Python

Python
(a veces)

CPU



Memoria



Python

Compartir memoria... ¿para qué?

● Caches demasiado grandes para entrar en memoria...

– N veces con N procesadores

● Multiprocessing: datos de entrada
● Tornado / mod_wsgi: caches de evolución lenta

– Cuando sólo un pequeño porcentaje es accedido frecuentemente

● El "set caliente" entra en memoria, pero no la totalidad
● Pagar un acceso a disco para obtener el valor infrecuente es aceptable





Compartir memoria... ¿para qué?

● Cuando el costo de serializar se vuelve prohibitivo

– Estructuras grandes y complejas en cache:

se pierde mucho tiempo serializando y deserializando muchos objetos

– Objetos muy pesados de serializar para cachear:

● Ej: SQLAlchemy





Compartir memoria... ¿para qué?

● La transición a un "bundle" compartido

– Separamos el cache en dos capas superpuestas:

● Una de lenta evolución, sólo lectura
● Una con la diferencia, de actualización contínua pero infrecuente

– La mayor parte de los objetos van a estar en la capa estática
– Lo que falte (o esté viejo) en esa capa, se accede como siempre





El bundle compartido

● Síntesis de lo mejor de ambos mundos

– Estructura compacta, eficiente y compartida para datos estáticos de

base

– Estructura dinámica, de actualización rápida, para el resto

Datos nuevos

Datos viejos

Bundle



Usuario



¿DEMO?





¿cómo?

Archivo

compartido con mmap

P3

P4

P5

P1

P2

P3





¿cómo?

Tan simple como:

fileobj = open("buf", "r+")
buf = mmap.mmap(
fileobj.fileno(), 0,
access = mmap.ACCESS_READ)





¿cómo uso eso para meter objetos?

Más complicado

● Hay que definir un esquema

– Que sea fácilmente manipulable sin serialización
– Que sea eficiente en espacio y tiempo de acceso

● Hay que armar maquinaria que permita acceder a esos datos

– Como si fueran objetos
– Sin copiarlos a la memoria privada de cada proceso





¿cómo uso eso para meter objetos?

Más complicado

● Hay que definir un esquema –struct—

– Que sea fácilmente manipulable sin serialización
– Que sea eficiente en espacio y tiempo de acceso

● Hay que armar maquinaria que permita acceder a esos datos

– Como si fueran objetos
– Sin copiarlos a la memoria privada de cada proceso –proxies—





Structs

En C:

En Python

import struct
struct.pack(
"if?", 1, 2.0, True)

struct {
int a;
float b;
bool c;
}





Structs

● ¿Por qué meter C en esto?

– El código nativo puede acceder nativamente a los structs
– Son multi-lenguaje (es posible interpretarlos en otros lenguajes)
– Cython





Proxies

● Clases que saben dónde en un buffer buscar un struct
● Convierten acceso a atributos a lectura del struct:

x = Proxy(buf, offset=10)
x.a # lee el int
x.b # lee el float
x.c # lee el bool





Proxies

● No requieren serialización

– Con conocer dónde está el struct basta

● Se pueden fácilmente "reapuntar"

– Cambiar el offset cambia qué objeto están mostrando eficientemente
– Evita el costo de crear objetos python todo el tiempo

● Son relativamente transparentes
– Se ven casi como el objeto original





Proxies – agregando complejidad

struct ComplexProxy {
int value;
int child_left_offset;
int child_right_offset;
}

class ComplexObj:
def __init__(self,
l = None, r = None):
self.value = 3
self.left = l
self.right = r





Proxies – agregando complejidad

class ComplexProxy:
def __init__(self, buf, pos):
self.buf = buf
self.pos = pos

a = IntProperty(offset=0)
b = ProxyProperty(ComplexProxy,
offset=4)
c = ProxyProperty(ComplexProxy,
offset=8)

class IntProperty:
def __get__(self, obj, kls):
return unpack("i",
obj.buf, obj.pos+self.offset)
class ProxyProperty:
def __get__(self, obj, kls):
voffset = unpack("i", obj.buf,
obj.pos+self.offset)
return ComplexProxy(
obj.buf, voffset)





Proxies – referencias cíclicas – OOPS!

● Se complica empaquetar objetos con referencias cíclicas

– Hay que reconocerlas al armar el archivo
– Requieren cuidado, como siempre

● Hay dos formas de manejarlas:

– Prohibirlas
– Soportarlas





Proxies – referencias cíclicas – OOPS!

Mapa de identidad

● Mapea id(objeto) → offset
● Al empaquetar un objeto, se actualiza el mapa de identidad

– Y chequearlo, para detectar objetos ya empaquetados

● Comprime el archivo

– Unifica referencias repetidas a un mismo objeto

● Rompe ciclos





Proxies – referencias cíclicas – OOPS!

● Cuidados a tener

Mapa de identidad

– Si se está iterando un generador para construir el "bundle", es

posible que hayan dos objetos con el mismo id()
● Hay que mantener sincronizado el mapa de identidad con los objetos

realmente en memoria. Si un objeto es destruido, tiene que limpiarse su
entrada del mapa

– El mapa de identidad puede crecer considerablemente

● En particular cuando se generan bundles grandes con millones de objetos





pará un cacho





Dijiste sin serializar





Manipulación sin serialización

● Generar un bundle cuesta

– Similar a serializar, sí





Manipulación sin serialización

● Generar un bundle cuesta

– Similar a serializar, sí

● Pero... usar, no

– Abrir
– Leer
– Buscar
– Hasta escribir (con ciertos límites)





Manipulación sin serialización

Estructura de un objeto





Manipulación sin serialización

Estructura de un objeto

Bitmap de atributos

presente:11010000

nulls:11010000





Manipulación sin serialización

Estructura de un objeto

Bitmap de atributos

presente:11010000

nulls:11010000

a : 4 bytes : int

b : 4 bytes : float

*c : 8 bytes : uint





Manipulación sin serialización

Estructura de un objeto

Bitmap de atributos

presente:11010000

nulls:11010000

a : 4 bytes : int

b : 4 bytes : float

*c : 8 bytes : uint

c : 12 bytes : str





Manipulación sin serialización

Anidando objetos

Bitmap de atributos

presente:11010000

nulls:11010000

a : 4 bytes : int

b : 4 bytes : float

*c : 8 bytes : uint

c : N bytes : object
Bitmap de atributos



presente:11010000

nulls:11010000

a : 4 bytes : int

b : 4 bytes : float
c : N bytes : object



*c : 8 bytes : uint

Manipulación sin serialización

Tipos dinámicos

Bitmap de atributos

presente:11010000

nulls:11010000

a : 4 bytes : int
a : 4 bytes : int

b : 4 bytes : float

*c : 8 bytes : uint

c : N bytes : any

typecode

value : 8 bytes : double





Manipulación sin serialización

Secuencias lineales

*i1

*i2

*i3

*i4

v1 : 4b

v2 : 4b

v3 : 10b

v4 : 40b

Índice

Datos





Manipulación sin serialización

Modificaciones

*i1

*i2

*i3

*i4

v1 : 4b

v2 : 4b

v3 : 10b

v4 : 40b

Índice

Datos





Manipulación sin serialización

Modificaciones

*i1

*i2

*i3

*i4

v1 : 4b

v2 : 4b

v3 : 10b

v4 : 40b

Índice

Datos





Mapas asociativos

● Tabla de hash compacta:

– Array ordenado de tuplas <hash, clave, valor>
– Búsqueda binaria optimizada para distribuciones uniformes

● Una predicción sabiendo la distribución de las claves (hash)
● Una iteración de búsqueda exponencial para ajustar la predicción
● Finalizar con una búsqueda binaria regular

● Tabla de hash aproximada:

– Tirar la clave, asumir las colisiones como error aceptable
– Particularmente eficiente para claves textuales largas





Mapas asociativos

Índice

h1

h2

h3

h4

*k1

*k2

*k3

*k4

*v1

*v2

*v3

*v4

pedro

Claves

2324 4141

Valores





Mapas asociativos

Índice

1

7

7

alice

bob

cloe

*v1

*v2

*v3

15

pedro

*v4

m['bob'] == v2
m['cloe'] == v3

pedro

Claves

2324 4141

Valores





Mapas asociativos aproximados

Índice

h1

h2

h3

h4

*v1

*v2

*v3

*v4



2324 4141

Valores



Mapas asociativos aproximados

Índice

1

7

7

15

*v1

*v2

*v3

*v4

m['bob'] == m['cloe'] == [v2,v3]



2324 4141

Valores



Mapas asociativos aproximados

Búsqueda binaria optimizada

3

27

...

56

87





Mapas asociativos aproximados

Búsqueda binaria optimizada

3

27

...

56

87

Predicción

inicial





Mapas asociativos aproximados

Búsqueda binaria optimizada

3

27

29

...

45

56

87

Predicción

inicial





Mapas asociativos aproximados

Búsqueda binaria optimizada

3

27

29

...

45

56

87

Predicción

inicial





Mapas asociativos aproximados

Búsqueda binaria optimizada

3

27

29

...

45

56

87

Predicción

inicial





Mapas asociativos aproximados

Búsqueda binaria optimizada

3

27

29

...

45

56

87

Predicción

inicial

Límite de
búsqueda





Mapas asociativos aproximados

Búsqueda binaria optimizada

3

27

...

56

87

Predicción

inicial

Valor

buscado

Límite de
búsqueda





Exprimiendo velocidad

● Performance:

– Sólo el set de datos "caliente" (más utilizado) necesita entrar en RAM
– Búsqueda binaria optimizada en 2 e log(e)

● e siendo el error entre la predicción y la posición efectiva
● e < n

● Tabla de hash aproximada:

– Tamaño fijo incluso con claves grandes (strings largos)
– Acceso incluso más eficiente (no hace falta verificar claves)





Exprimiendo velocidad

● Performance:

– Buen patrón de acceso a disco si no entra en memoria:
● La búsqueda exponencial resulta en acceso quasi-secuencial
● Buena localidad de referencia con buenas predicciones

– O(1) seeks en promedio

● Posiblidad de precargar el índice

– mucho más compacto que los valores o las keys





Exprimiendo velocidad

● Magia Cython:

– En vez de usar struct por todos lados
– Evita generar objetos python para operaciones temporales

● Reuso de proxies:

– En vez de crearlos todo el tiempo, reapuntar proxies existentes
– Transmutación de tipos para cuando cambia la forma del objeto

● proxy.__class__ = new_cls













No lo escribas desde cero

pip install sharedbuffers
  • Links de descarga
http://lwp-l.com/pdf9454

Comentarios de: Compartiendo memoria. Eficientemente. (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad