Tech Off Thread

1 post

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

std::set: count(v) vs. find(v) != end()

Back to Forum: Tech Off
  • User profile image
    tobiasloew

    Hi,

    I just came across std::set's count method and was wondering, why there is no std::set-specific optimization of count (e.g. by just returning find(arg)!=end()).

    The reason for my question is that the following code:

    #include <SDKDDKVer.h>
    
    #include <stdio.h>
    #include <tchar.h>
    #include <iostream>
    #include <set>
    
    #define USE_BUILTIN_COUNT
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        int n;
        std::cin >> n;
    
        std::set<int> s;
        s.insert(n);
    #ifdef USE_BUILTIN_COUNT
        size_t cnt = s.count(4);
    #else
        size_t cnt = size_t(s.find(4) != s.end());
    #endif
        std::cout << cnt << std::endl;
        return 0;
    }
    

    generates when build with VS 2015 Update 2 x64/release/O2 

    with USE_BUILTIN_COUNT defined: 64 lines of assembly for the "count"

    without USE_BUILTIN_COUNT defined: 21 lines of assembly for the "find != end"

    In x86-builds (release, O2) it get's even worse: with USE_BUILTIN_COUNT defined, the internal std::set calls to _Eqrange and _Distance2 won't get inlined!

    Please check, if it's possible to tweek std::set's count method.

    regards

    Tobias

    PS: I haven't looked up the standard, to check if this optimization is prohibited in some way.

     

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.