Можно ли вычислить трудоёмкость процесса (программы)?

В общем случае - нет.

> В общем случае - нет.

А где почитать, почему это не возможно?
И что и как возможно с ограничениями?

Но в тоже время один совсем извращённый способ есть. Если запускать программу в виртуальной машине типа bosch то наверняка одинаковое число тактов получить таки удастся.. Но это слишком... Надо, чтобы оно запускалось на реальном процессоре.

Как считать число тактов процессора на операции ввода/вывода? А user в показаниях time должны быть близки.

> Как считать число тактов процессора на операции ввода/вывода?
Да хоть бы не считать вовсе. Это в моём случае не принципиально.

> А user в показаниях time должны быть близки.
Но не для разных процессоров.

Я не совсем понимаю, что вы хотите. Обычно пытаются измерить/оценить скорость процессора во ФлОпсах (операциях в секунду). Разные процессоры тратят разное количество тактов на одну и ту же операцию с числом...

> Я не совсем понимаю, что вы хотите. Обычно пытаются измерить/оценить скорость процессора во ФлОпсах (операциях в секунду). Разные процессоры тратят разное количество тактов на одну и ту же операцию с числом...

В том то и дело, чтобы оценить именно трудоёмкость задачи, а не скорость процессора. Можно и во ФлОпах (т.е. просто в числе операций).

Да там даже просто на ветвлениях в коде разное количество тактов будет получаться. Ни одну реальную задачу так посчитать нельзя. Тем более что даже кеш и скорость памяти внесёт свои коррективы...

А если представить что нужно получить какую-то сводку вроде
X операций типа INC;
Y операций типа ADD;
Z операций типа JMP; ?

Это я так понимаю не реально сделать без ужасных торомозов?

> А если представить что нужно получить какую-то сводку вроде

Ну для этого, в общем-то, и запускать бинарник не обязательно. Можно просто его проанализировать и полчучить. Такого софта не встречал готового, но, по идее, там достаточно тривиально всё.

И, опять же, как считать условия типа if(...){ много кода } else { мало кода }? Одной цифрой не обойдешься...

> Это я так понимаю не реально сделать без ужасных торомозов?

Ну, думаю, где-то на уровне bosch получится. Для него это должно быть не трудно.

> И, опять же, как считать условия типа if(...){ много кода } else { мало кода }? Одной цифрой не обойдешься...

Надо посчитать для конкретных входных данных. Поэтому считаемая ветвь в точности определена.

> Ну, думаю, где-то на уровне bosch получится. Для него это должно быть не трудно.

Да.. Сложно...

> Поэтому считаемая ветвь в точности определена.

Это если i/o или его-то подобного нет.

> Да.. Сложно...

Угу.

Это вам просто ассемблерный листинг программы обработать.

На современных процессорах время выполнения команд зависит от их порядка. А в многозадачной системе, где постоянно происходят прерывание, вытеснения данных из кеша процессора, перемещение страниц в своп и обратно время выполнения одной и тоже программы будет разным. Но это время можно осреднить, а секунды потом перевести в такты процессора (считая что тактовая частота не меняется на время работы программы).

Оценка трудоемкости программы для процессора звучит как то странно для меня. ИМХО, обычно оценивают трудоемкость алгоритма, если задача счетная. Вы скажите конечную цель такой оценки. Это курсовая работа или реальная задача?

> Это вам просто ассемблерный листинг программы обработать.

Нужно обработать на конкретных данных. А это уже, считай, виртуальную машину написать. Поэтому, отнюдь, не "просто".

> На современных процессорах время выполнения команд зависит от их порядка. А в многозадачной системе, где постоянно происходят прерывание, вытеснения данных из кеша процессора, перемещение страниц в своп и обратно время выполнения одной и тоже программы будет разным. Но это время можно осреднить, а секунды потом перевести в такты процессора (считая что тактовая частота не меняется на время работы программы).

Так вот и хочется узнать "сырую" трудоёмкость, считая, что никаких вытеснений и прочих прелестей нет впомине.
Другими словами нужно вычислить время выполнения программы на однопроцессорной машине с фиксированной частотой процессора в однозадачном режиме, если считать, что время ввода/вывода любых данных равно нулю.

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

Дизассемблировать, прописать, сколько тактов на каждую команду в столбик, суммировать :)

> Оценка трудоемкости программы для процессора звучит как то странно для меня. ИМХО, обычно оценивают трудоемкость алгоритма, если задача счетная. Вы скажите конечную цель такой оценки. Это курсовая работа или реальная задача?

Если честно, то это просто мысли в слух об идеальной системе.
В такой системе каждая программа, прежде чем выполнятся, должна знать сколько и каких ей требуется ресурсов (по крайней мере в ближайшее время).
Благодаря чему у системы появляется очень хорошая база для проведения очень эффективной раздачи этих ресурсов (установления приоритетов и т.д.)
Если это вообще возможно, то можно даже попробовать что-то частично реализовать.. Ведь, всем известно что короткие задачи должны получать бОльший приоритет. А в современных системах (по-крайней мере на рабочих столах) это не выполняется и не может быть выполнено в принципе, так как изначально ничего с таким расчётом не писалось..

> Дизассемблировать, прописать, сколько тактов на каждую команду в столбик, суммировать :)

Таки это жестоко :-)
Потому как в идеале ещё нужно иметь возможность получить эту статистику в произвольном месте _выполняющейся программы_.
Подобно тому, как get_rusage() может быть вызван в произвольном месте программы.

> Потому как в идеале ещё нужно иметь возможность получить эту статистику в произвольном месте _выполняющейся программы_.

Ну тогда, пожалуй, только виртуалку велосипедить. Тот же Bosch допилить... Существующих решений имхо нет в виду повышенной странности задачи :)

Хорошо, всем спасибо!
Думаю, что совсем точно трудоёмкость всё же мне не так важна.
А приближённо можно будет делать так:
1) Написать некую тестовую программу, в которой будет среднестатистическое соотношение самых распространённых инструкций процессора.
2) Принять время её выполнения T (верней сумму пользовательского и системного времени затребованного процессом) за N=1/10/100/1000 попугаев.
3) Мерить getrusage'м время затраченное процессором на выполнение тестируемой программы R.
4) По формуле R/T*N получаем примерную трудоёмкость процесса в попугаях.

Если ошибка при этом будет не на порядки, то меня вполне устроит :-)

> А если представить что нужно получить какую-то сводку вроде
> X операций типа INC;
> Y операций типа ADD;
> Z операций типа JMP; ?

Погонять программу на тесте + профайлер?

А если
if [ "$((RANDOM % 3))" == "1" ]
?

> А если
> if [ "$((RANDOM % 3))" == "1" ]
> ?

:-) Значит посчитать конкретный запуск!