Jeder Listenknoten, Baumknoten oder jede Order, die ein Programm erzeugt, kommt von einem Allokator, und der Allokator entscheidet über ihre Adressen. Ein universelles malloc verstreut kleine Objekte mit Headern und mit den eigenen temporären Objekten des Programms; ein Pool packt sie dicht. Diese Lektion modelliert beides und durchläuft dieselbe Liste aus einem Pool mit 3,3-mal weniger Cache-Fehlzugriffen.
Woher kommen die Adressen?
Wenn ein Programm Speicher für ein Objekt anfordert, gibt ein Allokator ihm einen Block und liefert die Adresse. Ein universeller Allokator muss sich die Größe jedes Blocks merken, also legt er einen kleinen Header davor und rundet Blöcke auf ein Vielfaches von 16 Byte auf, damit jede Art von Wert hineinpasst. Das einfachste Modell verwendet nie Speicher wieder: Jede Anfrage nimmt einen Block direkt nach dem vorigen, und das Programm erhält die Adresse direkt hinter dem Header.
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]
- 1Der Block ist die Anfrage plus Header, auf ein Vielfaches von 16 aufgerundet: 24 Byte brauchen einen 48-Byte-Block, 100 Byte brauchen 128.
Ein Knoten von 24 Byte (ein Schlusskurs, ein Volumen und ein Next-Zeiger, je 8 Byte) bekommt einen Block von 48 Byte, doppelt so viel, wie er braucht, und ein temporäres Objekt von 100 Byte bekommt 128. Die drei Adressen sind 16, 64 und 192: Die zweite Anfrage beginnt nach dem 48-Byte-Block der ersten, die dritte nach dem 128-Byte-Block der zweiten.
Temporäre Objekte verstreuen Ihre Knoten
Echter Code baut eine Liste nicht im luftleeren Raum. Zwischen zwei Knoten formatiert er eine Nachricht, baut einen Schlüssel oder parst eine Zeile, und diese temporären Objekte werden ebenfalls allokiert. Bei einem einfachen Allokator, der nie Speicher wiederverwendet, liegen sie zwischen den Knoten. Die erste Funktion unten baut den Anfrageplan, einen Knoten gefolgt von drei temporären Objekten zu 100 Byte, und die zweite bedient den Plan und behält nur die Adressen der Knoten. Zum Vergleich schreiben wir auch einen Pool, der feste Plätze einen direkt nach dem anderen vergibt.
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]
Mit drei temporären Objekten pro Knoten liegen die Knoten 432 Byte auseinander: 48 für den Knoten und 3 × 128 für den Müll. Ohne temporäre Objekte sind es 48 Byte. In einem Pool sind es 24 Byte, genau die Größe eines Knotens, ohne Header und ohne Müll. Eine 64-Byte-Zeile enthält einen verstreuten Knoten, 1,3 Knoten bei nur Headern und 2,7 Knoten im Pool. Wir durchlaufen jetzt 3.000 Knoten, lesen von jedem das erste und das letzte Byte, durch den Cache der früheren Themen.
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
Die verstreute Liste kostet 3.750 Fehlzugriffe und erstreckt sich über 1.265 KB. Der Pool, der dieselben 3.000 Knoten enthält, kostet 1.125 Fehlzugriffe über 70 KB: 3,3-mal weniger, und die Knoten würden sogar in einen L2-Cache passen. Programm, Daten und Reihenfolge des Durchlaufs sind gleich; nur die Adressen haben sich geändert.
Ein Pool vergibt gleich große Plätze aus einem zusammenhängenden Stück und nimmt sie über eine Freiliste zurück. Eine Arena schiebt nur einen Zeiger vorwärts, vergibt jede Größe ohne Header und gibt alles auf einmal frei. Beide halten gemeinsam genutzte Objekte nebeneinander.
Eine Python-Liste mit 3.000 Floats enthält Zeiger auf 3.000 einzelne Float-Objekte, die der Allokator verstreut hat, während ein NumPy-Array die 3.000 Werte nebeneinander speichert. Das Array zu durchlaufen berührt ein paar hundert Zeilen, die Liste Tausende. Das ist ein weiterer Grund, warum NumPy schnell ist.
Ein Pool braucht Objekte einer Größe und eine gute Schätzung ihrer Anzahl, und eine Arena kann kein einzelnes Objekt früher freigeben. Nutzen Sie sie für die heißen Strukturen eines Programms, etwa ein Orderbuch oder eine Tick-Liste, und überlassen Sie den Rest dem universellen Allokator.
Was Sie bauen werden
Das Labor folgt der Lektion: das Aufrunden, der einfache universelle Allokator, der Pool, der Anfrageplan mit temporären Objekten, die Adressen der Knoten, die Zählung der Fehlzugriffe eines Durchlaufs und die Studie an einer Liste von SPY-Tagen.
- Funktion · FrageBaut auf
- round_up(n, align)Was ist n auf ein Vielfaches aufgerundet?Einfache Arithmetik
- malloc_addresses(sizes)Wohin legt ein universeller Allokator jeden Block?round_up
- pool_addresses(n, slot_bytes)Und ein Pool?Einfache Arithmetik
- alloc_plan(...)Welche Anfragen stellt das Programm?Einfache Arithmetik
- node_addresses(...)Wo landen die Knoten?alloc_planmalloc_addresses
- traversal_misses(addresses, node_bytes)Wie viele Fehlzugriffe kostet ein Durchlauf?Cache
- study(bars)Was spart ein Pool bei der SPY-Liste?node_addressespool_addressestraversal_misses
Nächstes Thema: Bisher kam jeder Kostenfaktor vom Speicher. Der letzte Hardware-Effekt dieser Fähigkeit kommt von den Vermutungen des Prozessors. In Sprungvorhersage modellieren Sie einen Prädiktor, zählen seine Fehler in einer Schleife mit einem if darin und sehen, warum dieselbe Schleife auf sortierten Daten schneller ist.
Lab: Was bewertet wird
7 Aufgaben · 100 Pkt.- Aufrunden5 Pkt.
- Ein einfacher universeller Allokator20 Pkt.
- Ein Pool10 Pkt.
- Die Anfragen eines Programms15 Pkt.
- Die Adressen der Knoten10 Pkt.
- Die Kosten eines Durchlaufs15 Pkt.
- Die Studie mit der SPY-Tabelle25 Pkt.