Характеристики производительности фундаментальных операций для вычислительной оценки алгоритмической сложности

Question

Я создал компилятор для языка программирования общего назначения. В качестве части цепочки инструментов я хотел бы включить профилировщик с возможностью оценки временной сложности данного выражения. Кажется довольно простым вычислить алгоритмическую сложность - то есть, если предположить, что все операции с постоянным временем занимают одинаковое количество времени - но я бы хотел иметь возможность приблизительно real сложность тоже. Для этого мне нужна информация об относительной производительности отдельных операций процессора, таких как inc, add, mul и т. Д., А также о некоторых операциях более высокого уровня, таких как ввод-вывод.

Я понимаю, что это зависит как от архитектуры, так и от реализации, в лучшем случае может дать только нечеткие результаты, и - вопрос двойственный. Но кто-нибудь знает какие-нибудь высококачественные ресурсы, которые помогут мне начать? Может ли рассмотрение реализаций операций высокого уровня с открытым исходным кодом дать мне достаточно информации, чтобы дать справедливую оценку их сложности?

Answer 1

На большинстве современных процессоров концепция «времени цикла для конкретной инструкции» не особенно полезна.Конвейер будет обрабатывать несколько инструкций одновременно, и они будут конкурировать за различные ресурсы внутри ЦП - поэтому выполнение данной инструкции может быть понято только в контексте окружающих инструкций.И детали будут существенно различаться, даже в разных моделях семейства процессоров.

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

Для x86: взгляните на Agner Fog "Ресурсы для оптимизации программного обеспечения" .

Answer 2

Intel имеет некоторую информацию об их реализации сборки в своей базе данных статей.Хорошие из них довольно плотные (как этот 600-страничный PDF-файл), но у них есть много интересной информации, включая некоторые таблицы с приблизительным временем ожидания.Также есть таблица с некоторым временем ожидания для их 64-битной архитектуры , так что вы можете найти аналогичный 32-битный, если хотите.

У меня лично нетИдея о любой информации для процессоров AMD.Google может показать некоторые результаты, но я не пользуюсь машиной AMD с 3000 дней Athlon, поэтому у меня не было необходимости искать такую ​​информацию.

Answer 3

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

Answer 4

Из того, что я знаю:
вкл .: мин. O (1) макс. O (журнал n)
сложение, sub: O (журнал n)
mul, div: O (n)

malloc: O (n * m) n - выделенный размер, m - количество предыдущих выделений.
free: O (1) (иногда O (log m)).