Alocadores e pools de memória

Cada nó de lista, nó de árvore ou ordem que um programa cria vem de um alocador, e o alocador decide que endereços eles recebem. Um malloc de uso geral espalha os objetos pequenos com cabeçalhos e com os próprios objetos temporários do programa; um pool os empacota. Esta aula modela os dois e percorre a mesma lista com 3,3 vezes menos faltas de cache a partir de um pool.

Quando um programa pede memória para um objeto, um alocador lhe dá um bloco e devolve o endereço. Um alocador de uso geral precisa lembrar o tamanho de cada bloco, então guarda um pequeno cabeçalho na frente dele, e arredonda os blocos para um múltiplo de 16 bytes para que qualquer tipo de valor caiba. O modelo mais simples nunca reutiliza memória: cada pedido toma um bloco logo depois do anterior e o programa recebe o endereço logo depois do cabeçalho.

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. 1O bloco é o pedido mais o cabeçalho, arredondado para um múltiplo de 16: 24 bytes precisam de um bloco de 48 bytes, 100 bytes precisam de 128.

Um nó de 24 bytes (um fechamento, um volume e um ponteiro seguinte, 8 bytes cada) recebe um bloco de 48 bytes, o dobro do que precisa, e um objeto temporário de 100 bytes recebe 128. Os três endereços são 16, 64 e 192: o segundo pedido começa depois do bloco de 48 bytes do primeiro, o terceiro depois do bloco de 128 bytes do segundo.

O código real não constrói uma lista no vácuo. Entre dois nós ele formata uma mensagem, monta uma chave ou analisa uma linha, e esses objetos temporários também são alocados. Com um alocador simples que nunca reutiliza memória, eles ficam entre os nós. A primeira função abaixo monta o plano de pedidos, um nó seguido de três temporários de 100 bytes, e a segunda atende o plano e guarda só os endereços dos nós. Para comparar, escrevemos também um pool, que entrega vagas fixas uma logo após a outra.

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]

Com três temporários por nó os nós ficam a 432 bytes um do outro: 48 do nó e 3 × 128 do lixo. Sem temporários ficam a 48 bytes. Num pool ficam a 24 bytes, exatamente o tamanho de um nó, sem cabeçalho nem lixo. Uma linha de 64 bytes guarda um nó disperso, 1,3 nó só com cabeçalhos e 2,7 nós no pool. Agora percorremos 3000 nós, lendo o primeiro e o último byte de cada um, pelo cache dos tópicos 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

A lista espalhada custa 3750 faltas e se estende por 1265 KB. O pool, que guarda exatamente os mesmos 3000 nós, custa 1125 faltas em 70 KB: 3,3 vezes menos, e os nós caberiam até num cache L2. O programa, os dados e a ordem do percurso são os mesmos; só os endereços mudaram.

O laboratório segue a aula: o arredondamento, o alocador de uso geral simples, o pool, o plano de pedidos com temporários, os endereços dos nós, a contagem de faltas de um percurso e o estudo sobre uma lista de dias do SPY.

• Função · perguntaBaseia-se em
• round_up(n, align)Quanto é n arredondado para um múltiplo?Aritmética simples
• malloc_addresses(sizes)Onde um alocador de uso geral põe cada bloco?round_up
• pool_addresses(n, slot_bytes)E um pool?Aritmética simples
• alloc_plan(...)Que pedidos o programa faz?Aritmética simples
• node_addresses(...)Onde os nós vão parar?alloc_planmalloc_addresses
• traversal_misses(addresses, node_bytes)Quantas faltas um percurso custa?Cache
• study(bars)Quanto um pool economiza na lista do SPY?node_addressespool_addressestraversal_misses

Próximo tópico: até agora cada custo vinha da memória. O último efeito de hardware desta habilidade vem dos palpites do processador. Em Previsão de desvios você modela um preditor, conta seus erros num laço com um if dentro e vê por que o mesmo laço é mais rápido com dados ordenados.