Localidad temporal y conjuntos de trabajo

Una caché solo ayuda con los datos que vuelve a leer, y lo que importa es cuánto tarda. Esta lección lo mide con un solo número, la distancia de reutilización, y lo usa para predecir de una vez la tasa de aciertos de todos los tamaños de caché, incluido el precipicio en el que un bucle es solo un poco demasiado grande para caber.

Los dos últimos temas trataron de adónde van las líneas. Este trata de cuándo vuelven. Un programa que lee un precio, trabaja un poco y vuelve a leer el mismo precio un momento después muestra localidad temporal. Cuanto más corto es el intervalo, más probable es que la línea siga en la caché. Piense en los libros de su escritorio: el que usó hace un minuto sigue allí, el del mes pasado volvió a la estantería.

Leer la línea 5 dos veces seguidas da distancia 0. En la secuencia 1, 2, 3, 1 la última lectura tiene distancia 2, porque las líneas 2 y 3 vinieron entre medias. Leer diez veces la línea 2 entre dos lecturas de la línea 1 sigue contando como una sola línea. El código guarda una lista de las líneas en el orden de su último uso, la más reciente al final. Cuando una línea vuelve, las líneas que la siguen en la lista son exactamente las usadas desde entonces.

def reuse_distances(lines):    stack = []    out = []    for line in lines:        if line in stack:            position = stack.index(line)            out.append(len(stack) - 1 - position)1            stack.pop(position)        else:            out.append(None)        stack.append(line)    return outprint(reuse_distances([1, 2, 3, 1, 2, 1, 1]))

[None, None, None, 2, 2, 1, 0]

1. 1Las líneas que siguen a esta en la lista son exactamente las usadas desde su última lectura: su número es la distancia.

Este es el hecho útil. Tome una caché que contiene C líneas y expulsa la menos recientemente usada, sean cuales sean los números de línea. En cada momento contiene las C líneas distintas usadas más recientemente. Una lectura acierta exactamente cuando su línea está entre ellas, es decir, cuando se han leído menos de C líneas distintas desde su último uso. Dicho de otro modo, la lectura acierta cuando su distancia de reutilización es menor que C.

El código siguiente comprueba la afirmación. Simula una caché LRU para capacidades de 1 a 4 y calcula también la tasa de aciertos solo a partir de las distancias, sin caché alguna. Las dos columnas coinciden. Las distancias se calculan una vez y luego dan la tasa de aciertos de cada tamaño de caché.

def lru_hit_rate(lines, capacity):    cache = []    hits = 0    for line in lines:        if line in cache:            hits += 1            cache.remove(line)        elif len(cache) >= capacity:            cache.pop(0)        cache.append(line)    return hits / len(lines)def hit_rate_from_distances(distances, capacity):    hits = sum(1 for d in distances if d is not None and d < capacity)    return hits / len(distances)lines = [1, 2, 3, 1, 2, 3, 4, 1, 2, 3]d = reuse_distances(lines)for capacity in (1, 2, 3, 4):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3), round(hit_rate_from_distances(d, capacity), 3))1

1 lines: 0.0 0.0
2 lines: 0.0 0.0
3 lines: 0.3 0.3
4 lines: 0.6 0.6

1. 1Los mismos números en ambas columnas: las distancias solas predicen la tasa de aciertos de cada tamaño de caché.

El conjunto de trabajo de una serie de lecturas es el conjunto de líneas distintas que tocan. Si cabe en la caché, el programa corre casi por completo desde la caché. Si es solo un poco mayor, LRU puede fallar del todo. Tome un bucle que lee 48 líneas en orden, tres veces. Cada línea se vuelve a leer tras otras 47, así que todas las distancias de reutilización son 47. Una caché de 47 líneas o menos nunca acierta, y una de 48 acierta en cada lectura tras la primera pasada.

def sweep_lines(n_lines, passes):    return list(range(n_lines)) * passeslines = sweep_lines(48, 3)for capacity in (16, 32, 47, 48):    print(capacity, "lines:", round(lru_hit_rate(lines, capacity), 3))

16 lines: 0.0
32 lines: 0.0
47 lines: 0.0
48 lines: 0.667

Una media móvil calculada a la fuerza bruta lee los últimos 20 valores cada día: vuelve a leer 19 de los 20 valores leídos el día anterior. Es un programa con mucha localidad temporal. El código construye las direcciones leídas para los primeros 600 cierres, las convierte en líneas y mide las distancias, la tasa de aciertos para cuatro tamaños de caché y el conjunto de trabajo de 20 lecturas consecutivas.

def rolling_mean_trace(n, window, elem_bytes):    trace = []    for end in range(window - 1, n):        for position in range(end - window + 1, end + 1):            trace.append(position * elem_bytes)    return tracedef working_set(lines, window):    return max(len(set(lines[i:i + window])) for i in range(len(lines) - window + 1))lines = [address // 64 for address in rolling_mean_trace(600, 20, 8)]d = reuse_distances(lines)print(len(lines), "reads from", len(set(lines)), "lines")for capacity in (1, 2, 4, 8):    print(capacity, "lines:", round(hit_rate_from_distances(d, capacity), 3))print("working set of 20 reads:", working_set(lines, 20), "lines")

11620 reads from 75 lines
1 lines: 0.831
2 lines: 0.831
4 lines: 0.994
8 lines: 0.994
working set of 20 reads: 4 lines

Una línea basta para el 83 % de las lecturas, porque el siguiente valor del arreglo está en la línea recién leída. Cuatro líneas alcanzan el 99,4 %. Las 75 líneas del conjunto de datos nunca tienen que caber: el conjunto de trabajo de 20 lecturas son solo 4 líneas, así que basta una caché diminuta. Esa es la diferencia entre el tamaño de los datos y el del conjunto de trabajo.

El laboratorio pide las piezas anteriores, más la ayuda que halla la caché más pequeña para una tasa de aciertos, y termina con el estudio sobre los cierres reales de SPY.

• Función · preguntaSe apoya en
• reuse_distances(lines)¿Cuánto tarda en releerse cada línea?Una lista en orden de último uso
• lru_hit_rate(lines, capacity)¿Cuánto acierta una caché LRU simulada?Líneas en orden LRU
• hit_rate_from_distances(distances, capacity)¿La misma tasa de aciertos, sin caché?reuse_distances
• working_set(lines, window)¿Cuántas líneas toca una serie de lecturas?Una ventana deslizante
• capacity_for(lines, target)¿Cuán pequeña puede ser la caché?reuse_distanceshit_rate_from_distances
• rolling_mean_trace(n, window, elem_bytes)¿Qué direcciones lee una media móvil lenta?Aritmética simple
• study(bars)¿Qué tan local es una media móvil sobre los cierres de SPY?rolling_mean_tracecapacity_for

Siguiente tema: ya sabe cómo una disposición se convierte en una traza y una traza en aciertos y fallos. En Arreglo de estructuras frente a estructura de arreglos lo usa para elegir cómo disponer una tabla de ticks, comparando lecturas de columnas y de filas enteras en ambas disposiciones.