[Lanthum]

Hello,

 I am in the process of designing my event scheduler/queue system, and I was hoping to get some ideas on how others had done it.  It is for a completely original codebase in C++, so I don't have any legacy issues with putting it into an old codebase.  I am hoping some of you might be able to share - either based on just ideas or experience implementing your own.


Do/should you use the event queue for everything, including every player action/command?  For example, say a command just sends output to the player - is there any benefit to using the queue for that?

What data structure do you use/is best?  I was originally thinking about using a doubly linked list, or a STL list.  But I want to make sure I am using the fastest possible structure since many things will be added and removed from it.


Any other ideas, thoughts, wisdom you might have gained from implementing one that you would like to share.


Thanks,

[Rhuarc]

In MudCore, I decided to have both a game loop, and an event system. The primary reasoning behind this was that many things happen all the time, (such as time passing, getting hungry, etc), and so are not best suited for events, while other things happen only occasionally (you are jumped by a mob), and do make sense to happen as events. So, in MudCore at least, events happen outside of the normal game loop, and may interrupt it, depending on the event.

As far as data structures go, I decided to use a simple list to hold all of the events, as I would be adding and deleting events very often, and lists are best suited for that. Also, I don't have one big list of events to search through, but rather each object that can receive events has their own list, so I don't have to search through a ton of events just to find out that the actor in question does not have any events to act on.

MudCore is also C++, and one important aspect of our event system is that actors can override the event handler, so that two different actors can treat the same event differently.

You can read more detailed information about our Event system in the (outdated, sorry) MudCore doc by logging in as 'guest' (password 'guest') to our perforce web at http://perforce.tarmongaidon.org:8080 and opening the //depot/MudCore/Main/Doc/... folder. Select the "MudCore.pdf" file and select "Open head revision in Browser".

(This link should work also...)
http://perforce.tarmongaidon.org:8080/@md=d&c....ore.pdf

[Yui Unifex]

Dispatching tasks is a relatively simple thing to do. Basically, the mud needs to sleep until it is time to dispatch the next task, or it is interrupted by some occurrance like player input.

Determining the which task is next is easy with a priority queue. The C++ standard library contains a implementation you can pop right into your codebase. Using a simple list would mean you have to go through each and every task to determine which fires next. With a priority queue, you can simply ask when the top task needs to fire, and sleep until that time.

Originally Posted by (Lanthum @ foo) Do/should you use the event queue for everything, including every player action/command? For example, say a command just sends output to the player - is there any benefit to using the queue for that?

I don't think you should queue that sort of thing. In my opinion, only tasks that work on a time delay need be queued. I do not recommend you use global limits on your scheduler to restrict which commands may be issued in battle, since the limit would also restrict other commands issued to the server. Instead, I'd simply restrict commands to that player's turn in battle, or only allow players to execute a command that he has enough action points for. Action point regeneration would be a scheduled task.

[Rhuarc]

Originally Posted by (Yui Unifex @ Mar. 05 2005,11:44) Determining the which task is next is easy with a priority queue. The C++ standard library contains a implementation you can pop right into your codebase. Using a simple list would mean you have to go through each and every task to determine which fires next. With a priority queue, you can simply ask when the top task needs to fire, and sleep until that time.

The only problem with using a priority_queue is that you cannot iterate through them. (they have no iterators) You can only access the .top member. So if you have any need at all for scanning through your events, a priority_queue is not a good choice.

[Yui Unifex]

Originally Posted by (Rhuarc @ Mar. 05 2005,12:31) The only problem with using a priority_queue is that you cannot iterate through them. (they have no iterators) You can only access the .top member. So if you have any need at all for scanning through your events, a priority_queue is not a good choice.

Of course not. It's a queue so it should be accessed like one. The priority_queue is only for the benefit of the scheduler. Other objects should hold direct references to events if they need them.

[eiz]

Originally Posted by (Rhuarc @ Mar. 05 2005,12:31) The only problem with using a priority_queue is that you cannot iterate through them. (they have no iterators) You can only access the .top member. So if you have any need at all for scanning through your events, a priority_queue is not a good choice.

This is true, however priority_queue is a trivial class implemented on top of the STL heap algorithms (push_heap, pop_heap, make_heap, sort_heap and is_heap), so it's trivial to write your own variant if you need this functionality.

[Rhuarc]

Originally Posted by (eiz @ Mar. 05 2005,16:27) This is true, however priority_queue is a trivial class implemented on top of the STL heap algorithms (push_heap, pop_heap, make_heap, sort_heap and is_heap), so it's trivial to write your own variant if you need this functionality.

priority_queue is typically an adapted vector, and is little more than a sorted vector, but yes, you could easily implement your own heap based priority_queue in just a few lines of code. However, the lack of iterators is the sole reason that priority_queue exists at all. They were removed for a reason.

I'm curious though, which do you think would be more expensive; iterating through a few thousand list elements every few seconds? or sorting a few thousand list elements several times, every few seconds? (every insert into the priority queue is going to cause the queue to be resorted (or resized, if the element is inserted into the proper location to keep the list sorted)).

I still maintain that a (standard) priority_queue is not an efficient data structure for this. While yes, it's true that lookups will be faster, inserts and deletes will be much slower, and in an event system, you are going to have alot of inserts and deletes.

You could certainly roll your own, but personally, I would wait and see if the performance merits it. (follow the 80/20 rule).

[Lanthum]

Originally Posted by Also, I don't have one big list of events to search through, but rather each object that can receive events has their own list, so I don't have to search through a ton of events just to find out that the actor in question does not have any events to act on.

Without one big list - wouldn't it make the server slower then, because there are many lists to check?  Maybe I'm seeing this wrong, but what I am understanding is that every object (char, obj, room, etc.) has it's own list to check each pulse.  If each list isn't checked each pulse, how do you handle knowing when to check each list?

Originally Posted by In my opinion, only tasks that work on a time delay need be queued.

The more I read everyone's ideas, the more I agree with this statement.  It was what I was kind of leaning towards before, but wasn't sure about.

Originally Posted by Basically, the mud needs to sleep until it is time to dispatch the next task, or it is interrupted by some occurrance like player input.

So does this mean you use your event system for more than just basic player commands?  Because that was what I was thinking more of before, but am still not sure about.  Movement, talking, combat, spells, regeneration, effects, etc ALL could be an event that fires.  But again - I wonder if this is going overboard on the event system.


Thanks for all the ideas so far.

[Yui Unifex]

Originally Posted by (Rhuarc @ Mar. 05 2005,18:26) I still maintain that a (standard) priority_queue is not an efficient data structure for this. While yes, it's true that lookups will be faster, inserts and deletes will be much slower, and in an event system, you are going to have alot of inserts and deletes.

I think you should be more worried about how clearly the datastructure fits the task than how performant it is until you've profiled and determined that it's a bottleneck. A priority_queue is ideal because it does the work of finding the next event to fire for you.

Also, you should not have any deletes. That's what weak referencing is for.

[eiz]

Originally Posted by (Rhuarc @ Mar. 05 2005,18:26) I'm curious though, which do you think would be more expensive; iterating through a few thousand list elements every few seconds? or sorting a few thousand list elements several times, every few seconds? (every insert into the priority queue is going to cause the queue to be resorted (or resized, if the element is inserted into the proper location to keep the list sorted)).

priority_queue is a binary heap (as I said, it's just a wrapper around the standard heap functions). Push and pop are O(log N). They do not have to 're-sort' the list, only perform updates to maintain the heap invariant. Basically what happens is the new item is added to the end of the vector (amortized constant time), and is then pushed up the tree. Since a binary heap is a complete binary tree (each level is completely filled from left to right), the tree never has more than log2 N levels, and this is efficient.

Normally I would agree to wait and see if it's a performance issue, but it's such a straightforward and easy optimization...

[Yui Unifex]

Originally Posted by (Lanthum @ Mar. 05 2005,18:49) Originally Posted by Basically, the mud needs to sleep until it is time to dispatch the next task, or it is interrupted by some occurrance like player input. So does this mean you use your event system for more than just basic player commands? Because that was what I was thinking more of before, but am still not sure about. Movement, talking, combat, spells, regeneration, effects, etc ALL could be an event that fires.

Yes, definitely. In fact I don't use the event system for player commands at all. Those are either executed immediately or the player is told why they can't be executed -- e.g., "You're exhausted", or "You don't have enough action points to do that", etc.

[Rhuarc]

Originally Posted by (Yui Unifex @ Mar. 05 2005,19:02) I think you should be more worried about how clearly the datastructure fits the task than how performant it is until you've profiled and determined that it's a bottleneck. A priority_queue is ideal because it does the work of finding the next event to fire for you. Also, you should not have any deletes. That's what weak referencing is for.

Exactly. and IMHO, a priority_queue is not the ideal structure for this work. Oh, maybe it's OK if all you have to worry about is when the event fires. If you never have to do any other processing on the events, then sure - use a priority_queue if you like - but even then, it's a trade off between the number of inserts/deletes into the queue, and the number of items you have to iterate through. Only solid profiling is going to give a "this container is better in these circumstances than that container" kind of answer. Generally though, adding/removing elements to a vector is slower (by far) then adding/removing elements to a list. Adding/removing elements in a sorted manner to a vector is slower still.

(Weak referencing does not apply - the elements still have to be removed from the queue at some point, regardless of how that's done)

[eiz]

Originally Posted by (Rhuarc @ Mar. 05 2005,22:46) Exactly. and IMHO, a priority_queue is not the ideal structure for this work. Oh, maybe it's OK if all you have to worry about is when the event fires. If you never have to do any other processing on the events, then sure - use a priority_queue if you like - but even then, it's a trade off between the number of inserts/deletes into the queue, and the number of items you have to iterate through. Only solid profiling is going to give a "this container is better in these circumstances than that container" kind of answer. Generally though, adding/removing elements to a vector is slower (by far) then adding/removing elements to a list. Adding/removing elements in a sorted manner to a vector is slower still. (Weak referencing does not apply - the elements still have to be removed from the queue at some point, regardless of how that's done)

Actually, no, you don't need to profile to know how these two structures will perform compared to each other: complexity analysis suffices just fine. Imagine this scenario using your unsorted list (or set of lists, it doesn't matter - you still have to process every non-empty queue): you have 1000 events in the queue. Each of these matures (becomes ready to fire) one at a time. Now, at each time interval, you have to walk the entire list to find which events to fire. Thus, this will take sum(1,1000) == 500500 iterations. Adding and removing 1000 elements to a binary heap 1 at a time is N log2 N ~= 9965 iterations. As I said before, appending to a vector is amortized constant time. It is not slow.

Now if the events in your queue never expire and you never have to process them, I suppose using a list could be a win.

edit: All of this, BTW, is from experience, but event usage patterns may differ for your mud. For instance, Aetas (which has had, at various times, performance problems ranging from horrific to completely ludicrous) does not have any fixed time interval (it's always based on the fire time of the next scheduled event, or an infinite select() on its input descriptors if there are no pending events, which vastly improves responsiveness), and thus can't get away with only doing checks, say, every quarter of a second. However, I'm fairly sure that even with a fixed interval, the list solution is much more costly.

[Kylotan]

Originally Posted by (Lanthum @ Mar. 05 2005,18:49) Without one big list - wouldn't it make the server slower then, because there are many lists to check?  Maybe I'm seeing this wrong, but what I am understanding is that every object (char, obj, room, etc.) has it's own list to check each pulse.  If each list isn't checked each pulse, how do you handle knowing when to check each list?

Well, you can keep a list of when each list is set to be needed. That seems like it would overcomplicate things. I go with a global list personally.

Originally Posted by "In my opinion, only tasks that work on a time delay need be queued." The more I read everyone's ideas, the more I agree with this statement.  It was what I was kind of leaning towards before, but wasn't sure about.

Interestingly, that's how my current system works, but in my next I think I'm going to queue everything. There's a certain benefit to having almost everything executing from the same part of the code.

Originally Posted by So does this mean you use your event system for more than just basic player commands?  Because that was what I was thinking more of before, but am still not sure about.  Movement, talking, combat, spells, regeneration, effects, etc ALL could be an event that fires.  But again - I wonder if this is going overboard on the event system.

I would have thought that talking, combat, spells, regeneration are precisely the things that an event system is there for? These all represent acts that take place some time in the future so it makes sense to create an event for them and trigger it when necessary. It's only ever going overboard if you complicate things, and I'd think that moving these concepts into an event-based system would simplify them in several ways.

[Rhuarc]

Originally Posted by (eiz @ Mar. 06 2005,07:22) Actually, no, you don't need to profile to know how these two structures will perform compared to each other: complexity analysis suffices just fine. Imagine this scenario using your unsorted list (or set of lists, it doesn't matter - you still have to process every non-empty queue): you have 1000 events in the queue. Each of these matures (becomes ready to fire) one at a time. Now, at each time interval, you have to walk the entire list to find which events to fire. Thus, this will take sum(1,1000) == 500500 iterations. Adding and removing 1000 elements to a binary heap 1 at a time is N log2 N ~= 9965 iterations. As I said before, appending to a vector is amortized constant time. It is not slow.

Oh, a little profiling never hurt anyone.

I've run a test comparing inserting/deleting and reviewing (iterating through each element) for lists, vectors and priority_queues, and here are the results when running with various amounts of elements in the list, in debug mode. (Note: I use the stlport library, instead of the horrible microsoft implementation).

[code]
Container Inserts Deletes Review Total

Mean = 10%, Count = 1000

list<int> 0.00098 0.00058 0.00046 0.00202
vector<int> 0.00038 0.00025 0.00009 0.00073
priority_queue<int> 0.00078 0.00103 0.00013 0.00194


Mean = 10%, Count = 10000

list<int> 0.00979 0.00585 0.00460 0.02025
vector<int> 0.00404 0.00257 0.00097 0.00758
priority_queue<int> 0.00763 0.01217 0.00152 0.02131


Mean = 10%, Count = 100000

list<int> 0.09417 0.05871 0.04641 0.19929
vector<int> 0.03514 0.02548 0.01000 0.07062
priority_queue<int> 0.07511 0.14003 0.01738 0.23252


Mean = 10%, Count = 1000000

list<int> 0.95361 0.58694 0.47611 2.01666
vector<int> 0.35431 0.25473 0.09621 0.70525
priority_queue<int> 0.77189 1.54682 0.19399 2.51270
[/quote]

(Time listed is in seconds)

Two things to consider:

1: The vector and list containers iterate through all elements, while the priority_queue stops once the value at the top exceeds the top() value. This means that, for a vector or list, the "Review" column indicates the time spent reviewing all 'Count' elements, while the priority_queue time reflects only reviewing the 'Mean' percentage of the elements.

(the 'mean' is a percentage of the total that are all the same value, and represent the 'top()' of the priority_queue)

2: The priority_queue review period must delete each element it reviews from the queue as it is reviewing it. So, the 'delete' column for the priority_queue only reflects the time it took to delete the remaining queue and the 'Review' column reflects the additional time required to do the deletes,, while the delete column for list and vector reflects the total time taken to delete all elements.

Here is the container code...

[code]
void TimeList()
{
CTimer Timer;
unsigned int nValue;
int nWatch = 1;
t_cli _cli;

// insert all values into the list. Record the time taken
Timer.Start();
for (nValue=0;nValue<(g_aValues.size()-1);nValue++)
List.push_front(g_aValues[nValue]);
Timer.Stop();

g_Times.list_tmInserts = Timer.Seconds();

// Iterate through all values, record the time taken.
Timer.Reset();
Timer.Start();
for (_cli = List.begin(); _cli != List.end(); _cli++)
{
if ( (*_cli) <= nWatch )
doSomething((*_cli));
else
nWatch++;
}
Timer.Stop();
g_Times.list_tmReview = Timer.Elapsed();

// Delete all list elements
// .clear() would be much faster, but I want to remove each element one
// at a time to simulate how it would be done in a working environment.
Timer.Reset();
Timer.Start();
while ( !List.empty() )
List.erase( List.begin() );

Timer.Stop();
g_Times.list_tmDeletes = Timer.Elapsed();

g_Times.list_tmElapsed = g_Times.list_tmInserts + g_Times.list_tmReview + g_Times.list_tmDeletes;
}

void TimeVector()
{
CTimer Timer;
unsigned int nValue;
int nWatch = 1;
t_cvi _cvi;

// insert all values into the vector. Record the time taken
Timer.Start();
for (nValue=0;nValue<(g_aValues.size()-1);nValue++)
Vector.push_back(g_aValues[nValue]);
Timer.Stop();

g_Times.vector_tmInserts = Timer.Seconds();

// Iterate through all values, record the time taken.
Timer.Reset();
Timer.Start();
for (_cvi = Vector.begin(); _cvi != Vector.end(); _cvi++)
{
if ( (*_cvi) <= nWatch )
doSomething((*_cvi));
else
nWatch++;
}
Timer.Stop();
g_Times.vector_tmReview = Timer.Elapsed();

// Delete all list elements
// .clear() would be much faster, but I want to remove each element one
// at a time to simulate how it would be done in a working environment.
Timer.Reset();
Timer.Start();
while ( Vector.size() > 0 )
Vector.erase( Vector.end()-1 );

Timer.Stop();
g_Times.vector_tmDeletes = Timer.Elapsed();
g_Times.vector_tmElapsed = g_Times.vector_tmInserts + g_Times.vector_tmReview + g_Times.vector_tmDeletes;
}


void TimePriorityQueue()
{
CTimer Timer;
unsigned int nValue;
int nWatch = 1;

// insert all values into the queue. Record the time taken
Timer.Start();
for (nValue=0;nValue<(g_aValues.size()-1);nValue++)
Queue.push(g_aValues[nValue]);
Timer.Stop();

g_Times.queue_tmInserts = Timer.Seconds();

// Iterate through all values, record the time taken.
Timer.Reset();
Timer.Start();
while ( (nValue=Queue.top()) == nWatch )
{
// we have to pop each one off the queue to see the next...
// it is worth noting here that if we decided we still needed this element,
// it would have to be re-added to the queue.
Queue.pop();
doSomething(nValue);
}
Timer.Stop();
g_Times.queue_tmReview = Timer.Elapsed();

// Delete all queue elements
Timer.Reset();
Timer.Start();
while ( !Queue.empty() )
Queue.pop();

Timer.Stop();
g_Times.queue_tmDeletes = Timer.Elapsed();

g_Times.queue_tmElapsed = g_Times.queue_tmInserts + g_Times.queue_tmReview + g_Times.queue_tmDeletes;
}
[/quote]

If anyone wants the full code & VC7.1 project for the test, email me and I'll be happy to provide it. (Your mileage will very though if you use the default stl library).

[eiz]

Your benchmark isn't actually testing event queue operations. The list and vector 'reviews' do not ensure proper ordering. Not only that, but you'll have to repeat the entire scan for each time interval: such is not the case with a priority queue. Care to try again? =)

BTW, the only reason to iterate through a queue or to delete from an arbitrary location is for diagnostics. That's why I suggested using the heap functions if you really need this.

edit: Let me clarify how our event queue works and why we use a priority queue. The top level loop is an event pump: As long as the current time is greater than the scheduled time of the next event, we pop the event and execute it. If the current time is less than the time of the next event, we calculate the time difference and go into an IO wait, until we receive input or the next event is ready to fire. If we were to use a list, at each iteration through the event loop we would need to find every event that was ready to fire, build a list, sort this list, fire the events in the appropriate order, and then go to sleep. A heap is an appropriate data structure. Performance was not the primary reason it was selected: it's just simpler. Although it is faster as well =)

edit2: What is 'nWatch' and why are you incrementing it for the list and vector versions, but not the priority queue version?