Threading in Text MUDs
Goto page 1, 2  Next
 
Post new topic   Reply to topic    mudlab.org Forum Index -> Coding
View previous topic :: View next topic  
Author Message
Myrd



Joined: 08 Jun 2005
Posts: 4

PostPosted: Wed Jun 08, 2005 5:41 am    Post subject: Threading in Text MUDs Reply with quote

Most MUDs around (Dikus, i'm looking at you) are single threaded. While this makes for a simple design, it prevents the MUD from benefiting from the advantages of a threaded model.

In a regular graphical client-side game, there's a few areas that are often threaded. These include:

    a) graphic thread (all rendering is done in this thread)
    b) gameplay logic thread (core of the engine)
    c) networking thread (handles tcp/ip packet I/O)
    d) audio thread

While such a model may work well for graphical engines, it obviously would not apply to a textual MUD server. However, there must be areas where a textual MUD server can benefit from threading, and I'd like to hear of some examples where threading has been used succesfully and unsuccessfully in text MUDs.

In fact, I'll start off with one example of an unsuccessful use of threading in a MUD server. One MUD, from a new original codebase done in Java, which AFAIK is no longer around, had a threading model where each room would have its own command input thread. Now, I was only a player of that MUD, so I don't know how things looked on the server side, but I'll tell you how they looked on the player side: sometimes, one room would just freeze, or start going really slowly. The rest of the MUD was fine, but anyone in that one room would be completely unable to do anything except connect/disconnect and get the initial log message. Also, it didn't help that multiplaying was not allowed, so you couldn't just log onto another character and ask for a transfer to elsewhere. I'm not sure why they went with this threading model for command input, but from the practical point of view, it was extremely annoying, and I'm guessing a nightmare to debug from the development point of view.
            Back to top
            View user's profile Send private message
            Author Message
            eiz



            Joined: 11 May 2005
            Posts: 152
            Location: Florida

            PostPosted: Wed Jun 08, 2005 7:25 am    Post subject: Reply with quote

            Myrd wrote:

            While such a model may work well for graphical engines, it obviously would not apply to a textual MUD server. However, there must be areas where a textual MUD server can benefit from threading, and I'd like to hear of some examples where threading has been used succesfully and unsuccessfully in text MUDs.


            I don't think threads are a very good concurrency model for MUDs at all, but the most obvious way to parallelize a MUD is through spatial partitioning (like the room example you mention, although obviously that's far too extreme). However, message passing is a better option than threading here, as message passing systems can be clustered without insanity like distributed shared memory. There have been a few such distributed systems: {Unter,Uber}MUD and CoolMud come to mind, although these may be quite a bit different in design from what you're thinking of. kpreid also wrote a peer-to-peer MUD in E.

            It sounds like the server you mentioned had some pretty bad deadlock issues. That's not at all uncommon in traditional threaded systems. As always, progress marches on: the latest shiny object in shared memory systems is composable memory transactions.
            Back to top
            View user's profile Send private message Visit poster's website
            Author Message
            Tyche



            Joined: 13 May 2005
            Posts: 176
            Location: Ohio, USA

            PostPosted: Thu Jun 09, 2005 9:28 pm    Post subject: Reply with quote

            There are some obvious candidates for multi-threading that muds use with success. I do consider multi-process applications to be conceptually equivalent to multi-threaded applications. The reason for the functional separation is the same, how they perform may not be.

            DNS lookups - I've seen this both threaded, spawning child processes or via RPC through a dedicated DNS lookup process.

            Network I/O - There are lot's of network models that work well multi-threaded. Even the traditional select/poll non-blocking model works well as a separate thread tied to a message queue. I've seen some muds that run the listening/accepting socket in a seperate thread. Language considerations might dictate the use or non-use of threads for network I/O.

            Database/File I/O - asyncrhonous file I/O might useful, I've never seen it in a mud. Many databases run as separate processes, the obvious advantage is mult-process use.

            Anything that blocks

            Soft-threading/fibers/Non-premptive threading - Many muds make use of non-premptive scheduling systems, LPmuds, ColdC, Muq come to mind. The advantage is it allows regular throughput, interruption, and long running background tasks. Synchronization and interruption is controlled by the engine at well-defined points, so there's no danger of race or deadlock conditions. It's implicit concurrency though the rules of the model differ from mud to mud. DGD I believe sports atomic transactions now. I support the opposite end, running read only events with intentional race conditions.

            Continuations - I have not seen these used in a mud, but I suspect they may be very useful for implementing state machines, login/character creation, menu systems and modal dialogs.
            Back to top
            View user's profile Send private message Visit poster's website
            Author Message
            eiz



            Joined: 11 May 2005
            Posts: 152
            Location: Florida

            PostPosted: Thu Jun 09, 2005 9:36 pm    Post subject: Reply with quote

            Tyche wrote:
            There are some obvious candidates for multi-threading that muds use with success. I do consider multi-process applications to be conceptually equivalent to multi-threaded applications. The reason for the functional separation is the same, how they perform may not be.


            Just so we're clear, when I say threads I specifically mean shared memory preemptive threads and their associated baggage. Concurrency in general is great for muds.

            Form based applications with back/forward can be implemented nicely using continuations, though I've never seen this done in a MUD. It's definitely something to think about. Similar concepts are used in continuation-based web frameworks (and I've seen at least one system for implementing traditional terminal apps this way). This is probably really only a good idea if your language heap allocates activation records (e.g. Chicken, SML/NJ, my own scripting language, many other functional languages). If you have efficient continuations you can implement cooperative tasks and such quite easily, and perhaps more importantly, there's no need to worry about stack sizes.
            Back to top
            View user's profile Send private message Visit poster's website
            Author Message
            gerund



            Joined: 24 Nov 2005
            Posts: 14

            PostPosted: Thu Nov 24, 2005 7:22 pm    Post subject: Reply with quote

            I am not that familiar with how people use threads, since I have never really had the need. Is there any chance someone could contrast what it is like when you use threads for a MUD server with my approach? Specifically, how you have to structure your server code to get best use of them.

            For my MUD programming, I use Stackless Python. Python as a language allows me to write what I consider to be readable, straightforward code; partly because of it is a high level language, but also because its whitespace structured syntax works for me. But what the Stackless Python enhancements give me is a lightweight threading equivalent. Tasklets. Which the built-in scheduler gives you the option of running either preemptively or non-preemptively. They are also cheap to create and can be used on a whim. If you have a Python function you want to run concurrently, you just wrap it in a tasklet instance and schedule it.

            Anything you need can be launched in a tasklet. An incoming network connection can have its own blocking socket reading tasklet. A logged in character can have a tasklet that blocks reading lines of input and then processing them. Functions that need to block for a fixed amount of time can just call a function that returns when the time has passed (as opposed to MudOS's call_out and callbacks in general).

            It feels kind of liberating to me to be able to program this way. Code is more readable because I don't need to structure code to get the behaviour I need - I can just call a blocking function. No callbacks or delayed function calls necessary. The blocking function just deschedules the tasklet until the time is right and then reschedules it, perhaps returning a result.

            There are some caveats. I do have to operate it with non-preemptive scheduling, this gives me valuable predictability and makes it an order of magnitude simpler to use. But the biggest is that all tasklets run as part of the thread that the Python interpreter runs in, you cannot use tasklets in other threads if you do use them - this is because of the way Stackless works. And no tasklet can actually block the thread, or it stalls the whole server/interpreter. Any blocking operations have to transparently deschedule the tasklet and asynchronously do the required operation and reschedule the tasklet when it is complete. And you have to remember to either yield your tasklet periodically if you are not going to do a blocking operation (which will yield implicitly when it deschedules your tasklet) or going to put it to sleep explicitly. Otherwise, your tasklet stays active and the others never get a chance to run. Any blocking operations generally have to be followed by a relevance check and give up if they are no longer relevant.

            However, despite the fact I claim that I find this to give me more readable code, increase my producivity and so forth, my MUD server never really goes anywhere. Too lazy I guess. But I am interested to know how people make use of threads in their server.
            Back to top
            View user's profile Send private message
            Author Message
            Lared



            Joined: 07 Oct 2005
            Posts: 26

            PostPosted: Fri Dec 02, 2005 12:12 am    Post subject: Reply with quote

            Unless you've got a multi-core system, threading does you no favors, and instead creates race conditions and other delightful errors of the logical flavor.

            I don't really see the value.
            Back to top
            View user's profile Send private message
            Author Message
            kelson76



            Joined: 27 Jun 2005
            Posts: 30

            PostPosted: Fri Dec 02, 2005 4:58 am    Post subject: I disagree... Reply with quote

            Lared wrote:
            Unless you've got a multi-core system, threading does you no favors, and instead creates race conditions and other delightful errors of the logical flavor.

            I don't really see the value.


            In 3-5 years, there won't be any single core CPU's on the market. So, while the value right now is questionable, if you plan to use the same base in the future, there is value to multi-threading.


            -Kelson
            (The other one...)
            Back to top
            View user's profile Send private message AIM Address
            Author Message
            gerund



            Joined: 24 Nov 2005
            Posts: 14

            PostPosted: Fri Dec 02, 2005 9:20 am    Post subject: Reply with quote

            Lared wrote:
            Unless you've got a multi-core system, threading does you no favors, and instead creates race conditions and other delightful errors of the logical flavor.

            I don't really see the value.


            Well, with the microthreads I use, it allows you to decouple your logic more easily. Just start a function as a microthread. No callbacks. No unnecessary boilerplate. Code becomes more straightforward. Concurrency is not important to me - predictability and ease of writing code is, and that is what I get from them. Cooperative scheduling at a high level.

            Race conditions are something I have rarely encountered, and because a microthread's logic is implemented in Python, when it does happen, you can automatically detect it, stacktrace all conflicting microthreads and send the stacktraces by email to notify someone who can examine the live state. In fact even without the live state still present, you can generally see the microthread that got the lock (for example, being the most common reason for a race condition), where it is stuck or blocked and all the others will be displaying the various conflicting ways the lock was wanted that helped to contribute to it.
            Back to top
            View user's profile Send private message
            Author Message
            Lared



            Joined: 07 Oct 2005
            Posts: 26

            PostPosted: Fri Dec 02, 2005 11:27 am    Post subject: Re: I disagree... Reply with quote

            kelson76 wrote:
            Lared wrote:
            Unless you've got a multi-core system, threading does you no favors, and instead creates race conditions and other delightful errors of the logical flavor.

            I don't really see the value.


            In 3-5 years, there won't be any single core CPU's on the market. So, while the value right now is questionable, if you plan to use the same base in the future, there is value to multi-threading.


            -Kelson
            (The other one...)


            Unnecessary optimization and complexity. You're running a MUD, not a physics simulation.

            I've been seeing a lot of this as of late among the MUD coders I talk to. "We need to do this, this, and this because it's better coding." I for one follow the KISS principle--keep it simple, stupid--and threading adds to the weight.

            Will multithreading be faster on a multicore system? Yes. Will it make your code easier to read? No. I've had sixty playing connections (borrowed my CS class) on a 233MHz server with 128MB RAM and zero lag. A MUD will run on even archaic hardware effectively; optimizing code just to incorporate the cool thing of the year is a waste of time.
            Back to top
            View user's profile Send private message
            Author Message
            KaVir



            Joined: 11 May 2005
            Posts: 565
            Location: Munich

            PostPosted: Fri Dec 02, 2005 12:46 pm    Post subject: Re: I disagree... Reply with quote

            Lared wrote:
            optimizing code just to incorporate the cool thing of the year is a waste of time.


            That depends entirely on what "the cool thing of the year" is, what it can add to your game, and what impact it might have on the mud if you don't optimise it correctly.

            I went for the "premature optimisation is evil" approach to start with as well - then later had to spend many hours optimising the code, because my mud was exceeding five times the maximum cpu usage my hosting provider permitted.
            Back to top
            View user's profile Send private message Visit poster's website
            Author Message
            MikeRozak



            Joined: 27 Nov 2005
            Posts: 15
            Location: Australia

            PostPosted: Fri Dec 02, 2005 10:14 pm    Post subject: Reply with quote

            Decent AI, decent NLP, better physics simulation (such as a server for a 3D graphical MUD, or hit locations, etc.) all take up plenty of CPU. (The state-of-the-art MUDs from the 1990's, like Diku, have rather poor AI and NLP, and no graphics.)

            Thus, if you're exploring algorithms that no MUD has explored, you'll probably consume more CPU than the typical Diku MUD (which is about 1 Mhz/player, as I recall). If you use more CPU (10Mhz+/player), then multithreading to take advantage of multicore CPUs is probably a good design choice.

            Contentious question: If you're not pushing AI, NLP, or graphics/physics, then is your MUD actually doing anything new? (I'm not saying that you're not doing anything new with feature Y, just that you should seriously ponder this question.)

            If you're not doing anything new (or better), is it worth doing?
            Back to top
            View user's profile Send private message Send e-mail Visit poster's website
            Author Message
            Kelson



            Joined: 18 May 2005
            Posts: 71
            Location: SC

            PostPosted: Fri Dec 02, 2005 10:55 pm    Post subject: Re: I disagree... Reply with quote

            kelson76 wrote:
            In 3-5 years, there won't be any single core CPU's on the market. So, while the value right now is questionable, if you plan to use the same base in the future, there is value to multi-threading.


            I'm not sure I agree that creating a multi-threading mud better utilizes all the CPU cores available than a single-threaded mud. Keep in mind that the hardware and software (compiler) already exploit parallelism in the code far beyond what is normally achievable by eye and this will certainly continue into the multi-core computers. While it is currently seen as useful to create threads for decoupled logic (network i/o, graphics, ai, game logic, etc), this has more to do with the conceptual seperation of those things running in parallel than much (if anything) to do with the true gains of running them on seperate processors. During development, I have no idea which conceptual grouping (AI, Graphics, etc) will eat what amount of CPU-time in the final product (and, honestly, I don't care much). What does matter to me is that they all run as needed and handle their jobs. Threads are wonderful because they let the computer figure out how to balance all those threads to maximize their effectiveness. It's a given that, on a single processor computer, my threads aren't actually executed in parallel, but the computer allows me to pretend they are (which means I don't need to worry about creating my own logic to schedule the AILoop and the GraphicsLoop and the NetworkingLoop...the OS will do it for me).

            This conceptual benefit carries over into multi-core machines where the benefit is STILL simply that we allow the OS to manage our parallel threads. In general, the programmer is going to fall far short of accurately guessing which way to schedule the threads on each CPU to maximize throughput - nor is it needed.

            -Kelson
            (The purple one...)
            Back to top
            View user's profile Send private message Send e-mail AIM Address
            Author Message
            MikeRozak



            Joined: 27 Nov 2005
            Posts: 15
            Location: Australia

            PostPosted: Fri Dec 02, 2005 11:23 pm    Post subject: Reply with quote

            I use multithreaded code, and it runs faster on my dual-core machine than an equivalent single-processor computer. I specifically designed my code so that some threads get higher priority than others, not exactly micromanaging the schedule, but as close as you can get with threading.

            In my server, most (50%?) of the compute cylces are in the main thread that handles the core game logic through a script. This heavy thread prevents me from taking advantage of 4-core systems, but NO WAY am I going to create a thread per user like some people are expousing; it's too inefficient (minor problem) and it's too easy to create deadlock conditions that only occur once a blue moon (major problem)... as for people who want to do this, that's their choice, but they're in for some pretty major debugging headaches. The secondary threads/processors mainly handle data compression (I send XML-ish data to my client) and database maintinence.

            My client utilizes multiple processors/cores better than my server because my client has 3D graphics, sound, and text-to-speech. When 16-cores become standard, I could even switch to ray tracing, which does very well with multiple processors.

            People that claim that multicore and multithreaded code are merely ways to clarify code should learn some more about multithreaded coding, or they will rue their words as much as the guy who said, "No one will every need more than 640K."

            However, most text MUDs (a) don't use many cycles per user, and (b) don't have many simultaneous players. For them, I'd recommend sticking to a single thread because multithreaded code can get tricky.

            But, if you have improved AI, NLP, graphics, and/or physics, your server will not only use more cycles per user, but your new and innovative features will (hopefully) get you more users. You'll need multithreaded code.
            Back to top
            View user's profile Send private message Send e-mail Visit poster's website
            Author Message
            kelson76



            Joined: 27 Jun 2005
            Posts: 30

            PostPosted: Sun Dec 04, 2005 12:54 am    Post subject: Re: I disagree... Reply with quote

            It really depends on how you are threading your mud server.

            I only use a few major threads.

            Communications Handler - Handles Network I/O, uses Queue's to transfer data to the other threads.
            Command Execution Handler - Receives commands via a queue from the communications handler thread.
            Logging Handler (I want to break File I/O off from the main execution path)
            Update Handler - This allows me do alot more AI in the background than if I put it in serial with handling user command processing.

            That is really it. I minimize the overlap between data structures that the threads are allowed to touch. I use queue's for all communications between the threads.

            - Kelson
            (The other one....)

            Lared wrote:

            Unnecessary optimization and complexity. You're running a MUD, not a physics simulation.

            I've been seeing a lot of this as of late among the MUD coders I talk to. "We need to do this, this, and this because it's better coding." I for one follow the KISS principle--keep it simple, stupid--and threading adds to the weight.

            Will multithreading be faster on a multicore system? Yes. Will it make your code easier to read? No. I've had sixty playing connections (borrowed my CS class) on a 233MHz server with 128MB RAM and zero lag. A MUD will run on even archaic hardware effectively; optimizing code just to incorporate the cool thing of the year is a waste of time.
            Back to top
            View user's profile Send private message AIM Address
            Author Message
            Kaz



            Joined: 05 Jun 2005
            Posts: 24
            Location: Hampshire, UK

            PostPosted: Tue Dec 13, 2005 8:09 pm    Post subject: Re: I disagree... Reply with quote

            KaVir wrote:
            I went for the "premature optimisation is evil" approach to start with as well - then later had to spend many hours optimising the code, because my mud was exceeding five times the maximum cpu usage my hosting provider permitted.


            So hopefully you profiled, found where the hotspots were, and solved them as they arose. This is surely better than spending weeks twiddling bits of algorithms to make them "perfect", when its not warranted.
            Back to top
            View user's profile Send private message
            Display posts from previous:   
            Post new topic   Reply to topic    mudlab.org Forum Index -> Coding All times are GMT
            Goto page 1, 2  Next
            Page 1 of 2

             
            Jump to:  
            You cannot post new topics in this forum
            You cannot reply to topics in this forum
            You cannot edit your posts in this forum
            You cannot delete your posts in this forum
            You cannot vote in polls in this forum

            Powered by phpBB © 2001, 2002 phpBB Group
            BBTech Template by © 2003-04 MDesign