2009-06-16 12 views
7

Tôi có một ứng dụng ++ C có thể được đơn giản hóa để một cái gì đó như thế này:Tôi có thể sử dụng Mẫu Mẫu kỳ lạ định kỳ ở đây (C++) không?

class AbstractWidget { 
public: 
    virtual ~AbstractWidget() {} 
    virtual void foo() {} 
    virtual void bar() {} 
    // (other virtual methods) 
}; 

class WidgetCollection { 
private: 
    vector<AbstractWidget*> widgets; 

public: 
    void addWidget(AbstractWidget* widget) { 
    widgets.push_back(widget); 
    } 

    void fooAll() { 
    for (unsigned int i = 0; i < widgets.size(); i++) { 
     widgets[i]->foo(); 
    } 
    } 

    void barAll() { 
    for (unsigned int i = 0; i < widgets.size(); i++) { 
     widgets[i]->bar(); 
    } 
    } 

    // (other *All() methods) 
}; 

ứng dụng của tôi là hiệu suất quan trọng. Thường có hàng nghìn widget trong bộ sưu tập. Các lớp bắt nguồn từ AbstractWidget (trong đó có hàng chục) thường để lại nhiều hàm ảo không bị ghi đè. Những cái được ghi đè thường có triển khai rất nhanh.

Với điều này, tôi cảm thấy tôi có thể tối ưu hóa hệ thống của mình với một số chương trình meta thông minh. Mục đích là để tận dụng chức năng nội tuyến và để tránh các cuộc gọi chức năng ảo, trong khi vẫn giữ mã có thể quản lý được. Tôi đã xem xét mẫu mẫu tò mò định kỳ (xem here để mô tả). Điều này có vẻ như gần như làm những gì tôi muốn nhưng không hoàn toàn.

Có cách nào để làm cho CRTP hoạt động cho tôi ở đây không? Hoặc, có bất kỳ giải pháp thông minh nào khác mà mọi người có thể nghĩ đến không?

+0

Chỉ cần một nit nhỏ - constructors trong C++ không thể là ảo :) –

+0

oops, xin lỗi, cố định –

+0

Bạn có thể thay đổi các lớp cơ sở của bạn "AbstractWidget" "WidgetCollection", hoặc được thiết kế bởi một nhà phát triển/cộng đồng? – umlcat

Trả lời

4

CRTP hoặc tính đa hình thời gian biên dịch là khi bạn biết tất cả các loại của mình tại thời gian biên dịch. Miễn là bạn đang sử dụng addWidget để thu thập danh sách các tiện ích khi chạy và miễn là fooAllbarAll thì phải xử lý các thành viên của danh sách tiện ích đồng nhất đó khi chạy, bạn phải có khả năng xử lý các loại khác nhau khi chạy. Vì vậy, đối với vấn đề bạn đã trình bày, tôi nghĩ rằng bạn đang bị mắc kẹt bằng cách sử dụng đa hình thời gian chạy.

Một câu trả lời tiêu chuẩn, tất nhiên, là để xác minh rằng hiệu suất của đa hình thời gian chạy là một vấn đề trước khi bạn cố gắng tránh nó ...

Nếu bạn thực sự cần phải tránh polymorpism chạy, sau đó một trong những cách sau các giải pháp có thể hoạt động.

Lựa chọn 1: Sử dụng một bộ sưu tập thời gian biên dịch của widget

Nếu các thành viên của WidgetCollection của bạn được biết tại thời gian biên dịch, sau đó bạn có thể dễ dàng sử dụng các mẫu.

template<typename F> 
void WidgetCollection(F functor) 
{ 
    functor(widgetA); 
    functor(widgetB); 
    functor(widgetC); 
} 

// Make Foo a functor that's specialized as needed, then... 

void FooAll() 
{ 
    WidgetCollection(Foo); 
} 

Lựa chọn 2: Thay thế đa hình runtime với chức năng miễn phí

class AbstractWidget { 
public: 
    virtual AbstractWidget() {} 
    // (other virtual methods) 
}; 

class WidgetCollection { 
private: 
    vector<AbstractWidget*> defaultFooableWidgets; 
    vector<AbstractWidget*> customFooableWidgets1; 
    vector<AbstractWidget*> customFooableWidgets2;  

public: 
    void addWidget(AbstractWidget* widget) { 
    // decide which FooableWidgets list to push widget onto 
    } 

    void fooAll() { 
    for (unsigned int i = 0; i < defaultFooableWidgets.size(); i++) { 
     defaultFoo(defaultFooableWidgets[i]); 
    } 
    for (unsigned int i = 0; i < customFooableWidgets1.size(); i++) { 
     customFoo1(customFooableWidgets1[i]); 
    } 
    for (unsigned int i = 0; i < customFooableWidgets2.size(); i++) { 
     customFoo2(customFooableWidgets2[i]); 
    } 
    } 
}; 

Ugly, và thực sự không OO. Các mẫu có thể giúp bằng cách giảm nhu cầu liệt kê mọi trường hợp đặc biệt; thử một cái gì đó như sau (hoàn toàn chưa được kiểm tra), nhưng bạn đang trở lại không có nội tuyến trong trường hợp này.

class AbstractWidget { 
public: 
    virtual AbstractWidget() {} 
}; 

class WidgetCollection { 
private: 
    map<void(AbstractWidget*), vector<AbstractWidget*> > fooWidgets; 

public: 
    template<typename T> 
    void addWidget(T* widget) { 
    fooWidgets[TemplateSpecializationFunctionGivingWhichFooToUse<widget>()].push_back(widget); 
    } 

    void fooAll() { 
    for (map<void(AbstractWidget*), vector<AbstractWidget*> >::const_iterator i = fooWidgets.begin(); i != fooWidgets.end(); i++) { 
     for (unsigned int j = 0; j < i->second.size(); j++) { 
     (*i->first)(i->second[j]); 
     } 
    } 
    } 
}; 

Lựa chọn 3: Loại bỏ OO

OO là hữu ích vì nó giúp quản lý phức tạp và vì nó giúp duy trì sự ổn định khi đối mặt với sự thay đổi. Đối với các trường hợp bạn dường như mô tả - hàng nghìn tiện ích, hành vi của họ thường không thay đổi và phương pháp thành viên của họ rất đơn giản - bạn có thể không có nhiều phức tạp hoặc thay đổi để quản lý. Nếu đó là trường hợp, thì bạn có thể không cần OO.

Giải pháp này giống như đa hình thời gian chạy, ngoại trừ việc bạn duy trì danh sách tĩnh các phương thức "ảo" và các lớp con đã biết (không phải là OO) và cho phép bạn thay thế các cuộc gọi hàm ảo bằng bảng nhảy chức năng nội tuyến.

class AbstractWidget { 
public: 
    enum WidgetType { CONCRETE_1, CONCRETE_2 }; 
    WidgetType type; 
}; 

class WidgetCollection { 
private: 
    vector<AbstractWidget*> mWidgets; 

public: 
    void addWidget(AbstractWidget* widget) { 
    widgets.push_back(widget); 
    } 

    void fooAll() { 
    for (unsigned int i = 0; i < widgets.size(); i++) { 
     switch(widgets[i]->type) { 
     // insert handling (such as calls to inline free functions) here 
     } 
    } 
    } 
}; 
+0

Xin chào Josh, Thật không may, các thành viên của WidgetCollection không được biết đến lúc biên dịch. Tôi có một WidgetFactory có thể chuyển đổi chuỗi thành AbstractWidget và WidgetCollection được tải từ một tệp văn bản. Đề xuất thứ hai của bạn là gợi ý tôi bắt đầu triển khai, nhưng có nhiều lý do tôi không thích có nhiều vectơ (xem phản hồi của tôi về rlbond ở trên). –

+0

Câu trả lời của bạn cho rlbond đã cho tôi một ý tưởng khác. –

+0

Tôi thích tùy chọn thứ 3 của bạn, vì nó đạt được khả năng nội tuyến trong khi vẫn giữ chỉ một vectơ tiện ích. Cảm ơn! –

3

Sự cố mà bạn sẽ có ở đây là với WidgetCollection::widgets. Một vectơ chỉ có thể chứa các mục của một loại và việc sử dụng CRTP yêu cầu mỗi AbstractWidget có một loại khác nhau, được sắp xếp theo loại có nguồn gốc mong muốn. Đó là, bạn AbstractWidget sẽ giống như thế này:

template< class Derived > 
class AbstractWidget { 
    ... 
    void foo() { 
     static_cast< Derived* >(this)->foo_impl(); 
    }   
    ... 
} 

Có nghĩa là mỗi AbstractWidget với một Derived loại khác nhau sẽ tạo thành một loại khác nhau AbstractWidget<Derived>. Lưu trữ tất cả trong một vector duy nhất sẽ không hoạt động. Vì vậy, có vẻ như, trong trường hợp này, các chức năng ảo là con đường để đi.

3

Không, nếu bạn cần một véc tơ của chúng. Các container STL hoàn toàn đồng nhất, có nghĩa là nếu bạn cần lưu trữ một widgetA và một widgetB trong cùng một thùng chứa, chúng phải được thừa hưởng từ một cha mẹ chung. Và, nếu widgetA :: bar() làm một cái gì đó khác với widgetB :: bar(), bạn phải làm cho các hàm ảo.

Tất cả các tiện ích con có nằm trong cùng một vùng chứa không? Bạn có thể làm điều gì đó như

vector<widgetA> widget_a_collection; 
vector<widgetB> widget_b_collection; 

Và sau đó các chức năng sẽ không cần phải ảo.

+0

Họ không * cần *, nhưng mọi thứ trở nên nguy hiểm nếu không. Lý do là, một số phương thức * All() có yêu cầu đồng bộ hóa thứ tự. Ví dụ, AbstractWidget có một phương thức getName() chuỗi và phương thức getValue() kép, và WidgetCollection có phương thức printAllNames() và phương thức printAllValues ​​() và các dòng in phải khớp với nhau. –

+0

Tôi chưa (xem) thấy vấn đề ở đó.Thứ tự lặp lại trên các widget vẫn có thể được xác định rõ (tất cả As, sau đó là tất cả các Bs), vì vậy bạn sẽ nhận được kết quả được đồng bộ với điều kiện là bạn không thay đổi bộ sưu tập trong thời gian đó. Họ sẽ không được liệt kê theo thứ tự các widget đã được thêm vào. –

+0

Nguy hiểm là nếu tôi bất cẩn, tôi có thể nhầm lẫn có A-for-loop trước B-for-loop trong printAllValues ​​(), nhưng sau đó là B-for-loop trước A-for-loop trong printAllValues(). Nhưng nếu đây là giải pháp tốt nhất, thì đó là điều tôi sẵn sàng sống cùng. –

7

Simulated ràng buộc (có sử dụng khác của CRTP) là khi lớp cơ sở nghĩ về bản thân như là đa hình, nhưng khách hàng chỉ thực sự quan tâm đến một đặc biệt lớp có nguồn gốc động. Vì vậy, ví dụ bạn có thể có các lớp đại diện cho một giao diện vào một số chức năng nền tảng cụ thể, và bất kỳ nền tảng nhất định nào sẽ chỉ cần thực hiện một lần. Điểm của mô hình là để templatize lớp cơ sở, để mặc dù có nhiều lớp dẫn xuất, lớp cơ sở biết tại thời gian biên dịch mà một trong những đang được sử dụng.

Nó không giúp bạn khi bạn thực sự cần đa hình thời gian chạy, chẳng hạn như khi bạn có vùng chứa AbstractWidget*, mỗi phần tử có thể là một trong các lớp dẫn xuất và bạn phải lặp lại chúng. Trong CRTP (hoặc bất kỳ mã mẫu nào), base<derived1>base<derived2> là các lớp không liên quan. Do đó, có derived1derived2. Không có đa hình động giữa chúng trừ khi chúng có một lớp cơ sở chung khác, nhưng sau đó bạn quay lại nơi bạn bắt đầu với các cuộc gọi ảo.

Bạn có thể tăng tốc bằng cách thay thế vectơ bằng một số vectơ: một cho mỗi lớp dẫn xuất bạn biết và một lớp chung cho khi bạn thêm các lớp mới có nguồn gốc sau và không cập nhật vùng chứa. Sau đó addWidget thực hiện một số kiểm tra (chậm) typeid hoặc một cuộc gọi ảo đến tiện ích, để thêm tiện ích vào vùng chứa chính xác và có thể có một số tình trạng quá tải khi người gọi biết lớp thời gian chạy. Hãy cẩn thận không vô tình thêm lớp con của WidgetIKnowAbout vào vector WidgetIKnowAbout*. fooAllbarAll có thể lặp qua mỗi vùng chứa để thực hiện các cuộc gọi nhanh chóng đến các chức năng không ảo fooImplbarImpl sau đó sẽ được inlined. Sau đó, chúng lặp lại trên nền vector AbstractWidget* nhỏ hơn nhiều hy vọng, gọi các hàm foo hoặc bar ảo.

Đó là một chút lộn xộn và không tinh khiết-OO, nhưng nếu gần như tất cả các tiện ích của bạn thuộc về các lớp mà vùng chứa của bạn biết, thì bạn có thể thấy hiệu suất tăng lên.Lưu ý rằng nếu hầu hết các widget thuộc về các lớp mà vùng chứa của bạn không thể biết (vì chúng nằm trong các thư viện khác nhau), thì bạn không thể có nội tuyến (trừ khi trình liên kết động của bạn có thể nội tuyến. 't). Bạn có thể giảm phí cuộc gọi ảo bằng cách lộn xộn với các con trỏ hàm thành viên, nhưng mức tăng sẽ gần như chắc chắn là không đáng kể hoặc thậm chí là âm. Hầu hết các chi phí của một cuộc gọi ảo là trong cuộc gọi chính nó, không phải là tra cứu ảo, và các cuộc gọi thông qua con trỏ chức năng sẽ không được inlined.

Hãy nhìn theo cách khác: nếu mã được gạch chân, điều đó có nghĩa là mã máy thực tế phải khác nhau đối với các loại khác nhau. Điều này có nghĩa là bạn cần nhiều vòng lặp hoặc vòng lặp với một công tắc trong đó, vì mã máy rõ ràng không thể thay đổi trong ROM trên mỗi lần truyền qua vòng lặp, theo loại của một số con trỏ được lấy ra khỏi bộ sưu tập.

Vâng, tôi đoán có lẽ đối tượng có thể chứa một số mã asm mà vòng lặp sao chép vào RAM, đánh dấu là có thể thực thi và nhảy vào. Nhưng đó không phải là chức năng thành viên C++. Và nó không thể được thực hiện một cách ổn định. Và nó có lẽ thậm chí sẽ không nhanh, những gì với việc sao chép và vô hiệu hóa icache. Đó là lý do tại sao cuộc gọi ảo tồn tại ...

4

Câu trả lời ngắn gọn là không.

Câu trả lời dài (hoặc ngắn vẫn campared một số câu trả lời khác :-)

Bạn đang tự động cố gắng tìm ra những gì chức năng để thực hiện trong thời gian chạy (đó là những gì các chức năng ảo). Nếu bạn có một véc tơ (các thành viên không thể xác định thời gian biên dịch) thì bạn không thể tìm ra cách để nội tuyến các hàm bất kể bạn cố gắng làm gì.

Caviat duy nhất cho điều đó là nếu các vectơ luôn chứa các phần tử giống nhau (nghĩa là bạn có thể tính toán thời gian biên dịch những gì sẽ được thực hiện khi chạy). Sau đó bạn có thể làm lại điều này nhưng nó sẽ đòi hỏi một thứ khác ngoài một vectơ để giữ các phần tử (có thể là một cấu trúc với tất cả các phần tử như các thành viên).

Ngoài ra, bạn có thực sự cho rằng công văn ảo là nút cổ chai không?
Cá nhân tôi rất nghi ngờ điều đó.

+0

Nếu ứng dụng thực sự không làm gì ngoài việc lặp qua các thùng chứa này, các hàm gọi có triển khai hoàn toàn tầm thường, thì tôi sẽ không ngạc nhiên nếu nút cổ chai là phí gọi. Nó không phải là công văn ảo như vậy, nhưng cuộc gọi out-of-line. Các ứng cử viên khác của khóa học là bộ nhớ cache bỏ lỡ truy cập hàng ngàn đối tượng disperate. –

+0

Martin đúng. Bạn đang đề xuất thêm độ phức tạp đáng kể cho lợi ích hiệu suất đầu cơ. Và hàng ngàn widget không phải là rất nhiều cho một vấn đề tối ưu hóa - tôi sẽ nghi ngờ vtable là đáng kể. Luôn luôn, luôn luôn hồ sơ nó đầu tiên khi tối ưu hóa. – joeld

+0

"Bạn đang đề xuất thêm độ phức tạp đáng kể cho lợi ích hiệu suất đầu cơ". Bây giờ là sai với điều đó, miễn là bạn đo lường hiệu suất trước và sau (trên tất cả các nền tảng mà bạn quan tâm), và không kiểm tra sự thay đổi nếu nó không được cải thiện. Một số người trong chúng tôi đã lập trình cho các hệ thống mà thậm chí không * có * một hồ sơ, khó khăn mặc dù có thể là để tưởng tượng ;-p –

1

Tỷ lệ cược là sau khi bạn trải qua tất cả nỗ lực đó, bạn sẽ thấy không có sự khác biệt về hiệu suất.

Điều này hoàn toàn là sai cách tối ưu hóa. Bạn sẽ không sửa lỗi logic bằng cách thay đổi các dòng mã ngẫu nhiên phải không? Không, đó là ngớ ngẩn. Bạn không "sửa" mã cho đến khi bạn lần đầu tiên tìm thấy những dòng thực sự gây ra vấn đề của bạn. Vậy tại sao bạn xử lý các hiệu suất lỗi khác nhau?

Bạn cần phải lập hồ sơ cho ứng dụng của mình và tìm xem điểm nghẽn cổ chai thực sự ở đâu. Sau đó tăng tốc mã và chạy lại hồ sơ. Lặp lại cho đến khi lỗi hiệu suất (quá chậm thực hiện) đã biến mất.

+0

Xin chào T.E.D., Tôi đã làm những gì bạn mô tả và kết luận rằng một giải pháp lập trình meta tốt nên hiệu suất gấp ba lần. Có một chút khó tả ở đây nhưng tôi sẽ thử: WidgetCollection của tôi từng là một lớp phức tạp hơn, với (một cách hiệu quả) một bộ AbstractWidget cố định, và với tất cả các cấu trúc dữ liệu cấu thành được sử dụng bởi các AbstractWidgets như các trường. Ứng dụng của tôi mất T giây để chạy. Sau đó tôi làm cho nó tổng quát hơn bằng cách giới thiệu AbstractWidgets. Sau đó, với cùng một bộ AbstractWidgets, nó mất 3T giây. –

+0

"Bạn sẽ không sửa lỗi logic bằng cách thay đổi dòng mã ngẫu nhiên phải không?" Không, tôi muốn thay đổi những dòng mà tôi nghĩ có nhiều khả năng là sai, và xem liệu dự đoán của tôi có đúng không. Tôi biết đó là không chắc chắn về mặt thống kê, nhưng thật thú vị khi cho rằng người hỏi đã xác định một nút cổ chai chính hãng và chúng tôi đang giúp giải phóng nó. Nếu không, mọi câu hỏi tối ưu hóa trên trang này đều có cùng câu trả lời: "(1) tìm thấy nút cổ chai của bạn. (2) ... (3) Lợi nhuận!". –

+1

Để giải thích khi nhận xét của tôi, có nhiều vấn đề gây nhầm lẫn làm phức tạp đánh giá của tôi.Nhiều widget trong số này có các phụ thuộc lẫn nhau, yêu cầu thêm một lớp bộ nhớ đệm mà WidgetCollection cũ, ít mạnh mẽ không yêu cầu. Việc biên soạn các hiệu ứng khác này không phải là tầm thường - có lẽ tôi nên cố gắng phân tích chúng tốt hơn. –