 |
Phantasmal MUD Lib for DGD
|
Phantasmal Site > DGD > Running a MUD > Scalability How Far Will DGD Scale?
From: dgd at list.imaginary.com (Erwin Harte)
Date: Mon Nov 12 11:39:01 2001
Subject: [DGD] Users
On Mon, Nov 12, 2001 at 06:18:13PM +0100, Troels Therkelsen wrote:
[...]
>
> Someone more into the black magic of the internals of the DGD driver will
> have to answer what the max value you can safely set users to is.
DGD will let you go up to whatever EINDEX_MAX is:
---- Quote from dgd/src/config.c ----
{ "users", INT_CONST, FALSE,
1, EINDEX_MAX },
----
In config.h you'll see that EINDEX_MAX is UCHAR_MAX, which I would
assume to be 255?
Of course if you change the typedef for eindex to something bigger and
change the EINDEX_MAX and EINDEX defines then you can go further, as
long as your operating system or user-limits don't stop you sooner.
Regards,
Erwin.
--
Erwin Harte
From: dgd at list.imaginary.com (Erwin Harte)
Date: Wed Dec 24 11:21:01 2003
Subject: [DGD] 4 bytes should be enough for anyone.
Nice gotcha I ran into this morning, thought it would be worth sharing
it and its solution with others:
I use a heuristic to occasionally force a swapout() when a lot of
memory has been allocated but a significant amount is not in use
(anymore), to avoid cluttering up the memory from the operating
system's point of view.
The condition I used is (simplified):
if (mem_used < 2 * mem_allocated / 3) {
/* trigger swapout */
}
So if I have 120MB allocated and less than 80MB is in use, it'll do
that quite nicely.
However, this morning the memory usage rose to about 1.5GB (1513MB to
be precise) and strangely enough the swapout didn't trigger. Closer
inspection revealed that:
1513 * 1024 * 1024 = 1586495488
1586495488 * 2 = -1121976320
1586495488 * 2 / 3 = -373992106
Uhm, oops, we ran into the limit of integers and since memory usage is
never going to be negative, it would happily continue to drag those
1.5GB of virtual memory around.
This should work without running into this particular problem:
if (mem_used / 2 < mem_allocated / 3) {
/* trigger swapout */
}
:)
Cheers,
Erwin.
--
Erwin Harte
From: dgd at list.imaginary.com (Par Winzell)
Date: Sat Apr 3 15:36:07 2004
Subject: [DGD] Re: Clones and very large arrays
Robert,
> So is there anything to stop me from making it an unsigned long, giving
> me a generous 2.1 million elements or so? I know 2.1 million isn't
> feasable for obvious reasons, but this is just a cap, right?
The basic reason (as I understand it) there is a limit is because DGD
implements powerful operators in the core language, such as array
addition and string addition, whose execution times are more or less
linearly proportional to the size of the operands (arrays).
Whenever linear operations are used for fundamental operations (clones
of a clonable is a perfect example), scalability goes out the window.
Making a game truly scale is surprisingly difficult, and pretty much the
first thing you do is get rid of every single place where you use an
array to store anything substantial.
If there are N clones of an object and cloning a new object takes time
proportional to N, then it takes N^2 time to clone all those objects.
That's the crux of the problem. It means that if your prototype runs
just fine on one machine with 300 players, you need your production
release to handle a thousand players, and you're already hovering near a
quadratic bottleneck, you will need to scale your hardware by a factor
10 to achieve a tripling of the playerbase. If you want to run the game
with 3,000 players, you'll need a cluster of one hundred machines.
In reality, this means that a server that uses linear-time
implementations of fundamental operations will never outgrow the
prototype stage.
So what do you do?
> I'm also wondering if it would be ok to have an array of arrays storing
> the clones:
> ({ ({ a_lot_of_clones }), ({ some_more_clones })... })
>
> Are there any reasons not to do it that way?
That's a possibility, and avoids the full O(N^2) problem, but it's kind
of clunky. I'd suggest using mappings of mappings for virtually every
place you store a significant list of anything. We have long since
written special-purpose LWO's for the Skotos mudlib (called bigmaps)
that do the grunt work of maintaining sets.
Thus clone-maintenance code looks something like:
object clones;
static void create() {
clones = new_object("/data/ob_bigmap");
}
atomic void add_clone(object clone) {
clones->add(clone);
}
atomic void del_clone(object clone) {
clones->del(clone);
}
object iterator() {
return clones->iterator();
}
while ob_bigmap.c looks something like (this is from memory, it will
probably not compile) --
mapping mapofmaps;
static void create() {
mapofmaps = ([ ]);
}
private atomic mapping get_row(object ob) {
mapping row;
int ix;
/* I kind of wish status(ob) returned the clone number */
if (sscanf(object_name(ob), "%*s#%d", ix) != 1) {
ix = status(ob)[O_INDEX];
}
row = mapofmaps[ix / 1024];
if (row == nil) {
row = mapofmaps[ix / 1024] = ([ ]);
}
return row;
}
atomic void add(object ob) {
get_row(ob)[ob] = TRUE;
}
atomic void del(object ob) {
get_row(ob)[ob] = nil;
}
object iterator() {
return new_object("/data/bigmap_iterator", mapofmaps);
}
I will leave the iterator as an excercise for the reader. :)
Zell
From: dgd at list.imaginary.com (Par Winzell) Date: Sat Apr 3 15:42:11 2004 Subject: [DGD] Clones and very large arrays > I'm using a linked list. This distributes the data across more objects (to > mitigate swapping concerns) and avoids any issues with respect to max array > size. Though obviously getting the actual list of all clones isn't anywhere > near as fast as it would be by your method. I don't find a need to get that > information too often, though. The problem with this approach is that in my experience, minimizing swapping is your primary concern, especially now that call_touch() actually enables us to affect objects without swapping them in. If you use a linked list where the next/prev pointers are stored in the actual objects, then to even enumerate all the clones of a clonable, you have to swap them all in. Swapping a quarter of a million objects into memory is not realistic, and if you do it lazily (i.e. try not to freeze your game) it takes hours and hours. Zell
From: DGD Mailing List (Par Winzell)
Date: Sun Apr 4 09:16:05 2004
Subject: [DGD] Re: Clones and very large arrays
Robert Forshaw wrote:
> Thanks for that, it was very insightful. I have a few questions.
>
> First of all, the following line:
>
> get_row(obj)[obj] = TRUE;
>
> seems to suggest that mappings are passed by reference! Is this the
> case? I wasn't aware of it.
Yes, they are, at least to some extent. I believe the contract with the
driver is that references last as long as you stay either inside one
thread or inside one object. In other words, if you store a reference in
one object, export it to another, and the thread ends, DGD reserves the
right to create a private copy of the mapping/array in the other object.
So you can't keep long-term references to data inside another object.
> Secondly, I understood everything in the code except the iterator. I
> know what an iterator is, but that's about it. I wouldn't mind knowing
> what was in /data/bigmap_iterator, but you haven't revealed that. I also
> have no idea what the second argument to new_object is supposed to be,
> as the driver version doesn't have one.
We redefined new_object() in our system-level auto object for
convenience; it reads something like (again from memory) --
static atomic
object new_object(mixed ob, mixed args...) {
ob = ::new_object(ob);
/*
** actually this is a simplification; we relay the call through a
** _F_configure() function to allow configure() to be static
*/
::call_other(ob, "configure", args...);
return ob;
}
> Thirdly, why 1024? As opposed to any other number.
No particular reason. It means you assume nobody is ever going to set
DGD's max-array-size parameter lower than 1024, and it means that you
can store a total of max-array-size * 1024 objects. You could make it
e.g. 4096 if you preferred. If you mean 1024 rather than e.g. 1000, 1024
is just a rounder number (2^10).
As for the iterator, there's a lot of ways you could implement it. There
are two basic kinds of iterators in the world; one that promises it will
capture the state of the data-structure when iterator() is called and so
even if the data structure itself changes later, the iterator will still
enumerate precisely what was there when the snapshot was made...
... and one kind of iterator that makes no such promise. Obviously the
former kind has to either use more memory, or special tricks. If you
don't mind the iterator using a fair bit of memory (temporarily) you can
simply let the iterator LWO make a private copy of the bigmap, keep
two index counters (one to index the mapping of mappings, one to index
the current inner mapping), and step through the whole thing step by
step as next() is called.
I stole Sun's most recent interface pretty much directly;
int has_next();
mixed next();
int size();
The nice bit about generalized iterators is that you are free to vary
your internal implementation both of the datastructure and of the
iterator as you please. All the caller cares about is being returned an
object that keeps track of the iteration state. For example, the Skotos
all-clones-of-a-certain-clonable data structure uses a SINGLE mapping
only. If the number of clones of a clonable grows beyound 1024 or so
(maybe we use 2048 or 4096), we just empty the data structure (!). Why?
Because DGD offers a second method to enumerate all the clones of a
given clonable, namly find_object().
Thus, for clonables with lots of clones, we return an iterator that
reads basically:
string clonable;
object next;
int ix;
static atomic
void configure(string str) {
clonable = str;
ix = 1; forward();
}
int has_next() {
return !!next;
}
object next() {
if (next) {
object ob;
ob = next;
forward();
return ob;
}
error("read past end");
}
private
void forward() {
while (ix <= status()[ST_OTABSZ]) {
next = find_object(clonable + "#" + ix);
ix ++;
if (next) {
return next;
}
}
next = nil;
}
From: Erwin Harte
Subject: [DGD] Big, bigger... biggest?
Date: Wed Jan 5 02:55:01 2005
Hello,
About 2-3 months ago the Castle Marrach game at Skotos
(www.skotos.net) broke the 2GB barrier, with its statedump currently
at 525394 sectors of 4k each:
> code 525394 * 4 * 1024
$40 = -2142953472
:-)
Are there any other big DGD-using games out there, or does that make
it the biggest DGD-based game in existence?
Cheers,
Erwin.
P.S: Good to see the list back up and running. :)
--
Erwin Harte
|