Asignadores y pools de memoria

Cada nodo de lista, nodo de árbol u orden que crea un programa sale de un asignador, y el asignador decide qué direcciones reciben. Un malloc de propósito general dispersa los objetos pequeños con cabeceras y con los propios objetos temporales del programa; un pool los empaqueta. Esta lección modela ambos y recorre la misma lista con 3,3 veces menos fallos de caché desde un pool.

Cuando un programa pide memoria para un objeto, un asignador le da un bloque y devuelve la dirección. Un asignador de propósito general tiene que recordar el tamaño de cada bloque, así que guarda una pequeña cabecera delante de él, y redondea los bloques a un múltiplo de 16 bytes para que quepa cualquier tipo de valor. El modelo más simple nunca reutiliza memoria: cada petición toma un bloque justo después del anterior y el programa recibe la dirección que está justo después de la cabecera.

def round_up(n, align):    return -(-n // align) * aligndef malloc_addresses(sizes, header=HEADER_BYTES, align=ALIGN):    addresses = []    start = 0    for size in sizes:        addresses.append(start + header)1        start += round_up(size + header, align)    return addressesprint(malloc_addresses([24, 100, 24]))print([round_up(size + 16, 16) for size in (24, 100)])

[16, 64, 192]
[48, 128]

1. 1El bloque es la petición más la cabecera, redondeada a un múltiplo de 16: 24 bytes necesitan un bloque de 48 bytes, 100 bytes necesitan 128.

Un nodo de 24 bytes (un cierre, un volumen y un puntero siguiente, 8 bytes cada uno) recibe un bloque de 48 bytes, el doble de lo que necesita, y un objeto temporal de 100 bytes recibe 128. Las tres direcciones son 16, 64 y 192: la segunda petición empieza tras el bloque de 48 bytes de la primera, la tercera tras el bloque de 128 bytes de la segunda.

El código real no construye una lista en el vacío. Entre dos nodos formatea un mensaje, construye una clave o analiza una línea, y esos objetos temporales también se asignan. Con un asignador simple que nunca reutiliza memoria quedan entre los nodos. La primera función siguiente construye el plan de peticiones, un nodo seguido de tres temporales de 100 bytes, y la segunda sirve el plan y conserva solo las direcciones de los nodos. Para comparar escribimos también un pool, que reparte ranuras fijas una justo después de otra.

def alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes = []    node_index = []    for _ in range(n_nodes):        node_index.append(len(sizes))        sizes.append(node_bytes)        sizes.extend([garbage_bytes] * garbage_per_node)    return sizes, node_indexdef node_addresses(n_nodes, garbage_per_node, garbage_bytes, node_bytes):    sizes, node_index = alloc_plan(n_nodes, garbage_per_node, garbage_bytes, node_bytes)    addresses = malloc_addresses(sizes)    return [addresses[i] for i in node_index]def pool_addresses(n, slot_bytes, base=0):    return [base + i * slot_bytes for i in range(n)]print(node_addresses(3, 3, 100, 24))print(node_addresses(3, 0, 100, 24))print(pool_addresses(3, 24))

[16, 448, 880]
[16, 64, 112]
[0, 24, 48]

Con tres temporales por nodo los nodos están separados 432 bytes: 48 del nodo y 3 × 128 de la basura. Sin temporales están separados 48 bytes. En un pool están separados 24 bytes, exactamente el tamaño de un nodo, sin cabecera ni basura. Una línea de 64 bytes contiene un nodo disperso, 1,3 nodos con solo cabeceras y 2,7 nodos en el pool. Ahora recorremos 3000 nodos, leyendo el primer y el último byte de cada uno, por la caché de los temas anteriores.

def traversal_misses(addresses, node_bytes):    cache = Cache()    for address in addresses:        cache.access(address)        cache.access(address + node_bytes - 1)    return cache.missesn = 3000for name, addresses in (("scattered", node_addresses(n, 3, 100, 24)), ("headers only", node_addresses(n, 0, 100, 24)), ("pool", pool_addresses(n, 24))):    print(name, traversal_misses(addresses, 24), "misses, last node at", addresses[-1] // 1024, "KB")

scattered 3750 misses, last node at 1265 KB
headers only 2250 misses, last node at 140 KB
pool 1125 misses, last node at 70 KB

La lista dispersa cuesta 3750 fallos y se extiende por 1265 KB. El pool, que contiene exactamente los mismos 3000 nodos, cuesta 1125 fallos en 70 KB: 3,3 veces menos, y los nodos incluso cabrían en una caché L2. El programa, los datos y el orden del recorrido son los mismos; solo cambiaron las direcciones.

El laboratorio sigue la lección: el redondeo, el asignador de propósito general simple, el pool, el plan de peticiones con temporales, las direcciones de los nodos, el recuento de fallos de un recorrido y el estudio sobre una lista de días de SPY.

• Función · preguntaSe apoya en
• round_up(n, align)¿Cuánto es n redondeado a un múltiplo?Aritmética simple
• malloc_addresses(sizes)¿Dónde pone cada bloque un asignador de propósito general?round_up
• pool_addresses(n, slot_bytes)¿Y un pool?Aritmética simple
• alloc_plan(...)¿Qué peticiones hace el programa?Aritmética simple
• node_addresses(...)¿Dónde acaban los nodos?alloc_planmalloc_addresses
• traversal_misses(addresses, node_bytes)¿Cuántos fallos cuesta un recorrido?Cache
• study(bars)¿Cuánto ahorra un pool en la lista de SPY?node_addressespool_addressestraversal_misses

Siguiente tema: hasta ahora cada coste venía de la memoria. El último efecto de hardware de esta habilidad viene de las apuestas del procesador. En Predicción de saltos modela un predictor, cuenta sus errores en un bucle con un if dentro y ve por qué el mismo bucle es más rápido con datos ordenados.