Thread: Re: [Algorithms] Complexity of new hardware
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: <ne...@tw...> - 2009-04-26 12:17:16
|
<html><body><span style="font-family:Verdana; color:#000000; font-size:10pt;"><br><blockquote webmail="1" style="border-left: 2px solid blue; margin-left: 8px; padding-left: 8px; font-size: 10pt; color: black; font-family: verdana;"><div ><br>
-------- Original Message --------<br>
Subject: Re: [Algorithms] Complexity of new hardware<br>
From: Sebastian Sylvan <seb...@gm...><br>
<br>
Being a massive Haskell fanboy myself, let me jump in with some<br>
other cool things it does that relates to game development.<br>
<br>
...<br>
<br>
2. It has Software Transactional Memory. So when you really need<br>
shared mutable state you can still access it from lots of different<br>
threads at once with optimistic concurrency (only block when there's<br>
an actual conflict). Yes, there are issues, and yes it adds<br>
overhead, but if the alternative is single threaded execution and<br>
the overhead is 2-3x, then we win once we have 4 hardware threads to<br>
spare.<br>
<br></div></blockquote><div ><br>I would like to sound a note of caution on STM. It's quite nice to <br>
program with -- think of it as threads-and-locks, made good. But I've <br>
been to many presentations on STM, from prominent researchers in the <br>
field, and the performance figures have always indicated that it doesn't <br>
scale. Past about two-four threads contending on a piece of <br>
transactional memory, the performance usually ends up worse than one <br>
thread, which is hardly what you want from parallel programming. I <br>
think a message-passing model is more promising, and is equally valid in <br>
Haskell or in C++ (disclaimer: I spend my days doing research into <br>
message-passing concurrency :-), whereas STM in C++ is not as <br>easy and simple as the Haskell version.<br><br></div><blockquote webmail="1" style="border-left: 2px solid blue; margin-left: 8px; padding-left: 8px; font-size: 10pt; color: black; font-family: verdana;"><div >
<br>
<br>
3. Monads! Basically this allows you to overload semi-colon, which<br>
means you can fairly easily define your own embedded DSLs. This can<br>
let you write certain code a lot easier.. You could have a<br>
"behaviour" monad for example, abstracting over all the details of<br>
entities in the game doing things which take multiple frames (so you<br>
don't need to litter your behaviour code with state machine code,<br>
saving and restoring state etc, you just write what you want to do<br>
and the implementation of the monad takes care of things that needs<br>
to "yield").<br>
<br>
4. It's safe. Most code in games isn't systems code, so IMO it<br>
doesn't make sense to pay the cost of using a systems programming<br>
language for it (productivity, safety).<br>
<br>
5. It's statically typed with a native compiler, meaning you could<br>
compile all your scripts and just link them into the game for<br>
release and get decent performance. Not C-like (yet, anyway!), but<br>
probably an order of magnitude over most dynamic languages.<br>
<br></div></blockquote><div ><br>Agreed on the monads and safety. Having programmed a large system in <br>
Haskell, I have found that the performance is surprisingly good, <br>
especially in terms of memory use. The laziness aspect seems to allow <br>
memory use to remain low, sometimes even lower than the equivalent C <br>
program. But I doubt that the straight-line performance is going to be <br>
as good as C, especially given the amount of garbage collection involved <br>
in Haskell programs.<br>
<br>
There was a talk a couple of years ago by Tim Sweeney that made a case <br>
for functional programming in games (the slides can be found here: <br>
<a href="http://morpheus.cs.ucdavis.edu/papers/sweeny.pdf" target="_blank" mce_href="http://morpheus.cs.ucdavis.edu/papers/sweeny.pdf">http://morpheus.cs.ucdavis.edu/papers/sweeny.pdf</a>), for anyone that's <br>
interested. I also think that Haskell could benefit game development, <br>
but it does take a little while to get your head round functional <br>
programming, monads, and all the other stuff that Haskell has to offer.<br>
<br>
Thanks,<br>
<br>
Neil.<br>
<br>
P.S. to be pedantic on the issue of the function of type a->a (from <br>
another post), const undefined is also a valid function of that <br>
type, if an unhelpful one :-)<br>
</div><blockquote webmail="1" style="border-left: 2px solid blue; margin-left: 8px; padding-left: 8px; font-size: 10pt; color: black; font-family: verdana;">
</blockquote></span></body></html>
|
|
From: <ne...@tw...> - 2009-04-26 16:52:14
|
<html><body><span style="font-family:Verdana; color:#000000; font-size:10pt;"><br><br> <blockquote webmail="1" style="border-left: 2px solid blue; margin-left: 8px; padding-left: 8px; font-size: 10pt; color: black; font-family: verdana;"> <div > -------- Original Message --------<br> Subject: Re: [Algorithms] Complexity of new hardware<br> From: Conor Stokes <bor...@ya...><br></div></blockquote><br><blockquote webmail="1" style="border-left: 2px solid blue; margin-left: 8px; padding-left: 8px; font-size: 10pt; color: black; font-family: verdana;"><div > Functional programming is a very good tool, but it's too pure a tool for production software. Most production software has areas that are "do this, then do that", which pure functional language still has awkward and heavy abstractions for (i.e. an extra level of thought that isn't necessary for the functionality required). It is also interesting that when Tim Sweeney said in his programming-language-for-the-future talk that the "graphics engine" would be "fuctional", yet he doesn't mention that rendering (as it currently stands) occurs in order and is highly stateful. Graphics hardware requires that you set your states, followed by your rendering commands, in order, which is a highly imperative way to think. This really shows that large problems tend to be made up of mixed solutions, that don't follow any one set of rules.<br><br></div></blockquote><br>Monads do give you a way to do imperative code in functional languages. As a half-way relevant example, I find it easier to program OpenGL using the Haskell bindings that I do using the C/C++ bindings. To turn off blending, then draw a long list of triangles, then a list of quads:<br><br>do blendFunc $= Nothing<br> renderPrimitive Triangles (mapM vertex vs)<br> renderPrimitive Quads (mapM vertex vs2)<br><br>versus something like:<br><br>glDisable(GL_BLEND);<br>glBegin(GL_TRIANGLES);<br>for (int i = 0; i < vs.length();i++) drawVertex(vs[i]);<br>glEnd();<br>glBegin(GL_QUADS);<br> for (int i = 0; i < vs2.length();i++) drawVertex(vs2[i]);<br> glEnd();<br><br>I realise that's some very simplistic code (no display lists and so on), but I think (especially with Haskell under discussion), saying that it cannot do ordered things is misrepresentative, once you understand monads. (I do accept that having to understand monads is a barrier to learning Haskell against, say, C.) In Haskell you can get all the nice little features of functional programming (map and so forth), alongside all the order of imperative programming.<br><br>I think you are right that Haskell has not been used in enough large-scale projects to see if it scales well enough in terms of software development, but it has at least the capability to do all aspects of games. Someone did port the Quake 3 engine to Haskell without any leftover C, for example (<a href="http://haskell.org/haskellwiki/Frag">http://haskell.org/haskellwiki/Frag)</a>.<br><br>Neil.<br><blockquote webmail="1" style="border-left: 2px solid blue; margin-left: 8px; padding-left: 8px; font-size: 10pt; color: black; font-family: verdana;"> </blockquote></span></body></html> |
|
From: Sebastian S. <seb...@gm...> - 2009-04-26 17:12:44
|
On Sun, Apr 26, 2009 at 5:52 PM, <ne...@tw...> wrote: > > > I think you are right that Haskell has not been used in enough large-scale > projects to see if it scales well enough in terms of software development, > but it has at least the capability to do all aspects of games. Someone did > port the Quake 3 engine to Haskell without any leftover C, for example ( > http://haskell.org/haskellwiki/Frag) <http://haskell.org/haskellwiki/Frag> > . > A minor niggle: It's not a port of Quake 3, it's a completely new engine that loads the Quake 3 level format. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 |
|
From: Sebastian S. <seb...@gm...> - 2009-04-26 12:52:12
|
On Sun, Apr 26, 2009 at 12:50 PM, <ne...@tw...> wrote: > > I would like to sound a note of caution on STM. It's quite nice to > program with -- think of it as threads-and-locks, made good. But I've > been to many presentations on STM, from prominent researchers in the > field, and the performance figures have always indicated that it doesn't > scale. Past about two-four threads contending on a piece of > transactional memory, the performance usually ends up worse than one > thread, which is hardly what you want from parallel programming. > Well that's kind of unavoidable though. If there is true contention on a piece of shared data, then no amount of software solutions will help you. So the name of the game is to reduce unnecessary contention (e.g. pessimistically excluding something from accessing data). For that reason avoiding shared data as much as possible is clearly a good idea - but once you're in the situation that you really do need it, what do you do? STM competes with locks and condition variables, not threads and messages. E.g. if you have a game world with 10K objects in it, and each object touches 5 other objects on average, when it's updated, then *actual* contention will probably be low, whereas *potential* contention is high, and that's where STM shines since it enables optimistic concurrency. I.e. the common case of no actual contention runs quickly, at the cost of some overhead when you're unlucky and two objects touch the same data. Whereas with locks you have to lock everything every single time even though it's unlikely that anything else is using it. For these cases STM does scale well beyond locks. I > think a message-passing model is more promising, and is equally valid in > Haskell or in C++ (disclaimer: I spend my days doing research into > message-passing concurrency :-), whereas STM in C++ is not as > easy and simple as the Haskell version. > Sure, message passing is another strategy, but I don't think they're in competition. STM is for shared state concurrency, which is to be avoided, but sometimes can't be, message passing offers very little benefit w.r.t. scalability over locks and condition variables when it comes to truly shared state (you pretty much end up simulating locks with them, by having some "server thread" manage access to data, and for transactions you need to gather up exclusive access somehow, which is essentially the same as "taking a lock"). Message passing can be very nice for some things, but I think there are plenty of cases where it doesn't work very well (e.g. the example mentioned earlier). Also, I find message passing can get very complicated in some instances, as it feels a bit like "goto programming", where you have to try to reason about how these messages flow through several threads - it can get hairy and "spaghetti-like" where the logic of the program is obscured by the details of coordination. So while there are problems where multiple sequential processes communicating through messages fit very nicely, I'd be very careful about considering them to be the *only* paradigm - we need to be able to support all the other problems too. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 |
Thanks for helping keep SourceForge clean.
X