Tại sao LINQ có thể hoạt động nhanh hơn vòng lặp bình thường?

Question

Một người bạn và tôi hơi bối rối trong một cuộc thảo luận lập trình ngày hôm nay. Ví dụ, chúng tôi tạo ra một vấn đề hư cấu về việc có một số List<int> của n số nguyên ngẫu nhiên (thường là 1.000.000) và muốn tạo một hàm trả về tập hợp tất cả các số nguyên có nhiều hơn một số nguyên. Khá đơn giản. Chúng tôi đã tạo ra một câu lệnh LINQ để giải quyết vấn đề này và một thuật toán dựa trên sắp xếp đơn giản.

Bây giờ, khi chúng tôi kiểm tra tốc độ mã chạy tại (sử dụng System.Diagnostics.StopWatch), kết quả đã gây nhầm lẫn. Mã LINQ không chỉ hoạt động tốt hơn loại đơn giản, mà nó chạy nhanh hơn mộtforeach/for mà chỉ làm một vòng lặp trong danh sách và không có hoạt động nào bên trong (trình biên dịch được cho là khám phá và loại bỏ alltogether).

Nếu chúng tôi tạo List<int> số ngẫu nhiên mới trong cùng một lần thực thi chương trình và chạy lại mã LINQ, hiệu suất sẽ tăng theo thứ tự độ lớn (thường là nghìn lần). Hiệu suất của các vòng trống là tất nhiên giống nhau.

Vì vậy, những gì đang diễn ra ở đây? LINQ có sử dụng song song để làm tốt hơn các vòng bình thường không? Các kết quả này thậm chí có thể như thế nào? LINQ sử dụng quicksort chạy ở n * log (n), mà mỗi định nghĩa đã chậm hơn n.

Và điều gì đang xảy ra ở bước nhảy hiệu suất trong lần chạy thứ hai?

Cả hai chúng tôi đều bối rối và hấp dẫn với những kết quả này và hy vọng một số hiểu biết rõ ràng từ cộng đồng, chỉ để thỏa mãn sự tò mò của chính chúng ta.

Answer 1

Chắc chắn bạn chưa thực sự thực hiện truy vấn, bạn đã chỉ xác định nó. LINQ xây dựng một cây biểu thức mà không thực sự được đánh giá cho đến khi bạn thực hiện một thao tác yêu cầu đếm được lặp lại. Thử thêm hoạt động ToList() hoặc Count() vào truy vấn LINQ để buộc truy vấn được đánh giá.

Dựa trên nhận xét của bạn, tôi mong đợi điều này tương tự với những gì bạn đã làm. Lưu ý: Tôi đã không dành thời gian để tìm hiểu xem truy vấn có hiệu quả nhất có thể không; Tôi chỉ muốn một số truy vấn để minh họa cách mã có thể được cấu trúc.

var dataset = ... 

var watch = Stopwatch.StartNew(); 

var query = dataset.Where(d => dataset.Count(i => i == d) > 1); 

watch.Stop(); // timer stops here 

foreach (var item in query) // query is actually evaluated here 
{ 
    ... print out the item... 
} 

Answer 2

Tôi cho rằng LINQ chỉ nhanh hơn 'vòng lặp bình thường' khi thuật toán của bạn ít hơn hoàn hảo (hoặc bạn có một số vấn đề trong mã của mình). Vì vậy LINQ sẽ phân loại nhanh hơn bạn nếu bạn không viết một thuật toán phân loại hiệu quả, v.v.

LINQ thường 'nhanh như' hoặc 'đủ gần' tốc độ của vòng lặp bình thường và có thể nhanh hơn (và đơn giản hơn) để mã/gỡ lỗi/đọc. Đó là lợi ích của nó - không phải tốc độ thực thi.

Nếu nó hoạt động nhanh hơn vòng trống, bạn đang làm điều gì đó sai. Nhiều khả năng, như được đề xuất trong các nhận xét, bạn không xem xét việc thực hiện trì hoãn và câu lệnh LINQ không thực sự thực thi.

Answer 3

Nếu bạn không biên dịch bằng "Mã tối ưu hóa" được bật, có thể bạn sẽ thấy hành vi này. (Chắc chắn nó sẽ giải thích lý do tại sao vòng trống không bị loại bỏ.)

Mã LINQ, là một phần của mã đã biên dịch, chắc chắn đã được tối ưu hóa (bởi JIT, NGen hoặc tương tự).