Localité temporelle et ensembles de travail

Un cache n'aide que pour les données que vous relisez, et ce qui compte est le délai. Ce cours mesure cela avec un seul nombre, la distance de réutilisation, et s'en sert pour prédire d'un coup le taux de succès de toutes les tailles de cache, y compris la falaise où une boucle est juste un peu trop grande pour tenir.

Les deux derniers sujets portaient sur l'endroit où vont les lignes. Celui-ci porte sur le moment où elles reviennent. Un programme qui lit un prix, travaille un peu, puis relit le même prix un instant plus tard montre de la localité temporelle. Plus l'écart est court, plus la ligne a de chances d'être encore dans le cache. Pensez aux livres sur votre bureau : celui que vous avez utilisé il y a une minute y est encore, celui d'il y a un mois est retourné sur l'étagère.

Lire la ligne 5 deux fois de suite donne une distance de 0. Dans la séquence 1, 2, 3, 1, la dernière lecture a une distance de 2, car les lignes 2 et 3 sont venues entre-temps. Lire dix fois la ligne 2 entre deux lectures de la ligne 1 compte quand même pour une seule ligne. Le code garde une liste des lignes dans l'ordre de leur dernier usage, la plus récente en dernier. Quand une ligne revient, les lignes qui la suivent dans la liste sont exactement celles utilisées depuis.

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. 1Les lignes qui suivent celle-ci dans la liste sont exactement les lignes utilisées depuis sa dernière lecture : leur nombre est la distance.

Voici le fait utile. Prenez un cache qui contient C lignes et évince la moins récemment utilisée, quels que soient les numéros de ligne. À tout moment il contient les C lignes différentes utilisées le plus récemment. Une lecture réussit exactement quand sa ligne en fait partie, c'est-à-dire quand moins de C lignes différentes ont été lues depuis son dernier usage. Autrement dit, la lecture réussit quand sa distance de réutilisation est inférieure à C.

Le code ci-dessous vérifie l'affirmation. Il simule un cache LRU pour des capacités de 1 à 4 et calcule aussi le taux de succès à partir des seules distances, sans aucun cache. Les deux colonnes concordent. Les distances sont calculées une fois, puis elles donnent le taux de succès de chaque taille de cache.

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. 1Les mêmes nombres dans les deux colonnes : les distances seules prédisent le taux de succès de chaque taille de cache.

L'ensemble de travail d'une série de lectures est l'ensemble des lignes différentes qu'elles touchent. S'il tient dans le cache, le programme tourne presque entièrement depuis le cache. S'il est à peine plus grand, LRU peut échouer complètement. Prenez une boucle qui lit 48 lignes dans l'ordre, trois fois. Chaque ligne est relue après 47 autres, donc toutes les distances de réutilisation valent 47. Un cache de 47 lignes ou moins ne réussit donc jamais, et un cache de 48 réussit à chaque lecture après le premier passage.

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

Une moyenne glissante calculée à la dure lit les 20 dernières valeurs chaque jour : elle relit 19 des 20 valeurs lues la veille. C'est un programme à forte localité temporelle. Le code construit les adresses lues pour les 600 premières clôtures, les transforme en lignes et mesure les distances, le taux de succès pour quatre tailles de cache et l'ensemble de travail de 20 lectures consécutives.

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

Une ligne suffit pour 83 % des lectures, car la valeur suivante du tableau est dans la ligne qu'on vient de lire. Quatre lignes atteignent 99,4 %. Les 75 lignes de l'ensemble de données n'ont jamais à tenir : l'ensemble de travail de 20 lectures n'est que de 4 lignes, un minuscule cache suffit donc. C'est la différence entre la taille des données et la taille de l'ensemble de travail.

Le labo demande les éléments ci-dessus, plus l'aide qui trouve le plus petit cache pour un taux de succès donné, et se termine par l'étude sur les vraies clôtures de SPY.

• Fonction · questionS'appuie sur
• reuse_distances(lines)Dans combien de temps chaque ligne est-elle relue ?Une liste en ordre de dernier usage
• lru_hit_rate(lines, capacity)Que réussit un cache LRU simulé ?Des lignes en ordre LRU
• hit_rate_from_distances(distances, capacity)Le même taux de succès, sans cache ?reuse_distances
• working_set(lines, window)Combien de lignes touche une série de lectures ?Une fenêtre glissante
• capacity_for(lines, target)Quelle taille minimale pour le cache ?reuse_distanceshit_rate_from_distances
• rolling_mean_trace(n, window, elem_bytes)Quelles adresses lit une moyenne glissante lente ?De l'arithmétique simple
• study(bars)Quelle est la localité d'une moyenne glissante sur les clôtures de SPY ?rolling_mean_tracecapacity_for

Sujet suivant : vous savez maintenant comment une disposition devient une trace et une trace des succès et des défauts. Dans Tableau de structures contre structure de tableaux, vous vous en servez pour choisir comment disposer une table de ticks, en comparant les lectures de colonnes et de lignes entières dans les deux dispositions.