Bạn có thể nhớ cache tra cứu chức năng ảo trong C++ không?

Question

Giả sử tôi có hàm foo() trên một con trỏ lớp cơ sở trừu tượng, mypointer-> foo(). Khi ứng dụng của tôi khởi động, dựa trên nội dung của một tệp, nó chọn khởi tạo một lớp cụ thể cụ thể và gán mypointer cho cá thể đó. Đối với phần còn lại của cuộc đời ứng dụng, con trỏ của tôi sẽ luôn là trỏ đến các đối tượng thuộc loại cụ thể đó. Tôi không có cách nào để biết loại bê tông này là gì (nó có thể được khởi tạo bởi một nhà máy trong thư viện được nạp động). Tôi chỉ biết rằng loại hình này sẽ giữ nguyên sau khi lần đầu tiên một thể hiện của loại bê tông được tạo ra. Con trỏ có thể không phải lúc nào cũng trỏ đến cùng một đối tượng, nhưng đối tượng sẽ luôn luôn có cùng loại bê tông. Lưu ý rằng loại được xác định về mặt kỹ thuật tại 'thời gian chạy' bởi vì nó dựa trên nội dung của một tệp, nhưng sau khi 'khởi động' (tệp được tải) loại được cố định.

Tuy nhiên, trong C++ tôi trả chi phí tra cứu chức năng ảo mỗi lần foo được gọi cho toàn bộ thời lượng của ứng dụng. Trình biên dịch không thể tối ưu hóa việc tìm kiếm vì không có cách nào để biết rằng loại bê tông sẽ không thay đổi theo thời gian chạy (ngay cả khi nó là trình biên dịch tuyệt vời nhất, nó không thể suy đoán về hành vi được nạp động thư viện). Trong một ngôn ngữ được biên dịch JIT như Java hoặc .NET, JIT có thể phát hiện rằng cùng một kiểu được sử dụng lặp đi lặp lại và làm inline cacheing. Tôi về cơ bản đang tìm kiếm một cách để tự làm điều đó cho con trỏ cụ thể trong C + +.

Có cách nào trong C++ để lưu bộ nhớ cache tra cứu này không? Tôi nhận ra rằng các giải pháp có thể khá đáng sợ. Tôi sẵn sàng chấp nhận các hacks cụ thể của ABI/trình biên dịch nếu có thể viết các bài kiểm tra cấu hình để khám phá các khía cạnh liên quan của ABI/trình biên dịch để nó "thực tế di động" ngay cả khi không thực sự di động.

Cập nhật: Đối với người trả lời: Nếu điều này không đáng được tối ưu hóa, thì tôi nghi ngờ JIT hiện đại sẽ làm điều đó. Bạn có nghĩ rằng các kỹ sư của Sun và MS đã lãng phí thời gian của họ trong việc triển khai bộ đệm ẩn nội tuyến và không đánh giá nó để đảm bảo có cải thiện không?

Answer 1

Vì vậy, giả định rằng đây là một vấn đề cơ bản mà bạn muốn giải quyết (để tránh tranh luận tối ưu hóa sớm), và bỏ qua nền tảng và hackery cụ biên dịch, bạn có thể làm một trong hai điều, ở hai đầu đối diện của phức tạp:

1. Cung cấp chức năng như một phần của .dll mà nội bộ chỉ đơn giản gọi trực tiếp chức năng thành viên phù hợp. Bạn trả chi phí của một bước nhảy gián tiếp, nhưng ít nhất bạn không phải trả chi phí của một tra cứu vtable. Số dặm của bạn có thể thay đổi, nhưng trên một số nền tảng nhất định, bạn có thể tối ưu hóa cuộc gọi hàm gián tiếp.
2. Tái cơ cấu ứng dụng của bạn sao cho thay vì gọi hàm thành viên cho mỗi trường hợp, bạn gọi một hàm duy nhất có tập hợp các phiên bản. Mike Acton có một tuyệt vời post (với một nền tảng cụ thể và loại ứng dụng cong) về lý do tại sao và làm thế nào bạn nên làm điều này.

Answer 2

Có hai chi phí cho cuộc gọi hàm ảo: Tra cứu vtable và cuộc gọi hàm.

Tra cứu vtable đã được phần cứng xử lý. CPU hiện đại (giả sử bạn không làm việc trên một CPU nhúng rất đơn giản) sẽ dự đoán địa chỉ của hàm ảo trong bộ dự đoán nhánh của chúng và thực thi nó theo cách song song với tra cứu mảng. Thực tế là tra cứu vtable xảy ra song song với việc thực thi đầu tiên của hàm có nghĩa là, khi được thực hiện trong một vòng lặp trong các tình huống bạn mô tả, các cuộc gọi hàm ảo có bên cạnh số không trên không so với các cuộc gọi hàm trực tiếp, không được nội tuyến.

Tôi đã thực sự thử nghiệm điều này trong quá khứ, mặc dù trong ngôn ngữ lập trình D, chứ không phải C++.Khi nội tuyến bị vô hiệu hóa trong các thiết lập trình biên dịch và tôi gọi hàm giống nhau trong một vòng lặp vài triệu lần, thời gian nằm trong epsilon của nhau cho dù hàm đó có ảo hay không.

Chi phí thứ hai và quan trọng hơn của các chức năng ảo là chúng ngăn cản nội tuyến của hàm trong hầu hết các trường hợp. Điều này thậm chí còn quan trọng hơn âm thanh bởi vì nội tuyến là một tối ưu hóa có thể cho phép một số tối ưu hóa khác như xếp liên tục trong một số trường hợp. Không có cách nào để inline một hàm mà không biên dịch lại mã. JIT có được xung quanh điều này bởi vì họ liên tục biên dịch lại mã trong khi thực hiện ứng dụng của bạn.

Answer 3

Tôi đã thấy các tình huống tránh cuộc gọi chức năng ảo có lợi. Điều này không nhìn tôi là một trong những trường hợp đó bởi vì bạn thực sự đang sử dụng hàm đa hình. Bạn chỉ đang theo đuổi thêm một hướng địa chỉ, không phải là một cú đánh lớn, và một thứ có thể được tối ưu hóa một phần trong một số trường hợp. Nếu nó thực sự quan trọng, bạn có thể muốn cấu trúc lại mã của bạn để các lựa chọn phụ thuộc kiểu như các cuộc gọi hàm ảo được thực hiện ít lần hơn, được kéo ra ngoài vòng lặp.

Nếu bạn thực sự nghĩ rằng nó đáng để tạo ảnh, bạn có thể đặt con trỏ hàm riêng biệt thành hàm không phải ảo cụ thể cho lớp. Tôi có thể (nhưng có thể sẽ không) xem xét thực hiện theo cách này.

class MyConcrete : public MyBase 
{ 
public: 
    static void foo_nonvirtual(MyBase* obj); 
    virtual void foo() 
    { foo_nonvirtual(this); } 
}; 

void (*f_ptr)(MyBase* obj) = &MyConcrete::foo_nonvirtual; 
// Call f_ptr instead of obj->foo() in your code. 
// Still not as good a solution as restructuring the algorithm. 

Khác với việc tự làm cho thuật toán trở nên khôn ngoan hơn một chút, tôi nghi ngờ mọi nỗ lực tối ưu hóa cuộc gọi hàm ảo theo cách thủ công sẽ gây ra nhiều sự cố hơn giải quyết.

Answer 4

Tất cả các câu trả lời đều giải quyết tình huống đơn giản nhất, khi gọi phương thức ảo chỉ yêu cầu nhận địa chỉ của phương thức thực tế để gọi. Trong trường hợp chung, khi thừa kế nhiều và ảo đi vào hoạt động, việc gọi một phương thức ảo đòi hỏi phải di chuyển con trỏ this. Cơ chế gửi phương thức có thể được thực hiện theo nhiều cách, nhưng thường thấy rằng mục nhập trong bảng ảo không phải là phương thức thực tế để gọi, mà là một số mã 'trampoline' trung gian được trình biên dịch chèn vào. di chuyển con trỏ this trước khi gọi phương thức thực tế.

Khi công văn đơn giản nhất, chỉ cần chuyển hướng con trỏ thêm, sau đó cố gắng tối ưu hóa nó không có ý nghĩa. Khi vấn đề phức tạp hơn, thì bất kỳ giải pháp nào cũng sẽ phụ thuộc vào trình biên dịch và hacker. Hơn nữa, bạn thậm chí không biết bạn đang ở trong kịch bản nào: nếu các đối tượng được nạp từ dll thì bạn không thực sự biết liệu thể hiện thực tế có thuộc về một hệ thống phân cấp kế thừa tuyến tính đơn giản hay một kịch bản phức tạp hơn.

Answer 5

Tại sao cuộc gọi ảo đắt tiền? Bởi vì bạn chỉ đơn giản là không biết mục tiêu chi nhánh cho đến khi mã được thực hiện trong thời gian chạy. Ngay cả các CPU hiện đại vẫn đang xử lý hoàn hảo cuộc gọi ảo và các cuộc gọi gián tiếp. Người ta không thể chỉ đơn giản nói rằng chi phí không có gì bởi vì chúng tôi chỉ có một CPU nhanh hơn. Không có nó không phải là.

1. Làm cách nào để chúng tôi có thể nhanh chóng?

Bạn đã hiểu khá rõ vấn đề. Nhưng, tôi chỉ có thể nói rằng nếu cuộc gọi hàm ảo dễ dự đoán, thì bạn có thể thực hiện tối ưu hóa phần mềm. Nhưng, nếu nó không (nghĩa là, bạn thực sự không có ý tưởng gì sẽ là mục tiêu của chức năng ảo), thì tôi không nghĩ rằng có giải pháp tốt cho bây giờ. Ngay cả đối với CPU, rất khó để dự đoán trong trường hợp cực đoan như vậy.

Thực ra, các trình biên dịch như PGO của Visual C++ (Tối ưu hóa hướng dẫn Profiling) có đầu cơ cuộc gọi ảo tối ưu hóa (Link). Nếu kết quả lược tả có thể liệt kê các mục tiêu chức năng ảo nóng, thì nó sẽ chuyển thành cuộc gọi trực tiếp có thể được gạch chân. Điều này cũng được gọi là devirtualization. Nó cũng có thể được tìm thấy trong một số trình tối ưu hóa động Java.

2. Đối với những ai nói nó không cần thiết

Nếu bạn đang sử dụng ngôn ngữ kịch bản, C# và lo ngại về hiệu quả mã hóa, vâng, nó là vô giá trị. Tuy nhiên, bất cứ ai mong muốn tiết kiệm một chu kỳ duy nhất để có được hiệu suất tốt hơn, thì chi nhánh gián tiếp vẫn là vấn đề quan trọng. Ngay cả những CPU mới nhất cũng không tốt để xử lý các cuộc gọi ảo. Một ví dụ tốt sẽ là một máy ảo hoặc thông dịch viên, thường có một trường hợp chuyển đổi rất lớn. Hiệu suất của nó khá liên quan đến dự đoán chính xác của nhánh gián tiếp. Vì vậy, bạn không thể đơn giản nói rằng nó quá thấp hoặc không cần thiết. Có hàng trăm người đang cố gắng cải thiện hiệu suất ở phía dưới. Đó là lý do tại sao bạn chỉ có thể bỏ qua các chi tiết đó :)

3. Một số thông tin về kiến ​​trúc máy tính nhàm chán liên quan đến chức năng ảo

dsimcha đã viết một câu trả lời tốt đối với CPU có thể xử lý cuộc gọi ảo một cách hiệu quả. Nhưng, nó không chính xác. Đầu tiên, tất cả các CPU hiện đại đều có bộ dự đoán nhánh, theo nghĩa đen dự đoán kết quả của một nhánh để tăng thông lượng đường ống (hoặc, song song hơn trong mức lệnh, hoặc ILP.Tôi thậm chí có thể nói rằng hiệu năng CPU đơn luồng chỉ phụ thuộc vào bạn có thể trích xuất ILP từ một sợi đơn. Dự đoán nhánh là yếu tố quan trọng nhất để có được ILP cao hơn).

Trong dự đoán nhánh, có hai dự đoán: (1) hướng (tức là nhánh được lấy? Hoặc không lấy? Câu trả lời nhị phân) và (2) mục tiêu chi nhánh (tức là, tôi sẽ đi đâu? câu trả lời). Dựa trên dự đoán, CPU speculatively thực thi mã. Nếu đầu cơ không chính xác, sau đó CPU rollbacks và khởi động lại từ các chi nhánh dự đoán sai. Điều này hoàn toàn ẩn khỏi quan điểm của lập trình viên. Vì vậy, bạn không thực sự biết những gì đang xảy ra bên trong CPU, trừ khi bạn đang lược tả với VTune, nó cung cấp tỷ lệ sai lệch chi nhánh.

Nói chung, dự đoán hướng chi nhánh có độ chính xác cao (95% +), nhưng vẫn khó dự đoán các mục tiêu nhánh, đặc biệt là các cuộc gọi ảo và chuyển đổi (tức là nhảy bảng). Gọi theo kiểu số là Nhánh gián tiếp yêu cầu tải bộ nhớ nhiều hơn và CPU cũng yêu cầu dự đoán mục tiêu chi nhánh. Các CPU hiện đại như Nehalem của Intel và Phenom của AMD có bảng mục tiêu chi nhánh gián tiếp chuyên biệt.

Tuy nhiên, tôi không nghĩ rằng việc tìm kiếm vtable có thể gây ra rất nhiều chi phí. Có, nó đòi hỏi một tải bộ nhớ nhiều hơn mà có thể làm cho bộ nhớ cache bỏ lỡ. Tuy nhiên, một khi vtable được tải vào bộ nhớ cache, sau đó nó khá nhiều bộ nhớ cache hit. Nếu bạn cũng lo ngại về chi phí đó, bạn có thể đặt trước mã tìm nạp để tải vtable trước. Nhưng, khó khăn thực sự của cuộc gọi chức năng ảo là CPU không thể thực hiện công việc tuyệt vời để dự đoán mục tiêu của cuộc gọi ảo, điều này có thể dẫn đến việc thoát khỏi đường ống thường xuyên do sự sai lệch của mục tiêu.

Answer 6

Bạn có thể sử dụng con trỏ phương pháp không?

Mục tiêu ở đây là trình biên dịch sẽ tải con trỏ với vị trí của phương thức hoặc hàm được giải quyết. Điều này sẽ xảy ra một lần. Sau khi chuyển nhượng, mã sẽ truy cập phương thức theo cách trực tiếp hơn.

Tôi biết rằng con trỏ đến một đối tượng và truy cập phương thức qua điểm đối tượng sẽ gọi đa hình thời gian chạy. Tuy nhiên, cần có cách để tải con trỏ phương thức đến một phương thức đã giải quyết, tránh tính đa hình và trực tiếp gọi hàm.

Tôi đã kiểm tra cộng đồng wiki để giới thiệu thêm thảo luận.

Answer 7

Bạn không thể sử dụng con trỏ phương thức vì con trỏ đến hàm thành viên không được coi là loại trả về biến đổi. Xem ví dụ dưới đây:

#include <iostream> 

struct base; 
struct der; 

typedef void(base::*pt2base)(); 
typedef void(der::*pt2der)(); 

struct base { 
    virtual pt2base method() = 0; 
    virtual void testmethod() = 0; 
    virtual ~base() {} 
}; 

struct der : base { 
    void testmethod() { 
     std::cout << "Hello from der" << std::endl; 
    } 
    pt2der method() { **// this is invalid because pt2der isn't a covariant of pt2base** 
     return &der::testmethod; 
    } 
}; 

Các tùy chọn khác sẽ có phương pháp tuyên bố pt2base method() nhưng sau đó trở lại sẽ là không hợp lệ vì der :: TestMethod không phải là loại pt2base. Ngoài ra, ngay cả khi bạn đã có một phương pháp nhận ptr hoặc tham chiếu đến loại cơ sở, bạn sẽ phải tự động truyền nó đến loại có nguồn gốc trong phương pháp đó để làm bất cứ điều gì đặc biệt là đa hình, bổ sung thêm vào chi phí mà chúng tôi đang cố gắng để tiết kiệm.

Answer 8

Vì vậy, những gì bạn về cơ bản muốn làm là chuyển đổi đa hình thời gian chạy thành tính đa hình thời gian biên dịch. Bây giờ bạn vẫn cần phải xây dựng ứng dụng của mình để ứng dụng có thể xử lý nhiều "trường hợp", nhưng khi nó đã quyết định trường hợp nào có thể áp dụng cho một lần chạy, đó là nó trong suốt thời gian.

Dưới đây là một mô hình của các trường hợp thời gian chạy đa hình:

struct Base { 
    virtual void doit(int&)=0; 
}; 

struct Foo : public Base { 
    virtual void doit(int& n) {--n;} 
}; 

struct Bar : public Base { 
    virtual void doit(int& n) {++n;} 
}; 

void work(Base* it,int& n) { 
    for (unsigned int i=0;i<4000000000u;i++) it->doit(n); 
} 

int main(int argc,char**) { 
    int n=0; 

    if (argc>1) 
    work(new Foo,n); 
    else 
    work(new Bar,n); 

    return n; 
} 

này có ~ 14s để thực thi trên Core2 tôi, biên dịch với gcc 4.3.2 (32 bit Debian), -O3 tùy chọn.

Bây giờ giả sử chúng ta thay thế các "tác phẩm" phiên bản với một phiên bản templated (templated vào loại bê tông nó sẽ được làm việc trên):

template <typename T> void work(T* it,int& n) { 
    for (unsigned int i=0;i<4000000000u;i++) it->T::doit(n); 
} 

main không thực sự cần phải được cập nhật, nhưng lưu ý rằng 2 cuộc gọi đến work hiện kích hoạt các cuộc gọi và cuộc gọi đến hai chức năng khác nhau và loại cụ thể (cf một chức năng đa hình trước đó).

Hey ưu tiên chạy trong 0,001 giây. Không phải là một yếu tố tăng tốc độ xấu cho một sự thay đổi 2 dòng! Tuy nhiên, lưu ý rằng tốc độ lớn lên là hoàn toàn do trình biên dịch, một khi khả năng đa hình thời gian chạy trong chức năng work bị loại bỏ, chỉ cần tối ưu hóa vòng lặp và biên dịch kết quả trực tiếp vào mã. Nhưng điều đó thực sự làm cho một điểm quan trọng: theo kinh nghiệm của tôi, lợi ích chính từ việc sử dụng loại lừa này đến từ cơ hội cải tiến nội tuyến và tối ưu hóa chúng cho phép trình biên dịch khi một hàm đa hình ít hơn, cụ thể hơn được tạo ra, không từ chỉ loại bỏ indirection vtable (mà thực sự là rất rẻ).

Nhưng tôi thực sự không khuyên bạn nên thực hiện các công cụ như thế này trừ khi hồ sơ hoàn toàn cho thấy đa hình thời gian chạy thực sự tác động đến hiệu suất của bạn. Nó cũng sẽ cắn bạn ngay sau khi một người nào đó phân lớp Foo hoặc Bar và cố gắng chuyển nó vào một hàm thực sự dành cho cơ sở của nó.

Bạn cũng có thể tìm thấy this related question thú vị.

Answer 9

Tôi hỏi một câu hỏi rất tương tự gần đây, và nhận được câu trả lời rằng nó có thể là một phần mở rộng GCC, nhưng không portably:

C++: Pointer to monomorphic version of virtual member function?

Trong đó, tôi cũng đã thử nó với Clang và nó doesn' t hỗ trợ phần mở rộng này (mặc dù nó hỗ trợ nhiều phần mở rộng GCC khác).