Top Mud Sites Forum Return to TopMudSites.com
Go Back   Top Mud Sites Forum > Mud Development and Administration > MUD Coding
Click here to Register

Reply
 
Thread Tools
Old 03-04-2005, 03:39 PM   #1
Lanthum
Member
 
Join Date: Oct 2002
Location: Suburbs of Chicago
Posts: 138
Lanthum is on a distinguished road
Send a message via MSN to 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,
Lanthum is offline   Reply With Quote
Old 03-05-2005, 10:30 AM   #2
Rhuarc
Member
 
Join Date: Jul 2003
Posts: 50
Rhuarc is on a distinguished road
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 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...)
Rhuarc is offline   Reply With Quote
Old 03-05-2005, 11:44 AM   #3
Yui Unifex
Senior Member
 
Join Date: Apr 2002
Location: Florida
Posts: 323
Yui Unifex is on a distinguished road
Send a message via ICQ to Yui Unifex Send a message via AIM to Yui Unifex
Question

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.

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.
Yui Unifex is offline   Reply With Quote
Old 03-05-2005, 12:31 PM   #4
Rhuarc
Member
 
Join Date: Jul 2003
Posts: 50
Rhuarc is on a distinguished road
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.
Rhuarc is offline   Reply With Quote
Old 03-05-2005, 01:10 PM   #5
Yui Unifex
Senior Member
 
Join Date: Apr 2002
Location: Florida
Posts: 323
Yui Unifex is on a distinguished road
Send a message via ICQ to Yui Unifex Send a message via AIM to Yui Unifex
Question

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.
Yui Unifex is offline   Reply With Quote
Old 03-05-2005, 04:27 PM   #6
eiz
New Member
 
Join Date: Feb 2005
Posts: 25
eiz is on a distinguished road
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.
eiz is offline   Reply With Quote
Old 03-05-2005, 06:26 PM   #7
Rhuarc
Member
 
Join Date: Jul 2003
Posts: 50
Rhuarc is on a distinguished road
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).
Rhuarc is offline   Reply With Quote
Old 03-05-2005, 06:49 PM   #8
Lanthum
Member
 
Join Date: Oct 2002
Location: Suburbs of Chicago
Posts: 138
Lanthum is on a distinguished road
Send a message via MSN to Lanthum
Lanthum is offline   Reply With Quote
Old 03-05-2005, 07:02 PM   #9
Yui Unifex
Senior Member
 
Join Date: Apr 2002
Location: Florida
Posts: 323
Yui Unifex is on a distinguished road
Send a message via ICQ to Yui Unifex Send a message via AIM to Yui Unifex
Question

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.
Yui Unifex is offline   Reply With Quote
Old 03-05-2005, 07:17 PM   #10
eiz
New Member
 
Join Date: Feb 2005
Posts: 25
eiz is on a distinguished road
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...
eiz is offline   Reply With Quote
Old 03-05-2005, 08:12 PM   #11
Yui Unifex
Senior Member
 
Join Date: Apr 2002
Location: Florida
Posts: 323
Yui Unifex is on a distinguished road
Send a message via ICQ to Yui Unifex Send a message via AIM to Yui Unifex
Question

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.
Yui Unifex is offline   Reply With Quote
Old 03-05-2005, 10:46 PM   #12
Rhuarc
Member
 
Join Date: Jul 2003
Posts: 50
Rhuarc is on a distinguished road
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)
Rhuarc is offline   Reply With Quote
Old 03-06-2005, 07:22 AM   #13
eiz
New Member
 
Join Date: Feb 2005
Posts: 25
eiz is on a distinguished road
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.
eiz is offline   Reply With Quote
Old 03-06-2005, 09:24 AM   #14
Kylotan
Member
 
Join Date: Jun 2003
Location: Nottingham, UK
Home MUD: Abattoir (Smaug)
Home MUD: ex-Jellybean (Smaug)
Home MUD: ex-Dark Chambers (Merc)
Posts: 174
Kylotan is on a distinguished road
Send a message via ICQ to Kylotan Send a message via AIM to Kylotan Send a message via MSN to Kylotan Send a message via Yahoo to Kylotan
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.

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.

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.
Kylotan is offline   Reply With Quote
Old 03-07-2005, 07:47 PM   #15
Rhuarc
Member
 
Join Date: Jul 2003
Posts: 50
Rhuarc is on a distinguished road
Rhuarc is offline   Reply With Quote
Old 03-07-2005, 08:22 PM   #16
eiz
New Member
 
Join Date: Feb 2005
Posts: 25
eiz is on a distinguished road
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?
eiz is offline   Reply With Quote
Old 03-07-2005, 09:02 PM   #17
Rhuarc
Member
 
Join Date: Jul 2003
Posts: 50
Rhuarc is on a distinguished road
Well -- the test I did was definately oriented towards an approximation of how events might appear in MudCore. But how is it not testing event queue operations? As far as the list and vector reviews not showing proper ordering, the order should not matter, since each element is visited anyway.

Maybe in your system. In MudCore however, there are reasons to review events and possibly act on or modify them dependant on the state of the actor, world, or particular rule-set being applied at the time. This is why I stated earlier that flexibility was important to us.

You'll notice, I'm only iterating through the members of the queue that are firing, once I get beyond those members, it leaves the loop.

So - in your system, you rarely have events that happen in the same time cycle? One of the reasons I coded the TimeQueue() to iterate through the events, is because we have alot of events that happen in the same time cycle.


One interesting note about my testing is that in release mode, this same test shows the priority_queue running faster, by almost 2/100ths of a second, instead of the much slower speed shown here.
Rhuarc is offline   Reply With Quote
Old 03-07-2005, 09:12 PM   #18
eiz
New Member
 
Join Date: Feb 2005
Posts: 25
eiz is on a distinguished road
Well, in Aetas, since there is no fixed time interval, we could be getting numerous events that are ready to fire, but were queued to fire at different times. So if we find out that events at times 6, 4, and 1 are ready to fire, we need to order these properly. I don't know how MudCore works, but I'll take your word that a list matches how your system is set up.

As for modifying events, we handle this in a more declarative fashion: instead of modifying the event queue itself, the event knows how to detect changed conditions. For example, an event applied to a player will have a weak reference to this player so that it knows if they have been disconnected.

So I would say to choose the data structure that best fits your event model. For us, that is a priority queue. Your mileage may vary =)

edit (boy, I'm doing a lot of these tonight): I think your benchmark demonstrates that all of the data structures have pretty good performance here, and the difference will probably only be noticeable on your 'ps' output. Better to worry about optimizing the amount of time you spend waiting for IO. (fire and brimstone, stupid censorship), most muds get away with iterating through the entire game dataset non-stop, I don't know why we're even discussing it...
eiz is offline   Reply With Quote
Old 03-07-2005, 09:36 PM   #19
Rhuarc
Member
 
Join Date: Jul 2003
Posts: 50
Rhuarc is on a distinguished road
Well, it was worth the effort. If nothing else, this little benchmark is what finally convinced me to spend the 10 minutes (5?) to upgrade to the STLport library.

[code]

// STLport version

Mean = 10%, Count = 1000000

Container Inserts Deletes Review Total
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]

[code]

// Microsoft STL

Mean = 10%, Count = 1000000

Container Inserts Deletes Review Total
list<int> 10.11678 18.21594 0.67912 29.01184
vector<int> 0.95311 0.85283 0.51623 2.32218
priority_queue<int> 2.79621 17.38918 2.11142 22.29680
[/quote]
Rhuarc is offline   Reply With Quote
Old 03-07-2005, 09:45 PM   #20
eiz
New Member
 
Join Date: Feb 2005
Posts: 25
eiz is on a distinguished road
...wow. That's pretty shocking. It almost makes me want to look at their STL to see what perverse and horrifying thing they're doing.

Here are my results:

[code]
Container Inserts Deletes Review Total

Mean = 10%, Count = 1000

list<int> 0.00006 0.00004 0.00000 0.00011
vector<int> 0.00002 0.00001 0.00000 0.00004
priority_queue<int> 0.00003 0.00007 0.00001 0.00012

Mean = 10%, Count = 10000

list<int> 0.00558 0.00041 0.00009 0.00608
vector<int> 0.00018 0.00010 0.00006 0.00034
priority_queue<int> 0.00033 0.00079 0.00010 0.00122

Mean = 10%, Count = 100000

list<int> 0.00830 0.00418 0.00101 0.01349
vector<int> 0.00171 0.00097 0.00028 0.00297
priority_queue<int> 0.00404 0.00958 0.00122 0.01483

Mean = 10%, Count = 1000000

list<int> 0.06068 0.04278 0.00850 0.11196
vector<int> 0.01621 0.00985 0.00285 0.02891
priority_queue<int> 0.03897 0.13929 0.01489 0.19315
[/quote]

Well, all of these numbers are noise so I'm not going to lose any sleep over it. I still think a priority queue is the fastest solution for our system, but we don't support the 386, so I don't think it's going to matter in practice.
eiz is offline   Reply With Quote
Reply


Thread Tools


Ideas on an Event Queue - Similar Threads
Thread Thread Starter Forum Replies Last Post
Mud Ideas Khaavren Bugs and Suggestions 0 08-28-2004 07:06 PM
Mud Ideas Khaavren Bugs and Suggestions 0 08-28-2004 07:06 PM
ideas aidan MUD and RPG Webmasters 3 05-13-2004 02:15 PM
Some ideas. Chikin Advanced MUD Concepts 3 04-26-2004 09:13 PM
Quest Ideas Angel Kenji MUD Administration 3 03-01-2003 04:16 PM

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off

All times are GMT -4. The time now is 07:26 AM.


Powered by vBulletin® Version 3.6.7
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Style based on a design by Essilor
Copyright Top Mud Sites.com 2022