Top Mud Sites Forum - View Single Post

eiz · 03-06-2005, 07:22 AM

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.

03-06-2005, 07:22 AM	#13
eiz New Member Join Date: Feb 2005 Posts: 25	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.