Discussion:
Idea about memory management. Game related.
(too old to reply)
Chad J
2006-05-31 04:53:24 UTC
Permalink
I intend to use D for game programming, and I will probably be facing a
lot of the memory management problems that other D game programmers seem
to be facing. I've read some good posts about this, like the one that
cropped up here a few days ago. Anyhow, I came up with this idea, and I
thought I'd run it by you folks.

My idea is to spawn a thread in C/C plus plus to handle the graphics,
audio, and anything else that needs to run smoothly no matter what. I'd
use a C thread because it would (I think) not be paused when D runs a
garbage collection. Then I could use the D program to do the other
stuff that would benefit from the GC, like GUI, skillsystem, AI, etc.
That way I can have uninterrupted working of the parts that need it, yet
still have development speedup from GC for everything else.

This comes from the perspective of writing a game for a PDA, as soon as
arm-wince-gdc is done. I am assuming that garbage collection will be
quite noticeable on an Xscale 400 MHz that has to do software graphics,
though I won't know for sure until I write the thing. I want to make
large parts of my game moddable, and I think C plus plus is probably a
crappy scripting language. I think D could do it though, and I'd put
all the user-modifiable code in a DDL or something so that mods can be
easily be dropped in after being compiled on a desktop or some such.
The idea of using a C thread kinda stemmed from my original plan to use
Java with C to accomplish the same thing. The lack of good Java VMs for
PDAs and Java's intense difficulty in talking to C have made me not want
to do the Java thing though, and D is faster anyways (probably easier
too). I really want Garbage Collection for parts of my game because
imposing manual memory management makes things a good deal harder to
code, which is very bad for both development time and modability. The
graphics, audio, and such can be done C style though because it'll all
be under the hood.

If this sort of thing would work well, it'd be nice to see
language/library support for this. Seems like a waste of perfectly good
man-hours to have to do all that C coding just to get a thread that
isn't paused by garbage collection. Perhaps some sort of thread-level
control over what style of memory management is used would work?
Something like this:

Thread GCed = new Thread( GARBAGE_COLLECTED ); /*GC'd memory*/
Thread MMed = new Thread( MANUAL ); /*manually managed, no pauses*/

or maybe

Thread T = new Thread();
gc.disable( T ); /*Main thread is still GCed, but T is not and it will
never pause*/

Also, correct me if I'm wrong, but it seems to me that something like
automatic reference counting would be much better for games than
mark-and-sweep garbage collection, and would still easy to use. Maybe
not as efficient as doing it by hand or using mark-and-sweep, but
probably worth it in development time.
Sean Kelly
2006-05-31 06:00:44 UTC
Permalink
Post by Chad J
I intend to use D for game programming, and I will probably be facing a
lot of the memory management problems that other D game programmers seem
to be facing. I've read some good posts about this, like the one that
cropped up here a few days ago. Anyhow, I came up with this idea, and I
thought I'd run it by you folks.
My idea is to spawn a thread in C/C plus plus to handle the graphics,
audio, and anything else that needs to run smoothly no matter what. I'd
use a C thread because it would (I think) not be paused when D runs a
garbage collection. Then I could use the D program to do the other
stuff that would benefit from the GC, like GUI, skillsystem, AI, etc.
That way I can have uninterrupted working of the parts that need it, yet
still have development speedup from GC for everything else.
Just be aware that if you use mutex-protected shared data for
communication with that thread, a GCed thread could be suspended during
a collection while it holds the lock and effectively block your
"real-time" thread from making progress. Test-acquire might be handy
here, which means you wouldn't be using the 'synchronized' statement either.
Post by Chad J
If this sort of thing would work well, it'd be nice to see
language/library support for this. Seems like a waste of perfectly good
man-hours to have to do all that C coding just to get a thread that
isn't paused by garbage collection. Perhaps some sort of thread-level
control over what style of memory management is used would work?
I've considered it in the past, but issues like the above have stopped
me from going ahead with the idea. Between that and resource tracking
difficulties when some roots are unavailable for scanning and it's
simply too easy for the user to make a mistake. I'd prefer to have a
specialized GC for this purpose--incremental perhaps, so threads are
rarely/never suspended.
Post by Chad J
Also, correct me if I'm wrong, but it seems to me that something like
automatic reference counting would be much better for games than
mark-and-sweep garbage collection, and would still easy to use. Maybe
not as efficient as doing it by hand or using mark-and-sweep, but
probably worth it in development time.
Perhaps, but without object copy semantics in D, rc-pointers are not the
panacea they are in Cpp. I wouldn't worry too much about garbage
collection in D for now, as I suspect performance and such will improve
before too terribly long.


Sean
Marcio
2006-06-02 15:52:52 UTC
Permalink
Post by Chad J
I intend to use D for game programming, and I will probably be facing a
lot of the memory management problems that other D game programmers seem
to be facing.
Can't we rephrase your message as "We need incremental, time-bounded,
Garbage Collection for D instead of Mark & Sweep" ?

Dave Ungar has done this type of stuff for Smalltalk a few decades ago.
It makes your app 3..5% slower, but without long pauses. Can you afford
5% degradation? See
http://www.smalltalkconsulting.com/papers/papersByOthers/visualworksGCTheory.html


I also remember the Train Algorithm in an ECOOP conference, probably in
1995. Just over a decade ago :-) It was done in Beta originally. Here:
http://www.daimi.au.dk/~beta/Papers/Train/train.html . I think I heard
those guys ended up working on it for the JVM, and it got added to the
HotSpot JVM. See http://www.artima.com/insidejvm/ed2/gc9.html

Pure Mark&Sweep is a bit too basic these days.

marcio
Walter Bright
2006-06-02 20:57:58 UTC
Permalink
The gc will pause all threads when it does a collection, even if those
threads are in another language.

Some thoughts:

1) The gc will only pause threads it knows about. So you can create a
thread that is unknown to the gc by calling the operating system thread
creation APIs directly. However, if you do this, then those threads must
not manipulate or reference any gc allocated data.

2) Using C++ new or malloc is no guarantee of latency. Neither of them
have any constraints on how long they take to call, and (due to
fragmentation) can cause a significant pause.

3) To deal with (2), professional game programmers I've talked to will
"preallocate" all the data they'll need before running the task that
cannot be paused.

4) It is very important to realize that the gc will not collect at some
random time. It will ONLY collect during calls to new. No calls to new,
no collections.

5) Therefore, to avoid pausing during critical times in the game, avoid
calling new during those times. You can call malloc() instead if
necessary. Calling malloc() won't cause the gc to run.

6) Collection pauses can be minimized by running the gc collector during
idle loops, such as waiting for user input.
AgentOrange
2006-06-02 22:43:32 UTC
Permalink
In article <e5q8sd$214f$1 at digitaldaemon.com>, Walter Bright says...
Post by Walter Bright
The gc will pause all threads when it does a collection, even if those
threads are in another language.
1) The gc will only pause threads it knows about. So you can create a
thread that is unknown to the gc by calling the operating system thread
creation APIs directly. However, if you do this, then those threads must
not manipulate or reference any gc allocated data.
2) Using C++ new or malloc is no guarantee of latency. Neither of them
have any constraints on how long they take to call, and (due to
fragmentation) can cause a significant pause.
3) To deal with (2), professional game programmers I've talked to will
"preallocate" all the data they'll need before running the task that
cannot be paused.
4) It is very important to realize that the gc will not collect at some
random time. It will ONLY collect during calls to new. No calls to new,
no collections.
5) Therefore, to avoid pausing during critical times in the game, avoid
calling new during those times. You can call malloc() instead if
necessary. Calling malloc() won't cause the gc to run.
6) Collection pauses can be minimized by running the gc collector during
idle loops, such as waiting for user input.
Thank you Walter, this is all useful information. But what about array
operations? Should one avoid using D arrays as well?
Tom S
2006-06-02 23:45:07 UTC
Permalink
Post by AgentOrange
Thank you Walter, this is all useful information. But what about array
operations? Should one avoid using D arrays as well?
During the real-time loop, yeah... In my experience, even the most
innocent memory allocations trigger the GC - and if you have lots of mem
allocated, you're going to get stalls. There are at least two options here:

1. use malloc for D arrays - an array struct template might be useful
2. bribe Walter with some cookies so he implements std.gc.disable()

And just a quick note: if you use malloc'd arrays to store object
references, remember to add the array to the GC or your objects will get
GCd.
--
Tomasz Stachowiak /+ a.k.a. h3r3tic +/
Walter Bright
2006-06-03 00:29:16 UTC
Permalink
Post by AgentOrange
But what about array
operations? Should one avoid using D arrays as well?
I don't see why one would avoid them.
MM
2006-06-11 22:47:11 UTC
Permalink
In article <e5ql8i$2abs$2 at digitaldaemon.com>, Walter Bright says...
Post by Walter Bright
Post by AgentOrange
But what about array
operations? Should one avoid using D arrays as well?
I don't see why one would avoid them.
Yes, could anybody pls explain why one should avoid using arrays for 'real'-time
threads?
(Also interested in creating a game engine in D)
Chad J
2006-06-12 03:05:56 UTC
Permalink
Post by MM
In article <e5ql8i$2abs$2 at digitaldaemon.com>, Walter Bright says...
Post by Walter Bright
Post by AgentOrange
But what about array
operations? Should one avoid using D arrays as well?
I don't see why one would avoid them.
Yes, could anybody pls explain why one should avoid using arrays for 'real'-time
threads?
(Also interested in creating a game engine in D)
byte[] A = new byte[128];
byte[] B = new byte[64];
A ~= B;

During the above concatenation, A will need to have 64 more bytes
allocated for it to hold the extra elements from B. Walter has said
that when you allocate memory in D, with possible exceptions like that
of C's malloc, a garbage collection may happen. Therefore, a simple
concatenation such as this could cause a garbage collection that may
pause your game for seconds. Actual time may vary, but it could be
unacceptable.

You might be able to reduce the frequency of garbage collections by
overallocating arrays, perhaps by doing something like
A.length = neededLength;
or
A.length = A.length * 2;
before you run your real-time code. Then the copy of B would fit in A
and no alloc would be needed. You could eliminate the threat of a
collection entirely by ensuring that no operations requiring new memory
are called unless there is enough memory available to complete them
without allocation.

I think you should be fine using arrays as long as you are careful with
them.
MM
2006-06-12 16:07:47 UTC
Permalink
Okay, so reading and writing to those arrays would not trigger gc, right?
I can use arrays without malloc as long as I don't change it size, right?
right? :D
Chad J
2006-06-12 18:52:22 UTC
Permalink
Post by MM
Okay, so reading and writing to those arrays would not trigger gc, right?
I can use arrays without malloc as long as I don't change it size, right?
right? :D
Afaik, those things should be fine.

Only one other thing I can think of to watch out for at the moment:

byte[] A = new byte[128];
byte[] B = new byte[64];
A = B;

Once it executes A = B, the memory held by what was once A is leaked
until a garbage collection occurs. I'm not sure, but this could mean
longer and more frequent garbage collections, unless you avoid
allocating on the gc heap altogether for the rest of the program's
execution. This would call for some manual management, like so:

byte[] A = new byte[128];
byte[] B = new byte[64];
delete A;
A = B;

Just make sure there don't happen to be other references to A floating
around in your program, or you are setting yourself up for disaster.

Also realize that you might be able to get away with using some GC.
What I worry about is that I don't know how well this will work in a
large game. But as long as the garbage collections don't last long
enough to be noticable, you are fine.
pragma
2006-06-12 20:18:47 UTC
Permalink
In article <e6kd4u$300u$1 at digitaldaemon.com>, Chad J says...
Post by Chad J
Once it executes A = B, the memory held by what was once A is leaked
until a garbage collection occurs. I'm not sure, but this could mean
longer and more frequent garbage collections, unless you avoid
allocating on the gc heap altogether for the rest of the program's
byte[] A = new byte[128];
byte[] B = new byte[64];
delete A;
A = B;
Wouldn't it be safe to say that if one were very pedantic about manually
deleting everything they weren't using, that any pending GC cycle would be
marginalized considerably? After all, the GC spends a lot of its time figuring
out what we already know at the point of deletion - that is, what is in use and
what is not.

- EricAnderton at yahoo
Sean Kelly
2006-06-13 23:12:19 UTC
Permalink
Post by pragma
In article <e6kd4u$300u$1 at digitaldaemon.com>, Chad J says...
Post by Chad J
Once it executes A = B, the memory held by what was once A is leaked
until a garbage collection occurs. I'm not sure, but this could mean
longer and more frequent garbage collections, unless you avoid
allocating on the gc heap altogether for the rest of the program's
byte[] A = new byte[128];
byte[] B = new byte[64];
delete A;
A = B;
Wouldn't it be safe to say that if one were very pedantic about manually
deleting everything they weren't using, that any pending GC cycle would be
marginalized considerably? After all, the GC spends a lot of its time figuring
out what we already know at the point of deletion - that is, what is in use and
what is not.
Yes. And passing some type information to the GC would also help
considerably. Currently, the GC must assume all data could potentially
be a pointer, while at the very least it should be possible for the GC
to avoid scanning array data if the arrays don't contain object
references or pointer types. For games, such bulk data probably makes
up a significant chunk of allocated storage.


Sean
Chad J
2006-06-14 00:02:15 UTC
Permalink
Post by Sean Kelly
Post by pragma
In article <e6kd4u$300u$1 at digitaldaemon.com>, Chad J says...
Post by Chad J
Once it executes A = B, the memory held by what was once A is leaked
until a garbage collection occurs. I'm not sure, but this could mean
longer and more frequent garbage collections, unless you avoid
allocating on the gc heap altogether for the rest of the program's
byte[] A = new byte[128];
byte[] B = new byte[64];
delete A;
A = B;
Wouldn't it be safe to say that if one were very pedantic about manually
deleting everything they weren't using, that any pending GC cycle would be
marginalized considerably? After all, the GC spends a lot of its time figuring
out what we already know at the point of deletion - that is, what is in use and
what is not.
Yes. And passing some type information to the GC would also help
considerably. Currently, the GC must assume all data could potentially
be a pointer, while at the very least it should be possible for the GC
to avoid scanning array data if the arrays don't contain object
references or pointer types. For games, such bulk data probably makes
up a significant chunk of allocated storage.
Sean
Sounds like my decision to use arrays instead of pointers-to-data for
all of my data (graphics and stuff traditionally done with pointers) is
not just good, but very very good. I originally decided on using arrays
just to be able to use bounds-checking during a debug phase, but I take
this as meaning it could be a big speed boost too!
Daniel Keep
2006-06-14 00:27:31 UTC
Permalink
Post by Sean Kelly
Post by pragma
In article <e6kd4u$300u$1 at digitaldaemon.com>, Chad J says...
Post by Chad J
Once it executes A = B, the memory held by what was once A is leaked
until a garbage collection occurs. I'm not sure, but this could mean
longer and more frequent garbage collections, unless you avoid
allocating on the gc heap altogether for the rest of the program's
byte[] A = new byte[128];
byte[] B = new byte[64];
delete A;
A = B;
Wouldn't it be safe to say that if one were very pedantic about manually
deleting everything they weren't using, that any pending GC cycle would be
marginalized considerably? After all, the GC spends a lot of its time figuring
out what we already know at the point of deletion - that is, what is in use and
what is not.
Yes. And passing some type information to the GC would also help
considerably. Currently, the GC must assume all data could potentially
be a pointer, while at the very least it should be possible for the GC
to avoid scanning array data if the arrays don't contain object
references or pointer types. For games, such bulk data probably makes
up a significant chunk of allocated storage.
Sean
I believe the Boehm GC has such an alloc function. I think they call it
"atomic" data or somesuch.

-- Daniel
--
Unlike Knuth, I have neither proven or tried the above; it may not even
make sense.

v2sw5+8Yhw5ln4+5pr6OFPma8u6+7Lw4Tm6+7l6+7D
i28a2Xs3MSr2e4/6+7t4TNSMb6HTOp5en5g6RAHCP http://hackerkey.com/
pragma
2006-06-14 02:20:51 UTC
Permalink
In article <e6nl5h$1kcj$1 at digitaldaemon.com>, Daniel Keep says...
[snip]
Post by Daniel Keep
Post by Sean Kelly
Yes. And passing some type information to the GC would also help
considerably. Currently, the GC must assume all data could potentially
be a pointer, while at the very least it should be possible for the GC
to avoid scanning array data if the arrays don't contain object
references or pointer types. For games, such bulk data probably makes
up a significant chunk of allocated storage.
Sean
I believe the Boehm GC has such an alloc function. I think they call it
"atomic" data or somesuch.
Didn't someone post a hack/mod to do just this over a year ago to the newsgroup?


If memory serves, all it did was somehow hint to the GC on new that the
allocated block doesn't contain pointer data - as you both have suggested. It
did this transparently, by using D's type information.

- EricAnderton at yahoo
Sean Kelly
2006-06-14 03:01:22 UTC
Permalink
Post by pragma
In article <e6nl5h$1kcj$1 at digitaldaemon.com>, Daniel Keep says...
[snip]
Post by Daniel Keep
Post by Sean Kelly
Yes. And passing some type information to the GC would also help
considerably. Currently, the GC must assume all data could potentially
be a pointer, while at the very least it should be possible for the GC
to avoid scanning array data if the arrays don't contain object
references or pointer types. For games, such bulk data probably makes
up a significant chunk of allocated storage.
I believe the Boehm GC has such an alloc function. I think they call it
"atomic" data or somesuch.
Didn't someone post a hack/mod to do just this over a year ago to the newsgroup?
If memory serves, all it did was somehow hint to the GC on new that the
allocated block doesn't contain pointer data - as you both have suggested. It
did this transparently, by using D's type information.
Yeah, I remember that as well. Haven't taken the time to try and find
the NG posts about it though.


Sean

Walter Bright
2006-06-12 18:59:43 UTC
Permalink
Post by MM
Okay, so reading and writing to those arrays would not trigger gc, right?
Right.
Post by MM
I can use arrays without malloc as long as I don't change it size, right?
right? :D
Right.
Bruno Medeiros
2006-06-03 17:47:14 UTC
Permalink
Post by Walter Bright
6) Collection pauses can be minimized by running the gc collector during
idle loops, such as waiting for user input.
Most games don't wait for user input. :D
--
Bruno Medeiros - CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Chad J
2006-06-04 20:38:52 UTC
Permalink
Post by Walter Bright
The gc will pause all threads when it does a collection, even if those
threads are in another language.
1) The gc will only pause threads it knows about. So you can create a
thread that is unknown to the gc by calling the operating system thread
creation APIs directly. However, if you do this, then those threads must
not manipulate or reference any gc allocated data.
Ah, good to know! I take this as implying that I can do my idea without
touching a line of C code, which is great.
Post by Walter Bright
2) Using C++ new or malloc is no guarantee of latency. Neither of them
have any constraints on how long they take to call, and (due to
fragmentation) can cause a significant pause.
3) To deal with (2), professional game programmers I've talked to will
"preallocate" all the data they'll need before running the task that
cannot be paused.
4) It is very important to realize that the gc will not collect at some
random time. It will ONLY collect during calls to new. No calls to new,
no collections.
5) Therefore, to avoid pausing during critical times in the game, avoid
calling new during those times. You can call malloc() instead if
necessary. Calling malloc() won't cause the gc to run.
Sounds to me like just use C++ style manual memory management. That's
fine for stuff that's under the hood in my game, but for the stuff that
modders will be working on, it is not acceptable.

If the GC can finish its collections within 50-100 millisecs, on an ARM
Xscale processor, I'm happy. I am going to use some manual memory
management to hopefully help it out. I don't think players will notice
such a short pause. A collection that would take several seconds
though, would not work.

In another response Marcio wrote about a GC that makes the app run about
5% slower but gets rid of long pauses. That is a tradeoff I would take
in an instant. Being able to do fully automatic memory management while
not worrying about pauses would be awesome, even if it causes some
performance loss. Hell I'd even try pushing something like 20%, but I
like 5% better :)
Post by Walter Bright
6) Collection pauses can be minimized by running the gc collector during
idle loops, such as waiting for user input.
I will do that of course, anything that helps, but it's no general
solution. I can't count on the player routinely going to the options
menu or some such in a clockwork fashion. There may be idle time in a
few minutes, or a few hours, or a few days. The game has to be able to
run without relying on that.

btw, Thanks for the killer language Walter!
Continue reading on narkive:
Loading...