Đo thời gian chính xác cao trong C

Question

Tôi đang cố gắng tìm ra cách để viết một số mã có thể xác định chính xác thời gian cần thiết để thực hiện tìm kiếm trên BST. Hiện tại, tôi đang sử dụng thời gian và tổng số phần tử là của đơn đặt hàng 10^5. Nó trông giống như sau: -

clock_t begin, end; 
begin = clock(); 
... 
... 
... 
end = clock(); 
difference = (end-begin)/CLOCKS_PER_SECOND; 

Tuy nhiên, điều này không cho tôi độ chính xác mà tôi đang tìm kiếm. Có bất kỳ chức năng libc khác mà tôi có thể sử dụng không?

Answer 1

BST? Bạn muốn loại chính xác nào? Phân chia bởi CLOCKS_PER_SECOND là 10^6 trên hệ thống 32 bit nên cung cấp độ chính xác 6 chữ số?

Bạn có bỏ tổng kết quả là gấp đôi không?

thử

difference = (double)(end-begin)/CLOCKS_PER_SECOND; 

Lưu ý sự khác biệt đó sẽ có thể tổ chức một đôi.

Answer 2

Để đánh giá thuật toán của bạn, bạn cần thực hiện một số lần lặp lại để vào phạm vi ít nhất hàng trăm mili giây. (Đây là thực hành tiêu chuẩn). Để đánh giá một thuật toán chỉ xảy ra trong không gian người dùng (không có luồng, cuộc gọi hệ thống, v.v.), bạn muốn sử dụng getrusage(RUSAGE_SELF, &r) và sử dụng giá trị r.ru_utime có chứa giây và micro giây.

Answer 3

Qt có QElapsedTimer hỗ trợ đo lên đến nano giây. Tôi không thể làm chứng cho nó chính xác như thế nào, IIRC nó sử dụng các triển khai khác nhau trên các nền tảng khác nhau. Đáng buồn thay, nó là C++, có thể không phù hợp với bạn. Ngoài ra:

Trên nền tảng không cung cấp độ phân giải nano giây, giá trị được trả về sẽ là ước tính tốt nhất có sẵn.

Chức năng clock() không sao cho các phép đo thô, nhưng nó hoạt động trong phạm vi mili giây. Trái với tên của nó, tôi không nghĩ rằng nó đo trong đồng hồ CPU, vì bộ xử lý hiện đại có thể thay đổi một chút, khiến cho việc xác định thời gian thực tế chỉ dựa vào đồng hồ CPU. IMO khái niệm này ngày trở lại những ngày khi tần số CPU được liên tục, không có quản lý năng lượng, không có "turbo boost" tự động ép xung hoặc bất cứ điều gì.

EDIT: Cũng thấy điều này (time.h):

int clock_gettime(clockid_t clk_id, struct timespec *tp); 

    ... and the target struct... 

    struct timespec { 
      time_t tv_sec;  /* seconds */ 
      long  tv_nsec;  /* nanoseconds */ 
    }; 

... and the clock options... 


CLOCK_REALTIME 
    System-wide realtime clock. Setting this clock requires appropriate privileges. 
CLOCK_MONOTONIC 
    Clock that cannot be set and represents monotonic time since some unspecified starting point. 
CLOCK_PROCESS_CPUTIME_ID 
    High-resolution per-process timer from the CPU. 
CLOCK_THREAD_CPUTIME_ID 
    Thread-specific CPU-time clock. 

Answer 4

Nếu thư viện của bạn hỗ trợ nó, C11 có timespec_get() đó sẽ đo lên đến nano giây, tùy thuộc vào độ phân giải hệ thống đồng hồ của bạn.

Answer 5

Điều bạn đang làm tương tự với những gì tôi đã làm gần đây.

Tôi nghĩ chức năng int gettimeofday(struct timeval *tv, struct timezone *tz); phù hợp với nhu cầu của bạn. Thông tin thời gian sẽ được đưa vào số struct timeval tv, thời gian sẽ tính bằng giây và micro giây.Các struct timeval từ trang người đàn ông:

struct timeval { 
       time_t  tv_sec;  /* seconds */ 
       suseconds_t tv_usec; /* microseconds */ 
}; 

Một ví dụ ngắn để đo thời gian với gettimeofday:

struct timeval time; 
if(gettimeofday(&time, 0)) return -1; 

long cur_time = 1000000 * time.tv_sec + time.tv_usec; 
double sec = cur_time/1000000.0; 

Một ví dụ nữa đã được đơn giản hóa và dễ dàng bao bọc như một C++ lớp để tiện sử dụng. Mã đã được đặt trên github của tôi: https://github.com/lulyon/LinuxTimeCounter, được sử dụng trong một dự án thế giới thực.

Answer 6

Nếu bạn đang chạy điểm chuẩn với CPU Intel. Có lẽ bạn có thể thử hướng dẫn RDTSC và RDTSCP.

here is a document about the instructions