Tại sao cuộc gọi chức năng mất quá nhiều thời gian?

Question

Tôi có sắp xếp chèn thực hiện thuật toán sau đây:

private static void InsertionSort(List<int> array) 
{ 
    for (int i = 1; i < array.Count; ++i) 
    { 
     for (int j = i; j > 0 && array[j - 1] > array[j]; --j) 
     { 
      //swap(array, j, j-1); 

      int temp = array[j]; 
      array[j] = array[j-1]; 
      array[j-1] = temp; 
     } 
    } 
} 

private static void swap(List<int> array, int i, int j) 
{ 
    int temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
} 

Khi tôi chạy thuật toán của tôi với swap(array, j, j-1); phải mất thời gian nhiều hơn nữa (2 giây cho 50000 phần tử) hơn nếu tôi làm chức năng cơ thể inline.

Tại sao?

Answer 1

Không phải là sai khi nội tuyến phương pháp thủ công, nó chỉ là không cần thiết. Nội tuyến các phương pháp nhỏ là một trong số standard optimizations được thực hiện bởi jitter. Điều đó không phải lúc nào cũng xảy ra, nhưng trên .NET 4.6.1 cả x86 và x64 jitters làm hoán đổi nội tuyến() trong mã mẫu này. Và hơn thế nữa, họ cũng bỏ vòng lặp bên trong để tạo ra hai lần hoán đổi mỗi lần vượt qua, loại lập trình tối ưu hóa bằng tay thường bỏ qua.

Đánh giá đúng cách ứng dụng .NET không phải lúc nào cũng thẳng thắn. Rất quan trọng để chạy Bản phát hành chương trình của bạn. Và để không hãy sử dụng trình gỡ lỗi. Mặc dù sau này là dễ dàng để sửa chữa, sử dụng Tools> Options> Debugging> General> untick tùy chọn "Suppress JIT optimization". Không có lý do chính đáng để bật nó trở lại.

Bây giờ bạn cũng có thể xem mã máy được tạo, đặt điểm ngắt trên Chèn() và khi lần truy cập sử dụng Gỡ lỗi> Windows> Gỡ cài đặt. Có xu hướng làm cho mắt người bị chảy máu nhưng rất dễ thấy rằng bạn nhận được hai lần hoán đổi nội tuyến(). Tôi sẽ phụ tùng bạn bãi chứa lắp ráp, chỉ cần có một cái nhìn xem. Và bạn nên thấy rõ sự khác biệt trong phép đo. Đây là những gì tôi nhận được:

Chạy nó 5 lần với swap() trên một danh sách với 50.000 số nguyên ngẫu nhiên trên x64:

00:00:05.4447216 
00:00:05.2928558 
00:00:05.6960587 
00:00:05.2835343 
00:00:05.2809591 

Cùng thử nghiệm nhưng bây giờ trao đổi() inlined bằng tay:

00:00:05.3015856 
00:00:05.2877402 
00:00:05.6369775 
00:00:05.2603384 
00:00:05.2616389 

Mất nhiều thời gian, như thường lệ.

Tôi sẽ thiếu sót nếu không hiển thị các kết quả tôi nhận được với List.Sort():

00:00:00.0075878 
00:00:00.0073398 
00:00:00.0076528 
00:00:00.0078046 
00:00:00.0066319