Performance difference between std::priority_queue vs std::set

Question

I am testing the performance difference between priority queue implementation of std::priority_queue vs implementation using std::set.

I have overloaded the < operator to sort based on score, in case when scores are equal use the next argument i. Also I am just calling the push,pop and top function to find the total time taken for these three operations.

In both implementation I am calling this 'timeQueue' function over 200 iterations and averaging the time obtained. I am seeing the std::set implementation takes around 38% faster. What could be the reason. Thank you.

(These are just for testing purpose)

std::set implementation

void timeQueue()

{
        NodeData res;
        for(int i=1;i<=500000;i++)
        {
                
                auto score = rand() %10000000;
                NodeData n1 = {i,i,score,i,i};
                // push:
                priorityList.insert(n1);
                
        }       
        for(int i=1;i<=500000;i++)
        {       
                std::set<NodeData>::iterator it = priorityList.begin(); 
                // top:
                auto s = it->id;
                // pop:
                priorityList.erase(it);
        }
}

Similarly, std::priority_queue

void timeQueue()
{
 NodeData res;
        for(int i=1;i<=500000;i++)
        {
                auto score = rand() % 10000;
                NodeData n1 = {i,1,score,1,1};
                priorityList.push(n1);
        }
        for(int i=1;i<=500000;i++)
        {
                res = priorityList.top();
                priorityList.pop();
                //std::cout<<res.id<<std::endl; 
        }
}
};

Also, make minimal reproducible examples. Why are you not using the same modulus in the two tests? You should preferably generate the test data before running the tests and then feed both the same data. You now spend time calculating the test data - and you are not doing it the same way in both tests. — Ted Lyngmo
@user253751 Those are push, pop, top equivalent when using std::set — user8349980
Note that regarding the benchmark the performance outcome can be significantly different. Indeed, the container target different cases. For example, std::priority_queue can be constructed from many element in a more efficient way than std::set. The same is true for the insertion of many element. Both cases are computed in O(n) time for std::priority_queue while it is O(n log n) for std::set. — Jérôme Richard
@JérômeRichard I was expecting a worst performance from std::stl because of the 0(n log n) insertion time. But I am confused with the results I am getting. — user8349980

user8349980 user8349980 · Accepted Answer · 2020-10-06T11:05:46

I think the reason for this performance difference is in set the elements are randomly generated and if by chance the generated elements are not unique, they are not inserted. Hence in effect, the std::set will have lesser elements than the std::priority_queue. And so lesser execution time.

Performance difference between std::priority_queue vs std::set

1 Answers