Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Zoomby

Priority Queue inefficient?

This topic is 5480 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hi, I use the stl priority queue in a game to hold game events (event with smallest timestamp on the top of the queue). But when I have many Objects (about 200-300) that send events at different times, the delivery of the events gets slow. On the other hand, when all Objects send events at the same time, the speed is ok. Is a Priority Queue inefficient when used in that way, should I use a normal queue instead? Any experience or suggestions? bye chris

Share this post


Link to post
Share on other sites
Advertisement
This sounds like the exact reason why you''d want to use a priority queue, so I can''t see why it would be slow unless you''re doing something wrong or inefficient. The rate of additions to the queue shouldn''t make much difference. What type of object do you store in the queue?

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites
hi, maybe I have another problem.
I store event Objects in the Queue (no pointers to event Objects). Don''t know if it would be better to store pointers, cause I don''t know how it''s implementet in the STL.

Share this post


Link to post
Share on other sites
I guess the problem could be that the priority_queue creates copies of stored objects at some point. This would give you the added overhead of object instanciation, so pointers would be faster.

Anyways:
priority_queue

Also, if I understand correctly, priority_queue performs a sorting algorithm, so that the largest element is on top. I think this is completely unnecessary, since, if you add a message to the queue as soon as it occures, they should already be in the correct order (from least recent to recent), so there''s no need for sorting. Thus queue might be better.

Share this post


Link to post
Share on other sites
Your''re maybe right Wildfire, I should try to store pointers in the queue.

A normal queue won''t work for me, cause you can add a message to the queue with a timestamp in the future. So it remains in the queue until the right time comes to handle it.

Share this post


Link to post
Share on other sites
If you are storing events themselves and not pointers to events then you are most likely suffering from a copy operations each time you put an object in and take it out. Also, depending on the implementation of the queue, it may be copying each event when one gets added or one gets removed. This is implementation dependent.

I am also unsure of what you mean by ''events at different times''. Are you putting events into the queue that are going to be posted much later? If so, then you must be sorting the queue every time something is added. This invokes the copy constructor as well. The larger your structure, the longer the copy takes.

In contrast, if you are using pointers then the copy is only a (on win2k) 32 bit copy, which is very quick.

You might also want to think about two queues, one that is ''immediate'' or close to that - messages that are to be passed next frame and don''t need to be sorted, and those that are further in the future, which do need to be sorted. In this way you are sorting only a subset of all messages in the game.

Alternatively, it might not be sensible to put messages for the future in a queue at all. In my system I have an event manager that is only responsible for collecting events from the current frame, and sending them out at the end of the frame so that next frame they can be acted on. Anything that takes place in the future is tied to a clock manager that will fire off an event once the clock expires.

Not sure if you really need so many events, but then you havn''t describe the kind of game system you are working on.

Nonetheless, pointers should give you a speed increase. What I would do is, on game start, allocate an array of, say, 200 events, and then put the address of each of these into a list. When you need a new event, get it from the ''free list'' and put it''s address into the priority queue. Once it comes out of the queue, put it back into the list. This should be speedy and avoids dynamic allocations during run time - it also lets you put a cap on the events so that, if suddenly you need 300 events, you''re aware of this and can decide if allocating more is the right thing to do, or revisiting your various subsystems is better.

Best of luck.

Share this post


Link to post
Share on other sites
thanks for the reply Sphet. It''s a very interesting idea to put only the future events into a priority queue.
about the game: it''s a rpg game. there are to types of events: events that are posted by the player. these events should normaly be handled very quickly. The other events are from npcs. the idea was to let every non player character post a TICK event to itsself in a short intervals, so there can be npcs with different reaction speed, when posting TICK events in different intervals.
Do you have any idea how efficient this system is, or how to improve it?

Share this post


Link to post
Share on other sites
I agree with Sphet, two Queues might be the way to go. (Had the same idea, but alas he wrote it first )

One question though:
quote:

...So it remains in the queue until the right time comes to handle it...



I don't quite grasp the idea behind that. How do you ensure that is stays in the queue?

Let's say I push an element with 'now' into the queue, and one with 'in two hours'.

Now, if I pop the first element ('now'), the next element will be 'in two hours' regardless of the time that's passed between the polls. Do you always compare the timestamp of an element you get, and leave it in the queue if it's still in the future?

And if so, how do you do it? I see 'top()' to get the topmost element, but have no idea how I could see it's timestamp so I could decide on leaving it in the queue or extracting.

edit: typos + small addition

[edited by - Wildfire on June 17, 2003 3:27:09 PM]

Share this post


Link to post
Share on other sites
The priority_queue contains Event objects. Every Event object saves a timestamp. So when the queue looks at its top and sees an object with a timestamp "in two hours", and the current gametime timestamp is "now", no event is handled, until the gametime reaches the "in two hours" timestamp or an event with an earlier timestamp is added to the queue.

Share this post


Link to post
Share on other sites
Personally, I''d just say store pointers (or smart pointers) to your objects, make sure that you alter the sorting function to take this into account, and leave it. Your slowdown is almost certainly due to the time involved in copying events, and moving to pointers will eliminate this.

[ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost
Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!