Allocateurs et pools mémoire

Chaque nœud de liste, nœud d'arbre ou ordre qu'un programme crée vient d'un allocateur, et c'est l'allocateur qui décide de leurs adresses. Un malloc généraliste disperse les petits objets avec des en-têtes et avec les propres objets temporaires du programme ; un pool les range serrés. Ce cours modélise les deux et parcourt la même liste avec 3,3 fois moins de défauts de cache depuis un pool.

Quand un programme demande de la mémoire pour un objet, un allocateur lui donne un bloc et renvoie l'adresse. Un allocateur généraliste doit se souvenir de la taille de chaque bloc : il garde donc un petit en-tête devant lui, et il arrondit les blocs à un multiple de 16 octets pour que n'importe quelle valeur puisse s'y ranger. Le modèle le plus simple ne réutilise jamais la mémoire : chaque demande prend un bloc juste après le précédent, et le programme reçoit l'adresse située juste après l'en-tête.

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. 1Le bloc est la demande plus l'en-tête, arrondie à un multiple de 16 : 24 octets demandent un bloc de 48 octets, 100 octets en demandent 128.

Un nœud de 24 octets (une clôture, un volume et un pointeur suivant, 8 octets chacun) reçoit un bloc de 48 octets, le double de ce dont il a besoin, et un objet temporaire de 100 octets en reçoit 128. Les trois adresses sont 16, 64 et 192 : la deuxième demande commence après le bloc de 48 octets de la première, la troisième après le bloc de 128 octets de la deuxième.

Le vrai code ne construit pas une liste dans le vide. Entre deux nœuds il formate un message, construit une clé ou analyse une ligne, et ces objets temporaires sont alloués aussi. Avec un allocateur simple qui ne réutilise jamais la mémoire, ils se placent entre les nœuds. La première fonction ci-dessous construit le plan des demandes, un nœud suivi de trois temporaires de 100 octets, et la seconde sert le plan et ne garde que les adresses des nœuds. Pour comparer, nous écrivons aussi un pool, qui distribue des emplacements fixes l'un juste après l'autre.

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]

Avec trois temporaires par nœud, les nœuds sont espacés de 432 octets : 48 pour le nœud et 3 × 128 pour les déchets. Sans temporaires, ils sont espacés de 48 octets. Dans un pool, ils sont espacés de 24 octets, exactement la taille d'un nœud, sans en-tête ni déchet. Une ligne de 64 octets contient un nœud dispersé, 1,3 nœud avec les seuls en-têtes, et 2,7 nœuds dans le pool. Nous parcourons maintenant 3 000 nœuds, en lisant le premier et le dernier octet de chacun, dans le cache des sujets précédents.

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 liste dispersée coûte 3 750 défauts et s'étale sur 1 265 Ko. Le pool, qui contient exactement les mêmes 3 000 nœuds, coûte 1 125 défauts sur 70 Ko : 3,3 fois moins, et les nœuds tiendraient même dans un cache L2. Le programme, les données et l'ordre du parcours sont les mêmes ; seules les adresses ont changé.

Le labo suit le cours : l'arrondi, l'allocateur généraliste simple, le pool, le plan de demandes avec temporaires, les adresses des nœuds, le décompte des défauts d'un parcours et l'étude sur une liste de jours SPY.

• Fonction · questionS'appuie sur
• round_up(n, align)Que vaut n arrondi à un multiple ?De l'arithmétique simple
• malloc_addresses(sizes)Où un allocateur généraliste place-t-il chaque bloc ?round_up
• pool_addresses(n, slot_bytes)Et un pool ?De l'arithmétique simple
• alloc_plan(...)Quelles demandes le programme fait-il ?De l'arithmétique simple
• node_addresses(...)Où les nœuds finissent-ils ?alloc_planmalloc_addresses
• traversal_misses(addresses, node_bytes)Combien de défauts coûte un parcours ?Cache
• study(bars)Que fait gagner un pool sur la liste SPY ?node_addressespool_addressestraversal_misses

Sujet suivant : jusqu'ici chaque coût venait de la mémoire. Le dernier effet matériel de cette compétence vient des paris du processeur. Dans Prédiction de branchement, vous modélisez un prédicteur, comptez ses erreurs sur une boucle qui contient un if et voyez pourquoi la même boucle est plus rapide sur des données triées.