C++ Logo


Advanced search

Re: Why is std::priority_queue so slow?

From: iSauron <isauron_at_[hidden]>
Date: Wed, 07 Jul 2021 18:41:07 +0000
Hi Kwasi Mensah!

Thank you very much for your time.
I will take note of these and search to learn about it and improve my coding,
best regards! Isauro

Sent with [ProtonMail](https://protonmail.com/) Secure Email.

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, July 7th, 2021 at 16:47, Kwasi Mensah <kwasi.mensah_at_[hidden]> wrote:

> Doing a super quick look over your code, it doesn't seem to be exception-safe, assumes memory allocation doesn't fail, and might be generating extra calls to the constructors/destructors for temporaries. I'm guessing the error-checking that the standard library has to do is what slows it down. You should run your test again with some combination of exceptions being turned off, objects that do actual work in their constructor/destructor and using an allocator with a restricted amount of memory
> On Wed, Jul 7, 2021 at 9:16 AM iSauron via Std-Discussion <std-discussion_at_[hidden]> wrote:
>> Hi there!
>> As you can see in the subject, I post this message to know why is std::priority_queue slow.
>> As a background context, I am a computer engineer student and I wanted to develop some data structures for fun and improve my C++ knowledge and skills. I decided it would be fun and interesting to speed test them out with std implementations and..
>> I ran some tests (with stack, vector, queue, deque, priority_queue for now) where I push 480000000 elements onto the diferent data structures and pops them afterwards. I timed out the amount of time and time per call for push and pop implementations.
>> The results for the priority_queue tests are as follows:
>> Executed with a Intel Core i5-4210CPU 1.70GHz and 8Gb of RAM.
>> My priorityqueue implementation:
>> Total Push time: 0.53 seconds
>> Total Pop time: 0.94 seconds
>> STD implementation of priorityqueue
>> Total Push time: 11.90 seconds
>> Total Pop time: 147.205 seconds
>> Surprisingly, std::priority_queue is very slow compared to other std implementations, I ran many tests and I don't know if I'm doing things right, am I missing something? If not, why is it so slow? Is it implemented as a linked list of nodes? If so, why?
>> You can check out the code and tests I ran here https://gitlab.com/iSauron/cpp-utils, you can also run the tests by executing:
>> - make all
>> - ./stress.test
>> The priority queue might be a little confusing to find out in my implementation, it is called heap. It is located in file src/ads/heap.hpp, in the definition of class MinHeap, you can find out push and pop implementations for the priority_queue.
>> Thank you in advance for taking the time to read this
>> Cordially, Isauro López Cortegano
>> Sent with [ProtonMail](https://protonmail.com/) Secure Email.
>> --
>> Std-Discussion mailing list
>> Std-Discussion_at_[hidden].org
>> https://lists.isocpp.org/mailman/listinfo.cgi/std-discussion

Received on 2021-07-07 13:41:13