Принцип местонахождения и инструкции по вызову

Question

При обсуждении принципа локальности мой учебник делает следующие утверждения:

За исключением команд ветвления и вызова, которые составляют лишь небольшую часть всех команд программы, выполнение программы является последовательным. Следовательно, в большинстве случаев извлекаемая инструкция следует непосредственно за последней извлеченной инструкцией.

Мне как новичку трудно в это поверить. Весь код, с которым я столкнулся, заполнен инструкциями по вызову. Действительно, мне кажется, что инструкции вызова действительно выполняют самые существенные действия в программе.

Я был бы очень признателен, если бы кто-то мог объяснить, почему эта концепция верна, несмотря на существенную роль инструкций вызова в программах.

Answer 1

Я выбрал случайный двоичный файл на моем компьютере, cargo менеджер пакетов. Затем я:

• разобрал его с otool -tvV cargo > assembly
• получил только инструкции: cat assembly | awk '{print $2}' > instructions
• Посчитали каждую инструкцию: sort instructions | uniq -c | sort -n > count

Я обработал результат в Libreoffice Calc в список вхождений для каждой инструкции. Вот те, которые составляют более 1% программы каждая (они составляют до 86%, так что есть значительное количество случайных операций, которые я отбросил для пивоварения):

| 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    |

Здесь определенно много разветвлений и звонков (callq, jmp, je, jne) но и довольно много операций с памятью. Операции с памятью сравнительно медленные и составляют большую часть времени выполнения программы. movq это только одна операция с памятью, и она составляет более трети программы!

Кэши ЦП используются для того, чтобы данные памяти, на которые недавно ссылались, были близки к ядру ЦП, что ускоряет будущие операции с памятью над теми же данными. Они могут сделать это благодаря принципу локальности, который гласит, что операции с одной и той же памятью часто сближаются во времени (временная локализация). Таким образом, данные в памяти могут быть кэшированы, потому что они, вероятно, скоро понадобятся вам снова.