CODEWITHSUNDEEP
c++stldictionarycontainers
Piotr Chojnacki
Piotr Chojnacki

Reputation: 6857

std::map performance c++

I have a problem with std::map performance. In my C++ project I have a list of GUIObjects which also includes Windows. I draw everything in for loop, like this:

unsigned int guiObjectListSize = m_guiObjectList.size();
for(unsigned int i = 0; i < guiObjectListSize; i++)
{
    GUIObject* obj = m_guiObjectList[i];
    if(obj->getParentId() < 0)
    obj->draw();                                
}

In this case when I run a project, it works smoothly. I have 4 windows and few other components like buttons etc.

But I would like to take care of drawing windows separately, so after modifications, my code looks like this:

// Draw all objects except windows
unsigned int guiObjectListSize = m_guiObjectList.size();
for(unsigned int i = 0; i < guiObjectListSize; i++)
{
    GUIObject* obj = m_guiObjectList[i];
    if((obj->getParentId() < 0) && (dynamic_cast<Window*>(obj) == nullptr))
        obj->draw();        // GUIManager should only draw objects which don't have parents specified
                            // And those that aren't instances of Window class
                            // Rest objects will be drawn by their parents
                            // But only if that parent is able to draw children (i.e. Window or Layout)
}

// Now draw windows
for(int i = 1; i <= m_windowList.size(); i++)
{
    m_windowList[i]->draw(); // m_windowList is a map!
}

So I created a std::map<int, Window*>, because I need z-indexes of Windows to be set as keys in a map. But the problem is that when I run this code, it's really slow. Even though I have only 4 windows (map size is 4), I can see that fps rate is very low. I can't say an exact number, because I don't have such counter implemented yet.

Could anyone tell me why this approach is so slow?

Upvotes: 2

Views: 528

Answers (2)

Ben Voigt
Ben Voigt

Reputation: 283624

This is what virtual functions are for. Not only do you eliminate the slow dynamic_cast, but you get a more flexible type check.

// Draw all objects except windows
unsigned int guiObjectListSize = m_guiObjectList.size();
for(unsigned int i = 0; i < guiObjectListSize; i++)
{
    GUIObject* obj = m_guiObjectList[i];
    if(obj->getParentId() < 0)
        obj->drawFirstChance();
}

// Now draw windows
for(int i = 1; i <= m_windowList.size(); i++)
{
    m_windowList[i]->drawSecondChance();
}

Where drawFirstChance doesn't do anything for windows and other floating objects.

The next optimization opportunity is to make the window list a vector and perform z-order sorting only when it changes (assuming windows are created/destroyed/reordered much less often than they are drawn).

Upvotes: 4

Agentlien
Agentlien

Reputation: 5116

The problem with this code doesn't seem to be with the use of std::map. Instead, the bottleneck is rather the use of dynamic_cast, which is a very expensive operation as it needs to wander through the inheritance tree of the given class.

This tree is most likely rather large for your GUI components, which would definitely explain why doing so in each iteration slows down the approach as a whole.

Upvotes: 2

Related Questions