Features Download

From: Kelly Brock <toolzer <at> gmail.com>
Subject: Multi-core solutions. (Was: Ditching C++)
Newsgroups: gmane.games.devel.sweng
Date: Tuesday 11th July 2006 06:42:30 UTC (over 12 years ago)
> Because Functional (i.e. Lisp) programming is
> conceptually miles away from Imperative Programming
> (i.e. c/c++). I actually find it's easier to train a
> good matematician into a good Lisp programmer than to
> try to retrain a C++ expert; most C++ programmers end
> up 'fighting' the system rather than working with it.

	I actually have messed with Lisp and other functional languages and
not found the transition "too" horrible.  I didn't stick with it as the
project it was used for was actually a conversion to C# of the
functionality, but once I started understanding things, breaking it into
smaller portable sections was not too difficult.  I was never an expert,
just able to understand enough to do the job.

> I'm also curious; I keep hearing Functional languages
> (Lisp, Haskel, etc) used as the 'salvation' for the
> whole multi-core problem. Is that something people are
> actually utilizing right now? Does the implicit
> ability to multi-thread overcome the context-switching
> and communication overheads?
> Or is this part of a theoretical "well, you know, the
> PS5 will have 1,000 cores, and that's when Haskel will
> really shine" argument?

	I can't say that I agree with those folks suggesting that you need
alternatives to C/C++ in this area.  It would be *nice* to have a language
with better support and less error prone behavior in multi-core, but I am
far from believing there is any fundamental reason we need a new language.
Threading is a complex beast; until you really work on heavily threaded
and start understanding the issues, you are not going to solve anything by
moving to another language.  As others have said, if you change languages
you are basically trading one set of problems in favor of another set of
problems.  I find that to be a loose/loose situation and unacceptable until
a "proven" better solution comes along which justifies the time I have to
take to learn the new language and its foibles.  (I mean "proven", not
wished for, not intended, but shipped and validated.)

	I'm extremely confident that C/C++ can deal with the issues cleanly
as I have two example systems to look at.  One is at work which runs our
game code like a bat out of hell on as many processors as you give it.  The
other is one I've been working on since back at Maxis when I picked up my
first dual processor P3 machine and wanted to experiment with distributed
simulation systems.  (Wish I'd known then that multi-core was going to be
big.. :))  Both have several similarities, though they end up getting there
from very different directions.

	Given that I mention solutions, let me be silly and paraphrase our
friendly neighborhood SpiderMan: "With greater power comes greater
responsibility.".  And it holds true for programmers, there are no golden
bullet solutions to multi-core.  You can make it as easy as possible by
hiding as many details as you can, but there are certain things you will
always have to watch out for as a "new" set of perils in your day to day
work.  Unlike everything I've seen here and on other lists, the fact that
you "can" hide most details from your programmers is possible.  After doing
a proper abstraction there are a couple things you have to watch out for,
I'll give you an example:

	Given an algorithm that distributes across n-cores and outputs data
to a list, there are the following issues:

1.	Ordering of the output data is not guaranteed.
2.	There can be no interdependent variables/flags unless they are also
3.	Every write to the list must be locked or otherwise synchronized.

	The above is a perfect example of a general algorithm ported from
single threaded code without thought to the impact it has on n-cores.  If
you do minimal work to change the algorithm from single threaded to n-core
aware, you can pretty much get rid of 1 and 2 (usually at the cost of a
little more memory), but #3 is still a killer.  Simply put the locking of
the output list is absolutely unacceptable in n-core programming.  Any OS
level lock can quickly bring your system to it's knee's, you MUST minimize
locks of all sorts.  Even a lockless list is not immune to the performance
degradation of data contention issues in this case if the loop is tight

	So, one possible solution, which I use a lot, is to avoid the
contention completely.  When I begin running an algorithm with this
in parallel I setup a thread local store with a list for each thread.  The
algorithm then runs with complete single threaded ownership of the list and
writes as fast as it wants.  When the last instance of the algorithm
finishes, a new task grabs up all those separate lists and merges them. 
result is more buss bandwidth via the mem-copies (assuming pod data, worse
if non-pod) but "NO" stall's per CPU caused by data contention when
running the algorithm.  In test cases, I can quickly prove the utility of
the solution, my simulator runs at 3.8X single threaded execution on a quad
Opteron, with a "single" contention issue it drops like a rock to 3.2X.  In
the case of using lockless in the same tight loop, the 3.8 drops to 3.7,
still notable and unacceptable for n-core.

	I don't see a "language" fixing the above, in fact, most of the
suggestions why other languages may be better, appear to me like the
proverbial "Ostrich with it's head in the sand", hiding from the real
issues.  I'm sure those posting such suggestions don't see it that way, and
I mean no offense to them in any manner, I'm just suggesting that you may
want to reconsider because C/C++ is here to stay at this time and solutions
"do" exist if you work at them.  The first problem for most programmers in
the games industry is *really* understanding multi-threaded programming.
Threading out one or two things and synchronizing contact with the primary
game loop does not count as "threading" in the multi-core world.

	OK, looonggg, e-mail, but it covers a lot of ground in terms of why
I believe the "Ditching C++" thread is only somewhat viable.  I'll ditch
C/C++ in a heartbeat given a better "proven" system though.


sweng-gamedev mailing list
[email protected]
CD: 15ms