Downcasting pointers

Question

Basically, I have two classes, Spatial and Node, inheriting from IEntity; IEntity is an abstract class (interface). I'm storing Entity object pointers in an std::vector in a SceneGraph class, like std::vector<IEntity*> So to differentiate between Spatials and Nodes, I first had the idea to do

if(!dynamic_cast<Node*>(myEntity)) // equals nullptr, cast failed
{
  BOOST_LOG_TRIVIAL(info) << "It is a node !";
}

But this code would be for a high performace engine, and I can't afford thousands/ millions of dynamic cast calls in a second; So what would you suggest to differentiate between Spatial pointers and Nodes to downcast without any errors (in the fastest way possible) ? PS. I know that it's not recommanded to store pointers in stl containers, but this is the best way around imo.

It depends on how do you want to do with the downcasted object? — songyuanyao, May 12 '16 at 13:22
well, in a scene graph, I need to differentiate between node entities and spatial entities (basically meshes) to either: parse the node or render the spatial (nodes contain other enitites; they're basically arrays, with an additionnal transform component) — Coder32, May 12 '16 at 13:23
Is it possible to abstract the action to a virtual function in `IEntity`? Then you can override it in `Spatial` and `Node`. — songyuanyao, May 12 '16 at 13:26
you mean like a virtual function IsNode() ? The only common thing between the two classes is that they're entites and have a transform component; but they need to be stored together because of my API design — Coder32, May 12 '16 at 13:27
@Coder32 Have you considered that this may indicate a flaw in the API design? — molbdnilo, May 12 '16 at 13:30
yes; but i've seen other API's use this (like the JMonkey Engine) — Coder32, May 12 '16 at 13:31
but it wouldn't be tragic to change either, because I just started implementing scene graphs / frustum culling / ordering yesterday — Coder32, May 12 '16 at 13:32
also, it's kind of logic to store nodes and entities together, because nodes are basically arrays with transformation : you just need to differentiate them from spatials at rendering (you can't render a node); — Coder32, May 12 '16 at 13:35
@Coder32 If you need to determine things based on runtime info, then CRTP and static polymorphism is out. But here is some info, look at question and accepted answer: http://stackoverflow.com/questions/19062733/what-is-the-motivation-behind-static-polymorphism-in-c — Erik Alapää, May 12 '16 at 13:35
@Coder32: Another idea might be to regularly sort the scene graph, so you know e.g the first 1.5 million elements are Node entities. Then you can re-use that info many times instead of downcasting all entities many times per second. — Erik Alapää, May 12 '16 at 13:38
I can't sort them like that, because they're already sorted for frustum culling — Coder32, May 12 '16 at 13:39
@Coder32: Maybe then create a new short-lived vector with naked ptrs to nodes, and use that repeatedly until next update? — Erik Alapää, May 12 '16 at 13:41
hmm.... maybe; But I also thought of making another interface like IRenderable and check if those pointers inherit from it, but that would leave us with the same problem — Coder32, May 12 '16 at 13:43
@Coder32: I will not spam the comment field w more ideas after this, but one idea may be to put a non-virtual boolean is_node() in the base class, and make that inline too. May be ugly, but smokin' fast... — Erik Alapää, May 12 '16 at 13:50

HiFile.app - best file manager · Accepted Answer · 2016-05-12T15:06:37.683

3

Firstly, having to downcast in such a situation is a clear sign of bad design breaking the Liskov principle. To fix it in the OOP domain, instead of downcasting you should call a certain virtual function for each your IEntity object which then would do something different for Node and something different for Spatial.

Secondly, if you aim for performance, you should abandon OOP in the performance critical code. I.e. no calls to virtual functions. You should also try to utilize memory caching as much as possible because memory access to non-cached data is usually the bottleneck of most performance critical code. How to do that? Google for "data driven design" or "data oriented programming". This is often implemented using something called "entity component system", typically in computer games. In your case you will probably need to keep separated your Nodes and Spatials in separated vectors and not by reference or pointer to IEntity but by value (use vector<Node> and vector<Spatial> instead of vector<IEntity*>) and then traverse it linearly or in a predictable/regular order (to benefit pro data prefetch). This will give you most speed you can achieve. And probably only after that you should start with some algorithm fine-tuning... This is the typical scenario so I assume this is also your case.

Btw. except for performance (as in your case) there is nothing wrong about storing pointers in STL containers. Or is there?

UPDATE: as you mentioned below, you probably need to keep the objects in a tree structure for some algorithmic reasons. In that case my advice about keeping objects in containers by value might not be that useful or straightforward to implement. Anyway and in any case you must profile our code first and then try to optimize and fiddle with caching etc. However my first note about bad design indicated by the need to downcast is still valid. :)

edited May 12 '16 at 15:06

answered May 12 '16 at 13:50

HiFile.app - best file manager

7,273
2
32
80

I once read about post descouriging that because if the pointer gets deleted it leads to undefined behaviour. Anyways, problem is that i can't store nodes and spatials in two different array : you may have situation like thishttp://imgur.com/W2RizCb – Coder32 May 12 '16 at 13:58
One general problem with storing naked pointers in STL containers is of course cleanup. But if those are 'non-owning' pointers, cleanup is up to some other part of the program. – Erik Alapää May 12 '16 at 13:59
Erik: Yes, the cleanup is the only problem but it is easily manageable. E.g. with smart pointers (unique_ptr preffered over shared_ptr) or with cleaning up yourself. This is so simple that I would not call it a problem. :) – HiFile.app - best file manager May 12 '16 at 13:59
Btw, I also use this kind of cleanup method for my opengl objects; they're accessed like std::shared_ptr object = CreateShaderProgram(args) – Coder32 May 12 '16 at 14:03
According to the link you provided, it seems you want to keep the data in a tree structure. Well, then it depends how you want to traverse it in the performance critical part of the code. Linear traversal is always best for caching, but I guess you want to use the tree because you are going to need it for some clever algorithm. Or is the three there because the ownership has a tree-like structure? – HiFile.app - best file manager May 12 '16 at 14:08
@V.K. I agree that in general, some smart ptr is better to use w containers. But if the ptr is non-owning, a naked ptr sometimes is exactly the right thing to use. – Erik Alapää May 12 '16 at 14:10
@ Erik: Well I would say it is better to use shared_ptr if you want to share ownership and unique_ptr if you do not want to. Unique_ptr has clear advantage - it is faster (no reference counting increments) and usually two times smaller. – HiFile.app - best file manager May 12 '16 at 14:12
@Aconcagua: Beware! No tree structure with pointers to elements in containers. This is really bad idea because when container is reallocated (e.g. when growing above its capacity), the pointer becomes dangling! Undefined behaviour! But you can use indices to containers rather than pointers. – HiFile.app - best file manager May 12 '16 at 14:14
@V.K actually I keep them in a tree structure to perform frustum culling and transparency ordering (for a 3d deferred renderer) – Coder32 May 12 '16 at 14:20
It's really important because oredered rendering can lead to 2* /3* perf. improvment – Coder32 May 12 '16 at 14:20
@V.K. Oh, shame over me. Actually I'm aware of that, don't know how this came into my mind (quickly deleted...). Still valid: have `vector` and `vector` instead of the single one. – Aconcagua May 12 '16 at 14:31

Downcasting pointers

1 Answers1