C++ Logo


Advanced search

Re: Why is std::priority_queue so slow?

From: Kwasi Mensah <kwasi.mensah_at_[hidden]>
Date: Wed, 7 Jul 2021 10:47:12 -0400
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

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]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-discussion

Received on 2021-07-07 09:47:26