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@lists.isocpp.org> 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:
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 Secure Email.

--
Std-Discussion mailing list
Std-Discussion@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-discussion