Làm cách nào để tối ưu hóa từ "hàm thuần túy" trong C#?

Question

Nếu tôi có chức năng sau, nó được coi là tinh khiết ở chỗ nó không có tác dụng phụ và sẽ luôn tạo ra cùng một kết quả cho cùng một đầu vào x.

public static int AddOne(int x) { return x + 1; } 

Như tôi đã hiểu, nếu thời gian chạy hiểu được độ tinh khiết chức năng, nó có thể tối ưu hóa việc thực hiện để không phải tính lại giá trị trả lại.

Có cách nào để đạt được loại tối ưu hóa thời gian chạy này trong C# không? Và tôi cho rằng có một cái tên cho loại tối ưu hóa này. Nó được gọi là gì?

Chỉnh sửa: Rõ ràng, chức năng mẫu của tôi sẽ không có nhiều lợi ích từ loại tối ưu hóa này. Ví dụ này được đưa ra để thể hiện loại thuần khiết mà tôi có trong tâm trí chứ không phải là ví dụ thực tế.

Answer 1

Như những người khác đã lưu ý, nếu bạn muốn tiết kiệm chi phí tính toán lại kết quả mà bạn đã tính toán, thì bạn có thể ghi nhớ hàm. Giao dịch này tăng mức sử dụng bộ nhớ cho tốc độ tăng - hãy nhớ xóa bộ nhớ cache của bạn đôi khi nếu bạn nghi ngờ rằng bạn có thể hết bộ nhớ thì bộ nhớ cache sẽ phát triển mà không bị ràng buộc.

Tuy nhiên, có một số tối ưu hóa khác mà người ta có thể thực hiện trên các hàm thuần túy hơn là ghi nhớ kết quả của chúng. Ví dụ, các hàm thuần túy, không có tác dụng phụ, thường an toàn để gọi các chủ đề khác. Các thuật toán sử dụng rất nhiều hàm thuần túy thường có thể được song song để tận dụng nhiều lõi.

Khu vực này sẽ ngày càng trở nên quan trọng vì các máy đa lõi ồ ạt trở nên ít tốn kém và phổ biến hơn. Chúng tôi có một mục tiêu nghiên cứu dài hạn cho ngôn ngữ C# để tìm ra cách nào đó để tận dụng sức mạnh của các chức năng thuần túy (và các hàm "không phân biệt") trong ngôn ngữ, trình biên dịch và thời gian chạy. Nhưng làm như vậy liên quan đến nhiều vấn đề khó khăn, các vấn đề về việc có ít sự đồng thuận trong công nghiệp hay học viện là cách tiếp cận tốt nhất.Đầu óc đang suy nghĩ về nó, nhưng không mong đợi bất kỳ kết quả chính nào sớm.

Answer 2

Điều này có lẽ sẽ được inlined (aka inline expansion) bởi trình biên dịch ...

Chỉ cần chắc chắn bạn biên dịch mã của bạn với "Tối ưu hóa Code" cờ thiết lập (trong VS: tính chất dự án/xây dựng tab/Optimize Mã)

---

Điều khác bạn có thể làm là lưu vào bộ nhớ cache kết quả (aka memoization). Tuy nhiên, có một hit hiệu suất ban đầu rất lớn do logic tra cứu của bạn, do đó, điều này là thú vị chỉ cho các chức năng chậm (tức là không phải là một bổ sung int).

Ngoài ra còn có tác động bộ nhớ, nhưng điều này có thể được quản lý thông qua việc sử dụng thông minh weak references.

---

Theo tôi được biết, nếu thời gian chạy hiểu được độ tinh khiết chức năng nó thể tối ưu hóa thực hiện để giá trị trả về sẽ không phải tính lại.

Trong ví dụ của bạn, thời gian chạy S W phải tính kết quả, trừ khi x được biết đến lúc biên dịch. Trong trường hợp đó, mã của bạn sẽ được tối ưu hóa thêm thông qua việc sử dụng constant folding

Answer 3

nếu tính toán là tốn kém, bạn có thể bộ nhớ cache kết quả trong từ điển?

static Dictionary<int, int> cache = new Dictionary<int, int>(); 
    public static int AddOne(int x) 
    { 
     int result; 
     if(!cache.TryGetValue(x, out result)) 
     { 
      result = x + 1; 
      cache[x] = result; 
     } 
     return result; 
    } 

tất nhiên, tra cứu từ điển trong trường hợp này là tốn kém hơn add :)

Có một cách khác mát nhiều việc phải làm memoization chức năng giải thích của Wes Dyer ở đây: http://blogs.msdn.com/wesdyer/archive/2007/01/26/function-memoization.aspx - nếu bạn làm một lot của bộ nhớ đệm này, sau đó chức năng Memoize mình có thể giúp bạn tiết kiệm rất nhiều mã ...

Answer 4

tôi nghĩ rằng bạn đang tìm kiếm functional memoization

Answer 5

một trình biên dịch có thể tối ưu hóa chức năng này thông qua một sự kết hợp của nội tuyến (thay thế cuộc gọi hàm với nội dung của chức năng đó tại trang gọi) và tuyên truyền liên tục (thay thế một biểu thức không có biến miễn phí với kết quả của biểu thức đó).Ví dụ, trong chút mã này:

AddOne(5); 

AddOne thể được inlined:

5 + 1; 

tuyên truyền liên tục sau đó có thể đơn giản hóa biểu thức:

6; 

(Chết loại bỏ đang thể sau đó đơn giản hóa biểu thức này hơn nữa, nhưng đây chỉ là một ví dụ).

Biết rằng AddOne() không có tác dụng phụ cũng có thể cho phép một trình biên dịch để thực hiện loại bỏ subexpression chung, do đó:

AddOne(3) + AddOne(3) 

có thể được chuyển thành:

int x = AddOne(3); 
x + x; 

hoặc bằng giảm sức mạnh, ngay cả:

2*AddOne(3); 

Không có cách nào để lệnh trình biên dịch C# JIT thực hiện các tối ưu hóa này; nó tối ưu theo quyết định riêng của mình. Nhưng nó khá thông minh, và bạn sẽ cảm thấy thoải mái dựa vào nó để thực hiện các loại biến đổi này mà không cần sự can thiệp của bạn.

Answer 6

Kỹ thuật bạn đang theo dõi là ghi nhớ: lưu vào bộ nhớ cache kết quả thực thi, khóa các đối số được truyền vào hàm, trong mảng hoặc từ điển. Runtimes không có xu hướng áp dụng nó tự động, mặc dù chắc chắn có trường hợp mà họ sẽ. Cả C# lẫn .NET đều không tự động ghi nhớ. Bạn có thể thực hiện ghi nhớ chính mình - nó khá dễ dàng - nhưng làm như vậy thường chỉ hữu ích cho các chức năng thuần túy chậm hơn, nơi bạn có xu hướng lặp lại các phép tính và nơi bạn có đủ bộ nhớ.

Answer 7

Trình biên dịch có thể làm như thế nào? Làm cách nào để biết giá trị của x sẽ được truyền vào lúc chạy?

và lại: các câu trả lời khác đề cập đến nội tuyến ... Hiểu biết của tôi là nội tuyến (như tối ưu hóa) được bảo hành cho các chức năng nhỏ chỉ được sử dụng một lần (hoặc chỉ một vài lần ...) không phải vì chúng không có tác dụng phụ ...

Answer 8

Một tùy chọn khác là sử dụng plugin fody https://github.com/Dresel/MethodCache bạn có thể trang trí các phương thức cần lưu trong bộ nhớ cache. Khi sử dụng điều này bạn nên tất nhiên xem xét tất cả các ý kiến ​​được đề cập trong các câu trả lời khác.