Is there a way to get RTTI directly in C ++ to improve branch prediction in virtual calls?

Question

So, I am creating a library that will have a class someBase {}; which will be displayed by downstream users in several classes.

class someBase { public: virtual void foo()=0; }; 

What I also have is a vector of pointers to someBase, and I do this: -

 vector <someBase*> children; // downstream user code populates children with some objects over here for (i=0; i<children.size(); i++) children[i]->foo(); 

Profiling now shows that incorrect branch predictions on virtual calls are one (of several) bottlenecks in my code. What I want to do is somehow get access to the RTTI objects and use them to sort the vector of children according to the type of class, in order to improve both the locality of the command cache and branch prediction.

Any suggestions / solutions on how to do this?

Key issues to consider: -

1.) I really do not know which or how many classes will be derived from someBase. Hypothetically, I could have a global enumeration in some common file somewhere that lower-level users can edit to add their own class type and then sort it (mainly using my own RTTI). But this is an ugly decision.

2.) PiotrNycz suggests using type_info in his answer below. However, only! = And == are defined for this. Any ideas on how to get a strict weak order on type_info?

3.) I really try to improve the location of branch prediction and the localization of the command cache, so if there is an alternative solution, this is also welcome.

Answer 1

There is a typeid .

You can use it to define a comparator to sort your objects in a vector.

Like this:

 inline bool compareTypes(BaseClass* obj1, BaseClass* obj2) { int compareRes = strcmp(typeid(*obj1).name(), typeid(*obj2).name()); if (compareRes < 0) return true; if (compareRes > 0) return false; std::less<BaseClass*> ptrComp; return ptrComp(obj1, obj2); } 

and

  sort(v.begin(), v.end(), compareTypes); 

[UPDATE]

Thank you for choosing me, that there is a function designed for this purpose. This is std::type_info::before(const type_info&) const Thus, the comparator will be as simple as this:

 inline bool compareTypes(A* obj1, A* obj2) { return typeid(*obj1).before(typeid(*obj2)); } 

My previous version is not so bad;) It can be used for cases when you need to sort and objects of this class.

Answer 2

You can classify pointers by type once in initialization using, for example:

 std::vector<derivedA*> derivedA_list; std::vector<derivedB*> derivedB_list; //... for (i=0; i<children.size(); i++) if (derivedA *d = dynamic_cast<derivedA*>(children[i])) derivedA_list.push_back(d); else if (derivedB *d = dynamic_cast<derivedB*>(children[i])) derivedB_list.push_back(d); //... 

And then to call the function you can make a non-virtual call:

 for (i=0; i<derivedA.size(); ++i) derivedA_list[i]->derivedA::foo(); for (i=0; i<derivedB.size(); ++i) derivedB_list[i]->derivedB::foo(); 

Also note that loops using iterators are more likely to be better optimized.