2009-06-16 1 views
7

다음과 같이 단순화 할 수있는 C++ 응용 프로그램이 있습니다.Curiously Recurring Template Pattern (C++)을 여기에서 사용할 수 있습니까?

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) 
}; 

응용 프로그램의 성능이 중요합니다. 일반적으로 수천 개의 위젯이 컬렉션에 있습니다. AbstractWidget (수십 가지가 있음)에서 파생 된 클래스는 대개 오버라이드되지 않는 많은 가상 함수를 남겨 둡니다. 오버라이드 된 것들은 전형적으로 매우 빠른 구현을 가진다.

이 점을 감안할 때 필자는 약간의 영리한 메타 프로그래밍으로 시스템을 최적화 할 수 있다고 생각합니다. 목표는 기능 인라이닝을 활용하고 가상 함수 호출을 피하고 코드를 관리 할 수있게 유지하는 것입니다. Curiously Recurring Template Pattern (here 설명 참조)을 조사했습니다. 이것은 거의 내가 원하는,하지만 꽤하지 않는 것 같습니다.

여기에 CRTP를 사용할 수있는 방법이 있습니까? 아니면 누군가가 생각할 수있는 다른 영리한 해결책이 있습니까?

+0

C++의 마이너 생성자는 가상 일 수 없습니다. –

+0

oops, 죄송합니다. –

+0

기본 클래스 "AbstractWidget" "WidgetCollection"을 변경하거나 다른 개발자/커뮤니티가 디자인 할 수 있습니까? – umlcat

답변

4

CRTP 또는 컴파일 타임 다형성은 컴파일 타임에 모든 유형을 알고있는 경우를위한 것입니다. addWidget을 사용하여 런타임에 위젯 목록을 수집하고 fooAllbarAll 길이라면 동등한 위젯 목록의 구성원을 런타임에 처리해야하므로 런타임에 다른 유형을 처리 할 수 ​​있어야합니다. 그래서 당신이 제시 한 문제에 대해서, 당신은 런타임 다형성 (polymorphism)을 사용하여 붙어 있다고 생각합니다.

표준 대답은 물론, 다음

당신이 정말로 런타임 다형성을 피하기 위해 필요한 경우 ... 당신이 그것을 피하려고하기 전에 런타임 다형성의 성능이 문제가 있음을 확인하려면 다음 중 하나입니다 해결책이 효과가있을 수 있습니다.

옵션 1 : 위젯

하여 WidgetCollection의 회원이 컴파일 타임에 알려진 경우, 당신은 아주 쉽게 템플릿을 사용할 수 있습니다의 컴파일시 모음을 사용합니다.

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); 
} 

옵션 2 : 자유의 기능 정말

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]); 
    } 
    } 
}; 

미운, 그리고 OO와 런타임 다형성을 교체합니다. 템플리트는 모든 특별한 경우를 나열 할 필요성을 줄임으로써이를 지원할 수 있습니다. 다음과 같은 것을 시도해보십시오 (완전히 테스트되지 않음). 그러나이 경우에는 인라인되지 않습니다.

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]); 
     } 
    } 
    } 
}; 

옵션 3 : 그것은 복잡성을 관리 할 수 ​​있기 때문에 그것은 변화의 얼굴에 안정성을 유지하는 데 도움이 있기 때문에 제거 OO

OO 유용합니다. 상황에 따라 수천 개의 위젯, 일반적으로 동작이 변경되지 않고 멤버 메소드가 매우 간단하다는 점을 설명하는 것처럼 보입니다. 관리하기 위해 복잡성이나 변경 사항이별로 없을 수도 있습니다. 그렇다면 OO가 필요하지 않을 수 있습니다.

"가상"메소드 및 알려진 하위 클래스 (OO가 아님)의 정적 목록을 유지해야하며 가상 함수 호출을 다음과 같은 점프 테이블로 대체 할 수 있다는 점을 제외하면이 솔루션은 런타임 다형성과 동일합니다. 인라인 함수.

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

안녕 Josh, 안타깝게도 WidgetCollection의 멤버는 컴파일 할 때 알 수 없습니다. 문자열을 AbstractWidget으로 변환하는 WidgetFactory가 있고 WidgetCollection이 텍스트 파일에서로드됩니다. 두 번째 제안은 구현하기 시작한 것이지만 여러 가지 벡터가있는 것을 싫어하는 이유가 있습니다 (위의 rlbond에 대한 내 응답 참조). –

+0

rlbond 님에 대한 귀하의 회신은 나에게 또 다른 아이디어를주었습니다. –

+0

위젯을 하나의 벡터로 유지하면서 인라인 기능을 구현하므로 3 번째 옵션을 좋아합니다. 감사! –

3

여기에있는 문제는 WidgetCollection::widgets입니다. 벡터에는 한 가지 유형의 항목 만 포함될 수 있으며 CRTP를 사용하려면 각 AbstractWidget에 원하는 유형의 템플릿으로 다른 유형이 있어야합니다. 즉, 당신은 AbstractWidget은 다음과 같이 보일 것입니다 :

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

것은 다른 Derived 유형 각 AbstractWidget는 다른 종류의 AbstractWidget<Derived>를 구성하는 것을 의미합니다. 이 모든 것을 단일 벡터에 저장하면 작동하지 않습니다. 따라서이 경우에는 가상 기능이 필요합니다.

3

해당 벡터가 필요한 경우가 아님. STL 컨테이너는 완전히 균질합니다. 즉, 동일한 컨테이너에 widgetA와 widgetB를 저장해야하는 경우 공통 부모에서 상속해야합니다. 그리고 widgetA :: bar()가 widgetB :: bar()와 다른 것을하면 함수를 가상으로 만들어야합니다.

모든 위젯이 동일한 컨테이너에 있어야합니까?

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

그런 다음 함수가 가상 일 필요는 없습니다.

+0

그들은 필요하지 않지만 위험하지 않습니다. 이유는 * All() 메서드 중 일부는 순서 동기화 요구 사항을 갖고 있기 때문입니다. 예를 들어 AbstractWidget에는 getName() 메서드와 double getValue() 메서드가 있으며 WidgetCollection에는 printAllNames() 메서드와 printAllValues ​​() 메서드가 있으며 인쇄 된 행은 서로 정렬되어야합니다. –

+0

나는 (아직) 거기에서 문제를 보지 못했다.위젯에 대한 반복 순서는 계속 정의 할 수 있습니다 (모든 As, 모든 Bs). 따라서 사용자는 컬렉션을 변경하지 않는 한 동기화 된 결과를 얻을 수 있습니다. 그들은 위젯이 추가 된 순서대로 나열되지 않습니다. –

+0

내가 부주의한다면, printAllValues ​​()에서 B-for-loop 전에 A-for-loop를 잘못 입력했을 수도 있지만 printAllValues의 A-for-loop 앞에있는 B-for-loop(). 그러나 이것이 최선의 해결책이라면, 그것은 내가 함께 살기를 원하는 어떤 것입니다. –

7

(CRTP의 다른 용도가있다)가 기본 클래스 다형성 것으로 자체 생각되지만 클라이언트는 실제로 약 특정 파생 클래스 상관 때의 바인딩 시뮬레이션 동적. 예를 들어 인터페이스를 나타내는 클래스를 특정 플랫폼 관련 기능으로 구현할 수 있으며 특정 플랫폼에는 구현이 하나만 필요합니다. 패턴의 요점은 기본 클래스를 templatize하는 것이므로 파생 클래스가 여러 개 있지만 기본 클래스는 컴파일 타임에 어느 클래스가 사용 중인지 알 수 있습니다.

예를 들어 컨테이너가 AbstractWidget* 일 때와 같이 런타임 다형성이 진정 필요한 경우에는 각 요소가 여러 파생 클래스 중 하나가 될 수 있으며이를 반복해야합니다. CRTP (또는 임의의 템플릿 코드)에서 base<derived1>base<derived2>은 서로 관련이없는 클래스입니다. 따라서 derived1derived2도 마찬가지입니다. 다른 공통 기본 클래스가 없으면 동적 다형성이 없지만 가상 호출로 시작한 곳으로 되돌아갑니다.

벡터를 여러 벡터로 바꾸면 속도가 향상 될 수 있습니다. 알고있는 파생 클래스마다 하나씩, 새 파생 클래스를 나중에 추가하고 컨테이너를 업데이트하지 않을 때 일반적인 벡터 하나를 사용할 수 있습니다. 그런 다음 addWidget이 위젯을 확인하거나 가상 호출을 수행하여 올바른 컨테이너에 위젯을 추가하고 호출자가 런타임 클래스를 알고있을 때 오버로드를 수행 할 수 있습니다 (느림) typeid. 실수로 WidgetIKnowAbout의 하위 클래스를 WidgetIKnowAbout* 벡터에 추가하지 않도록주의하십시오. fooAllbarAll은 차례대로 각 컨테이너를 반복적으로 처리하여 비 - 가상 fooImplbarImpl 함수에 대한 호출을 인라인 할 수 있습니다. 그런 다음 그들은 훨씬 더 작은 AbstractWidget* 벡터를 반복하여 가상 foo 또는 bar 함수를 호출합니다.

약간 지저분하고 순수한 OO가 아니지만 거의 모든 위젯이 컨테이너가 알고있는 클래스에 속하면 성능이 향상 될 수 있습니다.

대부분의 위젯이 컨테이너가 알 수없는 클래스에 속해있는 경우 (예 : 다른 라이브러리에 있기 때문에) 인라인 할 수없는 경우 (동적 링커가 인라인 할 수없는 경우) '티). 멤버 함수 포인터를 사용하여 가상 호출 오버 헤드를 줄일 수 있지만 이득은 거의 무시할 만하거나 부정적 일 수도 있습니다. 가상 호출의 오버 헤드는 대부분 가상 룩업이 아닌 호출 자체에 있으며 함수 포인터를 통한 호출은 인라인되지 않습니다.

다른 방법을 살펴보십시오. 코드가 인라인되어야한다면 실제 컴퓨터 코드가 다른 유형에 대해 달라야한다는 것을 의미합니다. 즉, 컬렉션에서 가져온 일부 포인터의 유형에 따라 루프를 통과 할 때마다 기계 코드가 ROM에서 명확하게 변경 될 수 없기 때문에 다중 루프 또는 스위치가있는 루프가 필요합니다.

글쎄, 아마 루프에 RAM, 실행 가능 표시 및 점프로 복사 할 수있는 일부 asm 코드가있을 수 있습니다. 하지만 C++ 멤버 함수는 아닙니다. 그리고 이식 할 수 없습니다. 그리고 그것은 아마도 심지어 빠르지도 않을 것입니다. 복사와 icache 무효화로 무엇을 할 것입니다. 그래서 가상 전화가 존재합니다 ...

4

짧은 대답은 없습니다. 여전히 짧은

:-) 다른 답변을 campared

긴 대답은 (또는 동적으로 (즉, 가상 함수가 무엇을) 실행시 실행 기능을 알아 내기 위해 노력하고있다. 컴파일 타임에 멤버를 결정할 수없는 벡터를 가지고 있다면 무엇을 시도해도 함수를 인라인하는 법을 배울 수 없습니다.

벡터가 항상 동일한 요소를 포함하고 있다면 (즉, 런타임에 실행될 컴파일 시간을 계산할 수있는 경우) 캐 비움이 유일한 것입니다. 그런 다음 다시 작업 할 수는 있지만 벡터를 사용하여 요소 (모든 요소가 구성원으로 구성된 구조)를 보유해야합니다.

또한 가상 디스패치가 병목 현상이라고 생각하십니까?
개인적으로 나는 그것을 매우 의심합니다.

+0

응용 프로그램이 진정으로 아무것도하지 않지만 이러한 컨테이너를 반복 할 경우 구현이 완전히 사소한 함수를 호출하면 병목 현상이 호출 오버 헤드 인 경우 놀라지 않을 것입니다. 가상 디스패치 같은 것이 아니라 외부 통화입니다. 물론 다른 후보자는 수천 개의 불필요한 객체에 접근하는 것에서의 캐시 미스이다. –

+0

마틴의 권리. 당신은 투기적인 성능 향상을 위해 상당한 복잡성을 추가 할 것을 제안합니다. 그리고 수천 개의 위젯은 최적화 문제에 대해별로 많지 않습니다. vtable이 중요하다고 생각합니다. 항상 최적화 할 때 항상 먼저 프로파일 링하십시오. – joeld

+0

"당신은 투기적인 성능 향상을 위해 상당한 복잡성을 추가 할 것을 제안합니다." 당신이 걱정하는 모든 플랫폼에서 이전과 이후의 성능을 측정하고 개선되지 않은 경우 변경 사항을 체크인하지 않는 한 잘못 생각한 것입니다. 우리 중 일부는 심지어 프로파일 러를 가지고 있지 않은 시스템을 위해 상상할 수는 없지만 프로그래밍이 어려웠습니다 .-p –

1

모든 노력을 다했다면 성능 차이가 없습니다.

이것은 절대적으로 입니다.은 최적화 할 방법입니다. 임의의 코드 행을 변경하여 논리 버그를 수정하지 않습니까? 아니, 그건 어리 석다. 실제로 문제의 원인이되는 행을 찾을 때까지 코드를 "수정"하지 마십시오. 그렇다면 왜 성능 버그를 다르게 처리하겠습니까?

응용 프로그램의 프로필을 작성하고 실제 병목 현상이 어디에 있는지 찾아야합니다. 그런 다음 해당 코드의 속도를 높이고 프로파일 러를 다시 실행하십시오. 성능 버그 (너무 느린 실행)가 없어 질 때까지 반복하십시오.

+0

안녕하세요 T.E.D., 좋은 메타 프로그래밍 솔루션이 성능을 3 배 향상시켜야한다고 설명했습니다. 여기에 대해 설명하기는 좀 어렵지만 필자의 WidgetCollection은 훨씬 더 복잡한 클래스 였고 (사실상) 고정 된 AbstractWidget 세트와 해당 AbstractWidgets에서 필드로 사용되는 모든 구성 데이터 구조가 사용되었습니다. 내 응용 프로그램을 실행하려면 T 초가 걸렸습니다. 그런 다음 AbstractWidgets을 도입하여 좀 더 일반화했습니다. 이후 동일한 AbstractWidgets 세트로 3T 초가 걸렸습니다. –

+0

"임의의 코드 줄을 변경하여 논리 버그를 수정하지 않습니까?" 아니요, 제가 가장 잘못 생각한 선을 바꾸고 제 추측이 옳았는지 확인하십시오. 나는 통계적으로는 불가능하다고 생각하지만, 질문자가 진정한 병목 현상을 확인했다고 가정하는 것은 재미 있고, 우리는 그것을 자유롭게 해줄 수 있습니다. 그렇지 않으면이 사이트의 모든 최적화 질문에는 "(1) 병목 현상을 발견하십시오 (2) ... (3) 이익을 얻으십시오!"라는 똑같은 대답이 있습니다. –

+1

내 의견을 요약하면 내 평가가 복잡해지는 혼란스러운 문제가 많이 있습니다.이러한 위젯 중 상당수는 상호 종속성이있어 이전 버전의 덜 강력한 WidgetCollection에는 필요하지 않은 캐싱 계층이 추가로 필요합니다. 이러한 다른 효과를 프로파일 링하는 것은 사소한 것이 아닙니다. 아마도 더 나은 분석을 위해 노력해야합니다. –

관련 문제