У меня есть дружеское соревнование с парой парней в области программирования, и в последнее время мы так заинтересовались написанием эффективного кода. Наша задача состояла в том, чтобы попытаться оптимизировать код (в смысле времени и сложности процессора) любой ценой (читаемость, возможность повторного использования и т. Д.).
Проблема в том, что теперь нам нужно сравнить наши коды и посмотреть, какой подход лучше по сравнению с другими, но мы не знаем никаких инструментов для этой цели.
Мой вопрос, есть ли (какие-нибудь!) Инструменты, которые занимают кусок кода
в качестве входных данных и рассчитывает количество команд на флопе или процессоре
необходимо для запуска? Есть ли какой-нибудь инструмент, способный измерить оптимальность
кода?
Постскриптум Целевым языком является c ++, но было бы неплохо узнать, существуют ли такие инструменты и для Java.
Вот небольшой секундомер C ++ 11, который я хотел бы развернуть, когда мне нужно что-то рассчитать:
#include <chrono>
#include <ctime>
template <typename T> class basic_stopwatch
{
typedef T clock;
typename clock::time_point p;
typename clock::duration d;
public:
void tick() { p = clock::now(); }
void tock() { d += clock::now() - p; }
void reset() { d = clock::duration::zero(); }
template <typename S> unsigned long long int report() const
{
return std::chrono::duration_cast<S>(d).count();
}
unsigned long long int report_ms() const
{
return report<std::chrono::milliseconds>();
}
basic_stopwatch() : p(), d() { }
};
struct c_clock
{
typedef std::clock_t time_point;
typedef std::clock_t duration;
static time_point now() { return std::clock(); }
};
template <> unsigned long long int basic_stopwatch<c_clock>::report_ms() const
{
return 1000. * double(d) / double(CLOCKS_PER_SEC);
}
typedef basic_stopwatch<std::chrono::high_resolution_clock> stopwatch;
typedef basic_stopwatch<c_clock> cstopwatch;
Использование:
stopwatch sw;
sw.tick();
run_long_code();
sw.tock();
std::cout << "This took " << sw.report_ms() << "ms.\n";
На любой достойной реализации, по умолчанию high_resolution_clock
должен дать очень точную информацию о времени.
Здесь std::clock()
функция от <ctime>
который возвращает, сколько процессорного времени было потрачено на текущий процесс (это означает, что он не считает время, в течение которого программа простаивала, потому что процессор выполнял другие задачи). Эта функция может использоваться для точного измерения времени выполнения алгоритмов. Используйте константу std::CLOCKS_PER_SEC
(также из <ctime>
) чтобы преобразовать возвращаемое значение в секунды.
Из встроенной сборки вы можете использовать команду rdtsc, чтобы получить 32-битный (наименее значимая часть) счетчик в eax и 32-битный (старшая значащая часть) в edx. Если ваш код слишком мал, вы можете проверить общие циклы ЦП с помощью только регистра eax. Если количество больше макс. 32-разрядного значения, приращения edx в цикле max-32-разрядного значения.
int cpu_clk1a=0;
int cpu_clk1b=0;
int cpu_clk2a=0;
int cpu_clk2b=0;
int max=0;
std::cin>>max; //loop limit
__asm
{
push eax
push edx
rdtsc //gets current cpu-clock-counter into eax&edx
mov [cpu_clk1a],eax
mov [cpu_clk1b],edx
pop edx
pop eax
}
long temp=0;
for(int i=0;i<max;i++)
{
temp+=clock();//needed to defy optimization to actually measure something
//even the smartest compiler cannot know what
//the clock would be
}
__asm
{
push eax
push edx
rdtsc //gets current cpu-clock-counter into aex&edx
mov [cpu_clk2a],eax
mov [cpu_clk2b],edx
pop edx
pop eax
}
std::cout<<(cpu_clk2a-cpu_clk1a)<<std::endl;
//if your loop takes more than ~2billions of cpu-clocks, use cpu_clk1b and 2b
getchar();
getchar();
Вывод: 74000 циклов процессора для 1000 итераций и 800000 циклов процессора для 10000 итераций на моей машине. Потому что часы () занимают много времени.
Разрешение цикла процессора на моей машине: ~ 1000 циклов. Да, вам нужно более нескольких тысяч сложений / вычитаний (быстрых инструкций), чтобы измерить это относительно правильно.
Предполагая, что рабочая частота процессора постоянна, 1000 тактов процессора почти равны 1 микросекунде для процессора 1 ГГц. Вы должны разогреть свой процессор, прежде чем делать это.
Довольно сложно рассчитать количество детализации времени процессора из блока кода.
Обычный способ сделать это — создать худшие / средние / лучшие входные данные в качестве контрольных примеров. И сделайте профилирование времени на основе вашего реального кода с этими тестовыми примерами. Ни один инструмент не может сказать вам флопы, когда он находится без подробных входных тестовых данных и условий.
Есть части программного обеспечения под названием профайлеры который точно делает то, что вы хотите.
Пример для Windows AMD анализатор кода а также дргоЕ для POSIX.
Измерять количество инструкций процессора довольно бесполезно.
Производительность зависит от узкого места, в зависимости от имеющейся проблемы узким местом может быть сеть, дисковые операции ввода-вывода, память или процессор.
Для просто дружеского соревнования я бы предложил время. Что подразумевает предоставление тестовых случаев, которые достаточно велики, чтобы иметь значимые меры, конечно.
В Unix вы можете использовать gettimeofday
для относительно точных мер.
Лучше всего для ваших целей Valgrind / callgrind