www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Idea about memory management. Game related.

reply Chad J <gamerChad _spamIsBad_gmail.com> writes:
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.
May 30 2006
next sibling parent Sean Kelly <sean f4.ca> writes:
Chad J wrote:

 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.

 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.


 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
May 30 2006
prev sibling next sibling parent Marcio <mqmnews123 sglebs.com> writes:
Chad J wrote:

 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
Jun 02 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
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.
Jun 02 2006
next sibling parent reply AgentOrange <AgentOrange_member pathlink.com> writes:
In article <e5q8sd$214f$1 digitaldaemon.com>, Walter Bright says...

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.


Thank you Walter, this is all useful information. But what about array
operations? Should one avoid using D arrays as well?
Jun 02 2006
next sibling parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
AgentOrange wrote:

 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 +/
Jun 02 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
AgentOrange wrote:

 But what about array
 operations? Should one avoid using D arrays as well?


I don't see why one would avoid them.
Jun 02 2006
parent reply MM <MM_member pathlink.com> writes:
In article <e5ql8i$2abs$2 digitaldaemon.com>, Walter Bright says...

AgentOrange wrote:

 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)
Jun 11 2006
parent reply Chad J <gamerChad _spamIsBad_gmail.com> writes:
MM wrote:

 In article <e5ql8i$2abs$2 digitaldaemon.com>, Walter Bright says...
 

AgentOrange wrote:


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.
Jun 11 2006
parent reply MM <MM_member pathlink.com> writes:
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
Jun 12 2006
next sibling parent reply Chad J <gamerChad _spamIsBad_gmail.com> writes:
MM wrote:

 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.
Jun 12 2006
parent reply pragma <pragma_member pathlink.com> writes:
In article <e6kd4u$300u$1 digitaldaemon.com>, Chad J says...

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;


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
Jun 12 2006
parent reply Sean Kelly <sean f4.ca> writes:
pragma wrote:

 In article <e6kd4u$300u$1 digitaldaemon.com>, Chad J says...

 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;


 
 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
Jun 13 2006
next sibling parent Chad J <gamerChad _spamIsBad_gmail.com> writes:
Sean Kelly wrote:

 pragma wrote:
 

 In article <e6kd4u$300u$1 digitaldaemon.com>, Chad J says...


 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;



 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!
Jun 13 2006
prev sibling parent reply Daniel Keep <daniel.keep.lists gmail.com> writes:
Sean Kelly wrote:

 pragma wrote:

 In article <e6kd4u$300u$1 digitaldaemon.com>, Chad J says...

 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;


 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/
Jun 13 2006
parent reply pragma <pragma_member pathlink.com> writes:
In article <e6nl5h$1kcj$1 digitaldaemon.com>, Daniel Keep says...


[snip]

 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



 Jun 13 2006



  parent  Sean Kelly <sean f4.ca>  writes:


pragma wrote:

 In article <e6nl5h$1kcj$1 digitaldaemon.com>, Daniel Keep says...
 [snip]

 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



 Jun 13 2006



prev sibling  parent  Walter Bright <newshound digitalmars.com>  writes:


MM wrote:

 Okay, so reading and writing to those arrays would not trigger gc, right?


Right.


 I can use arrays without malloc as long as I don't change it size, right?
 right? :D


Right.



 Jun 12 2006



prev sibling next sibling parent  Bruno Medeiros <brunodomedeirosATgmail SPAM.com>  writes:


Walter Bright wrote:

 
 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



 Jun 03 2006



prev sibling  parent  Chad J <gamerChad _spamIsBad_gmail.com>  writes:


Walter Bright wrote:

 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.
 


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.


 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 :)


 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!



 Jun 04 2006