18 Aug, 2014, Rarva.Riendf wrote in the 21st comment:
Votes: 0
>It can only be due to an enourmous amount of luck (we are talking nanoseconds on a modern JVM and machine)

It WILL happen, and more frequently that you think it can. For the only reason that indeed, machine are now so fast that they do millions of stuff very fast, so it statistically improve they number of time it can happen.
You obvisouly dont care tht much about consistancie in calculation as on a mud, it obviously does not matter that much if you have some weird behaviour from time to time at random time, most people would not even report, it, think of a fluke and forget about it.

Hope you dont have this mindset if you ever code professionally.
18 Aug, 2014, Kelvin wrote in the 22nd comment:
Votes: 0
alteraeon said:
At this point, I'd recommend we simply wait and see what happens. The overwhelming majority of experienced developers are saying "you don't want to do this"; Koteko himself is saying, "I'm going to do it anyway because I want to". Explaining to him why something might be a problem isn't going to convince him - he has a solution for everything. His mind is already made up, let's let him implement it and see what happens.


The big thing some may be concerned about is other developers seeing what Koteko is saying and taking it as good advice. For 99% of the cases (and even probably his case), you don't want to do what Koteko is doing. It adds no tangible benefit, and it may even be slower in some cases. Not to mention how difficult threading bugs can be to track down. Also, some threading issues aren't going to manifest until he gets a number of players in-game and playing at the same time.

For everyone else reading along considering threading a MUD: Unless you have a very specific reason: don't. Look at an async event loop/cooperative multi-tasking instead.
18 Aug, 2014, koteko wrote in the 23rd comment:
Votes: 0
I'm baffled guys. Isn't this a Board where "MUD Coding" can be discussed? I believe it should be used to technically discuss a subject that may be relavant to the programming of a MUD server, not just to say "No, don't do it, don't do it!". I'm discussing a technical aspect, and asked Quinx to argument more specifically on his remarks, but I'm not even sure if I'm going away from my global, thread-safe, async event loop (as Kevin puts it).

Surely I'm not trying to either convince anybody nor asking for help, as writing a MUD for me is a learning exercise. If somebody arrives here and tries to code a multithreaded server, either he knows what he's doing or he'll learn a lot - which is better than joining a crowd of "don't do that!" without actually understanding in dept what the real problems are with it.

Just a few points:

@Rarva (and also Runter, from his last comment):

http://en.wikipedia.org/wiki/CAP_theorem

Consistency is a trade-off in many systems. You haven't worked in a particularly big and competitive company if you don't understand that, as long as you understand the implications, you can "lose something" to achive "something else". The point here is understand the implications. Of course I understand race conditions. Of course I know my codebase well enough to make sure my data does not get corrupted. But I can decide to lose "consistency" from the user perspective in certain cases, if I feel it's appropriate for my game.

This does not mean that I'll have a variable outside of a synchronisation block being accessed by multiple threads so that the final result will be unexpected, NO. It means that if a player shoots on a target at east, then looks and the player disappeared, the arrow might be on the ground because there was no target. The "game state" is of course just fine, the player might be upset (but I believe the almost-victim will like the feature!). I hope you do understand to what level I meant "losing consistency" now.

@alteraeon:

Quote
Explaining to him why something might be a problem isn't going to convince him - he has a solution for everything


It's funny you say that: I just proposed a (sketch of a) model, received remarks and shown that those remarks are general, multithreaded programming remarks (they boil down to "beware of race conditions and deadlocks") and the model does not seem to suffer from them.

I just keep asking an explanation from what I cannot foreseen - namely, what in a complete MUD can be "shared state" and invalidate an event-loop-per-room model?

We have ONLY arrived to Doors, as in the old "Dragon's Dinner Problem". What else can be a shared state between Rooms?

It doesn't seem to me I'm being a "You say A and I say B! LALALALA" kind of guy, as your comment seems to imply. It's too much to ask technical remarks to technical guys within a technical board?
18 Aug, 2014, Kelvin wrote in the 24th comment:
Votes: 0
I guess I'm not seeing the reason to even attempt to incorporate arbitrary threading in your server. Nothing you have said so far sticks out to me as one of those "Yeah, he definitely needs some threads" type scenarios.

If you are just wanting to play with threading, efficiency and sanity be damned, I can understand that. I just wouldn't try to "argue" that what you are doing is sane. More so tinkering and experimenting (which is fine).
18 Aug, 2014, koteko wrote in the 25th comment:
Votes: 0
In fact Kelvin that's all there is to it, really. I'm not expecting to put this in a many-core machine (or a multi-machine cluster) with thousands of users, it's a bloody MUD :) but I find both concurrency and distribution challenging problems - and I'm payed to be good at them. And, not surely least of it is I do like progamming in that way, so why not?

Regarding threading in general, I believe that the best approach in MMO is one thread per machine core, dedicated to specific systems (for example a UserListener that accepts commands from players, parses them and assigns tasks, or a WeatherSystem that pushes events onto the same queue, and a central game loop for the logic), which is what many commercial products do. With some luck you avoid context switching and make use of a modern CPU well. But again, for a MUD.. just stick to what you feel comfortable with and/or what you want to experiment with, and avoid premature optimisation. Any programming language and model is enough for such a system..
18 Aug, 2014, plamzi wrote in the 26th comment:
Votes: 0
koteko said:
I just keep asking an explanation from what I cannot foreseen - namely, what in a complete MUD can be "shared state" and invalidate an event-loop-per-room model?


If you're truly open to feedback, you should re-read the thread because I think there have been plenty of explanations given by different voices, all experienced.

Let's set aside for a moment the fact that player interactions, and any kind of interactions that take place across rooms, will require a bureaucracy of locks. Let's say that you are either OK with the bureaucracy, or OK with skipping it and suffering some degree of bugginess, or OK with limiting yourself to only a few interactions across rooms (no ranged combat e. g. or remote triggering or remote skills or remote admin commands on your active players etc.)

But are you also OK with limiting yourself only to a certain amount of "active" rooms? If every room runs a thread, and every thread adds a slight overhead, you might hit a wall in world size or world complexity much sooner than you realize.

I hope FMUD can chime in here, because he has more recently authored a functional multi-threaded codebase. I believe that in his design there is a thread for every human player, and a single thread for the world. That's very similar to the tried and true approach of the Apache web server. Even so, lots of concurrent players will tax the server. Which leads me to a +1 of Kelvin's suggestion to look into the async model. This is what I use in my own little custom codebase project.
18 Aug, 2014, koteko wrote in the 27th comment:
Votes: 0
Indeed plamzi, I've read it all twice. You seem to have read my huge wall posts as well, as you say:

Quote
Let's set aside for a moment the fact that player interactions, and any kind of interactions that take place across rooms, will require a bureaucracy of locks. Let's say that you are either OK with the bureaucracy, or OK with skipping it and suffering some degree of bugginess, or OK with limiting yourself to only a few interactions across rooms (no ranged combat e. g. or remote triggering or remote skills or remote admin commands on your active players etc.)


which is quite correct. My job would be to: setup a model that requires the least amount of explicit locking and incurs in the least amount of "bugginess", that is unexpected behaviour for the players (I'm assuming you are not talking about game-breaking race-conditions/deadlocks - if the model incurs in those, I've failed according to my own benchmarks).

Two questions:

- what do you mean by remote triggering and remote skills? Can you make an example (so I can see if they can fit in the model or break it)?
- the only player interactions across rooms I can foresee, except for door management or maybe wall management, can be done by putting a Task onto the other Room's queue, therefore don't require locks. Can you make an example, even taken from your mud, where two players in two different rooms would be accessing one's another state, or the same object/room property, therefore requiring a lock?

Thank you if you are willing to expand a bit. Regarding the second part of your post:

Quote
But are you also OK with limiting yourself only to a certain amount of "active" rooms? If every room runs a thread, and every thread adds a slight overhead, you might hit a wall in world size or world complexity much sooner than you realize.


That's the first thing I have investigated in fact, when I started using Threads in java 2 or 3 years ago. It appears that nowadays threads are not so expensive to spawn on Linux. I had done a test and spawned many thousands threads in very little time and without even reducing the stack size (the number of threads that can concurrently be started is dependent on memory and stack size of course), but I don't remember the numbers.

But in any case, that's not an issue. I already use a Thread pool with a 1000 pre-instantiated threads, so I don't have creation overhead.

In addition, using blocking queues and blocking IO, most of my threads are sleeping all the time. The Player threads sleep on the socket and when data arrives, they quickly parse the input, fetch the Command and put it in the queue, then go back to sleeping.

If I had Room threads, those with players and "active npcs" inside would be "active" threads, while those remained empty would be sleeping on their blocking queue.

I do also have a caching mechanism, so Rooms that are inactive for while gets removed from memory. Here the rule would be to test and tweak, to see if the caching timeout is correct, but that I can do when I actually have players.

Can you elaborate on your system? Do you have a global queue where you push events/tasks and pull them out for execution one at the time, like I also do? Do you use game ticks?
18 Aug, 2014, koteko wrote in the 28th comment:
Votes: 0
Also I might add that if the number of threads increases a lot and I find this limiting or resource-taxing, I can easily switch to Quasar that implements user-space greenthreads and message passing in the JVM, inspired by Erlang. That essentially means being able to spawn millions of concurrent processes, as they are decoupled from os threads.
19 Aug, 2014, plamzi wrote in the 29th comment:
Votes: 0
koteko said:
Can you elaborate on your system? Do you have a global queue where you push events/tasks and pull them out for execution one at the time, like I also do? Do you use game ticks?


Nope. I use an async / event model running in a single thread. This gives me the best of both worlds. When I receive input, I can choose to process it synchronously. Or, if I expect it to take some noticeable amount of time, I can kick it off and assign a callback, and in the meantime other events can get processed.

To learn more:
http://blog.mixu.net/2011/02/01/understa...

koteko said:
In addition, using blocking queues and blocking IO, most of my threads are sleeping all the time. The Player threads sleep on the socket and when data arrives, they quickly parse the input, fetch the Command and put it in the queue, then go back to sleeping.

If I had Room threads, those with players and "active npcs" inside would be "active" threads, while those remained empty would be sleeping on their blocking queue.


It's good that you know that most of your threads will just be sitting there. In addition, as others have pointed out repeatedly, the more locks you have to add, the more you lose out on any real benefits. Which brings us back to Kelvin's question about what you think you are gaining from using threads this way, other than some hard-earned lessons.

I can see how threads can be useful for a certain set of specialized tasks that can be spun off to workers and whose result doesn't affect the main state (e. g. DNS lookups, or shooting off emails or tweets, all of which my Dikurivative does in separate processes). I can also see how running players in separate threads like ForgottenMUD does can optimize input processing and save everyone from being lagged if one user performs something intensive (at the cost of applying locks whenever a player interacts with the world). But I really can't for the life of me see any tangible benefits from running each room in a separate thread. I understand there are techniques you can apply that would allow you to run a world with several thousand populated rooms, but in the long run, this kind of design will simply not scale.
19 Aug, 2014, Idealiad wrote in the 30th comment:
Votes: 0
@plamzi, there is a clear benefit to writing threaded code, which koteko mentioned in passing earlier. It is much easier to reason about (i.e. understand the flow of) threaded coded compared to async/callback code.

Also I hear a lot of talk in this thread about what a mess of locks a multithreaded mud leads to. There are good abstractions over locking (immutable references and transactions to name a couple) which make locking a lot less painful.

I'm certainly not convinced that a thread-per-room or player is a good idea, but it's not completely out in left field either.

Finally koteko has been talking about this for a while. Maybe it's time to taste the pudding? :)
19 Aug, 2014, koteko wrote in the 31st comment:
Votes: 0
Ah, you use async IO of course. I admit I haven't personally benchmarked, but other people did and from Linux 2.6 sync io with threads became fa..., with java at least. Memory is cheap (but depends on your requirements) and if you want you can make threads lighter by reducing stack size, also creation overhead is removed with pools. It would be nice to see a mini benchmark with node.js :) With less than 10k players you should only see advantages.

One point: having many threads sitting is a very good thing. You only need to compute when there is something to do, be it a player input or the mob ai kicking in or a weather change. When some of those things need to process work they'll do it purely in parallel on a modern CPU. Of course a thread-per-room model could score worse than lightly threaded system, because there would be more active threads per CPU core most of the times (that's why I didn't do it at the time). It needs benchmarking.

plamzi said:
I can see how threads can be useful for a certain set of specialized tasks that can be spun off to workers and whose result doesn't affect the main state (e. g. DNS lookups, or shooting off emails or tweets, all of which my Dikurivative does in separate processes). I can also see how running players in separate threads like ForgottenMUD does can optimize input processing and save everyone from being lagged if one user performs something intensive (at the cost of applying locks whenever a player interacts with the world). But I really can't for the life of me see any tangible benefits from running each room in a separate thread. I understand there are techniques you can apply that would allow you to run a world with several thousand populated rooms, but in the long run, this kind of design will simply not scale.


Indeed it doesn't scale over a certain threshold, but so doesn't a singlethreaded application (ie, there is maximum amount of operations in a same game "tick", or if don't use them, in the same "time quantum", that your game loop/event executor can process - if you receive more than those, players will have lag). After a while with MMOs you need to distributed the computation in a cluster, but I believe our MUDs will be far, far away from that limit :)

I don't see tangible benifits either now, apart from experimenting. However, if I were to go mad and buy a server with this CPU: Intel Xeon Phi with 61 cores, then I would have an extremely reactive server where I could make NPCs go around like players and modify the world, without fearing they would lag the players themselves.

Also, it could allow experimenting with a Raspberry Pi cluster, or a cloud computing solution, or even with BOINC.

Needed for a MUD? No. Cool? For me yes! :D

@idealiad:
For now my mud server is pretty basic as I spend more time on technicalities than the game play :P for example I'm now rewriting all the "entities" code to use an entity-component approach. But one day you'll taste the pudding (together with my grandchildren :P).
19 Aug, 2014, Runter wrote in the 32nd comment:
Votes: 0
Quote
You haven't worked in a particularly big and competitive company if you don't understand that,


ad hominem.

Quote
I'm not expecting to put this in a many-core machine (or a multi-machine cluster) with thousands of users, it's a bloody MUD :) but I find both concurrency and distribution challenging problems - and I'm payed to be good at them. And, not surely least of it is I do like progamming in that way, so why not?


The comments as I've read them have people explain to you is that it's more complexity and not needed. I'm glad now you seem to agree. If you're just doing it to enjoy yourself and or learn more about threading then by all means.

However, most people here attempt to right wrongs like your comments here not because they're poor at what they do, nor because they're not paid well, nor because they haven't worked at a "big and competitive company", but generally because they genuinely think you've represented something for other readers–especially newbies–that displays indifference to reality.
19 Aug, 2014, Rarva.Riendf wrote in the 33rd comment:
Votes: 0
>Consistency is a trade-off in many systems. You haven't worked in a particularly big and competitive company if you don't understand that

Yeah tell that to a bank….
19 Aug, 2014, alteraeon wrote in the 34th comment:
Votes: 0
Quote
@plamzi, there is a clear benefit to writing threaded code, which koteko mentioned in passing earlier. It is much easier to reason about (i.e. understand the flow of) threaded coded compared to async/callback code.


I've heard this twice now in this thread, and other than corner cases having to deal with I/O waits, I have no idea what planet you guys are from. Threads rarely make anything easier to reason about.

-dentin

Alter Aeon MUD
http://www.alteraeon.com
19 Aug, 2014, Kelvin wrote in the 35th comment:
Votes: 0
Idealiad said:
@plamzi, there is a clear benefit to writing threaded code, which koteko mentioned in passing earlier. It is much easier to reason about (i.e. understand the flow of) threaded coded compared to async/callback code.


I'm sure it depends on the language/toolset, but I have a hard time agreeing with threaded code being easier to understand than async code. Especially for languages that support inline callbacks. This isn't necessarily the most beautiful example, but it's hard to beat just sticking some keyword in front of a deferred to make the particular task sleep until the result comes back: https://github.com/gtaylor/btmux_battles...

This sort of thing isn't unique to Python+Twisted. You can do similar (or even better things) with lots of other languages and libraries. No idea about what the equivalent would look like in Java land, though.

YMMV based on your tools being used, but what makes a threaded setup so much easier to understand than well designed async event loop? There are abstractions to make things "easier", but a lot of that benefit is lost when something goes wrong. As koteko has conceded, you are also somewhat constrained as to what attributes your systems can have unless you want to go down a tricky rabbit hole of queues and locks. That doesn't sound easier to me at all.
20 Aug, 2014, Idealiad wrote in the 36th comment:
Votes: 0
Kelvin said:
I'm sure it depends on the language/toolset, but I have a hard time agreeing with threaded code being easier to understand than async code. Especially for languages that support inline callbacks. This isn't necessarily the most beautiful example, but it's hard to beat just sticking some keyword in front of a deferred to make the particular task sleep until the result comes back


Correct me if I'm wrong, but isn't that basically the same code you'd use in say a thread per player model?
20 Aug, 2014, Kaz wrote in the 37th comment:
Votes: 0
Ah yes. Rule #1 of threading: Threads are hard.

There are many tricks to this, the first of which is to identify exactly what it is you want to achieve. In the OP, it is stated (with a little editing elision): " I would really like … threads to make everything a bit faster. While there are currently no bottlenecks, …"

What this indicates to me is that adding threads would not solve a problem here. But what it would do is make you feel awfully cool about having a multi-threaded mud, and I am totally down with that. :)

I would consider adding threads in stages, and using specific threads only in specific parts of the code (even if the entire codebase becomes multi-threaded, threads still do not escape module boundaries. I'll explain.)

For example, an obvious place for threads, as mentioned elsewhere in this discussion, is I/O. From the moment input is received from the client to the moment the input is fully formed and ready to take some decision on the game state, it does not interact with any other part of the system, and I/O for other clients may also be performed concurrently. This is therefore a candidate for parallelism, and I'd argue it's a good place to start.

Here's an architecture I'd suggest starting with: At game start, spin up several "worker" threads (it doesn't really matter how many, but make the number changeable if you want to "tune" it later,) and have them wait on some kind of condition variable. In your main game loop, where you have your select() call, which returns a set of FDs which have data pending (more or less), add the notified FDs to a thread-safe queue, and notify the condition variable N times, where N is the size of the set of FDs that changed (it doesn't matter if N is greater than the number of threads, since each worker thread should check that the queue is empty before waiting again). Each thread then reads data from the FD and does the work associated with that data.

// Worker Thread pseudo-code
void fn()
{
for(;;)
{
lock = do_lock();

while (is_empty(queue))
{
wait_for_condition(lock); // releases lock while waiting on condition
// lock is regained here.
}

item = pop_queue(queue);

do_unlock(lock);

do_work(item);
}
}


Shutting down properly is left as an exercise to the reader.

When it comes to the game state, however, you will need to pass messages back and forth to the game module using another thread-safe queue. Don't call functions from the I/O threads that work with the game's data directly. That way lies madness. Even if it's just querying a value. Threads must not escape the module that the thread works upon. If one set of threads writes to a queue, it is a different set of threads to the ones that read from a queue.

In the meantime, learn to use tools such as Helgrind (part of Valgrind), and Clang's thread sanitizer. They will find issues that you would never have imagined.

When the I/O is perfectly threaded, never crashes (and I mean never, not "only once in a blue moon"), then it's time to move onto the next part of the system. Identify the independent chunks that are obvious candidates for parallelism (which game state generally isn't, because nearly everything can be dependent on nearly everthing else.) and start again.

Finally, consider making it so that you can always fall back on "num_threads=1" if everything goes horribly wrong. Because threads are hard.
20 Aug, 2014, Kelvin wrote in the 38th comment:
Votes: 0
Idealiad said:
Kelvin said:
I'm sure it depends on the language/toolset, but I have a hard time agreeing with threaded code being easier to understand than async code. Especially for languages that support inline callbacks. This isn't necessarily the most beautiful example, but it's hard to beat just sticking some keyword in front of a deferred to make the particular task sleep until the result comes back


Correct me if I'm wrong, but isn't that basically the same code you'd use in say a thread per player model?


No, it'd be a completely different approach entirely. Network IO is non-blocking, but pretty much everything else is.
25 Aug, 2014, ForgottenMUD wrote in the 39th comment:
Votes: 0
plamzi said:
I hope FMUD can chime in here, because he has more recently authored a functional multi-threaded codebase. I believe that in his design there is a thread for every human player, and a single thread for the world. That's very similar to the tried and true approach of the Apache web server. Even so, lots of concurrent players will tax the server. Which leads me to a +1 of Kelvin's suggestion to look into the async model. This is what I use in my own little custom codebase project.


I've started my codebase from the tutorial on the Java website, which used a Server and ServerThread class. There was no deep thinking about it, I just copied & pasted a few lines of code. It looks like the tutorial doesn't exist anymore, but since it was on their website, I assume it's the classic method. There are a lot of Google results for ServerThread.java. The OP is using Java too for what it's worth.

This is true that I have one thread for each player, and one for the server that is created automatically when calling the "main" function (and also called "main"). I also see one for each timer, and some crap like the signal dispatcher.

Adding a lock doubles the execution time in the rare case where you are waiting for your turn but I don't see it as an issue because all the locks deal with functions that move items from one container to the other (or add HP) and execute in like what… 1 ms? The threads almost never wait anyway except when two players type the same command at the same time in the same room. So it's not true that the majority of threads spend their time waiting in a semaphore lock.

Should I add, if you only have one function that deals with changing the state of containers then there will only be one part of your code that uses locks so this is not something that's a nightmare to manage. For example addToContainer(mainContainer, subContainer, item), can be addToContainer(player, HP, 1) or addToContainer(room, floor, longsword). It depends how abstract your code is. But this is one good abstraction, not just for concurrency locks but also if you want to change your data structure. Kavir went further with God Wars 2, all containers are derived from a super object called "Thing".
25 Aug, 2014, Kelvin wrote in the 40th comment:
Votes: 0
You *can* make heavy threading work, but what most people on here are saying is that it's not worth it for a MUD. KISS. And what can go wrong often does.

It's possible to write a bug-free MUD with tons of threading, but unless you are just wanting to experiment with threads, why would you?
20.0/59