std::map and Performance Questions

[Spirrwell]

Hi there!

So I work on a mod that uses the Source Engine. I did a performance profile and found we were losing a LOT of FPS from it computing animations. The biggest offender here being stricmp()

For every animated model, it iterates through all of its sequences comparing the requested animation name with its list using stricmp. So with lots of animations and with longer animation names, that has to kill performance a significant amount especially since they're C strings which probably need to be measured each and every frame.

This is what that looks like:

for (int i = 0; i < pstudiohdr->GetNumSeq(); i++)
{
mstudioseqdesc_t &seqdesc = pstudiohdr->pSeqdesc( i );
if (stricmp( seqdesc.pszLabel(), label ) == 0)
return i;
}

So I want to optimize this a bit better. I was thinking std::strings would be better in this scenario, and I was also thinking of using std::map to map std::strings to the sequence index, so I could do something like:

return sequenceMap[label];

Instead of iterating over a for loop. Does std::map iterate over a for loop internally? I guess what I'm getting at is would using an std::map give a performance gain over the above for loop?

Lastly, is there any way to control the auto initialization of std::map data? For instance, if I do std::map < std::string, int >, trying to access a key value that doesn't exist should auto initialize the int to 0. I would like to say auto initialize it to -1 instead.

Any help or information is greatly appreciated!

[JLBorges]

> would using an std::map give a performance gain over the above for loop?

Yes. Lookup, insertion and removal take O(log N) (logarithmic) time.
http://en.cppreference.com/w/cpp/container/map

With std::string as the key type, std::unordered_map would be very fast; on the average, lookup, insertion and removal take O(1) (constant) time. http://en.cppreference.com/w/cpp/container/unordered_map


> is there any way to control the auto initialization of std::map data? For instance,
> if I do std::map < std::string, int >, trying to access a key value that doesn't exist
> should auto initialize the int to 0. I would like to say auto initialize it to -1 instead.

Yes; wrap it in a user-defined type with a custom default initialised value.

For example, for a mapped type that can appear as the type of a temple non-type parameter:

#include <iostream>
#include <unordered_map>
#include <string>

namespace detail
{
    template < typename T, T DEFAULT_VALUE > struct init_wrapper
    {
        constexpr init_wrapper( T v = DEFAULT_VALUE ) noexcept : value(v) {}

        operator T& () noexcept { return value ; }
        constexpr operator T& () const noexcept { return value ; }

        int* operator& () noexcept  { return std::addressof(value) ; }
        constexpr const int* operator& () const noexcept { return std::addressof(value) ; }

        T value ;
    };
}

template < typename KEY, typename VALUE, VALUE DEFAULT_VALUE >
using map_dv = std::unordered_map< KEY, detail::init_wrapper< VALUE, DEFAULT_VALUE > > ;

int main()
{
    map_dv< std::string, int, -1 > my_map { {"abc",22}, {"xyz",17} } ;
    std::cout << my_map["abc"] << ' ' << my_map["def"] << ' ' << my_map["xyz"] << '\n' ; // 22 -1 17

    my_map["def"] = 99 ;
    my_map.erase("xyz") ;
    my_map["abc"] += 55 ;
    std::cout << my_map["abc"] << ' ' << my_map["def"] << ' ' << my_map["xyz"] << '\n' ; // 77 99 -1
}

http://coliru.stacked-crooked.com/a/1e8316f13b874780
http://rextester.com/HWT35847

Note that if the mapped type is not a type that can appear as the type of a temple non-type parameter, the code for the wrapper would be quite a bit more involved.

If there are a large number of non-repeating spurious look ups, it would be cheaper to use the find() member function. http://en.cppreference.com/w/cpp/container/unordered_map/find

[Spirrwell]

Ahaha, oh yeah. I did a very basic implementation and just sort of hacked it together to see if it would work and I'm already seeing 60+ FPS gains.

Oh man, I can't wait to post about this on the Source SDK forums. Thanks for the info!