Understanding memory allocation of std::queue and std::priority_queue

Question

Continuing from my previous question: std::priority_queue pre-allocate memory memory error

I'm working on a deterministic real time project which has an execution cycle per iteration of couple of hundred micro-seconds.

I'm facing issue where by the push operation on a std::queue and std::priority_queue randomly is taking large amount of time. Push operation generally takes around 5-25 micro-seconds but randomly takes 300 micro-seconds to 5 milli-seconds.

To overcome this issue, I decided to pre-allocate memory for my std::queue and std::priority_queue.
Development OS: Ubuntu 24.04 LTS.
My target OS: vxWorks 7
Language: C++17

Code:

struct DemoStruct
{
    int a;
    float b;
    std::string data;
    bool operator>(const DemoStruct& object) const //Check if greater
    {
        return this->a > object.a;
    }
};

std::vector<DemoStruct> container;

container.reserve(1000);

std::priority_queue
<
    DemoStruct, 
    std::vector<DemoStruct>, 
    std::greater<void>
>   
    mReceiveDataQueue {
        {}, std::move(this->container)
    };

while (i < 10)
    {
        DemoStruct d = {
            .a = 10 - i,
            .b = i * 2.0f,
            .data = "Hello, World!!!"; //Will mostly hold data with 85 characters
        };
        mReceiveDataQueue.push(d); //or mReceiveDataQueue.push(std::move(d))
    }

What I wish to understand, will reserving memory help? From what I understand, every-time in the while loop DemoStruct constructor will be called and (re)allocate memory. With move schematics wouldn't the compiler just move the memory to std::priority_queue or std::queue. So is reserving memory helpful at all or will it be counter-productive? If I use some other data-structure like boost::circular_queue what would be the effect?

I expect that, in this example, there would only be one memory allocation for the queue, in container.reserve(1000). (There would be multiple memory allocations for std::string, unless optimized away by small string optimization). — Igor Tandetnik
– Igor Tandetnik, Commented Feb 16 at 19:19
"I'm working on a deterministic real time project which has an execution cycle per iteration of couple of hundred micro-seconds." I would advise against using either standard library container-adaptor for this. You want a bespoke container that's specifically designed for your use case. — Nicol Bolas
– Nicol Bolas, Commented Feb 16 at 20:01

Tiger Ros · Accepted Answer · 2025-02-16 21:46:39Z

0

Yes, reserving memory should help. std::priority_queues usually use std::vectors are their underlying data structure (you actually specify the structure in your code here: std::vector<DemoStruct>), and a std::vector is stored in a single place in memory, while something like a std::deque can be split up in memory. When a std::vector runs out of space and needs to add another item, it'll find a larger space in memory and move the whole vector there, which is probably what those runtime spikes are. If you make sure it has enough room ahead of time, it shouldn't have to move somewhere else. You could also try changing the underlying structure to std::deque<DemoStruct>, but that might slow things down more overall.

answered Feb 16 at 21:46

Tiger Ros

644 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Understanding memory allocation of std::queue and std::priority_queue

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related