Top Mud Sites Forum Return to TopMudSites.com
Go Back   Top Mud Sites Forum > Mud Development and Administration > MUD Coding
Click here to Register

Reply
 
Thread Tools
Old 02-12-2012, 07:36 PM   #1
Kitriel
New Member
 
Join Date: Jul 2010
Posts: 10
Kitriel is on a distinguished road
High volume scripting question

I've been dabbling and testing my lua scripting embedded into my c++ original code base, and i've got it working fine. No errors and it all does what I want. My issue is when I have a high volume of scripts running at once.

I was just curious how other codebases that use these combinations, or other combinations of source and scripting language, handle high volume of scripts being executed at once.

Possible solutions I've thought of that don't quite work:

-I currently outsource my saving code to a seperate program, which saves on its own. This frees the core program to continue what it's doing and the background program saves on its own time and taking up its own resources(albeit shared with the core program, just not slowing the core down while it waits for it). This example works perfectly with saving data, as it is not time sensitive and does not need to return anything to the core program. Since scripts interact with the core (to pull or set variables/etc), this tactic gets a tad more complicated and i'm not overly sure it'd even work, but it is something i've been debating about doing.

-Another example would be to throttle the number of scripts that can execute 'at once', but this still comes back to the problem of idle scripts(executed every 1sec) having the potential to be greatly delayed. In high volumes, this delay could be as high as minutes. (say 2500 scripts, for example. Theoretical, of course, but that delay using this method would still exist)

-I've looked into multi-threading and learned how it works, and it's quite useful if used right. But my concern comes down with integrity of the variables being used by the scripts if several scripts are being run at the same time against the same mob or player. If one script on one thread changes a variable that another script on another thread is currently using ... yeah, ****(pardon my language) goes down hill fast.

So basically i'm just wondering how others have handled this issue and hoping they can share their experiences(and headaches) that this issue may have caused and how they solved it as i'm currently scratching my head over this problem. And quite frankly, it's game breaking and extremely demoralizing because I wanted a game filled with scripts to enhance 'reality' or 'believability' of the world. aka having mobs actually go to jobs and do things and wander (not aimlessly) between shops/friends/etc.

Thanks for your time and any responses,
-Kitriel
Kitriel is offline   Reply With Quote
Old 02-13-2012, 09:03 AM   #2
dentin
Member
 
Join Date: Apr 2008
Home MUD: Alter Aeon
Posts: 245
dentin is on a distinguished road
Re: High volume scripting question

Kitriel,

Any time you add threading to the system, you're opening yourself up to a whole new class of bugs and problems. Unless you know what you're doing, have the resources to spare, and are using a language that's intrinsically thread safe, you're risking a lot.

Quite frankly, I'm not smart enough to do it well, so I handled it on AA by simply running everything single threaded and simulating the multithreading aspect using event handlers. We currently have three lists with different time bases, and shortly after boot we have about 25k events pending:

Slice events: 21555
Prompt events: 2978
Tick events: 850

While AA is a moderately sized game in terms of DB size, I wouldn't consider it particularly 'NPC active'; my guess is that with everything you want to do on your server, you're going to have an order of magnitude more stuff going on. Consider for the moment that you may end up having half a million threads, and I think the scale of the problem with threading becomes clear.

So in short, I would recommend running everything except for possibly world saves single threaded using your own internal event queues. Doing this eliminates the need for all the expensive locking, and guarantees consistency of data without it needing to be explicitly handled. You do have to take care of proper destruct handling, but that's arguably less of a concern than managing 100k threads, and will be easier to debug (especially if you use structure pools.)

Another thing to consider is that there's a CPU processing limit, and that if you're doing this because you need more cores to handle the workload, you're probably doing something wrong. At full bore with a hundred people logged in, 30k events in the queues, and 25k mobs, the AA server runs 1-5% CPU; even with a world ten times as complex, there should be no reason to thread the workload as long as the latency requirements are met.

-dentin

Alter Aeon MUD
http://www.alteraeon.com
dentin is offline   Reply With Quote
Old 02-13-2012, 09:50 AM   #3
Kitriel
New Member
 
Join Date: Jul 2010
Posts: 10
Kitriel is on a distinguished road
Re: High volume scripting question

First, thanks for the response Dentin.

Second, just to be clear, I don't actually have threading implemented. I tried it, and took it out because at that moment I had no need for it and it just made everything needlessly complex.

The game runs smooth as butter except for this one issue. I accidentally stumbled onto this issue when I implemented randomly generated areas and putting an idle script on each mob in the areas generated. At around 60 idle scripts, the game starts to hiccup every second. At 250 it becomes unplayable. The issue is that all of these idle scripts are being executed at once, and the game has to wait for all of them to finish before it can continue.

I tried staggering them slightly, by tracking the exact millisecond the script executes and adding a second to that(instead of the simple execute all idle scripts each second), so that for example script 1 executes at 0.2sec and script 2 executes at 0.21sec and so on. Although it helped slightly, the issue is still there.

And that's why i'm here, because atm i am just stumped as to what to do or how to fix this.

-Kitriel
Kitriel is offline   Reply With Quote
Old 02-13-2012, 05:48 PM   #4
camlorn
Member
 
Join Date: Aug 2011
Posts: 144
camlorn is on a distinguished road
Re: High volume scripting question

Hi,
So I'm no expert on programming or anything, but I'm curious about stuff and did look at this issue. A few thoughts which may or may not be good ideas; take these with a grain of salt.

First, lua has something called coroutines, which basically lets you pause and play executing scripts; this would allow you to simulate multitasking. Have each script execute for a set time each iteration through the loop, pause, handle whatever, and start again.

As for script integrity, in general, that's a very tricky issue. I'd say don't let scripts touch anything manipulated by the engine, and the engine anything by the scripts, but that does limit a lot of possibilities. Iirc, coffeemud did something like that; if you wish your script or whatever to affect a player, say, int +2, you send out a message that says you're now affecting the player that way, and the player class handles applying your affect in the math.

But, my immediate idea would be this: a critical block. That's a name I gave it; there probably is an actual name out there for it. Basically, have a method, begincritical() and endcritical(), such that the script is garenteed to run uninterrupted from the beginning to the end. The major drawback to that is that now, to use this safely, builders have to know about threading and when to (not) use it. There's a variety of approaches out there, if you want to go that route, look up thread safety and mutex.

In line with the above, have objects marked as unmodifiable and make the game engine not touch them until they become modifiable again; this is basically clallbacks, and is really a suboptimal sollution.

Finally, I really don't think you should see that much slowdown. The easiest bit is to have the engine only execute so many scripts each time through the main loop; players aren't giong to notice errors from that. But that again introduces possible bugs.

Honestly, if you're creating the area with these on idle scripts, don't; implement it in the codebase. If you're just making the mobs say a random line, there's some functionality to add to olc. Also look at optimizing the actual functions that scripts call into. I know gcc has a profiler which looks halfway decent, as does visual studio ultimate which isn't free by any means.

Just some (useless?) thoughts.
camlorn is offline   Reply With Quote
Old 02-14-2012, 12:48 AM   #5
Ide
Senior Member
 
Join Date: Feb 2006
Location: Seattle
Posts: 361
Ide will become famous soon enoughIde will become famous soon enough
Re: High volume scripting question

Quote:
Originally Posted by Kitriel View Post
The game runs smooth as butter except for this one issue. I accidentally stumbled onto this issue when I implemented randomly generated areas and putting an idle script on each mob in the areas generated. At around 60 idle scripts, the game starts to hiccup every second. At 250 it becomes unplayable. The issue is that all of these idle scripts are being executed at once, and the game has to wait for all of them to finish before it can continue.
What happens if, instead of each mob running its own idle script, the game runs an update function or holds an update queue and calls each mob in turn as necessary?
Ide is offline   Reply With Quote
Old 02-14-2012, 08:40 AM   #6
dentin
Member
 
Join Date: Apr 2008
Home MUD: Alter Aeon
Posts: 245
dentin is on a distinguished road
Re: High volume scripting question

Kitriel,

Instead of scheduling the events to happen one second from now, schedule them to happen at 1 second plus or minus 200 ms. This way your long term timing at once per second will be preserved, but after a very few iterations they'll be spread out all over the place instead of bunched up.

However, I think you've answered your original question: if the server and/or machine is becoming unplayable at a mere 250 scripts per second, then you simply cannot do high-volume scripting with the tools you've picked. Lua is powerful and convenient, but it's interpreted; it's not designed for speed or performance. If you really want to do high-volume work, you'll probably have to switch to a higher speed language like C.

Good luck!

-dentin

Alter Aeon MUD
http://www.alteraeon.com
dentin is offline   Reply With Quote
Old 02-15-2012, 06:53 PM   #7
camlorn
Member
 
Join Date: Aug 2011
Posts: 144
camlorn is on a distinguished road
Re: High volume scripting question

So, did you solve this?

Also, if you haven't; there's a small chance you're repeatedly loading the lua code and then executing it. If you load lua code from a text representation (string in memory, text file), the lua engine compiles it to bytecode. Sollution: cache the returned bytecode or call lual_loadstring (sp?) only once. I'm not a lua expert, again, but have been looking at lua as something to use in one of my own projects, when I get around to it.
camlorn is offline   Reply With Quote
Old 02-16-2012, 09:34 AM   #8
Kitriel
New Member
 
Join Date: Jul 2010
Posts: 10
Kitriel is on a distinguished road
Re: High volume scripting question

Camlorn, thanks for that suggestion. Caching the bytecode instead of using lua_dofile decreased script run time from ~0.005sec per script to ~0.0005 to ~0.001sec per script. Not exactly where I wanted it, but it's certainly faster this way. (Ideally, I want it to be able to run 10k scripts without having any lag at all ... maybe that's wishful thinking :P)

In addition to the above, I also added an 'active' system to areas. If a player is not in an area for over 5min, it becomes inactive (thus suspending all scripting action in the area). This, coupled with the 50 script throttle (only 50 scripts can be executed in one sitting), the lag is basically non-existant now. But, the potential for script delay is still there and i'll continue to work on this. (if there's 25000 scripts and only 50 get cycled through every 0.01sec, the last scripts would be way longer than 1sec intervals).

If anyone has any other suggestions or ideas, feel free to post. And thank you to everyone that has posted ideas and what not.

-Kitriel
Kitriel is offline   Reply With Quote
Old 02-16-2012, 12:09 PM   #9
camlorn
Member
 
Join Date: Aug 2011
Posts: 144
camlorn is on a distinguished road
Re: High volume scripting question

Hi, so I do have some more...

First, what exactly are you working on? I'd be curious to see. I mean, the game in general.

Second, there are a few things you can do to help the scripting problem. I really think, given the time you're siting, that you should implement a scheduler of which two approaches present themselves: dedicating a certain amount of time to each script before pausing or allowing scripts to run more often.

So basically, the first of these is what windows does: your application gets so many microseconds to process before windows allows the next and the next, going around forever...This is oversimplified. I don't begin to understand the windows scheduler beyond the basics, but it is an interesting idea. Again, lua coroutines, or some other pausing mechanism. Depending on your situation, you could allow the mud to use 100% of cpu, so...

The second approach is a bit different. I'm making a few assumptions here, however. Given a main loop and some delay to prevent full cpu usage, remove the delay and reprogram it so that it's only idle when no scripts are left. Each time through, check the scripting queue and run, say, 5 or 500 or whatever of the scripts waiting to execute; if other things need delay, it becomes a bit tricky (I can see what you'd have to do in that case, but can't seem to express it).

Finally, do consider other solutions. If you need dialog trees, build a dialog tree editor in c++, save the tree with the mob, and have the leaves set flags or not. Basically, this is what most of the major games with dialog on like ps3 are doing; I've never heard of another approach. Given some initial response, and 3 responses, and 3 responses off each of those, you've got nine leaves; either assign each leaf a script or give each leaf the ability to flag the player somehow.

Just my thoughts; again, I've done none of this in practice (yet).

And, you probably don't need nor will you ever have thousands of scripts per second...if you do, consider reimplementing scripts that load everywhere in c++. Circlemud, for instance, has mob behaviors, where a heal script becomes a flag that says this mob heals people periodically, or there's one for this mob casts spells...basically, if builders are writing a bunch of scripts to do the same thing, try moving it to the engine.
camlorn is offline   Reply With Quote
Old 02-16-2012, 04:59 PM   #10
Kitriel
New Member
 
Join Date: Jul 2010
Posts: 10
Kitriel is on a distinguished road
Re: High volume scripting question

Camlorn,

First, unfortunately the project I am working on is not open to the public but I can supply you with some teaser pictures i've uploaded for friends. (Pictures by 7tus - Photobucket). It won't be open to the public til i'm at least 95% happy with where the game is and when it has a solid world. But basically, it's a complete codebase written from scratch. I haven't even seen any source code from other muds.

As for your first suggestion, I will look into it. I'm not overly sure where allowing each script 0.0001sec run-time vs allowing only 50 scripts full run-time per cycle of the mud loop would be more beneficial or quicker. But I will look into it.

Second, I already do this. There is no 'pause' in the mud loop at the moment so everything is being calculated/etc the second it needs to be. I haven't seen an issue with this, and at full script running speed the cpu sits at 50% (running 50scripts/cycle).

As for dialog trees, i'm not 100% sure what you mean by these and i'll certainly look them up. But if they are what I think they are (more trigger scripts based on user action than self run scripts based on time), I already have a ton of these implemented. Not only on the mob for certain events(such as someone entering/leaving the room or giving the mob an item) but also the capability for the builder to set unique trigger scripts based on user input (such as trying to interact with an object in the room desc or on the ground/etc. Basically whatever keyphrase the builder wants).

Once again, thanks for your suggestions and ideas. They're greatly appreciated since i've been beating my head against the wall on this issue for quite some time now.

-Kitriel
Kitriel is offline   Reply With Quote
Old 02-16-2012, 07:36 PM   #11
camlorn
Member
 
Join Date: Aug 2011
Posts: 144
camlorn is on a distinguished road
Re: High volume scripting question

Hi again;

First, thanks for the pictures. I'm unfortunately visually impaired and will not be looking at them. In case you weren't aware, that is a good advertising avenue/playerbase source: making sure your game is blind-accessible. Not hard to do, I assure you, but this is taking the topic in another direction.

Recall I did say that I was only making suggestions based on somewhat shaky assumptions. This could be totally wrong; I don't have nearly enough experience to come close to calling myself an authority on this. Listen to dentin or KaVir over me, as I can personally vouch for them, or just about anyone else on here who's actually done this.

Anyhow, the idea with allowing scripts a certain time is this, and it may (probably?) isn't applicable in your case:

Using the numbers, both before and after as an illustration (this is good because it's going to run slower until those scripts run the first time).

You have scripts taking anywhere from 1 millisecond to .5 milliseconds and want to run 50 each game loop. Assume that you have some scripts queued, and that (due to players) you can't control which. They could take anywhere from .5 milliseconds all the way up to 1 millisecond each. So, you have as a worst-case scenario 50 milliseconds and a best-case scenario of half that: 25 milliseconds.

Here's the catch. You have to write your game logic to assume the worst-case scenario, if you want no lag whatsoever.

Let's assume that you account for the worst-case scenario above. You allot 50 scripts and assume at worst, 50 milliseconds.

Well, ok, good. So you get a bunch of scripts queued. But. It's one of the iterations after the mud's been up for a day, and each one's going to take only .5 seconds. So, you account for 50 milliseconds, but can't let the mud just barrel ahead because that's going to cause combat to speed up and slow down as well. So you have to add a delay in for the unused time: 25 milliseconds in which potentially another fifty scripts could get done without waiting for the next iteration.

As I said, lua coroutines would allow you to pause the scripts after a certain period of time; alolow .5 milliseconds for each script to run, or even .1 really, and pause until the next iteration, whereupon you unpause them. Now, you've got 100 running in parallel with no noticeable lag.

So, that said, that does introduce some potential bugs that I could forsee, depending on use-case. You'd probably have to add additional functionality to avoid them, but if you really want to run thousands of scripts at the same time, you're looking at something like this or even more complex (threads and a multi-core system would work wonders, but as dentin said is beyond difficult to get right).

One final note. If you're not providing the computer and are working off your home pc, you need to consider that a server is generally sharing processing power with other stuff. The nice not-laggy codebase that's the only piece of software running in an environment with all sorts of priveleges and no virtualization...that's going to come crashing down when you put it on someone else's machine. At least, if you're not prepared. If you want to run thousands of scripts (a goal I kinda agree with), you're either going to have to provide the computer or do a ton of optimization.

Also, something that you could check. Try compiling without debugging if you aren't already. I didn't know till earlier this week that f5 in visual studio for instance slows down the application by 5 times. This one's direct from my c++ professor who's been teaching for 16 years; he made a point of telling us. Just something to check.

When are you going to open? I'd be interested to see a new type of mud, that is, one done from scratch. So many are circle/diku/<derivitive used by everyone else goes here>.
camlorn is offline   Reply With Quote
Reply


Thread Tools


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off

All times are GMT -4. The time now is 12:19 PM.


Powered by vBulletin® Version 3.6.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Style based on a design by Essilor
Copyright Top Mud Sites.com 2014