game_loop(), select(), and dual core CPUs

I'm not sure exactly how to figure this out, who to ask, or where to begin looking for this kind of problem. But here goes.

I recently upgraded both of my servers to dual core AMD64 CPUs. Obviously I am thrilled with the new speed and such. But it seems to have had an interesting side affect I wasn't counting on.

In the game_loop handlers that deal with idling descriptors, my code is just like any other Merc derivative. It adds one to the idle counter with each pulse as it runs the game loop. Immortals are all set to idle off the mud after 2 hours. Lately though, this has been drastically cut to somewhere in the neighborhood of 15 minutes.

The deeper implications of this should be clear. This would suggest that all of the handlers that game_loop stalls time for are firing off at greatly increased intervals. Zeno was able to verify this easily enough on his game which is also affected by this ( same server etc ). It appears as though everything has been accelerated to about 8x normal speed.

Is this something that is known and can be corrected? Or have I stumbled into one of those uncharted areas us bleeding edgers often end up in?

When you say "pulse", what do you mean exactly? You would expect that with faster CPUs things will go faster, so that can't be the exact problem.

With select() you get to specify the time to wait before it proceeds (without any IO necessarily happening), what have you set that to?



Can't you do a simple time-of-day check?

Perhaps the above will help clear up what I was getting at. This clock sync stuff happens in game_loop() right at the end of the while( !mud_down ) loop.

By "pulse" I mean it in this usage. The sync is supposed to stall execution for a certain length of time, which in Smaug is 1/4 second by default. It's the heart of the entire update system. And it seems to have found some way to speed itself up majorly, though I couldn't tell you why. It's especially disturbing since I wasn't the only one on the server to have become affected by it.

Part of the problem, and a fairly signifigant part I suspect it is, would be that the entire mu* time system is written for the 32 bit architecture. As with any other software wrtten for a specific architecture, putting it on another architecture may have some... unforseen results.

The long and short of the answer is you've found yourself deep in bleeding edge land and will probably have to do a 64 bit patch (and possibly a dual core patch to boot) for the time system to fix the problem.


Just for reference on comparative datat processing per processor:

32 bit - 2^32 bits per second
64 bit - 2^64 bits per second
dual core 64 bit - 2(2^64) per second

It actually gets very very silly if you start dealing with multiple dual core processors. Just an upgratde from 32 to 64 improves data thruput by a silly amount, adding a 2nd core just compounds the issue. My personal suggestion would be not to run mu*s on a 64 bit system but failing that, go with either a win64 ifdef in the time system or tweak the win32 to account for the massive speed boost from the 64bit dual core (multiply delay by 16 and adjust from there).

I'm not trying to run this in Windows. This is on Fedora Core 6 with a dual core CPU.

I did some further testing, did a 'make clean' and sat idle again. This time instead of being crazy fast at 8x normal speed, it cut me off after 1 hour, which is half of the expected time frame.

So you're probably on to something here. The dual core is probably causing it to literally process twice the information in the same clock cycle. I suppose that throws things off, but hey. I can't just "not run in 64 bit" at this point. Which means a patch it is. But that's the problem. I haven't got any idea where to start on something like this.

Whether you're running in windows or not, the cumputations per cycle are what I gave earlier. The suggested increase all your delays by 16x and adjust from there stands for all operating systems as well. Only reason I suggested the win64 ifdef was so it's something you could include in the standard distro instead of having to support 2 (or perhaps 3) distros. Not sure if theres a simple way to do the time definitions for 64 bit and maintain a single distro but thats the very challenge you face now. Actually, in looking back over that piece of code, if by some miracle pulse_per_second is a multiple of 4 you could have an easy out - quarter the pulses and see how it works compared to a 32bit system.


Oh yeah, Nick, a time of day check would be the simple solution if the only affect the upgrade had was kicking imms early. Unfortunately I suspect this hits on everything that has a timer of any kind - spell durations, wait states, idle timers, etc etc etc as they're all controlled by that function Samson pasted for review. It's just not a pretty situation he finds himself in today.

Well if the solution is as simple as you suggest, I may well be in luck.

My "pulse per second" value is currently 4, which is the Smaug default. Long ago, I added functionality to cset to allow people to fiddle with these values, either to increase or decrease them as they saw fit. Might have been a huge stroke of luck combined with foresight :)

I don't have time tonite anymore to run a test, but I think if I understand you right I can change "pulse per second" to 2 and cut the rate in half? If so, from the look of things now, that should return everything to "normal" speed.

Might have to hook up my linux drive again to see if my single core AMD64 box I use in Windows is affected by this, or if this is in fact an issue with having the second core.

Woah, woah. Changing from 32 to 64 bit does not double your processor speed. So although the processor might be moving more bits around per cycle, you are not doing more cycles per second, therefore not more computations per second.

Just think about it. Think of all the programs that run on both 32 and 64 bit processors, especially games that have cycles and the like. A game designed before 64 bit processors were mainstream won't run twice as fast just because you stick it on a 64 bit machine.

64 bit machines have a larger address space. The number of bits doesn't affect the number of cycles per second.

I will look into this as well, because this is a very worrying symptom, but I would be really, really surprised if this had to do with a direct problem with 64 bits, as opposed to something that worked by accident on 32 bits but was not fully proper to begin with.

120m * 60s = 7200 sec.
28800 pulses / 4 = 7200 sec.

In Smaug, 4 is PULSE_PER_SECOND by default.
So codewise, it should be working fine.

The idle counter for SmaugFUSS:



The idle counter for AFKMud 2.0:



32000 pulses / 4 = 8000 sec, or approximately 133 minutes.

For my test I changed the disconnect to a message display saying when it reached 32000 pulses. Whether it should be or not, I consistently got the 32000th pulse at just over *ONE* hour instead of two. I tested it for AFKMud 2.0 obviously, but there's no difference between that and stock SmaugFUSS as far as the timing loops.

I don't know if it's because of 64 bit, or because of my second CPU core. I'll need to confirm this with a single core CPU running the same OS. Also not sure if it's relevant but I'm running the x86_64 version of Fedora Core 6.

I really am not sure what to say. Dual-cores or 64 bit processors should not double the execution time of a single-threaded application, by causing time to go by twice as quickly. That just doesn't make sense... this is odd, and something else is going on here, not that 64 bits or dual-cores are doubling time's passage.

I just edited my copy of SMAUGfuss to print out the current time at the end of every sleep, like so:



As expected, I get 4 ticks per second. I am running on a dual-core AMD64 processor, with Ubuntu.

I really, really, really don't think that this has something to do with the code note being "64-bit compatible" or "dual-core compatible". If anything, there might be an object file or a library that needs to be recompiled somewhere, so that everything is on par in 64-bit world. (Problems might arise if parts of the library are 32, and others 64.)

I would pursue that route aggressively, making sure that all linked object files were compiled on the same system, using the same compiler, before anything else.

So exactly how would I go about verifying all of that? When I did my system upgrades, I installed FC6 from scratch with no OS on the system. I only copied back important stuff like apache configs, user data, and the /home directory. All of the system libraries should be what got put there by the installer.

I've done "make clean" more often than I care to know and it hasn't helped. I'm also not dreaming this, Zeno said he had the same thing happen to him. Both of us use Smaug based code with vastly different modifications compared to each other.

Someone on TMC suggested this might be to blame, but was speculating:


So I'm testing to see what happens with the (int) cast removed. I'm not even sure why it's there, it comes from stock Smaug. Stock Rom has the same thing, but Merc 2.2 does not.

Oh, and one other question. Is your copy of Ubuntu 32bit or are you using the 64bit install?

Hm, could we get a 3rd party here to make sure they see the pulse speed increase as well? Sign on my MUD or Samson's and see if you notice the speed increase as well. I watched the MUD game time to see the pulse increase, but it's also pretty obvious from the speed of combat.

Removing the (int) cast also had no affect. So that wasn't the problem either. I'm still getting 2 hour idle messages popping at the 1 hour marker.

I am pretty certain what your problem is here. :)

It is nothing to do with 64-bit numbers, dual-CPUs or anything like that.

Your main problem is you have two "select" calls in your main loop.

The first one is used to check for incoming IO on the sockets:


if( select( maxdesc + 1, &in_set, &out_set, &exc_set, &null_time ) < 0 )


The second is attempting to introduce some sort of delay into processing (your "game pulse"):



Note, and this is important, that when I did the Windows version I found that the select here did nothing, and thus I did a Sleep instead, otherwise it just went crazy using CPU very quickly.

Check the documentation for select:


timeout is an upper bound on the amount of time elapsed before select returns.


Notice the words "upper bound". It does not guarantee that the time will actually elapse.

I suggest rewriting with only a single select in the game loop (my preferred option), or make the "time delay" select use a different method, like the Sleep in Windows.

Another approach would be to take the "real" select (the one that waits on sockets), introduce a small fixed delay (eg. 1/10 second), and then check (using the system clock) whether your pulse time is up.

Or, perhaps, make the real select wait 1/4 second, which is your game pulse time anyway, then your only problem is that the select might return sooner, because of TCP IO. Thus you still need a check, to not do a game pulse, if 1/4 second has not elapsed since last time through the loop.

Strange, here are my results from testing the pulse speed.

Normal (32bit) server:


Samson's (64bit) server:


There should be 1min between each of those. (These were taken from the exact same times, so the first log on normal server is the same time on Samson's, just different timezones/clocks a little off)

I stick by my earlier explanation. The select function is intended to wait for asynchronous IO to complete, with a timeout, so that you can do things if the IO does not complete in a reasonable time (eg. your fighting loops).

However if you supply an empty list of IO ports to test, it is possible that the operating system decides to optimize away the wait, on the grounds that the IO will never complete (as there is none to test for), and thus it may as well return immediately.

Ok, so. Not to be a prick or anything, but how would you explain it then that this select() strategy that's been in use in every MERC derivative since 1993 has pretty much stuck to the 1/4 second pulse value it gets? The code I showed you is all stock Smaug, but I've checked all the Merc derives I have and they all have it too. And nobody has ever complained about this until it happened on my server.

But this is what's really going to bake everyone's noodle:

The server popped a kernel panic, had to be rebooted, and afterward the problem seems to have gone away. The mud has returned to the usual timeout period. Load averages on the box have returned to normal. So if we were going to find a reason for this, that time has probably passed. :P

I'm verifying now, just in case I'm on crack.

The kernel realized it was wrong and panicked? Oh well. :)



If the operating system writers decided to optimize select, so that it does not wait, if there are no ports to test, then that would explain it. I presume you have changed operating system versions, in the upgrade to the new hardware?

Anyway, this looks strange, this is from smaug17fuss.tgz:



Unless I am missing something, null_time is never initialized. That looks wrong straight away.

Nick's explanation makes much more sense to me. It is quite possible that the implementation for select changed slightly, given that it still respects the man page. Still, the manpage also says that select is a good way to do a portable sub-second precision sleep, so it would be odd.

Of course, if your kernel rebooting fixed the problem, it's possible that something was screwed up to begin with.

From a processor architecture standpoint, I can assure you that it makes absolutely no sense whatsoever that passing from 32 to 64 bits, and from single-core to dual-core, would double the passing of time. Seriously.

And yes, I am running 64 bit Ubuntu Edgy Eft.


I rewrote my networking code some time ago to better handle timing and stuff like that. I don't know if it's portable to SMAUGfuss, but I'll see what I can do. (Gee, I already have about 5 other patches pending... :P)

Again, this code here has been around forever. We haven't done anything to any of the networking core. If it's busted, it's been that way for 10 years now. Certainly wouldn't surprise me either. It was my understanding though that if you declare something static, it gets filled with zeros. So perhaps when it sees &null_time, it got set to NULL?

And I'm a bit baffled at what the system was doing, but yes, after it rebooted, it seems to have righted itself and the game_loop has gone back to being its normal self again.

http://bugzilla.kernel.org/show_bug.cgi?id=5105

Something Tyche posted on TMC led me to this bug report which does seem to describe the problem, though the bug itself is closed now. So it's possible this may not be the code's fault, but rather a fault in the kernel itself.

> Unless I am missing something, null_time is never initialized.

It's static storage so it's bit zeroed out.

On Windows you have to fool select() with a dummy FD_SET to get it to act as a timer, but the Posix select() is well documented as a timer.

One thing to note is that the timeout parameter MAY be modified during a select call! Posix doesn't guarantee it, so one should always reinitialize the timeout parameter between calls.

OK, I see that the uninitialized static variable will be zero, although I think it is poor documentation to make it implicit.




This is correct, and was going to be my next point. According to the man page for select:


The select function may update the timeout parameter to indicate how much time was left.


Thus the uninitialized variable null_time may be zero the first time, but not necessarily subsequent times. I think it would be neater to make it explicit, each time through the loop.

If the problem has gone away, well and good, maybe the kernel had some obscure timing issue internally.

However I still think that having two selects in each main loop is redundant and looks bad. After all, you are basically waiting for IO to complete, and want to do stuff anyway each game tick. A single select statement, with the timeout adjusted so that it completes when a game tick would be up, should do the trick.

Nick, that will not quite work, because select will exit as soon as it has data. If you do your tick after select, you will be doing it potentially far too early.

(EDIT: after rereading what you wrote, it looks like you might actually have said what I just said... oops. :P)

However having two selects isn't useful; in addition to being redundant, it has a perhaps undesirable consequence:
After any socket is ready for, say, input (so the MUD), the MUD will process that, and then sleep until the next tick.
What this means is that, during the entire remaining time, absolutely nothing will happen. The remaining time is somewhere close to a quarter second, which, while not that much, is still an awful lot of wasted time.

What I feel is the better way of doing this is the following:



This way, you process as much data as there is to be processed, waiting until the next tick if nothing shows up, but not wasting time sleeping, doing nothing at all. Of course, if nothing is there to be done, the process will still just sit there, waiting for something to happen (or for the timeout to elapse).

Incidentally, for those who were following the discussion on client time, this will get rid of that silly lag due to only sending 512b at a time (per tick!), because the MUD will keep sending as much as it can.
Perhaps now it is clear why there appears to be a delay: it sends out 512b, then waits an entire tick (~250ms) before sending out another 512b. So to get 2k, you need to wait a whole second, just for that data to be sent from the server.

> However I still think that having two selects in each main
> loop is redundant and looks bad. After all, you are
> basically waiting for IO to complete, and want to do stuff
> anyway each game tick. A single select statement, with the
> timeout adjusted so that it completes when a game tick would
> be up, should do the trick.

Firstly, the reason select() was used as a timer is that a reliable sub-second timer call wasn't around in the early days of unix. I believe the timing desired in the original mud was 4 pulses per second. One could probably substitute in something like usleep() today and it might have wider support.

Second the above won't work because the timeout parameter is the maximum time to wait. select() can return earlier if there is i/o. That's why one has to use null or empty FDSETS is one wants to use select() as a timer, because it guarantees select won't return early.

Pulses/Ticks are handled differently in other muds. In TinyMud and LPMud the alarm signal handler is used as a reliable timer. In my Windows ports of those muds I use a timer thread that uses sleep().

Exactly. I agree with David here 100%.

Having two select statements is a fundamental design flaw.

Jon, that's precisely the point of the pseudo-code I proposed: it keeps looping, selecting, getting input, and will only exit that loop when the tick time has elapsed.

The whole point is that we really do not want to just sleep. We might as well be servicing our sockets until the next game tick comes around; there's no point sitting around just idling.

I think a reasonable approach would be to have a single select, and have it time out after about 1/2 of a pulse, in this case about 1/8 of a second.

Each time through the loop you check to see if the pulse time is up (that is, if the next 1/4 second has elapsed). If so, you do your pulsing stuff. If not, do nothing. Now the worst case is that you go through the loop just before the pulse was due to arrive (say 1/100 of a second before), and you only wait 1/8 of a second before going through the loop again.

Now to stop "pulse creep" you make the pulse time a fixed amount from the previous (theoretical) time, not from when it actually fired. That is, the pulses should occur every 0.25 seconds from server startup. If a particular pulse processing takes longer than another this won't matter, as the next pulse time is a fixed amount -- not 1/4 of a second from the previous one. To put it another way, you basically want your pulses to occur when the time of day (in milliseconds) divided by 250 is modulo zero.

That's a good idea (both parts), and it's actually what my code does anyway (the part about tick creep, not the 1/8 second part). My pseudo-code should actually be:

next tick time = last tick time + tick delay

instead of

next tick time = time + tick delay

This way, if somehow your tick takes a fair amount of time to process, the next one happens on schedule, even if that means that there isn't as much time to process network data.

This doesn't address the problem of artificially introducing a delay where none is needed. Take an example, where nothing has happened for a while, and someone types "help" - while you are inside your usleep command.

You have now guaranteed that the user has to wait 1/4 second to respond to his/her request (admittedly not long, but why make him/her wait?).

The only way to respond, virtually instantly, to input from players, is to have a single select, with an appropriate (small) timeout. That way, the moment they type something, you respond.

Then, after the (small) timeout elapses, you do your game pulses, to handle the case that you need to do something (like move a mob) even if no player is sending any commands.

However, naturally you check the elapsed time before doing that. In other words, if a fight pulse is 1/4 second, you call the fight pulse routine every 1/4 second, or as close to that as you can.

Exactly. That was what I was trying to say in my wordy way.

Really I would say:


next tick time = last scheduled tick time + tick delay


Let me put it another way. If you make your game pulse time quite large (say 5 seconds), with the existing code it will now take 5 seconds to respond to all command input - obviously unacceptable.

With my proposal, the only thing that would take 5 seconds would be fight rounds, everything else would be instant.

Then you customise the tick time to give fights the pace that you want.

<I>Let me put it another way. If you make your game pulse time quite large (say 5 seconds), with the existing code it will now take 5 seconds to respond to all command input - obviously unacceptable.</I>

Yes but it isn't 5 seconds, it's the difference between 0.25 second and the time it takes to handle all the i/o. Look at the code "between" the selects. :-)

In any case the solution I used for LPMud...

int time_to_call_heart_beat;

void alarm_run (void * ignored)
{
while (1) {
Sleep(2000);
time_to_call_heart_beat = 1;
}

}

game_loop() {
blah blah blah
select i/o

...bottom of i/o loop...
if (time_to_call_heart_beat)
call_heart_beat ();
}


void call_heart_beat (void)
{
static unsigned long alarm_thread = 0;
...
do stuff for heartbeat
...
time_to_call_heart_beat = 0;
if (!alarm_thread) {
alarm_thread = _beginthread(alarm_run, 256, 0);
}
}

This is also portable to unix pthreads with a handful of macros.

> The whole point is that we really do not want to just sleep.

Oh yes you really do want to do nothing.

What? No we don't -- why should we? Why only process player input once per tick? Please explain your position a bit more, I'd be curious to hear your justification.

Making this single change on my MUD -- handling IO as many times as possible between ticks, while avoiding tick creep -- made the entire experience much more fluid. Players noticed it, so it's not just some academic question of what is "better design" for performance and what isn't.

By the way, the code you posted is essentially the same as what Nick and I are advocating. You are most certainly not doing nothing between ticks. I don't understand why you told me that just sleeping is what we want to do when it is not what you are doing.

> What? No we don't -- why should we? Why only process player input once per tick? Please explain your position a bit more, I'd be curious to hear your justification.

If you read the code, you'll see the inverse is actually true. Diku's will not process the player input any faster than one command per 1/4 second. It would actually break the game as designed to do it faster.

There is a difference between servicing the sockets once per tick and processing one command per tick. The code we are talking about services the sockets once per tick and then just sits there. That is what we are trying to avoid.

> There is a difference between servicing the sockets once per tick and processing one command per tick. The code we are talking about services the sockets once per tick and then just sits there. That is what we are trying to avoid.

Again you need to read the code between the selects in Diku. There is no separation of between "servicing sockets" and processing commands in Diku. You are trying to solve a problem that just doesn't exist. It makes no sense to service socket i/o when you don't need the input.

Your design may even peg your CPU servicing a spammers I/O if they stream garbage to a socket. The original code won't. The change would require a rewrite of everything between the selects, separating out what is strictly network I/O from command and update processing. For what purpose? It's not fixing anything, because nothing is broken.

I think you do not understand the problem we are trying to solve, or perhaps you don't think it is a problem for you. You also seem to have forgotten about servicing sockets for output.

The loop we are talking about processes the input for EVERYBODY once per tick. Not just one person's input, but EVERYBODY's. Therefore, it's not just that each client gets one command per tick -- EVERYBODY gets one window per tick to get their packets in and out.

So, if I send a line in, and it wakes up select, and you send something in just after me, you have to wait a tick to get that command processed.

Furthermore, there is the case where (for some reason -- probably for a reason relevant before due to bandwidth concerns, but no longer) SMAUG breaks up >4k into 512b segments. Only processing sockets once per tick means that you only send 512b per tick, or 1k per second. That can create a noticeable slowdown for clients.

A client streaming garbage isn't much of a problem, because the code already has guards against too much data coming in too quickly, and just boots the player.

I do not agree that the change requires such a drastic rewrite. The notion of wait_state already slows down players' input when they do something that should prevent them from doing something else. But, a command that creates no lag, such as typing "help", has absolutely no reason to prevent the player from making another such command.

There already is a separation of out-of-game and in-game commands, using wait_states, so a massive rewrite is not necessary.

It appears to me that we simply disagree that this is a problem. You claim that only one command should be processed per tick, and we claim that is not correct behavior.

It would be helpful if you could explain positions a little more instead of just stating them. It makes it very hard to hold this discussion with you to have to keep dragging information bit by bit out of you. :)

OK, I think I see your point here. You are saying that you are happy to have, effectively:


usleep (250); // adjusted to compensate for IO time


... in your main loop, because you are using it to "pace" player input, keep fights moving at a normal pace, reduce spam, and so on.



Whilst I understand the argument, I think it relies on a compromise, that effectively stops the game designers changing (say) fight round times, or decreasing spam input.

• If you lower the time interval (say to 1/10 of a second), it would be more responsive to player input, but fights would go too fast.
  
• If you raise the time interval (say to 1/2 of a second), it would reduce spam, fights would go slower, and players would complain of lag.

Effectively you are tying in a number of different things:

• Response time to player input
• The rate at which player output is chunked (eg. big help screens)
• Fight round rate
• Other periodic events, like mob movement
• Player spam prevention

All these are being squeezed into a single, compromise, sleep time in your main loop.

A different design could use a single "select" statement to handle input/output as responsively as possible, but then various timer queues to manage the other issues. You might choose to do, for example:

• Max of 2 player commands per second
• Do a fight round 3 times a second
• Move mobs once a second

That is more or less what already happens. The update loop has an inner check that sees if it's time to run various sub-updates, such as the fight round update, mobile AI, area resets, and so forth.

In fact, every character already implements a form of queue for its commands, with the wait state mechanism. What that does it that it won't remove a line from the input buffer as long as the wait state is greater than zero. Therefore, if you want to introduce a (perhaps artificial) delay into input processing, you simply increase a character's wait state.

So, basically, all of this timing stuff is already implemented, even though it's not perfect (wait states, for example, allow the player to queue up commands, but not cancel that queue).

Of course, it would be nicer if this were done properly, with actual time-based queues, threads and so forth; Nick's event manager code solves the problem of a time-based event queue. Nonetheless, changing the select loop in the way we propose does not appear to require such a big rewrite at all. It seems to only entail reworking how/where the select call is made.

> I think you do not understand the problem we are trying to solve, or perhaps you don't think it is a problem for you. You also seem to have forgotten about servicing sockets for output.

There is no problem. At least nothing discussed here relates in any way whatsoever to Samson's timing problem on his MP kernel at all. Diku and all it's derivatives network code ought to work perfectly fine.

> The loop we are talking about processes the input for EVERYBODY once per tick. Not just one person's input, but EVERYBODY's. Therefore, it's not just that each client gets one command per tick -- EVERYBODY gets one window per tick to get their packets in and out.

> So, if I send a line in, and it wakes up select, and you send something in just after me, you have to wait a tick to get that command processed.

This indicates a fundamental understanding of multiplexed I/O or perhaps the select calls in the original code. When the first select polls on the 0 timeout value all the sockets that have I/O ready on them will be set. Nothing wakes up this select as it returns immediately. While the second select is sleeping and really while any other code in the process is running, network I/O is in fact still occuring during that time. Nothing wakes up that select either since the test sets are null. Like I said the second select() is functionally equivalent to usleep().

OTOH, the single select design with a timeout parameter will in fact exhibit the behavior you describe where only a few sockets will be caught everytime you race through the loop. And of course for the handful of ready I/O you are processing you are going to loop through that descriptor list far more times than you would with the Diku design. For example, if you have 10 people online and they all send data within the same 1/4 second, your select loop will at the worst possible case run 10 times. And that means you'll sequentially search the descriptor link list 10 times in the worst possible case. For what purpose do you burn up the CPU, when you could just process all the I/O that has occurred during the last 1/4 second all at once? And frankly that's all that matters to Diku.

> Furthermore, there is the case where (for some reason -- probably for a reason relevant before due to bandwidth concerns, but no longer) SMAUG breaks up >4k into 512b segments. Only processing sockets once per tick means that you only send 512b per tick, or 1k per second. That can create a noticeable slowdown for clients.

Errmmm from the code I've read stock Merc, ROM, Smaug and AFKMud will all send up to 4K per pulse. That would be 16K per second. That's also by design. I don't know any humans that can handle 4 screens of text per second, regardless of whether it slows their client down.

> I do not agree that the change requires such a drastic rewrite. The notion of wait_state already slows down players' input when they do something that should prevent them from doing something else. But, a command that creates no lag, such as typing "help", has absolutely no reason to prevent the player from making another such command.

Given a different game design. I don't think you understand the game affects of allowing players to issue more than one command per pulse. Just one example would be the ability to move past mobiles. Another would be changing the game to strongly favor fast typers and bots. It would be impossible to chase down a speedwalker/robot in a pk game. And if you don't think someone spamming "chat hulabulloo" or "help foo" 100 times a second causes a problem... well I think you do and this is why you would be rewriting many of the routines. See read_from_descriptor()... it breaks the input into a command. So you have to modify the command handler.

> There already is a separation of out-of-game and in-game commands, using wait_states, so a massive rewrite is not necessary.

Not really. I would not define cast "some spell", kick, save as in-game commands because just they have wait states and wear, north, wield, score as out-of-game commands because they don't. Other servers like MOO and Cold have a strong separation, but not Diku. The wait_state is used to delay the processing of commands beyond the pulse rate. So given that you'd modify the command interpretor to add a WAIT_STATE to all the commands. Simple, but the changes are adding up.

> It appears to me that we simply disagree that this is a problem. You claim that only one command should be processed per tick, and we claim that is not correct behavior.

That's the way the Diku game was designed. If you want to see all the neat side effects of that seemingly innocuous decision of your psuedo code simply change it.

> It would be helpful if you could explain positions a little more instead of just stating them. It makes it very hard to hold this discussion with you to have to keep dragging information bit by bit out of you. :)

Given that problem reported has nothing whatsoever to do with the network code present in DikuMuds, I can only wonder why it's necessary to suddenly discuss Diku networking code.

The real design problem of DikuMuds and some others is the tight coupling of the network code to the game itself. It is certainly NOT the two selects()! A network design which used two selects() as Diku does or select()/usleep() are no way better or worse than a design that uses a single select().

Nick's summary.

Yes that covers many of the problems. The problem with Diku code is the tight coupling of the networking code and the game itself. That's not unique to Diku. There is nothing wrong with how it uses select(). As a matter of fact all my servers use single select statements, but the choice to use two can be quite easily defended, despite it not being my code.

As far as I know, we had changed subjects and were talking about other aspects of the network code. Of course this doesn't have to do anymore with the MP kernel etc.

Yes, I was projecting my own solution and misspoke. However, if you get your input in after that one select, you still need to wait a tick, which is what is a problem for me. (Clearly you don't care about it.)

Not according to the MUD it's not. Obviously the OS is still accepting packets and managing its own buffers. But the MUD is not filling up or emptying its buffers and so forth until the sockets are serviced.

To you, perhaps, but not to me. (And by the way, we're not really talking about Diku directly. I have never looked at Merc or Diku source code other than via Smaug's code. I make no claim about those games.) Besides, it's not burning up CPU -- you talk about moving a few kbytes of data, maybe even 50k, like it's a massively expensive operation. You have to do it later anyhow, so what cost is there in doing it now? (Assuming, of course, that you work to prevent tick creep and so forth.)

Then go read the code again. :-) Search for the comment: If buffer has more than 4K inside, spit out .5K at a time -Thoric.

If the output buffer contains more than 4096 bytes, the MUD does not send more than 512 bytes on that pulse. Therefore, if you have, say, 6k, it will take 5 pulses for that buffer to get sent.

It really bothers me to type, say, "commands" or "wizlist" and see the result come to my client choppy and bursty. Maybe you don't care, but I find it very, very unattractive.

Score is fairly clearly an out-of-game command to me, although just as clearly wear, north, wield are not. Nonetheless it's not hard to add a wait of one, if you want to have delay. But:Hardly the massive rewrite you were warning about, no?

My MUD has been running that change for years now and nothing adverse has happened. Players can't use the increased command throughput to their advantage at any time it actually matters due to the stock usage of wait states.

Conversations change focus; the original thread started out by examining the timing code, and we moved on from there. Wherefore is our crime? Please forgive us. :-)

That depends on what you want, doesn't it? You obviously don't care at all about the decreased processing, Nick and I seem to care.

Even if I could rather easily grant your point about input to the MUD (minus the "complete rewrite" part of the side effects), I disagree completely that it's not important to service the output as quickly as possible, especially given the 4k-becomes-0.5k change. Of course, you don't seem to care about choppy output, so this might not bother you.

Thank you though for taking the time to explain your positions at length.

The 0.5K thing is why a lot of folks have changed flus_buffer to spit out larger chunks at once. In AFKMud, this function spits out an entire 4K chunk instead of the original 0.5K. That alone made for a pretty significant difference in the feeling of being "choppy" for most people, and even felt a bit smoother for me connecting over my local LAN.

You do have to be careful with deregulating the select() delay if you make no other considerations. Removing it, or even reducing the sleep period, has what I'd call catastrophic affects on the operation of the game. Not just from a standpoint of spam to the user, but to the game's server as well. I experimented once with removing the delay and could barely get the kill command typed due to the runaway CPU usage. It may well be the result of bad game design, but it's what most Dikus are stuck with for now.

That shouldn't happen; what you probably did was to remove all notion of idle time, and simply kept pounding on the main loop, constantly checking if enough time had gone by to process a tick. That will indeed have very negative effects on the CPU, but it's not what we suggested.

The idea is not to completely remove the delay and busy-loop, but to be waiting on input while "sleeping". So if there is nothing to do, the MUD will do nothing and just wait until the timeout expires.

As I said, my game implements the revised network loop Nick and I have outlined in this thread and the CPU usage is quite normal.

> Not according to the MUD it's not. Obviously the OS is still accepting packets and managing its own
> buffers. But the MUD is not filling up or emptying its buffers and so forth until the sockets are
> serviced.

Now just how much time are you saving when all that a non-blocking socket read does is copy memory from kernel space? None.

> (And by the way, we're not really talking about Diku directly. I have never looked at Merc or Diku
> source code other than via Smaug's code. I make no claim about those games.)

They are all the same. That is at least in reference the claim here that the two selects() was bad design, it is relevant to all Diku derived muds that I know of.

> Besides, it's not burning up CPU -- you talk about moving a few kbytes of data, maybe even 50k, like
> it's a massively expensive operation. You have to do it later anyhow, so what cost is there in doing
> it now? (Assuming, of course, that you work to prevent tick creep and so forth.)

No I haven't at all. In fact I pointed out that you will be executing your loop much more frequently than Diku does. You haven't addressed the scenario I mentioned.

> Then go read the code again. :-) Search for the comment: If buffer has more than 4K inside, spit out
> .5K at a time -Thoric.
> If the output buffer contains more than 4096 bytes, the MUD does not send more than 512 bytes on that
> pulse. Therefore, if you have, say, 6k, it will take 5 pulses for that buffer to get sent.
> It really bothers me to type, say, "commands" or "wizlist" and see the result come to my client choppy
> and bursty. Maybe you don't care, but I find it very, very unattractive.

Okay I found that bit of code. Still all these Dikus will send up to 4K per pulse. In Smaug's case which commands would send more than 4K in output? It looks to me like certain OLC commands that list objects, possibly long help files, command lists, social list, area list, etc. Looks like Derek took the opposite tack from you and essentially nerfed the output rate of commands that produce large output. Those that you've called out of game commands. Since Derek was actually running a game that had 200+ players online at it's peak, I'm certainly not going to gainsay that experience and what he's done. I'd suggest to you that he was doing performance tuning. I don't consider tweaking buffer sizes to be fundamanetal design problems.

> Hardly the massive rewrite you were warning about, no?

I never said any such thing. I said "The change would require a rewrite of everything between the selects, separating out what is strictly network I/O from command and update processing." And that is true.

> Players can't use the increased command throughput to their advantage at any time it actually matters
> due to the stock usage of wait states.

So you've gained nothing from processing I/O faster than the commands are processed, except searching the descriptor list dozens of times more every pulse. Oh wait, no that's not it, you've actually optimized the handling of commands without a wait state. So the player typing "HELP STORY" 20 times a second will have optimal servicing. Brilliant. ;-)

> That depends on what you want, doesn't it? You obviously don't care at all about the decreased
> processing, Nick and I seem to care.

You've actually increased processing per the scenario you ignored my last post. If your argument is now that all things are relative, then it hardly makes any sense to post crap like, "The remaining time is somewhere close to a quarter second, which, while not that much, is still an awful lot of wasted time." and "Having two select statements is a fundamental design flaw."

> Even if I could rather easily grant your point about input to the MUD (minus the "complete rewrite"
> part of the side effects), I disagree completely that it's not important to service the output as
> quickly as possible, especially given the 4k-becomes-0.5k change. Of course, you don't seem to care
> about choppy output, so this might not bother you.

No the code reads that output greater than 4K gets changed to .5K per pulse until it falls below 4K.
One of the interesting things about the Diku loop is that because of the order of execution (input/update/output) all output will be sent every pulse levaing only that that exceeds 4K for the next pass. As noted, the choppy output appears to be something deliberate in Smaug.

Now I searched for the phrase "complete rewrite". Who exactly are you quoting? Is his name StrawMan? ;-)

Yes, but so what? The point is that the MUD is not processing input, and not emitting output. The point is not how much CPU time is saved, but how long I/O takes from the player's perspective. As long as we don't exceed, in real-time, the time until the next pulse, then we don't care how much extra time we spend.

Which one? That I would run the loop more often? Yes I have: it's not a problem, because you're not processing that much I/O to begin with, and since you recheck time till the next tick after each processing loop, you won't get behind schedule.

I'd want to see actual performance measurement before believing that it's that much more efficient to chop data into small chunks. If we're talking about network efficiency, the OS is supposed to take care of that. If we're talking about the time it takes to copy data, well, ok, I agree that tweaking buffer sizes isn't a fundamental design problem. (Then again, I didn't say it was.) What I *did* say was a fundamental design problem was to not bother even sending out output when you are otherwise doing nothing at all.

Yes, I apologize, you did not use those exact words. I got the impression due to your suggesting that it would take a separation of I/O from command/update processing, which to me, if it were to be done completely properly, could indeed entail a fairly substantial rewrite. Unless I misunderstood what you meant, of course.

I believe you misunderstood. I meant that players cannot get an advantage over other players in e.g. combat by typing in lots of commands in the hope to get multiple ones in per tick.

As for the output servicing, I think we've established over and over again that you don't give a hoot either way but it really bothers me to get choppy output. Unless you demonstrate to me that I am wrong to care about choppy output, I suggest that we should declare that issue to be pretty much over due to being an apparent matter of opinion.

We are not talking about the same kind of processing, I think. I am saying that you do not seem to care about the decreased output throughput. Or, put another way, you do not seem to care about the potential to increase output throughput.

I am not sure what point you are making here. And I don't refer to your claims as crap. :-)

Besides, I still don't understand why we should not be sending output when we'd be doing nothing whatsoever instead anyhow. Again, if it has to do with network usage, let the OS's implementation of the network protocol worry about that. And yes, I do consider it a design flaw to be sitting around idle when there is stuff you could be doing (at what is basically no cost as far as the rest of the system is concerned) that you are not doing.

Well, sure, of course it's deliberate. What I'd like to see are the reasons for the decision, and if possible, some data points to back them up.


Let's forget about input for now. As I said, I can see potential problems in properly handling the input case. Let's focus on output. What I'd like to hear from you is simply why we should sit idle when there is output we could be sending.

My original suggestion was that maybe the select with no descriptors might have been timing out prematurely, due to possible optimization, which is what the behaviour is under windows. Thus, that was relevant.

However it seems that rebooting the PC fixed the problem. As I didn't have the problem on my PC I couldn't say for sure whether or not my suggestion would work.

I accept what you have said earlier about the sleep in the main loop as being defensible - up to a point - on the grounds you outlined.

I think you will find however that any large online program (eg. a web server, MMORPG) would never build sleeps into the main loop, simply because they are going for optimal performance.

The main justification for the "sleep select" seemed to be that it reduced the number of times select needed to be called, thus potentially reducing the times through the main loop.

However it seems to me the downside of that is, in return for that saving, and by allowing more user input to "batch up", ready for when the sleep is over, that you are forcing processing of user input to be chunked more. That is, when the 250 ms is up, you have a lot of work to do, possibly even more than 250 ms worth.

However, the design which has more "turns through the loop" will process user input as it occurs, thus smoothing out the processing. This would be particularly noticeable if the thing the user wants to do (maybe a spell lookup) involves a lot of CPU.

The main argument Jon seems to have given against this, as far as I can tell, is that you have lots of useless traversals of the descriptor list. I'm not sure this is really such a big cost, because a linear scan of even 500 elements is very fast. It is probably noise when compared to the time it takes to, say, actually run the tick update function. But it would take actual performance measurements to know for sure.

Effectively the dual-select technique is a variant of doing IO by polling. That is, you sleep for a while (to give the CPU a chance to do something else), and then you poll the IO list to see if there is anything to do.

I accept that this works on lightly to medium loaded MUDs, as obviously everyone is happy with it.

I think you would find that at a certain point (and I can't say what that is, maybe even 1000+ players), that the sleep/poll technique would become noticeably ineffecient.

For more lightly loaded MUDs the existing technique may well be perfectly satisfactory.

For input, yes; but the delay in output can be quite noticeable. Maybe it doesn't bother some people (clearly Jon thinks it's fine) but to me it's very unaesthetic to have output come in chunky bits.

>> So you've gained nothing from processing I/O faster than the commands are processed, except searching
>> the descriptor list dozens of times more every pulse. Oh wait, no that's not it, you've actually
>> optimized the handling of commands without a wait state. So the player typing "HELP STORY" 20 times a
>> second will have optimal servicing. Brilliant. ;-)

> I believe you misunderstood. I meant that players cannot get an advantage over other players in e.g.
> combat by typing in lots of commands in the hope to get multiple ones in per tick.

But you are still ignoring the scenario of a user issuing "help <some massive help file>" 20 times or more per second. Instead you are actually giving priority servicing to users spamming the game with "out of game" commands. I would suggest that it may be a fundamental mud design flaw NOT regulating the user's rate of issuing commands, leaving yourself open to what amounts to in game DoS and spam attacks.

> As for the output servicing, I think we've established over and over again that you don't give a hoot
> either way but it really bothers me to get choppy output.

No we've instead established that Derek Snider decided to chop the output of commands that produce large output. I've postulated that since he was running a mud with a fairly large amount of players, and quite possibly had either limited bandwidth or machine, he did it for performance reasons. I don't really think he needs to provide any proof that whatever tuning he did for his mud must necessarily apply to anyone else.

Secondly there is no need to personalize my defense of the Diku network architecture. I didn't write it and I don't run one.

> Let's forget about input for now. As I said, I can see potential problems in properly handling the
> input case. Let's focus on output. What I'd like to hear from you is simply why we should sit idle
> when there is output we could be sending.

No because you can't separate output from the input/update/output loop and discuss it in isolation because all of the output that will be generated comes from that input/update sequence. It doesn't get magically produced elsewhere. The only leftover output once that pulse loop ends is 1) that which would write block anyway, and 2) the output generated that exceeds the buffer size of the write routines. In the first case, that's what select was designed to test, there is really nothing to do but wait on those sockets to ripen. In the second case as already mentioned you simply tweak your write buffer. Now you aren't going to gain anything in implementing application write buffer sizes greater than the underlying OS sockets stack, which I'm guessing are still 32K for both input and output on most Unices, as you'll be hitting write block conditions again.

Now if you did an analysis and measurement, you are going to discover that 99% of the output generated from a stock Diku/Merc/Smaug Mud per pulse falls under the 4K buffer size. That's about a screen and 1/4 on your traditional 80x40 dummy console, or 5 screens per second. Let's not ignore that DikuMuds and kin are already delivering sub-second response time to their users.

Lastly in the realm of user response time, IBM did studies on response time on multi-user systems and discovered that response times greater than 2 seconds caused the attention of the user to drift and become less productive. That's not suprising and I would posit that "productive" might translate into distracted or annoyed when it comes to text gaming. But they also discovered that installations that provided sub-second but irregular response times to users received more user complaints about "lag" than when response times were uniform but longer.

> My original suggestion was that maybe the select with no descriptors might have been timing out
> prematurely, due to possible optimization, which is what the behaviour is under windows. Thus, that
> was relevant.

Fair enough as he did not specify which OS he was running. Windows select is not Posix compliant. If some version of Linux/BSD broke select() in that way I'm certain it would have generated thousands of bug reports within hours because it would have broken the large body of applications that depend on using select() in the same way Diku uses it, like say apache, rsync, subversion, mailman, kmail, openssl, etc.

> I think you will find however that any large online program (eg. a web server, MMORPG) would never
> build sleeps into the main loop, simply because they are going for optimal performance.

I'm not sure what you mean by large program. If you are talking about web servers and GRAPHICAL MMORPGs we are talking apples and oranges in terms of network architecture decisions.

Apache's main server process does select() sleep in between the select wait for accepting connections and waiting for child processes to end. However that's not even relevant to mud discusion because Apache's optimal architecture is in forking processes for each user (at least on Linux). That architecture would not work very well for muds at all because we share data among users.

On graphical MMOPRGS there are still different architectural considerations. In UOL for example almost all the world data resides on the client, and communications between the server and clients consists primarily of UDP broadcasting of very small packets, mostly under 1K chunks or so I was told. I understand that movement and collisions are resolved simultaneusly on both the client and server and that data syncronization and verification information is exchanged. These games also have front end load sharing code. Frankly the only thing I have to go on is past discussions I've had with some of the authors on mud-dev, as the source to such games like Ultima Online are not generally available for examination.

> The main justification for the "sleep select" seemed to be that it reduced the number of times select
> needed to be called, thus potentially reducing the times through the main loop.

Correct but consider the effects of not regulating user command rate. Other muds like MOO, Cool and ColdC move the command quota regulation out of the networking loop and into the system parse events, thus you see a single poll or select in the networking code. While I might think ColdC's architecture for example is in almost every way superior to a Diku it still doesn't make Diku's fundamentally broken.

> I think you would find that at a certain point (and I can't say what that is, maybe even 1000+ players),
> that the sleep/poll technique would become noticeably ineffecient.

Sure but I would suggest that someone planning, designing and writing a text mud server to support 1000+ players is extraordinarily optimistic, possibly even delusional. ;-)

I have to agree with that, and this is why, with faster CPUs, the existing design, which has theoretical problems, is probably totally acceptable in the current environment.

You may well find that you expend hundreds of hours "improving" it, with no noticeable performance improvements with existing player base numbers.

Honestly I think throughout all this the number one improvement that I made was in sending 4K buffer chunks if the data exceeds 4K. For whatever reason, quite possibly even the placebo affect, things feel faster to me and anyone else who happens by.

Trivial fix -- check the rate of output to prevent DoS attacks, and leave the speed-up for everybody else. Not a problem.

It's not a placebo effect, it is in fact a very tangible speed-up. I'm not sure what else to say since I feel this horse has been beaten into undeadness and back a few times now. :)

I say placebo because I can't imagine that we have THAT much data flowing around in every last possible situation. I could buy it from the overland display for immortals, but really, not much else we have should come anywhere close to spitting out 4K chunks.

Anyway, I figured people might like to know that it looks like the original problem has been fixed. Turned out that the clock timer issue was OS related, and it was due to boot arguments to the kernel that got left behind during the installation of the OS. It's been 4 days now and no sign of trouble from the clock on either server.

It was one of those half-fluke scenarios where the installer wouldn't run without special arguments, but the OS itself needed them removed after the installer was done. I'll definitely have to keep it in mind for the future.

Which parameters were they out of curiosity? Was it noapic by any chance?

I had:
ro root=LABEL=/ noapic acpi=off no_timer_check

Changed it to:
ro root=LABEL=/ acpi_use_timer_override

So far that's eliminated the issue.

Hmm. I'm booting using noapic and am not having timer issues, however I don't have acpi=of and no_timer-check.

Well, in any case, I'm glad that the problem was resolved in a very sane manner without 64 bits causing the world to end as we know it. :-)

Or, needing to rewrite the main game loop <wink>.

Aww, I still think the main loop should be rewritten anyhow. :-) It would be pretty nice to have a proper separation of in-game actions and out-of-character commands. Still, that's a pretty big "should"...

I stick mostly to the philosophy of "if it works, it doesn't need fixing". Especially in cases where messing with it without really understanding what's happening under the hood can foul you up bigtime.

The descriptor handling in most Diku code seems to work just fine for the purpose. It takes input, performs updates, then sends output. The chain seems to flow pretty well since input should affect the outcome of update hanlders and those should in turn affect what gets output.

As long as the clock is reliable it should never be a problem. But as we saw, symptoms in your game are not always caused by your code :)