find vs equal_range and performance

Question

I am doing some tests with find, equal_range and my own binary search functions and I am having some trouble understanding why equal_range takes so long when compared with a find.

I have a sorted vector and I time the duration of the search operation. The initial idea was to see what would be the performance difference between find and equal_range but I was expecting that as the amount of data grew iterating over the vector would be worse than a binary search and that's not happening.

My code is pretty simple but I "suspect" that something is wrong in here and I don't know what.

-- EDIT -- I am doing these tests in VS2012 --

        #include "stdafx.h"
        #include <vector>
        #include <algorithm>
        #include <chrono>
        #include <iostream>
        #include <list>

        using namespace std;

        #define TIMING

        #ifdef TIMING
        #define INIT_TIMER auto start = std::chrono::high_resolution_clock::now();
        #define START_TIMER  start = std::chrono::high_resolution_clock::now();
        #define STOP_TIMER(name)  std::cout << name << ": " << \
            std::chrono::duration_cast<std::chrono::nanoseconds>( \
            std::chrono::high_resolution_clock::now()-start \
            ).count() << " ns " << std::endl; 
        #else
        #define INIT_TIMER
        #define START_TIMER
        #define STOP_TIMER(name)
        #endif

        template<typename T> int mybsearch(const std::vector<T>& vec, unsigned start, unsigned end, const T& key)
        {
            // Termination condition: start index greater than end index
            if(start > end)
            {
                return -1;
            }

            // Find the middle element of the vector and use that for splitting
            // the array into two pieces.
            unsigned middle = start + ((end - start) / 2);

            if(vec[middle] == key)
            {
                return middle;
            }
            else if(vec[middle] > key)
            {
                return mybsearch(vec, start, middle - 1, key);
            }

            return mybsearch(vec, middle + 1, end, key);
        }

        template<typename Iterator, typename T> Iterator Tbsearch(Iterator& begin, Iterator& end, const T& key)
        {
            // Keep halving the search space until we reach the end of the vector
            Iterator NotFound = end;

            while(begin < end)
            {
                // Find the median value between the iterators
                Iterator Middle = begin + (std::distance(begin, end) / 2);

                // Re-adjust the iterators based on the median value
                if(*Middle == key)
                {
                    return Middle;
                }
                else if(*Middle > key)
                {
                    end = Middle;
                }
                else
                {
                    begin = Middle + 1;
                }
            }

            return NotFound;
        }

        int _tmain(int argc, _TCHAR* argv[])
        {
            vector<int> V;
            typedef vector<int>::iterator it;
            std::pair<it,it> res;
            it val;

            list<int> L;
            typedef list<int>::iterator itL;
            std::pair<itL,itL> lpair;
            itL lval;

            for(int i=0; i<1000000; i++)
            {
                V.push_back(i+1);
                L.push_back(i+1);
            }

            INIT_TIMER

            cout << "-- find --\n";
            for(int k=0;k<10;k++)
            {
                int look = pow(k,k);

                START_TIMER
                val = std::find(V.begin(),V.end(),look);
                STOP_TIMER("find took ")

                if(val!=V.end())
                    cout << look << " found\n";
                else
                    cout << look << " not found\n" ;
            }
            cout << "-- homemade bsearch (index) --\n";
            for(int k=0;k<10;k++)
            {
                int look = pow(k,k);

                START_TIMER
                int a = mybsearch(V, 0, V.size()-1, look);
                STOP_TIMER("find took ")

                if(a>0)
                    cout << look << " found\n";
                else
                    cout << look << " not found\n" ;
            }

            cout << "-- homemade bsearch (iterators) --\n";
            for(int k=0;k<10;k++)
            {
                int look = pow(k,k);

                START_TIMER
                it f = Tbsearch(V.begin(), V.end(), look);
                STOP_TIMER("find took ")

                if(f!=V.end())
                    cout << look << " found\n";
                else
                    cout << look << " not found\n" ;
            }



            cout << "-- equal range --\n";
            for(int k=0;k<10;k++)
            {
                int look = pow(k,k);

                START_TIMER
                res = std::equal_range(V.begin(),V.end(),look);
                STOP_TIMER("equal_range took ")

                if(res.first!=res.second)
                    cout << look << " found\n";
                else
                    cout << look << " not found\n" ;
            }

            return 0;
        }

The output of this run is

    -- find --
    find took : 0 ns
    1 found
    find took : 0 ns
    1 found
    find took : 0 ns
    4 found
    find took : 0 ns
    27 found
    find took : 0 ns
    256 found
    find took : 0 ns
    3125 found
    find took : 0 ns
    46656 found
    find took : 2000200 ns
    823543 found
    find took : 2000200 ns
    16777216 not found
    find took : 2000200 ns
    387420489 not found
    -- homemade bsearch (index) --
    find took : 0 ns
    1 not found
    find took : 0 ns
    1 not found
    find took : 0 ns
    4 found
    find took : 0 ns
    27 found
    find took : 0 ns
    256 found
    find took : 0 ns
    3125 found
    find took : 0 ns
    46656 found
    find took : 0 ns
    823543 found
    find took : 0 ns
    16777216 not found
    find took : 0 ns
    387420489 not found
    -- homemade bsearch (iterators) --
    find took : 0 ns
    1 found
    find took : 0 ns
    1 found
    find took : 0 ns
    4 found
    find took : 0 ns
    27 found
    find took : 0 ns
    256 found
    find took : 0 ns
    3125 found
    find took : 1000100 ns
    46656 found
    find took : 1000100 ns
    823543 found
    find took : 0 ns
    16777216 not found
    find took : 0 ns
    387420489 not found
    -- equal range --
    equal_range took : 683068300 ns
    1 found
    equal_range took : 681068100 ns
    1 found
    equal_range took : 681068100 ns
    4 found
    equal_range took : 679067900 ns
    27 found
    equal_range took : 679067900 ns
    256 found
    equal_range took : 680068000 ns
    3125 found
    equal_range took : 683068300 ns
    46656 found
    equal_range took : 677067700 ns
    823543 found
    equal_range took : 680068000 ns
    16777216 not found
    equal_range took : 678067800 ns
    387420489 not found

Cheers

"Premature optimization... Premature optimization everywhere..." — , Aug 06 '13 at 13:51
It seems very unlikely that equal_range is in fact taking over half a second to complete on a vector of a million items. Do you notice this delay on the console when running the program? Timing functions in this way is also prone to produce incorrect values. — dunc123, Aug 06 '13 at 13:56
@dunc123 Yes, I know... but I can actually see it taking half a second every time. — André Moreira, Aug 06 '13 at 13:57
Unless you are working with special hardware, using nanoseconds as your measurement have little to no use as off-the-shelf hardware does not have accuracy even close to nanoseconds. Other than that, what compiler flags (optimization level) are you using? How is the experiment setup? — David Rodríguez - dribeas, Aug 06 '13 at 13:59
@DavidRodríguez-dribeas I grant you that, and I know it's not the best measure in the world but it's the metric I can use — André Moreira, Aug 06 '13 at 14:00
Ah OK. This type of measurements on a debug build are meaningless. Also, concerning what David said, maybe make the test longer and measure in miliseconds. — juanchopanza, Aug 06 '13 at 14:02
@VaughnCato - compiler specific differences? It's probably using gcc. — André Moreira, Aug 06 '13 at 14:06
@juanchopanza, in release build I get very different results indeed. equal_range is quite fast — André Moreira, Aug 06 '13 at 14:07
what kind of "garbage" can cause this performance difference? — André Moreira, Aug 06 '13 at 14:11
@Candag: always measure in Release/Optimized builds, because this is what matters. The longer answer is that templates benefit a lot from optimizations (inlining) and thus when comparing two template solutions you may get widely different performance results (even ratios) depending on how you optimize. — Matthieu M., Aug 06 '13 at 14:14
@juanchopanza as you were the first to point me in the right direction, put that in an answer and I will accept it as the right one! — André Moreira, Aug 06 '13 at 15:07
@MatthieuM. Thank you for your answer. I just stumbled over the same problem, that equal_range is sooo slow in DEBUG mode compared to when I write a small my_equal_range function myself which does the same thing. I find it annoying that the performance of this function is so different in Debug and Release. I did not measure it, but my program runs in less than one second versus several minutes, just by switching equal_range with my_equal_range. I know no other STL function with such a huge difference, at least none that I need to use within a loop. — Fabian, May 12 '16 at 12:30
@Fabian: Do you have some debug checks activated? A number of checks can be performed in debug to help ensure that iterators are properly used. These are usually activated via preprocessor directives and may be removed "locally" for hot-spots by defining/un-defining appropriately. Another solution could maybe to switch to O1 with debug symbols. — Matthieu M., May 12 '16 at 12:34

score 0 · Accepted Answer · answered Aug 06 '13 at 14:13

In debug build in VS2012 I got

-- equal range --
equal_range took : 796079600 ns
1 found
equal_range took : 792079200 ns
1 found
equal_range took : 785078500 ns
4 found
equal_range took : 786078600 ns
27 found
equal_range took : 785078500 ns
256 found
equal_range took : 784078400 ns
3125 found
equal_range took : 785078500 ns
46656 found
equal_range took : 786078600 ns
823543 found
equal_range took : 784078400 ns
16777216 not found
equal_range took : 784078400 ns
387420489 not found

whereas in a release build I got

-- equal range --
equal_range took : 0 ns
1 found
equal_range took : 0 ns
1 found
equal_range took : 0 ns
4 found
equal_range took : 0 ns
27 found
equal_range took : 0 ns
256 found
equal_range took : 0 ns
3125 found
equal_range took : 0 ns
46656 found
equal_range took : 0 ns
823543 found
equal_range took : 0 ns
16777216 not found
equal_range took : 0 ns
387420489 not found

The iterator checks in a debug build will slow it down lots.

find vs equal_range and performance

1 Answers1