Single Threaded UDP

You'd have to make your socket non-blocking, but I suppose it'd work. In today's world of multi-cpu/core hyperthreaded machines, I just don't understand why people keep writing single-threaded server code ...

Robert

If you ever consider improving your server model try IOCPs for Windows NT+, epoll for Linux 2.5+, or kqueue for FreeBSD 4.1+.

Well epoll sounded worth checking out since ultimately im going to be developing on linux.

Quote:

DESCRIPTION epoll is a variant of poll(2) that can be used either as Edge or Level Triggered interface and scales well to large numbers of watched fds.

Doesn't seem like it would really help in a udp situation where theres only one fd thats going to be watched.


As far as threaded vs non-threaded I've seen arguments for one being better than the other and vice versa. I really don't want this thread to end up being a war on which is better. Once I get a solid single threaded implementation done, I can run some tests and see which one wins out.

-=[ Megahertz ]=-

Quote:

Original post by rmsimpson You'd have to make your socket non-blocking, but I suppose it'd work. In today's world of multi-cpu/core hyperthreaded machines, I just don't understand why people keep writing single-threaded server code ...

There's no need to make the socket non-blocking if you use select() as it is intended, to determine when it is possible to send/recv more data.
Single-threaded code is much easier to write is one reason.

You probably don't really need multiple threads at all.

You can use select() or some similar call to wait for a message, or a timeout. If the timeout happens, then you process your time-based events (i.e. tick the game objects) and send any messages arising. If a message arrives from the (single) UDP socket, you process that, send any response necessary and then go back into select.

This approach can be used with TCP as well, but there are more sockets.

If you're using UDP and only have one socket, using these other fancy methods of waiting won't improve anything, as they are just really intended for quick switching between a large number of sockets (i.e. thousands).

If your game server uses sufficiently little processor time that it can run on one CPU easily, there is very little point in making it multithreaded.

Mark

Quote:

Original post by markr You can use select() or some similar call to wait for a message, or a timeout. If the timeout happens, then you process your time-based events (i.e. tick the game objects) and send any messages arising. If a message arrives from the (single) UDP socket, you process that, send any response necessary and then go back into select. Mark

Well having a timeout on select was somewhat of a concern. I see it takes a timeval struct as a parameter telling it how long to wait (currently i just pass in NULL so it waits forever, but since its currently off in another thread thats fine). Whats a good timeout value? Would something as low as 10ms be unreasonable? Should I go lower? Higher?

It seems that a MMORPG would need to have the game loop run pretty fast (few hundered iterations per second). Things like attack timers and damage over time timers would need to get checked quite frequently so that events happen as accurately as possible.

Everquest had the notion of a "tic" that was 6 seconds. Wow I think uses 2 seconds. So if a DOT spell was cast on an NPC in EQ the damage that spell did would be applied every 6 seconds. Obviously their game loop ran much faster than this and im quite sure they just had a timer with a timeout value of 6 seconds that just got checked every iteration.

I guess I'll have to write a bare bones example of the above and see how well it does to get an idea of the practicality of it all.

-=[ Megahertz ]=-

Quote:

... Would something as low as 10ms be unreasonable? Should I go lower? Higher?

You can set the timeout to be zero, which is presumably what you would want if your program is single-threaded. man page for select() says:

To effect a poll, the timeout argument should be non-nil, pointing to a zero-valued timeval structure.

I don't even bother with select(), I set the socket non-blocking and check if I got a WOULDBLOCK error from it.
I'm with markr in saying there is no necessity for multiple threads. If you think about it any socket based app is already multithreaded anyway, the OS is managing the data in the socket buffers in between your app and the transport layer. Even a simple app with a socket listening for connections will have two threads, check in the task manager.

If you're reading from a single socket, using select() just means you make a useless kernel call. It's more efficient to just set the socket in non-blocking mode, and reading from the socket until it returns no more data; then go through your regular game loop.

Non-threaded game loops mean that you don't have to worry about locking your world state, which is a performance improvement. However, on a multi-core CPU, you'll probably do OK by doing receipt in one thread, and put data on a queue for the main world processing thread to pick up; you only need to lock this queue once per game tick which is a negligible cost. You can even double-buffer the queue if you're so inclined, although that may incur a latency penalty.

Yes of course - using select() with just one socket and either no timeout or a zero timeout, is totally pointless, as those could be done by calling recv() on either a blocking or nonblocking socket respectively.

However I was talking about calling select() with a finite timeout, which will be the time until the next "interesting thing" happens. This could be a timer event for a regular "tick" time, which could be done 10 times per second, 100 times per second or every 10 seconds it would depend entirely on your game design.

Certainly you would want to periodically run some timed tasks. You would at the very least, want to disconnect (which in UDP basically means "forget about") clients which had been silent for too long.

Mark

Quote:

Original post by hplus0603 If you're reading from a single socket, using select() just means you make a useless kernel call. It's more efficient to just set the socket in non-blocking mode, and reading from the socket until it returns no more data; then go through your regular game loop.

Agreed. If you're really concerned about optimizing your main game loop, you need to evaluate and weigh every single kernel transition your loops causes.

Quote:

Non-threaded game loops mean that you don't have to worry about locking your world state, which is a performance improvement. However, on a multi-core CPU, you'll probably do OK by doing receipt in one thread, and put data on a queue for the main world processing thread to pick up; you only need to lock this queue once per game tick which is a negligible cost. You can even double-buffer the queue if you're so inclined, although that may incur a latency penalty.

I do most of my programming on a dual xeon, and all of it in Windows. When it came time to write my octree code and run through all the entities and determine which entities can "see" the other entities around it, I found doing this in multiple threads was both easy and yielded phenomenal performance gains. I could successfully run this computation on 500,000 entities in about 750ms in my simple unoptimized test octree app using both cpu's (speed depends on density of the entities and other factors of course).

This ran with two threads running side-by-side, calling InterlockedIncrement() on a shared index to the entities. There is one SWMR (single writer multiple reader) lock class I wrote that manages the array in its entirety, but those locks are only called at the beginning and ending of each walk.

Ya'll can pry multithreading from my cold dead fingers! Until then, I ain't givin' it up!! :)

Robert

I think as long as you spend more time on the computations than you spend doing the context switches or waiting for shared resources to have mutexes unlocked then multi-threading is going to see a performance gain.

-=[ Megahertz ]=-

Quote:

Original post by rmsimpson I do most of my programming on a dual xeon, and all of it in Windows. When it came time to write my octree code and run through all the entities and determine which entities can "see" the other entities around it, I found doing this in multiple threads was both easy and yielded phenomenal performance gains.

Naturally if you do actually have two physical processors, making your code multithreaded will see performance gains of oh say... double? :) But how about for a multithreaded game server with threads using real critical sections, and blocking waiting for input, running on a single cpu.
My bet is that any performance improvement is not worth the effort of dealing with the issues multithreading brings in.

Maybe I should have qualified that - any performance improvement is not worth the effort of dealing with the issues multithreading brings in for threads doing socket management. Most likely the main reason that multithreading topics come up in relation to network programming is because people see that sockets block. Just think, if sockets were non-blocking by default and there was no way to set them to blocking, what problem would it pose to a game server? Having a socket block is only really useful for applications that must have some data to read/send or else they have nothing else to do eg. FTP.
Of course there's nothing wrong with multithreading in general. With sockets though, since the OS is already managaging a thread under your socket layer, there seems little point in adding another thread between that and your main app. Like someone mentioned here already it's mostly a matter of taste whether multithread code is uglier than a single thread 'giant loop' with interruption logic, I just don't think either has any great performance advantage over the other. Single threaded is definitely easier to debug (but comes with more management issues, like handling non-blocking connect() properly etc).

Here's another statement that needs qualification: "You can get more then double the performance if you pay close attention to what you are doing."
On a single cpu??

Quote:

Naturally if you do actually have two physical processors, making your code multithreaded will see performance gains of oh say... double? :) But how about for a multithreaded game server with threads using real critical sections, and blocking waiting for input, running on a single cpu. My bet is that any performance improvement is not worth the effort of dealing with the issues multithreading brings in.

My point really, is this: The days of single-core CPU's are numbered. Coding for single-threaded, single CPU's will very soon be like writing for DOS or in 16-bit.

If you're going to write new code, right now, and actually want to see improvement in its performance when you upgrade your equipment in a year, you need to start writing scalable code.

While we're on the subject of performance, which is more taxing on the CPU:

A. Polling a socket in a tight game loop in a single thread, potentially 100,000 kernel transitions a second or even higher.

B. Putting a thread to sleep and having the kernel wake it up when socket data arrives. A couple small kernal sync objects added to that and you have no more than say a dozen kernel transitions per message.

Oh, and just for kicks to demonstrate performance of multiple threads in a single CPU ... try this on for size:

In a single thread, do the following (assuming Windows because, well, that's all I write for!)

FindFirstFile() on "*.*" of the root C Drive
For each directory, re-enter the function with the new path
For each file, open the file and call CreateFileMapping() to map the file. Then close the mapping and the file.
Call FindNext() and loop until no more files.

A simple re-entrant function to iterate the entire filesystem of your harddrive and map all the files to memory, unmap them, and close the files.

Once you've run this program once which will take some time, the subsequent runs will be much faster (caching). Now, complicate this function a bit by introducing another thread and some synchronization between the two threads. Some of you might guess that the thread overhead and synchronization might just cause the whole thing to take much longer, but you'd be dead wrong. The multithreaded version completely obliterates the single-threaded version in performance. I'm more than happy to follow up with source code here if anyone's remotely interested.

Robert

Quote:

Naturally if you do actually have two physical processors, making your code multithreaded will see performance gains of oh say... double? :)

If you are entirely compute bound, and run in cache, that's possible.

If you're contending for the memory bus, then that's not true. There's still only a single interface to main memory, which now two separate CPUs have to suck data through.

It all depends on what you're trying to optimize.

To multithread or not to multithread. This is a topic under much debate in many worlds. My personal opinion is as follows.

If you plan to run your software on a single CPU don't multithread. I noticed that you said "I multithread database accesses" but does this really need to be multithreaded? If your database API is accessing over TCP/IP writing your own handeller might do wonders for the efficiency of your code. Task switches on a CPU with the locking and blocking waste more cycles than it's worth. Try to look at your design and clean it up maybe. You might dazzle yourself on what you learn about how to handle multiple tasks at once. For example, in my client engine for my games, I got events like input (mouse etc), harddrive, sockets, and more on a single system call. It's alot cleaner, alot more optimized, and god does it feel good ^_^

On my personal project I'm working on I developed a microthread/multithread software. Basically in a single CPU it uses microthreading and in multi cpu it uses multi threading.

The software will run on machines with more than one CPU as long as the code can be designed to take advantage of more than one and see a reasonable performance increase from doing so.

"If your database API is accessing over TCP/IP writing your own handeller might do wonders for the efficiency of your code."

I'm not sure what you mean by this but it sounds similar to what hplus has mentioned before about what he did in his own project. If its definitely more efficient then perhaps its worth looking into. Could you explain what you mean a little better?

Right now I have a thread that gets "query packets" from the server. Queries are put on a queue and then executed and their results are stored and returned on queue that the server can pop the results off of later once they've been processed.

The only reason I did this is that I didnt want to block on waiting for the results from a query that could potentially take a while to process thus holding up the server from doing other things in the meantime.

It's my first go around with coming up with a solution to such a problem, so my current solution could be less than ideal. Just one of those things you have to try and see how it works and if it doesn't, learn from it and do it better the next time around.

Ideas are always appreciated tho. =)

-=[ Megahertz ]=-