Измерить быстродействие алгоритма

← →
SpellCaster (2007-04-19 11:00) [0]

Подскажите, чем можно замерить быстродействие куска программы? Моя софтина стала отжирать около 90% процессора, хочу посмотреть, где именно находится слабое место.

← →
Reindeer Moss Eater © (2007-04-19 11:15) [1]

не вижу связи между быстродействием, загрузкой проца и слабым местом

← →
Desdechado © (2007-04-19 11:26) [2]

гуглить profiler

← →
Jeer © (2007-04-19 12:04) [3]

SpellCaster (19.04.07 11:00)

Вот это
while True do;
загрузит твой процессор на все сто.
Найди здесь слабое место в алгоритме.

← →
SpellCaster (2007-04-19 13:00) [4]

Возможно, я неверно выразился. Забудем про загрузку, нужно просто быстродействие.
Desdechado, благодарю, поищу.
Jeer, очень смешно.

← →
{RASkov} (2007-04-19 13:24) [5]

N:=GetTickCount;
....
<msek>:=GetTickCount-N;

← →
SpellCaster (2007-04-19 15:34) [6]

{RASkov}, мне тоже этот способ первым пришел в голову, но хочется более продвинутое решение.

← →
Jeer © (2007-04-19 15:54) [7]

Измерять тики через rdtsc

function GetCPUTicksP_:int64;
// 88 ticks
asm
dw 310Fh // rdtsc
end;

← →
Kolan © (2007-04-19 16:02) [8]

> Моя софтина стала отжирать около 90% процессора

поток + sleep ему делай иногда&#133

← →
SpellCaster (2007-04-19 16:09) [9]

Нашел ProDelphi профайлер, если не выйдет с тиками, попробую разобраться...

← →
{RASkov} (2007-04-19 16:16) [10]

> [7] Jeer © (19.04.07 15:54)
function GetCPUTicksP_:int64;

А что эта функция возвращает? Судя по названию Tickи - зависит от частоты процессора?

← →
Jeer © (2007-04-19 16:36) [11]

http://ru.wikipedia.org/wiki/Rdtsc

← →
{RASkov} (2007-04-19 16:52) [12]

читающая счётчик TSC (Time Stamp Counter) и возвращающая в регистрах EDX:EAX 64-битное количество тактов с момента последнего сброса процессора
rdtsc чаще всего используется:
для точного измерения временных интервалов;
Чет я так и не понял что вернет функция, т.е. понятно что - TSC, но на разных процах поразному вроде должно быть
N:=GetCPUTicksP_;
...
X:=GetCPUTicksP_-N;
так в чем же этот временный интервал измеряется, т.е. в тиках, но как из них узнать сколько по времени выполняется на одном проце и сколько на другом один и тотже код.? Чет тупю :)

← →
homm © (2007-04-19 17:02) [13]

> как из них узнать сколько по времени выполняется на одном
> проце и сколько на другом один и тотже код.?

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

← →
{RASkov} (2007-04-19 17:07) [14]

> Чем меньше получится тиков для твоего алгоритма, тем лучше.

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

← →
Jeer © (2007-04-19 17:15) [15]

На TSC подается частота процессора, отсюда и считай.
dT = 1/ Fcpu
При Fcpu = 2 GHz, dT = 0.5 ns

Только особых иллюзий не стоит строить.
- Latency time составляет 60-90 ticks
- при использовании технологии снижения мощности частота уплывет
- временная стабильность кварцев примерно 10^-5

Это [7] простейший и не совсем точный метод.
О более правильном читать мануалы от Intel

← →
Jeer © (2007-04-19 17:19) [16]

> {RASkov} (19.04.07 17:07) [14]

Один и тот же алгоритм на процах с разными частотами затратит одно и то же число ticks, что говорит об абсолютности измерения быстродействия (эффективности) алгоритма.

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

← →
{RASkov} (2007-04-19 17:20) [17]

> [15] Jeer © (19.04.07 17:15)

Доходчиво. Спасибо.

← →
{RASkov} (2007-04-19 17:26) [18]

> Один и тот же алгоритм на процах с разными частотами затратит
> одно и то же число ticks

На одном и том же проце по разному, не то что-б на разных процах :(

var N: Int64; K: Byte;
begin
N:=GetCPUTicksP_;
for K := 0 to 255 do Caption:=IntToStr(K);
ShowMessage(IntToStr(GetCPUTicksP_-N));
end;

← →
{RASkov} (2007-04-19 17:30) [19]

Кстати, вот этот код:
var N: Int64; K: Byte; begin N:=GetCPUTicksP_; ShowMessage(IntToStr(GetCPUTicksP_-N)); end;
на моем практически всегда возвращает - 20, пару раз было 19;

> На одном и том же проце по разному, не то что-б на разных
> процах :(

Многозадачность.... блин.

> Многозадачность.... блин.

Ну а что же ты хотел.

Для измерений с минимизацией погрешности от многозадачности:

- на время измерений повысить приоритет до RealTime
- измерять относительные интервалы не более slice для конкретной операционки
- использовать рекомендации от Интел по вызову rdtsc

← →
{RASkov} (2007-04-19 18:17) [21]

> Ну а что же ты хотел.

Да нет, просто никода этим не занимался, ....надобности не было, да и думаю и не будет... См [17] :)

← →
{RASkov} (2007-04-19 18:18) [22]

> никода

*никогда.
Дерёвня... блин. :)

Как скажешь:)

← →
Sapersky (2007-04-19 20:35) [24]

Один и тот же алгоритм на процах с разными частотами затратит одно и то же число ticks, что говорит об абсолютности измерения быстродействия (эффективности) алгоритма.

А на процах с разной архитектурой?
И главное, зачем эта "абсолютность"? Практически при оптимизации приходится сравнивать результаты лучшего/худшего алгоритмов на одной машине.

По средствам измерения: есть ещё QueryPerformanceCounter. В хелпе написано, что это некий high-resolution performance counter. Может быть, просто обёртка для rdtsc (судя по тому, что зависит от частоты).

Использовать, например, так (результат в мс/мкс):

Var
PCTime1, PCTime2, PCFreq : Int64;
PCEnabled : Boolean;

procedure QueryPerformanceCounter(Var Cnt : Int64);
Var Thread, OldMask : DWord;
begin
// force the thread to CPU 0 for multi-core CPU
Thread := GetCurrentThread; OldMask := SetThreadAffinityMask(Thread, 1);

// update counter frequency for CPUs with variable clock rate (Athlon64, Pentium M)
QueryPerformanceFrequency(PCFreq);
PCEnabled := (PCFreq <> 0);
Windows.QueryPerformanceCounter(Cnt);

// restore threads
SetThreadAffinityMask(Thread, OldMask)
end;

procedure TimeReset;
begin
QueryPerformanceCounter(PCTime1);
end;

function TimeMs: Integer;
begin
If PCEnabled then begin
QueryPerformanceCounter(PCTime2);
Result:=( (PCTime2-PCTime1) * 1000 ) div PCFreq;
PCTime1:=PCTime2;
end else Result:=0;
end;

function TimeMks: Integer;
begin
If PCEnabled then begin
QueryPerformanceCounter(PCTime2);
Result:=( (PCTime2-PCTime1) * 1000000 ) div PCFreq;
PCTime1:=PCTime2;
end else Result:=0;
end;

Sapersky (19.04.07 20:35) [24]

> А на процах с разной архитектурой?

Меня кормить манкой не надо, родной.

> По средствам измерения: есть ещё QueryPerformanceCounter.
> В хелпе написано, что это некий high-resolution performance
> counter. Может быть, просто обёртка для rdtsc (судя по тому,
> что зависит от частоты).

Сие изложенное Вами означает, что Вы не в "курсе".

QP timer еще худшее средство измерения интервалов, чем TSC.

Основные проблемы с QP и TSC в общем-то уже понятны квалифицированному народу.
Для QP даже публикуется список платформ на которых возникают проблемы с измерениями и список возглавляют отнюдь не аутсайдеры.

Во первых, QP просто хуже по дискретности, чем TSC.
Во-вторых и это главное:
- подвержен прыжкам, о чем есть KB Q274323 от мелких;
- есть проблема чтения частично измененного состояния в случае racing condition;

Основная проблема же с TSC отнюдь не мультизадачность.
- проблема "размазывания" частоты (Frequency spreading) для соблюдения стандарта по фону излучения;
- наличие фич "power save" (SpeedStep и аналоги);
- на SMP-системах для разных процессоров timing-и отличаются, а значит только QPC-системы, а для HT-систем вообще пока не все понятно;
- проблема конвейера (весьма часто приводит к измерению не тикс выполнения, а тикс декодирования, что, как понятно, совсем "немного" другое)

> И главное, зачем эта "абсолютность"? Практически при оптимизации
> приходится сравнивать результаты лучшего/худшего алгоритмов
> на одной машине.

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

> [24] Sapersky (19.04.07 20:35)
> И главное, зачем эта "абсолютность"? Практически при оптимизации
> приходится сравнивать результаты лучшего/худшего алгоритмов
> на одной машине.

СРАВНИВАЙ! Кто мешает то? В абсолютных значениях производительности (число тиков), это куда проше чем в относительных (времени).

Измерить быстродействие алгоритма Найти похожие ветки