Prinzip der Lokalität und Anrufanweisungen

Question

In dem Prinzip der Lokalität zu diskutieren, macht mein Lehrbuch die folgenden Aussagen:

Außer Zweig und rufen Sie die Anweisungen, die nur einen kleinen Bruchteil aller Programmanweisungen darstellen, die Programmausführung ist sequenziell. Daher folgt in den meisten Fällen der Befehl, der sofort abgerufen werden soll , der letzte abgerufene Befehl.

Als Anfänger, finde ich das schwer zu glauben. Der gesamte Code, auf den ich gestoßen bin, ist stark mit Anrufanweisungen gefüllt. Tatsächlich scheint mir, dass Anrufanweisungen tatsächlich die wesentlichsten Aktionen in einem Programm ausführen.

Ich würde es sehr schätzen, wenn jemand könnte bitte erläutern, warum dieses Konzept wahr ist, trotz der erheblichen Rolle von Aufruf Anweisungen in Programmen.

Answer 1

Ich wählte eine zufällige binäre auf meinem Computer, der cargo Paket-Manager. Dann ich:

• zerlegt es mit otool -tvV cargo > assembly
• bekam nur die Anweisungen: cat assembly | awk '{print $2}' > instructions
• Gezählt jede Anweisung: sort instructions | uniq -c | sort -n > count

ich das Ergebnis in Libreoffice Calc in eine Liste von Vorkommnissen verarbeitet für jede Anweisung. Hier sind diejenigen, die mehr als 1% des Programms bilden sich (diese Summe auf 86%, so gibt es eine beträchtliche Anzahl von Streu Operationen, die ich für brewity verworfen):

| 34.83% | movq | 
| 7.30% | leaq | 
| 7.00% | callq | 
| 6.90% | je  | 
| 5.61% | movl | 
| 4.86% | cmpq | 
| 3.77% | testq | 
| 3.11% | jmp  | 
| 2.23% | jne  | 
| 2.17% | popq | 
| 2.05% | pushq | 
| 1.69% | addq | 
| 1.29% | cmpl | 
| 1.20% | movabsq | 
| 1.18% | movb | 
| 1.05% | xorl | 

Es ist auf jeden Fall eine Menge Verzweigung und ruft hier weiter (callq, jmp, je, jne) aber auch ziemlich viele Speicheroperationen. Die Speicheroperationen sind vergleichsweise langsam und machen einen Großteil der Laufzeit des Programms aus. movq ist nur eine Speicheroperation und es macht mehr als ein Drittel des Programms aus!

CPU-Caches werden verwendet, um kürzlich referenzierte Speicherdaten in der Nähe des CPU-Kerns zu speichern, wodurch zukünftige Speicheroperationen für dieselben Daten beschleunigt werden. Sie können dies aufgrund der Principle of Locality tun, die besagt, dass Operationen im selben Speicher oft zeitlich nahe kommen (zeitliche Lokalität). So können die Speicherdaten zwischengespeichert werden, da Sie sie wahrscheinlich bald wieder benötigen werden.