Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[SSBR]

Like for example Bitonic sort or scan (ok these ARE pretty lame examples but i guess you get the drift).

And yet without seeing the code or knowing in detail the data structures (and their uses elsewhere), we wouldn't know that we could suggest, say, radix sort. We can't do all that much without seeing the code, just state the obvious. The obvious is sadly not all that helpful.

The boost would be unnoticeable at the start but as he adds more and more code it would add up. When he notices how much of a boost he is getting (His current computer is a quad core apparently!) he will learn more about multiple core programming until finally he knows and is excited enough to use it properly.

The benefit to performance is tiny for each new thread here, we agree. That he wouldn't learn very much or very well from bolting threading onto DF in hacky ways is something I would believe. What is almost certainly true is that the process would result in a buggy DF with a nastier and less maintainable codebase, leading to a buggier DF that sucks more time out of more valuable features than an iota of speed and a little bit of knowledge.

If you're going to do threading, do it right. It's not really as easy to get right as some people have suggested, not when you get to finer-grained parallel algorithms.

[GoldenH]

That he wouldn't learn very much or very well from bolting threading onto DF in hacky ways is something I would believe.

I disagree, he'll learn a lot. It might take DF longer to 'finish', but DF will probably never be finished, so lets make the game more fun to play now.

What is almost certainly true is that the process would result in a buggy DF with a nastier and less maintainable codebase, leading to a buggier DF that sucks more time out of more valuable features than an iota of speed and a little bit of knowledge.

That's probably true but frankly the game is already full of buggy code. I have found ways to Crash DF completely whenever I want, and all the unoptimized algorithms are going to have to be rewritten anyway. What's the harm if it's an unoptimized single thread or an unoptimized multi thread? None that I can see. And it will definitely speed up the game, at the _least_ to the point where temperature, water, magma, animals, etc no longer slow down the game which would go a long way to make it more playable for me, and implement new features like say adding pathfinding to workshop jobs and animal interaction completely for free.

If you're going to do threading, do it right. It's not really as easy to get right as some people have suggested, not when you get to finer-grained parallel algorithms.

I definitely agree that multithreading isn't the cure to everything, it doesn't have as big a speedup as some people in this thread, nor is it as easy as some people have said (but it is even easier than alternatives other people have said, so i think it evens out). Stuff like the d# code that require a graphics processor isn't going to help, for instance on integrated chipsets it definitely works much worse than if the graphics code had just been put on another core (I say that because the d# code isn't faster on computers i've tested that have intel integrated chipsets). but it will absolutely help. But especially as we go into the future, cores are going to be a lot cheaper than speed and we're going to see more and more cores. Technologies like Larrabee show that.  Toady's just going to have to decide, does he want this game to be playable for a lot of people who have a bargin or midrange system, or only those who have cutting edge computers, it is simply a matter of money.

[SSBR]

I disagree, he'll learn a lot.

Sure, he'll learn a lot.

Here's the situation in that regard as I see it: he could learn threading by trying it out elsewhere and doing the reading, or doing it with DF first and reading. The first system he builds will probably not be good. I can't speak in certainties, for all I know he'll luck out, or for all I know he's a genius coder like the world has never seen, or for all I know he's done this before and this situation is all a lie. But in all probability, it will be slow and painful to develop the first threaded systems. Also, some programs are better for using threading than others. DF may be a relatively fine-grained algorithm to turn parallel. This makes it even more difficult, even harder. And it moves away a lot of the learning from learning how to do threaded code properly, to learning how to hack on individual pieces as parallel code. This is not a valuable learning experience, and yet a lot of the "learning" time will be wasted on it. A lot will also be spent learning the APIs, the nature of race conditions, etc.-- that's fine, but there are other ways to learn it. Other ways that don't involve corrupting an existing codebase, and wasting time learning things that won't matter when you rewrite the whole bloody thing.

What's the harm if it's an unoptimized single thread or an unoptimized multi thread? None that I can see.

Have you ever had to deal with badly written threaded code? It's damn near impossible to debug.

But especially as we go into the future, cores are going to be a lot cheaper than speed and we're going to see more and more cores. Technologies like Larrabee show that.  Toady's just going to have to decide, does he want this game to be playable for a lot of people who have a bargin or midrange system, or only those who have cutting edge computers, it is simply a matter of money.

I've been holding my tongue here to this point, but frankly I don't think threads are the long-term answer. If he wants his code to be scalable he needs to eliminate shared state and do it entirely using intercommunication.. Memory access has been a well-known bottleneck, and eventually manufacturers are going to want to give blocks of memory per-core instead of having them all access the same memory. Threaded code won't scale to this as it's normally done, multiprocess code with pipes or IPC over sockets will for certain. And the thing is, multiprocess code with pipes or IPC over sockets is easier to get right  (funny story: you might want to use threads for some of the async stuff), but there's a catch-- increased overhead for process creation and communication. On the other hand, this cost is nowhere near what people seem to think it is, and moving away from it for speed is a premature optimization with its own costs attached.

And it will definitely speed up the game, at the _least_ to the point where temperature, water, magma, animals, etc no longer slow down the game

That's not definite, not really. And I'm not sure it's worth it, and it's certainly not necessary to play (for example, somebody has made a UI wrapper that could be played over SVN, by using curses with the terminal)

[GoldenH]

I disagree, he'll learn a lot.

Sure, he'll learn a lot.

Here's the situation in that regard as I see it: he could learn threading by trying it out elsewhere and doing the reading, or doing it with DF first and reading. The first system he builds will probably not be good. I can't speak in certainties, for all I know he'll luck out, or for all I know he's a genius coder like the world has never seen, or for all I know he's done this before and this situation is all a lie. But in all probability, it will be slow and painful to develop the first threaded systems. Also, some programs are better for using threading than others. DF may be a relatively fine-grained algorithm to turn parallel. This makes it even more difficult, even harder. And it moves away a lot of the learning from learning how to do threaded code properly, to learning how to hack on individual pieces as parallel code. This is not a valuable learning experience, and yet a lot of the "learning" time will be wasted on it. A lot will also be spent learning the APIs, the nature of race conditions, etc.-- that's fine, but there are other ways to learn it. Other ways that don't involve corrupting an existing codebase, and wasting time learning things that won't matter when you rewrite the whole bloody thing.

This is why I suggest that he code in new parts of the game as threaded instead of old parts. If its too hard to be parallel than of course don't do it, and modifications to old parts of the game shouldn't require complete overwrites just so it is parallel. This way he'll also learn how to make the game into relatively few threads instead of running into the problems with having hundred thousands of threads. But even 2 threads would be better than one.

What's the harm if it's an unoptimized single thread or an unoptimized multi thread? None that I can see.

Have you ever had to deal with badly written threaded code? It's damn near impossible to debug.

True but that is changing. Lots of debug improvements in the last year. However this is why I suggest not heavily threading the app, just having a few threads that certain parts of the game run in.

But especially as we go into the future, cores are going to be a lot cheaper than speed and we're going to see more and more cores. Technologies like Larrabee show that.  Toady's just going to have to decide, does he want this game to be playable for a lot of people who have a bargin or midrange system, or only those who have cutting edge computers, it is simply a matter of money.

I've been holding my tongue here to this point, but frankly I don't think threads are the long-term answer. If he wants his code to be scalable he needs to eliminate shared state and do it entirely using intercommunication.. Memory access has been a well-known bottleneck, and eventually manufacturers are going to want to give blocks of memory per-core instead of having them all access the same memory. Threaded code won't scale to this as it's normally done, multiprocess code with pipes or IPC over sockets will for certain. And the thing is, multiprocess code with pipes or IPC over sockets is easier to get right  (funny story: you might want to use threads for some of the async stuff), but there's a catch-- increased overhead for process creation and communication. On the other hand, this cost is nowhere near what people seem to think it is, and moving away from it for speed is a premature optimization with its own costs attached.

Here's the thing with doing it with sockets, there is a bandwidth limitation and performance hit to doing it that way. Yes, it's nice with a client/server model but it can lag, and even a little bit of lag will seriously degrade the dwarf fortress. I'm willing to bet that the memory access issues you're supposing he'd have with threaded apps would be magnified ten fold in such a system.

Personally I've been experimenting with various client/server programming techniques in order to make a MMOG server engine that is easily scalable to a network. The experiences I'm having prove that for me anyway, threading is much easier to learn and implement than sockets.

Meanwhile the number of cores in single computers and even in server computers are going to continue to rise. Look for servers to have 50ish cores in the next decade and household computers to have equal numbers of much slower chips as companies seek a broader market for their technology.

And it will definitely speed up the game, at the _least_ to the point where temperature, water, magma, animals, etc no longer slow down the game

That's not definite, not really. And I'm not sure it's worth it, and it's certainly not necessary to play (for example, somebody has made a UI wrapper that could be played over SVN, by using curses with the terminal)

It is absolutely definite. Even if he doesn't make the threads asynchronous (which he could easily do with weather and almost as easily with temperature), one of the threads is going to be the limiting factor, which means your fortress can do other things that by themselves would slow your game down noticeably without losing a single FPS. And if one thread is a hog, and threads take turns being the hog, if you have more threads than cores than the hog thread gets its own core and another core takes care of everything else. That means that you'd see an improvement even on just two threads.

And you have to realize that even though two cores isn't twice as fast, more than two cores IS more than twice as fast. And when the fastest core on the market is only twice as fast as the slowest, the only way to get more performance is to utilize as many cores as possible.

[SSBR]

Here's the thing with doing it with sockets, there is a bandwidth limitation and performance hit to doing it that way. Yes, it's nice with a client/server model but it can lag, and even a little bit of lag will seriously degrade the dwarf fortress. I'm willing to bet that the memory access issues you're supposing he'd have with threaded apps would be magnified ten fold in such a system.

The issues I mentioned have nothing to do with latency, and IPC latency is only an issue if your app really does rely on shared state and you need to get around it with IPC. If you need that, there are sometimes better ways of sharing state efficiently anyway, but it's not nice.

It's also nothing about a client/server model. Nor is there any significant bandwidth limitation, it's just a method of communication that involves some overhead, which goes away with time as improvements get piled on. There's nothing limiting about it in any innate sense, except the speed of light or some such thing.

Meanwhile the number of cores in single computers and even in server computers are going to continue to rise. Look for servers to have 50ish cores in the next decade and household computers to have equal numbers of much slower chips as companies seek a broader market for their technology.

Please don't repeat what we all know, it sounds patronizing, and makes me unsure as to what exactly your intent is here. I have already mentioned why threading is not necessarily a valid option for future scalability, but you repeat this without addressing my point. Why?

Personally I've been experimenting with various client/server programming techniques in order to make a MMOG server engine that is easily scalable to a network. The experiences I'm having prove that for me anyway, threading is much easier to learn and implement than sockets.

Sure, sockets are a pain. There are libraries and frameworks to abstract this away, you know. There are for threads, too, but there are problems in that it's not easy to cleanly remove shared state. And where you can't you have to mess with locks, and before you know it you might have even made your app slower. It happens.

It is absolutely definite. Even if he doesn't make the threads asynchronous (which he could easily do with weather and almost as easily with temperature), one of the threads is going to be the limiting factor, which means your fortress can do other things that by themselves would slow your game down noticeably without losing a single FPS. And if one thread is a hog, and threads take turns being the hog, if you have more threads than cores than the hog thread gets its own core and another core takes care of everything else. That means that you'd see an improvement even on just two threads.

You've said a lot of things I concur with, and yet you have not proven that threads definitely speed your app up. The fact is, they don't. Fine-grained locking can result in slow-downs. Are you aware of the architectural issues surrounding threads? It's not so cut-and dry. Nobody here as fully explored the depths of the tradeoffs that must be made (myself included-- I am no expert). Threading is not a magic bullet, not even to speed. Done badly it could drastically slow DF down; done well, it will still slow DF down on certain systems (in particular, 1-core systems).

And you have to realize that even though two cores isn't twice as fast, more than two cores IS more than twice as fast. And when the fastest core on the market is only twice as fast as the slowest, the only way to get more performance is to utilize as many cores as possible.

This is flat out untrue. It is not at all necessarily true that you pass some specific constant speed multiplier, because asymptotically the rate of change of speed when you add more threads goes to zero. When you start reaching this efficiency bound depends on your app, but it could indeed be after just 2 threads. This is basic parallel computing knowledge-- there is an upper bound so long as some tasks must be chained linearly, and in DF this is obviously true. Then this upper bound can be found by Amdahl's Law.

[eerr]

And you have to realize that even though two cores isn't twice as fast, more than two cores IS more than twice as fast. And when the fastest core on the market is only twice as fast as the slowest, the only way to get more performance is to utilize as many cores as possible.

Each core is only as useful as the fraction of the program it can run.
I can't think of any program which is infinitely divisble as you would have it.
"Marginal core effect" trends towards 0, as programs must rely on code that works in sequence.

you know, like you subtract x= x-4000000
then  x=x/30
You repeat this over and over again.

you can't multithread that!, some things have to happen in order!

[Googolplexed]

And you have to realize that even though two cores isn't twice as fast, more than two cores IS more than twice as fast. And when the fastest core on the market is only twice as fast as the slowest, the only way to get more performance is to utilize as many cores as possible.

Yes but then we get into Amdahl's law http://en.wikipedia.org/wiki/Amdahl's_law.

I think we would be lucky if more then 50% of DF was multi-threaded.
Using the Amdahl's law it states that the maximum speed-up is 2x, using 16 cores, before this the law of diminishing returns kicks in but still.

Even at 75% it would take 8 cores to 3x, maxing out at 4x with 128 cores.

I'm no expert on Parallel computing but if I haven't made a mistake here, then this shows a major limitation to DF being multi-threaded.

I'm not saying there's no speed-up, At least early on, but don't expect DF to benefit much from more cores in future, other optimizations are more important.

[sproingie]

Yay, someone brought up Amdahl's law, and indeed it's another thing that would kick us in the ass.  DF has tons of data dependencies.  Every step a dorf takes changes the pathing of every dorf around him.  Everything built takes from globally available materials.  Everything updates the shared state of the world on which everything else depends.  No matter how many threads you have, joining those dependencies back together tends to be a linear operation, and that's where Amdahl's law kicks in.  It doesn't help that the available synchronization primitives for C++ and pretty much all languages that aren't functional (like Haskell or Erlang) are themselves quite heavyweight, adding even more overhead to these joins.

Now it's true there's quite a few calculations that are "embarassingly parallel" and don't suffer as much from this: fluid simulations have been mentioned, and seem like a good candidate for running in the background, possibly even vectorizing.  At that point I suspect just plain MMX would be fast enough, no need for GPGPU (it's pointless to ship it off to the GPU if you just wait around for your other data dependencies for another million cycles).

It appears the next iteration of "just slap in multithreading" is "just slap on threads just for new things", as if that really changed anything other than to add *new* bugs when interacting with code that isn't threadsafe (i.e. all of DF).  I still feel justified in my initial hostility to the topic, though I admit I'm pleasantly surprised this time around at the depth in the responses that explain why it isn't such a simple or immediately feasible thing.  This isn't to say you'd get no benefit from concurrency.  In fact, DF could gain a whole lot from concurrency -- all it would take would be a total rewrite.  My experience with rewrites is, well, it's safe to say DF would go the way of Slaves To Armok Part 1.

[profit]

I'm no expert on Parallel computing

What your missing from the law is, what if the calculations that take 95% of the time in the code is the one you make massively parallel.

Then you get at least a 6x speedup with only 8 processors..

Lets see 6x.. that would turn 10FPS to 60... seems not insignificant to me..

Now what if ONLY one or two things were taking huge amounts of processor time.  Maybe its path-finding and Fluid Simulation.  Those COULD be redone (In theory depending on how his code is) without a total rewrite... if the rest of his code spent almost zero time in comparison (Which seems likely), then he would only need maybe 15% of his code parallelised before he would reach the 90% + range on the little graph you showed.

I am currently agnostic to what method is used to speed up the game... code cleanup, new algorithms, multi-threaded... I don't care.  Make it faster. I just see its obvious it's not threaded at all and could be, does not mean it is the best way to achieve speed, just it might be.

  I still feel justified in my initial hostility to the topic

Your initial hostility to multi-threading pales in comparison to my blatent, seething adamantine strength anger at sub 10 FPS forts where one core does all the work and the rest sit idle.  You have no idea the depths of rage available for me to tap in the fight against forts that crawl along at 3FPS and if you did you would certainly try to get me committed.  We accept this for the moment because it is an alpha game, it has the most potential ever, and it's free...  But I can assure you, if it looks like there will not be a faster smoother game coming down the pipes rather than dwarves that smell bad or wear purple spinals in their beards.... THIS SHIT WILL NOT FLY!

and dwarf fortress WILL die.

[sproingie]

Urist McProfit has flown into a rage!

Meantime, if and when the new version fails to bring down civilization or even my computer, I'll feel justified in throwing another donation Toady's way.  And I do kinda suspect it's *always* going to be "alpha".

[Googolplexed]

@Profit

My point was, at the end of the day, multi-threading cannot be slapped onto the original code. Yes the water simulations and pathfinding could be multi-threaded quite well and yes the major slowdowns should be water sims and pathfinding, but if that was all then why did the D# series make any progress. The rest of the code is inefficient in places, and until it is fixed I don't believe that just "Multi-threading it" is the answer.

My points were less directed towards you and more at people who just assumed that multi-threading would be finished in a month and would have 4x gains on a quad.

I'm not saying that multi-threading won't be a good thing to do, and if done well then the speed benefits may be great, I'm just trying to point out to everyone that multi-threading isn't a quick fix. A better idea would be to try to optimize the rest of the code first, and to carefully redesign the algorithms so that they can be efficiently multi-threaded.

Also, the fluid simulation here doesn't seam embarrassingly parallel to me.
http://www.gamasutra.com/view/feature/3549/interview_the_making_of_dwarf_.php?print=1
Some of it could be, but alot of that seams sequential to me, doesn't mean it couldn't be rewritten though.

Remember though that DF is toady's project and that he is developing it for fun. If he cared about the money more then DF then he would get a job. Toady won't do it if he doesn't want to.

[dragnar]

I'm no expert on Parallel computing

What your missing from the law is, what if the calculations that take 95% of the time in the code is the one you make massively parallel.

Ah, but those sections of code only take up so much time because they are hideously inefficient, improving the pathfinding/water flow algorithms would be both easier and more effective than multithreading the game, and I believe that is one of toady's goals.

[sproingie]

Cellular automata do pretty well in parallel.  Conway's Life on a shader for example.

Still, when the amount of stone in a fortress drastically affects the speed of everything else, something else sounds amiss, and there may be easier targets for optimization.  I wish there was a way for DF to be open source with Toady still making money and keeping creative control, but alas.

[Googolplexed]

Still, when the amount of stone in a fortress drastically affects the speed of everything else, something else sounds amiss, and there may be easier targets for optimization.

Yes, These are the types of optimizations that should be made first, before going into much more drastic measures.

I wish there was a way for DF to be open source with Toady still making money and keeping creative control, but alas.

Possibly toady should release some of the code, under an extremely restrictive license. Microsoft have the Microsoft Reference Source License, you can view the source, and that's about it.
He could leave out enough of the code to make it pointless to try to recreate DF, whilst leaving enough for us to look over and offer suggestions.

Inevitably some bastard would come along and steal what he can though.

[Shades]

Possibly toady should release some of the code, under an extremely restrictive license. Microsoft have the Microsoft Reference Source License, you can view the source, and that's about it.

Better he only releases stuff like how he did with the renderer. That worked very well so it's a proven model