Top Mud Sites Forum - View Single Post

eiz · 03-07-2005, 08:22 PM

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?

03-07-2005, 08:22 PM	#16
eiz New Member Join Date: Feb 2005 Posts: 25	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?