Cách so sánh hiệu suất của hai phần mã số

Question

Tôi có một cuộc cạnh tranh thân thiện với vài người trong lĩnh vực lập trình và gần đây chúng tôi đã trở nên rất quan tâm đến việc viết mã hiệu quả. Thách thức của chúng tôi là cố gắng tối ưu hóa mã (theo thời gian và độ phức tạp của CPU) với bất kỳ chi phí nào (khả năng đọc, khả năng sử dụng lại, v.v ...).

Vấn đề là, bây giờ chúng ta cần phải so sánh các mã của chúng tôi và xem cách tiếp cận nào tốt hơn so với các mã khác nhưng chúng tôi không biết bất kỳ công cụ nào cho mục đích này.

Câu hỏi của tôi là, đang có một số (bất kỳ!) Công cụ mà sẽ đưa một đoạn mã như là đầu vào và tính toán số lượng thất bại hoặc hướng dẫn cpu cần thiết để chạy nó? Có công cụ nào có thể đo lường mức độ tối ưu của mã không?

T.B. Ngôn ngữ đích là C++ nhưng sẽ rất hay khi biết các công cụ như vậy có tồn tại với java hay không.

Answer 1

Dưới đây là một chút C++ 11 đồng hồ bấm giờ tôi muốn tung ra khi tôi cần thời gian một cái gì đó:

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

Cách sử dụng:

stopwatch sw; 
sw.tick(); 

run_long_code(); 

sw.tock(); 
std::cout << "This took " << sw.report_ms() << "ms.\n"; 

Trên bất kỳ thực hiện phong nha, mặc định high_resolution_clock nên cung cấp thông tin thời gian rất chính xác.

Answer 2

Thật khó để tính toán số chi tiết thời gian CPU từ một khối mã. Cách thông thường để thực hiện điều này là thiết kế dữ liệu đầu vào tồi tệ hơn/trung bình/tốt nhất làm trường hợp kiểm tra. Và thực hiện định thời gian dựa trên mã thực của bạn với các trường hợp kiểm tra này. Không có công cụ nào có thể cho bạn biết thất bại khi nó không có dữ liệu và điều kiện kiểm tra đầu vào chi tiết.

Answer 3

Có chức năng std::clock() từ <ctime> trả về lượng thời gian CPU được sử dụng cho quy trình hiện tại (có nghĩa là nó không tính thời gian chương trình đang chạy không tải vì CPU đang thực hiện các tác vụ khác). Hàm này có thể được sử dụng để đo chính xác thời gian thực thi của các thuật toán. Sử dụng hằng số std::CLOCKS_PER_SEC (cũng từ <ctime>) để chuyển đổi giá trị trả về thành giây.

Answer 4

Có một số phần mềm được gọi là profilers chính xác là những gì bạn muốn.

Ví dụ cho Windows là AMD code analyser và gprof cho POSIX.

Answer 5

Tốt nhất cho mục đích của bạn là valgrind/callgrind

Answer 6

Đo số lượng lệnh CPU là khá vô ích.

Hiệu suất liên quan đến nút cổ chai, tùy thuộc vào sự cố trong tầm tay, nút cổ chai có thể là mạng, ổ đĩa IO, bộ nhớ hoặc CPU.

Đối với một cuộc thi thân thiện, tôi sẽ đề xuất thời gian. Điều đó ngụ ý cung cấp các trường hợp thử nghiệm đủ lớn để có các biện pháp có ý nghĩa, tất nhiên.

Trên Unix, bạn có thể sử dụng gettimeofday để có các biện pháp tương đối chính xác.

Answer 7

Từ lắp ráp nội tuyến, bạn có thể sử dụng lệnh rdtsc để nhận bộ đếm 32 bit (phần quan trọng nhất) vào eax và 32 bit (phần quan trọng nhất) tới edx. Nếu mã của bạn quá nhỏ, bạn có thể kiểm tra toàn bộ các chu kỳ CPU tương thích chỉ với đăng ký eax. Nếu số đếm lớn hơn số tối đa. giá trị 32 bit, số gia tăng edx cho mỗi chu kỳ giá trị tối đa 32 bit.

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(); 

Đầu ra: 74000 chu kỳ CPU cho 1000 lần lặp và 800000 chu kỳ CPU cho 10000 lần lặp trên máy của tôi. Bởi vì clock() tốn nhiều thời gian.

Độ phân giải chu kỳ CPU trên máy của tôi: ~ 1000 chu kỳ. Có, bạn cần nhiều hơn hàng ngàn phép cộng/trừ (hướng dẫn nhanh) để đo lường nó tương đối chính xác.

Giả sử tần số làm việc cpu không đổi, 1000 chu kỳ CPU gần bằng 1 micro giây cho CPU 1GHz. Bạn nên làm ấm cpu của bạn lên trước khi làm điều này.