Reposting, as I didn't have my name show up properly due to outlook express configuration fun, and any threaded readers are going to camoflauge my response to a nearly year old post :)


"Marcio" <mqmnews123@sglebs.com> wrote in message news:ecipfc$15v4$1@digitaldaemon.com...
> http://www.cs.princeton.edu/~dpw/popl/06/Tim-POPL.ppt


I'm new here but this somewhat old thread starting with this .ppt is very interesting to me since I work with the UE3 engine as a middleware.  Its pretty much dead on, as far as what the future is going to be, and that is in a massively parallel/threaded environment.  Those that do not make the transition are going to have very noticably 'rigid' game simulations that are far less capable.  Only the problem from my point of view is there isn't a single good language make the leap with.  Sure you can have a truely expert programmer get your threading right with the current tools available, but the reality is the current tools and languages available to make threaded programs are pretty bad.  In addition you end up with only 'one guy' who is responsible for far too much code since he has to wrangle everyone elses broken stuff into shape, and always on a rather riduclous timeline.

So how do games, threading, and D all tie into this?

Ok so I've been following D as a lurker off and on.  From the outside as a C++ programmer, D looks great to me.  I literally get more angry working with C++ every day.  And its all because doing anything 'cool' in C++, particularly templates, requires jumping through hoops.  Jumping through hoops is really the reality of having to deal with language deficiencies. So looking at D the initial impression is 'sweet' I want to write something in that.  Except from my world there are several huge problems:

Problem A : Garbage Collection is a dealbreaker.  But not because it exists or even that is is forced or a default.  We definitely want garbage collection.  It is a dealbreaker because of how it behaves.  There are several behaviors that make it such a strong negative as to be a dealbreaker, primarily the unknown frequency of collections, duration of collections, and the fact all our threads get suspended.  The more hardcore games run at a required 60 fps (gran turismo, god of war, etc).  This means all threads are executing a full cycle in 16.6 ms.  How much time do we want the GC to spend?  The answer is 0 ms.  Even spending 1ms for any kind of function in any game is pretty damn slow in a game engine.  If it starts pushing 5 or 10ms it starts impacting response of input, and noticebly hitches the rendering, since this hitch generally isn't every single frame. Consistency of the frame rate matters a lot.   In fact consistency matters so much that collecting could take 2ms of every 15 and we would be ok with it as long at was predictable so we can budget the game around it.  Even if it would only really need 10ms every 5 minutes, that is unacceptable, because a collector taking 10ms is a dealbreaker.

Problem B : Threading support.  The language of the future addresses threading head on, understanding that the number of cores on CPU processors is going to rapidly be in the tripple digits and beyond.  The chip makers have hit a wall, and the gains are going to come predominantly from core increases and memory I/O catching back up to the CPUs.  Eventually the line between CPU's and GPU's will blur quite a bit.  Which means we need to write threadable code safely, efficiently, without jumping through hoops, and not even really worrying about it a whole lot.  If our CPU based languages fail at this, we are going to be ending up writing game-physics raytracing code on the GPU instead via stuff like NVIDIA's GPGPU.  Which is essentially going to be stealing GPU performance to make up for the inability to take advantage of a massively parallel CPU core architecture.  Languages that are created, or are modified to make this leap cleanly will be the dominant players of the future.  I believe that if D makes this leap, it will be the one of them.  Judging by the progress of c++0x, I believe it has lost the agility necessary to make this transition and will be superceded by another language at this transition.


My gut feeling says that if the threading issues of are dealt with up front it would help a lot with garbage collection, since the requirements of moving the data efficiently in a massively threaded environment would drive evoloution in the GC system.  Even if the end-result is simply that you can construct isolated threads to get private GC heaps, and that data must be marshalled to them as if they were in another process space, it would be an improvement, because at least then the GC doesnt show down every single thread, and thin threads can collect very very fast.

I basically agree with the GC issues.

If it were up to me, I'd integrate a separate mode into the GC, in which it is only run in debug mode - and breaks on collection! Basically, I'd not use it as a collector per se, but as a tool to make manual memory cleaning easier.

Apart from that, I agree D is not quite ready for a massively parallel future - but the strength of the language is such that it can be made to be ready, without requiring any in-depth changes.
Take the following example.

foreach (foo; parallel(bar)) { /* do stuff with foo */ }

Looks neat? It can be made to work _today_, with D 1.0 or 2.0, GDC or DMD, without requiring _any changes to the compiler_, using exclusively language features (about one page of code) - and even without any significant runtime overhead! :D
And there's a decent amount of multithreading extensions for D already. Take a look at StackThreads  or DCSP on http://assertfalse.com/projects.shtml , all implemented using a minimum of machine specific code, and working fine (I think. I hope. :p )

From my (admittedly overoptimistic and fanboyish) perspective, even without threading built into the language, D is quite prepared for a massively-multithreaded future. :)

 --downs

Sean Cavanaugh wrote:
> Reposting, as I didn't have my name show up properly due to outlook express configuration fun, and any threaded readers are going to camoflauge my response to a nearly year old post :)
> 
> 
> "Marcio" <mqmnews123@sglebs.com> wrote in message
> news:ecipfc$15v4$1@digitaldaemon.com...
>> http://www.cs.princeton.edu/~dpw/popl/06/Tim-POPL.ppt
> 
> 
> I'm new here but this somewhat old thread starting with this .ppt is very
> interesting to me since I work with the UE3 engine as a middleware.  Its
> pretty much dead on, as far as what the future is going to be, and that is
> in a massively parallel/threaded environment.  Those that do not make the
> transition are going to have very noticably 'rigid' game simulations that
> are far less capable.  Only the problem from my point of view is there isn't
> a single good language make the leap with.  Sure you can have a truely
> expert programmer get your threading right with the current tools available,
> but the reality is the current tools and languages available to make
> threaded programs are pretty bad.  In addition you end up with only 'one
> guy' who is responsible for far too much code since he has to wrangle
> everyone elses broken stuff into shape, and always on a rather riduclous
> timeline.
> 
> So how do games, threading, and D all tie into this?
> 
> Ok so I've been following D as a lurker off and on.  From the outside as a
> C++ programmer, D looks great to me.  I literally get more angry working
> with C++ every day.  And its all because doing anything 'cool' in C++,
> particularly templates, requires jumping through hoops.  Jumping through
> hoops is really the reality of having to deal with language deficiencies.
> So looking at D the initial impression is 'sweet' I want to write something
> in that.  Except from my world there are several huge problems:
> 
> Problem A : Garbage Collection is a dealbreaker.  But not because it exists
> or even that is is forced or a default.  We definitely want garbage
> collection.  It is a dealbreaker because of how it behaves.  There are
> several behaviors that make it such a strong negative as to be a
> dealbreaker, primarily the unknown frequency of collections, duration of
> collections, and the fact all our threads get suspended.  The more hardcore
> games run at a required 60 fps (gran turismo, god of war, etc).  This means
> all threads are executing a full cycle in 16.6 ms.  How much time do we want
> the GC to spend?  The answer is 0 ms.  Even spending 1ms for any kind of
> function in any game is pretty damn slow in a game engine.  If it starts
> pushing 5 or 10ms it starts impacting response of input, and noticebly
> hitches the rendering, since this hitch generally isn't every single frame.
> Consistency of the frame rate matters a lot.   In fact consistency matters
> so much that collecting could take 2ms of every 15 and we would be ok with
> it as long at was predictable so we can budget the game around it.  Even if
> it would only really need 10ms every 5 minutes, that is unacceptable,
> because a collector taking 10ms is a dealbreaker.

I think this is one area where D will improve quite a bit over time. Personally, the GC I am most interested in is IBM's Metronome (a Java GC), and I'm hoping that a similar approach will be possible with D.

> Problem B : Threading support.  The language of the future addresses
> threading head on, understanding that the number of cores on CPU processors
> is going to rapidly be in the tripple digits and beyond.  The chip makers
> have hit a wall, and the gains are going to come predominantly from core
> increases and memory I/O catching back up to the CPUs.  Eventually the line
> between CPU's and GPU's will blur quite a bit.  Which means we need to write
> threadable code safely, efficiently, without jumping through hoops, and not
> even really worrying about it a whole lot.  If our CPU based languages fail
> at this, we are going to be ending up writing game-physics raytracing code
> on the GPU instead via stuff like NVIDIA's GPGPU.  Which is essentially
> going to be stealing GPU performance to make up for the inability to take
> advantage of a massively parallel CPU core architecture.  Languages that are
> created, or are modified to make this leap cleanly will be the dominant
> players of the future.  I believe that if D makes this leap, it will be the
> one of them.  Judging by the progress of c++0x, I believe it has lost the
> agility necessary to make this transition and will be superceded by another
> language at this transition.

D is in a better position than C++ in this respect, and things will only get better.  So far, the greatest obstacle has been available time to develop such tools.

> My gut feeling says that if the threading issues of are dealt with up front
> it would help a lot with garbage collection, since the requirements of
> moving the data efficiently in a massively threaded environment would drive
> evoloution in the GC system.  Even if the end-result is simply that you can
> construct isolated threads to get private GC heaps, and that data must be
> marshalled to them as if they were in another process space, it would be an
> improvement, because at least then the GC doesnt show down every single
> thread, and thin threads can collect very very fast.

The static data region is still an issue, since it is obviously shared between threads.  But it may be that either something could be done with multiple specialized allocators, or simply linking against a custom GC if you're willing to code to a certain model.  That said, do some Googling for Metronome, which I mentioned above.  It's a hard realtime GC and would be perfect for games, since they have fairly well-established runtime requirements, memory use, etc.


Sean

I can see where you are coming from and appreciate your enthusiasm. However, I can also see Sean Cavanaugh's point about threading capabilities being overly complex.  I can see that D is trying to address thread support using libraries.  There are many classes in Tango that work toward this purpose.  And they seem to be clean and capable, but IMO not a huge leap forward when compared to how threading is done in other modern languages.

The problem with threading is complexity.  For example, there are many classes in Tango that accommodate concurrency:  Thread, Atomic, Barrier, Condition, Mutex, ReadWriteMutex, Semaphore.  To someone like myself, who is not exactly a concurrency expert, this can be quite overwhelming.  How can we make it simpler for programmers?  Perhaps is can't be simplified any further and the best we can do is documentation, tutorials, etc.

But I think there are ways to make it easier.  I am a fan of the Concur project.  I think at least some of the abstractions that Sutter and friends have identified can be implemented in D with libraries.  Some may not be implementable with libraries, but may require support in the compiler. Whatever the case, I think D's compiler/standard libraries should be extended to deliver the features that Sutter is promoting.

-Craig

"downs" <default_357-line@yahoo.de> wrote in message news:f7aigu$1uif$1@digitalmars.com...
>I basically agree with the GC issues.
>
> If it were up to me, I'd integrate a separate mode into the GC, in which it is only run in debug mode - and breaks on collection! Basically, I'd not use it as a collector per se, but as a tool to make manual memory cleaning easier.
>
> Apart from that, I agree D is not quite ready for a massively parallel future - but the strength of the language is such that it can be made to be ready, without requiring any in-depth changes.
> Take the following example.
>
> foreach (foo; parallel(bar)) { /* do stuff with foo */ }
>
> Looks neat? It can be made to work _today_, with D 1.0 or 2.0, GDC or DMD, without requiring _any changes to the compiler_, using exclusively language features (about one page of code) - and even without any significant runtime overhead! :D
> And there's a decent amount of multithreading extensions for D already. Take a look at StackThreads or DCSP on http://assertfalse.com/projects.shtml , all implemented using a minimum of machine specific code, and working fine (I think. I hope. :p )
>
> From my (admittedly overoptimistic and fanboyish) perspective, even without threading built into the language, D is quite prepared for a massively-multithreaded future. :)
>
>  --downs 

Craig Black wrote:
> I can see where you are coming from and appreciate your enthusiasm. However, I can also see Sean Cavanaugh's point about threading capabilities being overly complex.  I can see that D is trying to address thread support using libraries.  There are many classes in Tango that work toward this purpose.  And they seem to be clean and capable, but IMO not a huge leap forward when compared to how threading is done in other modern languages.

Yup.  I feel that these classes are building blocks for something more comprehensive, rather than an end in themselves.

> The problem with threading is complexity.  For example, there are many classes in Tango that accommodate concurrency:  Thread, Atomic, Barrier, Condition, Mutex, ReadWriteMutex, Semaphore.  To someone like myself, who is not exactly a concurrency expert, this can be quite overwhelming.  How can we make it simpler for programmers?  Perhaps is can't be simplified any further and the best we can do is documentation, tutorials, etc.

It can be simplified further, but tutorials help anyway.  One idea would be to perform in-process messaging with the clustering package.  It's a bit heavyweight compared to, say, DCSP, but I like that it largely eliminates the differences between in-process and out-of-process concurrency.  Futures are another option, and they aren't terribly difficult to implement.

> But I think there are ways to make it easier.  I am a fan of the Concur project.  I think at least some of the abstractions that Sutter and friends have identified can be implemented in D with libraries.  Some may not be implementable with libraries, but may require support in the compiler. Whatever the case, I think D's compiler/standard libraries should be extended to deliver the features that Sutter is promoting.

You might want to look at Mikola Lysenko's DCSP:

http://www.assertfalse.com/projects.shtml

Concur is heavily based on Hoare's CSP model, so if you're familiar with Concur then DCSP may not be too much of a stretch.


Sean

Sean Cavanaugh wrote:
> Reposting, as I didn't have my name show up properly due to outlook express configuration fun, and any threaded readers are going to camoflauge my response to a nearly year old post :)
> 
> 
> "Marcio" <mqmnews123@sglebs.com> wrote in message
> news:ecipfc$15v4$1@digitaldaemon.com...
>> http://www.cs.princeton.edu/~dpw/popl/06/Tim-POPL.ppt
> 
> 
> I'm new here but this somewhat old thread starting with this .ppt is very
> interesting to me since I work with the UE3 engine as a middleware.  Its
> pretty much dead on, as far as what the future is going to be, and that is
> in a massively parallel/threaded environment.  Those that do not make the
> transition are going to have very noticably 'rigid' game simulations that
> are far less capable.  Only the problem from my point of view is there isn't
> a single good language make the leap with.  Sure you can have a truely
> expert programmer get your threading right with the current tools available,
> but the reality is the current tools and languages available to make
> threaded programs are pretty bad.  In addition you end up with only 'one
> guy' who is responsible for far too much code since he has to wrangle
> everyone elses broken stuff into shape, and always on a rather riduclous
> timeline.
> 
> So how do games, threading, and D all tie into this?
> 
> Ok so I've been following D as a lurker off and on.  From the outside as a
> C++ programmer, D looks great to me.  I literally get more angry working
> with C++ every day.  And its all because doing anything 'cool' in C++,
> particularly templates, requires jumping through hoops.  Jumping through
> hoops is really the reality of having to deal with language deficiencies.
> So looking at D the initial impression is 'sweet' I want to write something
> in that.  Except from my world there are several huge problems:
> 
> Problem A : Garbage Collection is a dealbreaker.  But not because it exists
> or even that is is forced or a default.  We definitely want garbage
> collection.  It is a dealbreaker because of how it behaves.  There are
> several behaviors that make it such a strong negative as to be a
> dealbreaker, primarily the unknown frequency of collections, duration of
> collections, and the fact all our threads get suspended.  The more hardcore
> games run at a required 60 fps (gran turismo, god of war, etc).  This means
> all threads are executing a full cycle in 16.6 ms.  How much time do we want
> the GC to spend?  The answer is 0 ms.  Even spending 1ms for any kind of
> function in any game is pretty damn slow in a game engine.  If it starts
> pushing 5 or 10ms it starts impacting response of input, and noticebly
> hitches the rendering, since this hitch generally isn't every single frame.
> Consistency of the frame rate matters a lot.   In fact consistency matters
> so much that collecting could take 2ms of every 15 and we would be ok with
> it as long at was predictable so we can budget the game around it.  Even if
> it would only really need 10ms every 5 minutes, that is unacceptable,
> because a collector taking 10ms is a dealbreaker.
> 

I doubt that many class-A games would use garbage collection if they had the possibility (ie, the language supported it), even if the GC was a very good one, Java VM like. The need for performance is too great for that. And yes, maybe an app using a very good GC can be faster that a normal manually-memory-managed app (Walter's words, not mine, according to his GC page), but I doubt using any GC could ever beat a well optimized manually-memory-managed app.

> Problem B : Threading support.  The language of the future addresses
> threading head on, understanding that the number of cores on CPU processors
> is going to rapidly be in the tripple digits and beyond.  The chip makers
> have hit a wall, and the gains are going to come predominantly from core
> increases and memory I/O catching back up to the CPUs.  Eventually the line
> between CPU's and GPU's will blur quite a bit.  Which means we need to write
> threadable code safely, efficiently, without jumping through hoops, and not
> even really worrying about it a whole lot.  If our CPU based languages fail
> at this, we are going to be ending up writing game-physics raytracing code
> on the GPU instead via stuff like NVIDIA's GPGPU.  Which is essentially
> going to be stealing GPU performance to make up for the inability to take
> advantage of a massively parallel CPU core architecture.  Languages that are
> created, or are modified to make this leap cleanly will be the dominant
> players of the future.  I believe that if D makes this leap, it will be the
> one of them.  Judging by the progress of c++0x, I believe it has lost the
> agility necessary to make this transition and will be superceded by another
> language at this transition.
> 
> 

This has been said countless times, and I think everyone (in D and the overall programming community) acknowledges that. What happens is that no one really yet knows how to make parallelism and concurrency easier to do. So there is really no point in asking for D to be better at this, if the way *how* to do it is not yet know.
I read in a recent article (I think it came from Slashdot, but not sure) that a new programming paradigm is needed to make concurrency easier, just in the same way as OO (and class encapsulation) improved on the previous data abstraction paradigm to make code cleaner and easier to write. Just in the same way as structured programming (ie, using functions/scopes/modules) improved on the previous paradigm of sequential/global/goto-using code, so to speak.


-- 
Bruno Medeiros - MSc in CS/E student
http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D

Bruno Medeiros wrote:
> I read in a recent article (I think it came from Slashdot, but not sure) that a new programming paradigm is needed to make concurrency easier, just in the same way as OO (and class encapsulation) improved on the previous data abstraction paradigm to make code cleaner and easier to write. Just in the same way as structured programming (ie, using functions/scopes/modules) improved on the previous paradigm of sequential/global/goto-using code, so to speak.

http://www.pragmaticprogrammer.com/articles/erlang.html

search for "Concurrency Oriented Programming"

BA

Bruno Medeiros wrote:
> Sean Cavanaugh wrote:
> 
> I doubt that many class-A games would use garbage collection if they had the possibility (ie, the language supported it), even if the GC was a very good one, Java VM like. The need for performance is too great for that. And yes, maybe an app using a very good GC can be faster that a normal manually-memory-managed app (Walter's words, not mine, according to his GC page), but I doubt using any GC could ever beat a well optimized manually-memory-managed app.

I think it depends on the app design.  Without garbage collection, sharing data between threads can be quite expensive.  For example, boost::shared_ptr uses an atomic operation to adjust its reference counter, which is typically more than 70 cycles if a LOCK operation is used on x86 (in truth, I think they've optimized it to use a spin-lock, which is more efficient but more complicated to get right).  But I do agree that explicit allocation and deletion only is more efficient than allocation and deletion combined with the occasional GC sweep (for obvious reasons).

> This has been said countless times, and I think everyone (in D and the overall programming community) acknowledges that. What happens is that no one really yet knows how to make parallelism and concurrency easier to do. So there is really no point in asking for D to be better at this, if the way *how* to do it is not yet know.

Well, there are a lot of ways to make it easier than explicit manipulation of mutexes and such--some of the involved research dates back to the early 60s--but even with these alternate methods, concurrency isn't easy.

> I read in a recent article (I think it came from Slashdot, but not sure) that a new programming paradigm is needed to make concurrency easier, just in the same way as OO (and class encapsulation) improved on the previous data abstraction paradigm to make code cleaner and easier to write. Just in the same way as structured programming (ie, using functions/scopes/modules) improved on the previous paradigm of sequential/global/goto-using code, so to speak.

This is what I think needs to happen.  Concur and such are an improvement, but they still require the programmer to do a lot explicitly.  Ultimately, we need a fundamental change in the way we do multithreaded programming if we want our applications to scale on future architectures.


Sean

Brad Anderson wrote:
> Bruno Medeiros wrote:
>> I read in a recent article (I think it came from Slashdot, but not sure)
>> that a new programming paradigm is needed to make concurrency easier,
>> just in the same way as OO (and class encapsulation) improved on the
>> previous data abstraction paradigm to make code cleaner and easier to
>> write. Just in the same way as structured programming (ie, using
>> functions/scopes/modules) improved on the previous paradigm of
>> sequential/global/goto-using code, so to speak.
> 
> http://www.pragmaticprogrammer.com/articles/erlang.html
> 
> search for "Concurrency Oriented Programming"

Thanks for the link Brad, this is a great article.  I've never really looked into erlang, but it sounds like it's the type of language I've been thinking we'll end up with (based on message-passing, but a bit evolved from that).  I'm still not convinced that a functional language is required for this, but it is certainly a more natural fit.  Seems like the greatest obstacle for erlang would be getting schools to teach functional programming again--it's a bit of a chicken & egg problem.


Sean

Bruno Medeiros Wrote:

> I doubt that many class-A games would use garbage collection if they had the possibility (ie, the language supported it), even if the GC was a very good one, Java VM like. The need for performance is too great for that.

I hate to call you out, but.. I happen to be working for a class-A games' company who are writing their latest title in C#.