Print

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

[Footkerchief]

Has anyone brought up how switching the game to multithreading wouldn't have as much of an impact as it would seem?

Depends on what you could multithread. Water physics is probably not really parallelizable given its reliance on stateful data, but pathing almost certainly is (and given certain degenerate cases, would be a pretty big chunk to actually deal with). Given an omniscient pather like the current one, it should be relatively easy. Pathing already locks important stuff so other dwarves can't get to it, it seems like it would be a simple task to parallelize give the source code.

I still wonder how much impact pathfinding actually has, though (aside from the processor-crushing bug with pet-locked doors).  People take it for granted that 200-dwarf fortress crawls because of pathfinding, but others have recently shown that just having thousands of stones on the map can cause at least as large a performance hit, and those factors tend to go hand-in-hand in long-term fortresses.

Toady's going to be working through the top 10 ESV items after this release, along with improved sieges and Adv. Mode improvements, and "Improved (Speed Up) Pathfinder" is #4 on ESV.  So we could see some pathfinder work within the next couple months, depending on what he wants to do first.  I'm guessing that'll turn into more of a general performance item, which will hopefully include the use of a code profiler so that the relative importance of pathing, fluids, population, item count, etc. will become clearer.

[Blacken]

This would be why affining it to a single CPU often sees (sometimes significant) perf improvements.

This is sort of off topic (although given that the topic is apparently irredeemably flawed I guess that's all right) but are there any good utilities out there for facilitating or automating core affinity?

http://www.robpol86.com/index.php/ImageCFG

So... finding prime numbers sounds like it would have two fundamental stumbling blocks:

1) The basic code utilized by computers, having at its most basic level only a yes/no or odd/even, in other words opposite or mathematically speaking 0/1, +/- aspect is very limiting in this instance.

I realize this is the basis of computing, so please don't jump my case. I'm just pointing out that the way our most basic computer system exists disqualifies it to a large degree for this kind of work.

Correct. Computers are bad at certain things. (Who knew?)

The other reason why forcing DF to a single core also leads to better performance is because at the same time it also removes the CPU limits for Dwarf Fortress. (So instead of 30% it can go up to 100%)

This is counterfactual. An even-spread scheduler tends to do this. There is no "CPU limit" on it.

Is "counterfactual" polite enough for you, sir?

Has anyone brought up how switching the game to multithreading wouldn't have as much of an impact as it would seem?

Depends on what you could multithread. Water physics is probably not really parallelizable given its reliance on stateful data, but pathing almost certainly is (and given certain degenerate cases, would be a pretty big chunk to actually deal with). Given an omniscient pather like the current one, it should be relatively easy. Pathing already locks important stuff so other dwarves can't get to it, it seems like it would be a simple task to parallelize give the source code.

I still wonder how much impact pathfinding actually has, though (aside from the processor-crushing bug with pet-locked doors).  People take it for granted that 200-dwarf fortress crawls because of pathfinding, but others have recently shown that just having thousands of stones on the map can cause at least as large a performance hit, and those factors tend to go hand-in-hand in long-term fortresses.

Toady's going to be working through the top 10 ESV items after this release, along with improved sieges and Adv. Mode improvements, and "Improved (Speed Up) Pathfinder" is #4 on ESV.  So we could see some pathfinder work within the next couple months, depending on what he wants to do first.  I'm guessing that'll turn into more of a general performance item, which will hopefully include the use of a code profiler so that the relative importance of pathing, fluids, population, item count, etc. will become clearer.

He's probably iterating the stones somewhere he shouldn't be, or something similar. Obviously I don't have the code, but any big project can contain lots of similar pitfalls. The problem with pathfinding is that pathfinding is a problem you can't just magic away by writing better code or not doing something--you have to pathfind, and as such it's just One Of Those Things that, even if other stuff gets cleaned up, is going to remain ugly in terms of serial processing.

[bombcar]

So... finding prime numbers sounds like it would have two fundamental stumbling blocks.

(It's also a direct reference to breaking encryption. The details are kind of boring, but basically:

Therefore, unless someone makes a very large and unexpected mathematical breakthrough, it's practically impossible to find out the private key from a public key with RSA encryption, making it one of the most secure methods ever invented.

The "large an unexpected breakthrough" is quickly finding primes. Computers can find primes, but finding, for example, all of them in a 128 bit keyspace will still take more time than the remaining life of the universe.

[Neonivek]

There is no "CPU limit" on it.

There is a CPU limit. Basically it is what stops a single program from multiplying its processess until it eats up your computer.

The CPU Limit Remover is done at the same time as forcing it to a Single Core. (In fact it is the whole point to doing so)

Is "counterfactual" polite enough for you, sir?

You could have said "That isn't true". You don't have to be a bastion of politeness and rain heavenly light to all those who see you

The details are kind of boring, but basically:

Dang it the secret police strike ag

[keith.lamothe]

Architect, thread-tone issues aside, let me assure you that making an application that is:

1.1) non-trivial
1.2) single-threaded
1.3) not written with a change to multi-threading in mind

into an application that:

2.1) is significantly multi-threaded (such that, say, at least 1/3rd of its processing can be on other cores)
2.2) behaves in a semantically identical fashion to the original application

without:

3.1) performing an extensive review of all current source code to identify candidate "threads", and the resources (objects, I/O, etc) they'll need to read and/or modify
3.2) identifying which resources will be needed by multiple threads (read and/or modify), and deciding on an appropriate method of synchronizing those accesses
3.3) refactoring the source code to implement the new threading scheme
3.4) extensive testing of the new application to ensure the semantics are identical to the old one (to some degree of acceptability)

is an unsolved problem in computer science.

To put it another way: your enthusiasm for improving DF and dealing with hard problems is a good thing, but it would be put to much better use on other, more-tractable issues.

[bombcar]

There is no "CPU limit" on it.

There is a CPU limit. Basically it is what stops a single program from multiplying its processes until it eats up your computer.

This is not correct. A single-threaded process will never multiply processes - it cannot. You may be thinking of the "resource limit" that prevents fork bombs or of the renice capability - a form of priority.

A single-threaded process will use all available CPU unless something else is running - there is no reason for the computer to allow idle CPU to hang around.

[Blacken]

There is no "CPU limit" on it.

There is a CPU limit. Basically it is what stops a single program from multiplying its processess until it eats up your computer.

The CPU Limit Remover is done at the same time as forcing it to a Single Core. (In fact it is the whole point to doing so)

This is also counterfactual. A program can spawn processes as often as it likes, so long as it doesn't hit a limit designed to stop processes from rabbiting and making a fork bomb.

The key thing that makes you very hard to take seriously is that we're not talking about processes, but threads. All affining a single-threaded program (or, since virtually every Windows application has at least 2-3 threads, a few-threaded program) to a single core ensures that you don't suffer the overhead of cache misses, register copyovers, etc. inherent from moving between cores (and avoids other stuff like busy-waiting on in-flight threads on whatever core the process is being dumped to). There is no magical "limit," there are just the algorithmic tendencies of the scheduler.

EDIT: damn yooooooooooou, bombcaaaaaaaaaaaaaaaaaaaaaaaaaar!

[Neonivek]

Hmm Likely Resource limit

Though there are ways around it as viri know.

[bombcar]

EDIT: damn yooooooooooou, bombcaaaaaaaaaaaaaaaaaaaaaaaaaar!

I've got twelve copies of Firefox open, each multi-threaded enough to make even IBM cry; bound to more hyper-threaded CPUs than you could count even with 256 bit primes. You goin' down!

[bombcar]

Anyway, a reason you may see "30%" CPU usage when running DF on a multi-core machine could be as follows:

1. DF is using much of CPU 0.
2. OS says, CPU 1 is not doing anything! DF, go to CPU 1!
3. OS says, CPU 0 is not doing anything! DF, go to CPU 0!

And then it loops. That's thread-thrashing; it's not very useful. Processor affinity helps; but modern OSes should be good enough to not need it.

There can also be sampling errors, and a DF that is FPS limited won't use the entire CPU (as it will sleep).

[Blacken]

EDIT: damn yooooooooooou, bombcaaaaaaaaaaaaaaaaaaaaaaaaaar!

I've got twelve copies of Firefox open, each multi-threaded enough to make even IBM cry; bound to more hyper-threaded CPUs than you could count even with 256 bit primes. You goin' down!

I know you're lying because Firefox multithreads like walruses mate.

Poorly.

[bombcar]

EDIT: damn yooooooooooou, bombcaaaaaaaaaaaaaaaaaaaaaaaaaar!

I've got twelve copies of Firefox open, each multi-threaded enough to make even IBM cry; bound to more hyper-threaded CPUs than you could count even with 256 bit primes. You goin' down!

I know you're lying because Firefox multithreads like walruses mate.

Poorly.

That's why I have twelve of them! And I have so many connections to the internet that my routing table makes DF's pathfinding look positively P.

[Moneo]

Given cooperation from Toady on whatever necessary level, is it even possible to create an interface/utility that would do what I've suggested?

I know I'm late to the party here, but as has been stated numerous times already:

"no, just no."

At least not with the problems far outweighing any benefits. I'm not claiming to be as up with DF-threading knowledge as these blokes seem to be, but the more I hear the more I'm convinced. It really is like you're telling a mechanic "just add another engine and 5 more wheels - that'll make it go twice as fast!"

[Rysith]

Chiming in as another programmer beating a dead horse, making programs multithreaded correctly when you're designing them to be multithreaded and giving the computer specific instructions about what needs to happen before what is hard enough. The idea of doing that automatically is well into the "no, just no."

I wouldn't be surprised, though, if we could pick up major performance improvements with a bit of profiling, even informally. Graphics was something that someone picked up and we got a major improvement out of. What if someone made a 200-dwarf minimal item fort, or a seven-dwarf thousands of items fort[1], to measure the performance of those two? I know that I feel like I see significant FPS drops with traders (or ambushes) on the map, though that may be my imagination. We've also got temperature and weather as significant FPS-drains. Figuring out what conditions cause slowdowns, and by how much, could definitely be useful to Toady when he's trying to make dwarf fortress faster, even in the absence of a real profiler attached to it.

[1] For example, I know that when I have more than a few thousand bars or stones it can take a noticeable amount of time to select them in the stocks menu, but not so with stacks of food or ammo. Might there be a "stones" data structure that's growing too large, and causing slow lookups whenever a dwarf tries to start a task involving a stone, that could be solved by changing the data structure?

[Blacken]

[1] For example, I know that when I have more than a few thousand bars or stones it can take a noticeable amount of time to select them in the stocks menu, but not so with stacks of food or ammo. Might there be a "stones" data structure that's growing too large, and causing slow lookups whenever a dwarf tries to start a task involving a stone, that could be solved by changing the data structure?

Food is in stacks, though. So the food-eating-units being iterated are probably more like anywhere from 10 to 40 per "item."

If you got half a million food, that'd probably be 10,000+ stacks, and you'd see the same thing.

From half-assed timing of it on a test fortress tonight, it seems close to linear in terms of the delay from selecting a stone stack when you select a ton of them. I would guess that the game just iterates all of them.