Print

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

[profit]

Any reason why OpenMP couldn't be use? Adding it to C++ code is as simple as adding few OpenMP Directives (no need to rewrite whole code creating client-server, emulators, etc...) and each for loop with independent elements could be divided to processor cores with almost zero effort.

I *Highly* doubt it would be as easy as you are making it out to be, however, it would be a good method to investigate to see if there are any plausible areas where it could be used in DF without major code re-writes. (since things only need to be synchronized at the frame barrier, there could be large area's that could be parallelised.. Maybe not though.) But yes, alot better than a ground up re-write to handle client/server interface (which I didn't quite get, it may be good but I just couldn't see how it would help that much besides decoupling the interface.. Doesn't mean it wouldn't help though I just don't get how.)

The nature of Temprature is that it doesn't need to update changes very fast, with the except of stuff moving like water, magma and stone. Changes in temprature can happen at 1/16 the rate (and 16x the power?) rate of water is now and nobody will every notice. Then bear in mind that temprature doesn't require pathfinding like water does.


Exactly how will you make 100 threads of moving fluid?? Threads are not cheap to create or destroy, nor can you run more threads than the number of processors available.
Far better to make 1-5 threads and allow those threads to handle seperate bodies of water, or individually numbered tile.
I suppose that might actually work, but there is some syncronization overhead necessary.

Depending on the implementation, It might or might not be faster with just 2 processors, and would require some really impressive threading magic.



"Every pathfinding job could each have its own thread..."
The pathfinding jobs only cause lag when they start colliding with each other. Only one creature can stand up on a tile at a time! The problem is how DF handles these conditions. All paths that conflict are dumped into memory. This will invariably occur with two paths at a time, and can cause syncronization-issues. issues that are very problematic no matter how you attack them, short of revamping the whole movement system.


I know multi-threading is possible, I just don't want Tarn to destroy DF to make it support multithreading. Just because other people built the engine with multithreading from the bottom up doesn't mean it takes Tarn a mere four months to write in Multithreading.

I was using the specific example of having a massive number of processors available, such as stream processing units in a video card, or for future proofing the code for the days when we have computers with 48 main cores and 16,000 math cores...
 ( I figure it is only a matter of time before AMD or INTEL introduce limited math cores to compete with the CUDA's and FUSION's of the world, Honestly I am really surprised they haven't already...)

As for the movement... Well.. maybe that is the problem, but I am sure even badly designed code done by 4x the processors is faster than badly designed movement code done by 1. But yeah maybe it would be better to fix it up somehow... I don't know.

As for speedups.. Dwarf fort NEEDS some desperately.. I cannot say with 100% certainty that many threads are the best way to go.. They are just the only obvious way.

But.. after working on an open tibia server I do know that making it multi-threaded did speed it up somewhat by using a greater number of cores... however what really made the difference in the end and caused processor usage to be tolerable even when you had 400 people on was code cleanup...

Not that the code cleanup was easy.. it took 40+ (not working full time but still) people nearly 3 years to find all the bugs that were causing issues and clean it up... the multithreading was way faster in the end.  They did that in a couple days, and it only took a few weeks to make it semi stable...  Not that it was stable before so... More like getting it back to the original stability.. (now it is much more stable but they have been working on it for years)

Apache and Mysql... As far as I know they have just always been threaded and threaded well... I see apache has hundreds of threads sometimes, and it does not seem to be slowing things down.

[sproingie]

Apache can run hundreds of independent processes with no data dependencies whatsoever.  MySQL locks or uses MVCC to control concurrency.  They are completely different things.  DF is a complex simulation with zillions of data dependencies.  It would require a complete rewrite to support threading.  I really wish people would stop comparing programs as if they were all the same.

[zagibu]

I really wish people would stop comparing programs as if they were all the same.

Bu...bu...but they are all .exe files...

[Shades]

Apache can run hundreds of independent processes with no data dependencies whatsoever.  MySQL locks or uses MVCC to control concurrency.  They are completely different things.  DF is a complex simulation with zillions of data dependencies.  It would require a complete rewrite to support threading.  I really wish people would stop comparing programs as if they were all the same.

Have to agree with this.

Apache processes for example tend towards low cpu/ram usage and short lifetimes. If you write page cgi scripts you can soon see how fast you can slow it down too

Dwarf Fortress is a single threaded high cpu monster of a process. You can't just 'add threads' to make it faster first you have to pull out tasks that can be run independently of the main process (or at least mostly independent). Which is why I suggest pathfinding. It's possible the rendering process could be another one that is easy to pull out and would just take snapshots when DF pass details over.

[GoldenH]

I think that people who say that Toady needs a way to learn multhtreading with mini-goals are correct. However there are several perfect examples of this. I mentioned hosting the temperature and water code in separate threads in my past post, because they're new to 3D dwarf. But really, just about any new feature could be split into a thread. Toady could have a goal, 'make animals run in  a separate thread from dwarves.' or whatever new feature he makes, just writing it to use a second thread. 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.

I just think it needs to be done because I would like to be able to play the game with all the features enabled, on interesting maps, and build interesting designs and do interesting things, unfortunately I regularly get my dwarves down to 0 FPS (not even 1 fps) by doing things as simple as letting animals roam free or wanting to just continually dump water into an evaporating basin. I remember one time i breached the HFS and my framerate went to 0 so I went to sleep, when i woke up the framerate was still 0 and the HFS still hadn't done anything Fun.

Right now DF is unplayable for me because I have to design my fortress to have decent FPS, it's a more important consideration than seiges moods or food.

[eerr]

Everybody spam's "toady do multithreading"
Yet they don't even give a good example about a program which is already multithreaded and works.

[Shades]

Everybody spam's "toady do multithreading"
Yet they don't even give a good example about a program which is already multithreaded and works.

To be fair the only decent example would be one that showed how it could be applied to DF which depends on how isolated the various features are. Writing a multi-threaded example application is simple, especially if your using things like boost::thread.

People, including myself, have given examples of what areas might be applicable to being run in a separate thread however as noone really knows how the code works we can only give so many suggestions.

To be honest the best way might be to take the code for the 40dX renderer and shift that into it's own thread which, if done right, is a good example, something that can be integrated into the existing code and might even be useful for performance gains (dependant on how the DF and the renderer transfer information).

[eerr]

Everybody spam's "toady do multithreading"
Yet they don't even give a good example about a program which is already multithreaded and works.

To be fair the only decent example would be one that showed how it could be applied to DF which depends on how isolated the various features are. Writing a multi-threaded example application is simple, especially if your using things like boost::thread.

People, including myself, have given examples of what areas might be applicable to being run in a separate thread however as noone really knows how the code works we can only give so many suggestions.

To be honest the best way might be to take the code for the 40dX renderer and shift that into it's own thread which, if done right, is a good example, something that can be integrated into the existing code and might even be useful for performance gains (dependant on how the DF and the renderer transfer information).

I totally thought DF did this already. Then again, you wouldn't want DF (main) blocking DF(graphics) from updating, or vice versa on an ordinary machine.

[Shades]

I totally thought DF did this already. Then again, you wouldn't want DF (main) blocking DF(graphics) from updating, or vice versa on an ordinary machine.

Nope the code is separate but it's still one process I think. That said I've not looked at the code
It wouldn't really matter if the example blocked waiting for DF (main) because that would be as it currently is (except with more threads waiting doing nothing)

[eerr]

I totally thought DF did this already. Then again, you wouldn't want DF (main) blocking DF(graphics) from updating, or vice versa on an ordinary machine.

Nope the code is separate but it's still one process I think. That said I've not looked at the code
It wouldn't really matter if the example blocked waiting for DF (main) because that would be as it currently is (except with more threads waiting doing nothing)

I mean, for a single processor only one thread runs at a time.
So either graphics are running or main is running.
But which should run at a given time?
What is managing the two threads?

[Shades]

I mean, for a single processor only one thread runs at a time.
So either graphics are running or main is running.
But which should run at a given time?
What is managing the two threads?

The os manages it, it's fairly normal though as your average app has ui and rendering on different threads. Not something to worry about it's easy to add a yield after each render loop for example.

[Googolplexed]

Too many people are looking at whether multi-threading can be implemented.

I don't think its a question of if,but a question of how long would it take, Toady has said that he doesn't know much about multi-threading and it could take him a while to learn. There are many good multi-threaded applications out there but I don't think DF was ever designed to utilise it, remember that it had been in development a while before duel-core processors took off.

Toady could multi-thread DF, but if he does it incorrectly it could cause the program to be slower/buggier then it is now,in which case many months of coding go down the drain. The only real way to take full advantage of multi-threading is to re-code large portions of the application. How many games/applications have you seen that are multi-threaded but don't take advantage of it, its hard to just bolt-on multi-threading to an application as large as dwarf fortress.

And if anyone mentions CUDA or GPGPU stuff, understand that it is not meant for an application like dwarf fortress. Until 2008 most graphics cards lacked an IF statement and are still incredibly slow at executing it.

PS:I would like to see the 2002 computer that supposedly ran DF, its unusual considering that in 2005 most computers weren't even duel core yet. (And actually the single-core performance of processors is still increasing, if a little slower then before). According to the performance statistics my single core ATOM netbook is slightly faster then an 02 computer, and DF lags like hell on it.

[CaptainNitpick]

PS:I would like to see the 2002 computer that supposedly ran DF, its unusual considering that in 2005 most computers weren't even duel core yet. (And actually the single-core performance of processors is still increasing, if a little slower then before). According to the performance statistics my single core ATOM netbook is slightly faster then an 02 computer, and DF lags like hell on it.

The problem with such statements is that there's no objective standard for performance in Dwarf Fortress. It's not like a first-person shooter, where low framerate can literally make the game unplayable. DF's lower speed limit is based purely on what the player is willing to tolerate.

[Kai_Kratz]

I was thinking quite some time i should reply to this topic or not, well obviously i came to the conclusion to take part in this discussion.

So far i had the pleasure to work with the usual suspects when it comes to threading or parallelism in general (boost, posix, windows threads, java threads, MPI and C for CUDA). I think parallel programming is hard but manageable. Will DF benefit from it? In my opinion it will, but i doubt it will be the solution to the speed problem.
Someone ,in my opinion correctly, pointed out that some heavy duty algorithms are not as fast (in terms of big-O) as they could be. Any reduction in time-complexity beats parallelism for what i learned.

But unless we see the code we can only guess, which usually deteriorates from educated guessing to less educated guessing. Since it was stated already that see-some-code is a no-no, how about some profiler results? And of course which algorithms used the most time (just in case it isn't path finding which it probably is). This info could help to slowly introduce a) better algorithms and b) better parallel algorithms to DF. Like for example Bitonic sort or scan (ok these ARE pretty lame examples but i guess you get the drift).

On a sidenote: Is DF really a cellular automaton?(Multiple states of one cell at one time violate the definition if i remember correctly) If the answer is yes, then some more classical texts on computer science (im talking 60s here) might be of increased interest. The 60 where the golden age of parallel programming and cellular automate where one of the main research objects ( yes they are highly parallelizable ).

[Draco18s]

On a sidenote: Is DF really a cellular automaton?(Multiple states of one cell at one time violate the definition if i remember correctly) If the answer is yes, then some more classical texts on computer science (im talking 60s here) might be of increased interest. The 60 where the golden age of parallel programming and cellular automate where one of the main research objects ( yes they are highly parallelizable ).

Yes and no.  There are parts that are (liquids for example are either water or magma (defined by a single bit) and have a depth from 0 to 7) and parts that...are less so.  Such as occupancy (there can only be one standing creature, but an infinite number laying down in the same tile).