Print

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

[Pseudo]

Pathfinding requires duplication of the entire graph in order to do across multiple threads, I don't know how weighty the map itself is, but it's nothing to sneeze at.

Incorrect if you have an implied "per thread" there. If not... it's a couple bits per tile (depends on how many classes of movement you wish to support - my guess would be 4). And it's not that much overhead compared to the map itself - take a look. (That's per 4x4 square, so everything that's an array of 16 is 1 / tile. I hadn't looked at it in a while - it's astounding how much there is.) You're spot on with the rest of your post, however.

[milo christiansen]

I write a lot of code in Go, and one of it's main features is easy concurrency via light weight thread-like objects and special communications "channels". Even with all that special language-level support for multi-threading it can be a real pain sometimes.

That said DF really needs to perform better, and the best/easiest way to do that is multi-threaded path finding. Take a look at any settlement management game and you will see the developers talking about path finding problems, optimizing path finding, etc Fast path finding is an industry wide problem, not just something DF needs to worry about.

Many games solve the problem via a separate path finder that runs all the time, taking requests from a list and returning results to the requester. These path finders generally have access to a cache of some kind, and sometimes use multiple worker threads managed by one dispatcher. Such path finders need to somehow calculate path in priority order, so that short paths are calculated first (so combat and such does not have weird "pathing pauses") and by age (so no unit waits forever for a path).

No mater how multi-threaded path finding is managed it would require the game to be retrofitted in the following ways:
1) The game needs to know that a path will not be immediately available when requested, this is a lot of work to add.
2) The game needs away to asynchronously update a unit's path and notify the unit that the path is valid. Some kind of atomically updated flag in the unit would probably work for this.
3) The path finder needs a way to read the map at all times, even while it (the map) is being updated. This is also a probably hard to fix problem. A possible solution would be to "double buffer" the critical parts of the map (but not the whole map!), eg update one copy while reading from the other. A better solution would be to make a list of changes that need to be made, then lock the map (pausing the path finder) and make all the updates in one fast go. Obviously you would only do this for the part of the map the path finder needs, namely the passability data and the reachability cache (which can be just a few bytes per tile).

Theoretically it may be possible to try different single-thread path finders via memory editing. What you would do is replace all calls to the game path finder with calls to your own injected function (probably by rewriting the path finder function in memory to point to your own function).

Everyone here seems excited by 64 bit? Don't be. The ONLY thing 64 bit will improve is memory address range. If you do not have problems with DF crashing due to OOM conditions (which is only really a problem with long/large worldgens) then 64 bit will do NOTHING for you.

[athenalras]

And my point was that that performance wall doesn't mean he'll have to get help - doesn't even mean he'll have to bite the bullet and multithread.

I never said Toady never had any other options did I? What Toady decides to do is up to his discretion. My post is a mere reminder of eventual confrontation with fixing performance issues due to hardware limitation.

Dwarf Fortress has been well behind industry standards since its inception - see, for example, the graphics. And yet, the ever-improving standards of computer graphics and graphics cards have not killed Dwarf Fortress, even as it lags so far behind them, because Dwarf Fortress isn't about graphics. As long as its graphics are good enough to be understood, it's enough.

This is an example of a terrible argument. How old are you? What grade are you in? Have you even taken your SAT's yet?

And yet, the ever-improving standards of computer graphics and graphics cards have not killed Dwarf Fortress, even as it lags so far behind them

By your logic, the older the graphics, the worse it should run on newer, compatible technology? That makes absolutely no sense.

Dwarf Fortress has been well behind industry standards since its inception - see, for example, the graphics.

Why are you focusing on the graphics? What blasphemy! How is this relevant to performance issues?
Dwarf Fortress was first released when only single-core processors were around so I fail how to see how that "falls behind industry standards" since inception. Second, Toady intentionally released Dwarf Fortress with ASCII graphics as are some games today. In that regards, it is not "behind industry standards" but a choice of aesthetics.
Take a look a the original PC tomb raider and the newer 2013 tomb raider. That is an example of "industry standards" regarding graphics.

Dwarf Fortress also isn't about performance, or real-time/twitch play. Same argument.

How dare you assume that I think of DF as real-time/twitch game. That aside, the entire reason for this discussion on hardware (and) performance is because Dwarf Fortress' pace of development, together with the technological development for single-core processing, is beginning to encroach on the unacceptable in terms of frame rate.

I am not alone in thinking that 1-3 fps in fortress mode is nigh unplayable. (I only play fortress mode so I am unsure of adventurer mode performance)

The Dwarf Fortress fanbase, or at least Toady's income stream, has only grown over the years, even as the technology behind DF has become more and more out-of-date. Sure, it'll probably eventually peak. But I don't think a lack of multithreading is what's going to do it. We don't play Dwarf Fortress for pretty graphics or smooth gameplay. We play to lose.

The Dwarf Fortress fanbase has grown over the years due to a mix of good press and fan-made products. Do you think there will be continued good press and fan-made articles if Dwarf Fortress became less accessible due to performance issues?

We don't play Dwarf Fortress for pretty graphics or smooth gameplay. We play to lose.

My writing style usually avoids name calling but by this point, I have to do it here. Are you an imbecile? Seriously, not only are these last two sentences sound so contrived but it is just downright, past-the-border, retarded when said in context, like its some sort of mantra that you've chanted to yourself for a whole year in a dark room.

And seriously, stop using the word 'technology'. Technology isn't going out of date in DF and it never has. What is outdated is the reliance on only a single-core processor in a world where technological advancements are focused on multi-core processing and multi-core compatible programs. You have lost your privilege to use the word 'technology' since you obviously fail to recognize its proper definition as well as its use in a proper context.

Also, and this is just a fun tangent, I wouldn't be surprised if automatic multi-threading becomes a thing in the next 20 years

There already is automatic multithreading of trivial code, e.g. accumulation loops (incidentally the same loops that can be automatically vectorized). But any nontrivial code (non-loops or loops that access other elements during the loop) will likely never be automatically multithreaded.

Edit: there's a whole subgenre of programming which is easily multi threaded, and that is functional programming. Given Toady's mathematics background (IIRC), he may even be familiar.

There's your answer to your last 'tangent'.

[athenalras]

I write a lot of code in Go, and one of it's main features is easy concurrency via light weight thread-like objects and special communications "channels". Even with all that special language-level support for multi-threading it can be a real pain sometimes.

That said if DF really needs to perform better, and the best/easiest way to do that is multi-threaded path finding. Take a look at any settlement management game and you will see the developers talking about path finding problems, optimizing path finding, etc Fast path finding is an industry wide problem, not just something DF needs to worry about.

Many games solve the problem via a separate path finder that runs all the time, taking requests from a list and returning results to the requester. These path finders generally have access to a cache of some kind, and sometimes use multiple worker threads managed by one dispatcher. Such path finders need to somehow calculate path in priority order, so that short paths are calculated first (so combat and such does not have weird "pathing pauses") and by age (so no unit waits forever for a path).

No mater how multi-threaded path finding is managed it would require the game to be retrofitted in the following ways:
1) The game needs to know that a path will not be immediately available when requested, this is a lot of work to add.
2) The game needs away to asynchronously update a unit's path and notify the unit that the path is valid. Some kind of atomically updated flag in the unit would probably work for this.
3) The path finder needs a way to read the map at all times, even while it (the map) is being updated. This is also a probably hard to fix problem. A possible solution would be to "double buffer" the critical parts of the map (but not the whole map!), eg update one copy while reading from the other. A better solution would be to make a list of changes that need to be made, then lock the map (pausing the path finder) and make all the updates in one fast go. Obviously you would only do this for the part of the map the path finder needs, namely the passability data and the reachability cache (which can be just a few bytes per tile).

Theoretically it may be possible to try different single-thread path finders via memory editing. What you would do is replace all calls to the game path finder with calls to your own injected function (probably by rewriting the path finder function in memory to point to your own function).

Everyone here seems excited by 64 bit? Don't be. The ONLY thing 64 bit will improve is memory address range. If you do not have problems with DF crashing due to OOM conditions (which is only really a problem with long/large worldgens) then 64 bit will do NOTHING for you.

Sorry if my post blocked yours. My anger-post was a bit long so I'll repost yours here.

[Button]

I don't know if you need to drink more or less, athenalras, but whichever it is, get on it.

[milo christiansen]

Oh, ouch, oh my sides...

I don't have anything against athenalras, but that is hilarious!

[funkydwarf]

Single core performance will continue to improve.

  Amds zen architecture will be out sometime next year. They CLAIM a baseline 40% increase in instructions per cycle.

The cpu industry has been milking development of more cores because they are afraid to hit the limit of smallness for copper, and thus speed(smaller wire traces have less capacitance). But they can't keep that adding cores forever, sooner or later they will focus on the speed of each core again.

I been watching this thread cause the people pushing for multithreading are amusing about how "easy" it would be. I believe I speak for alot of the silent majority that would rather Toady work in cool new features, than an extra year of devtime in between each round. Once this thing is 1.0, then optimization can be done.

As soon as the cpu boys focus on deving raw core speed again, and they will, it will improve drastically in a few gen of chips.

[xordae]

Clearly we can see from what the OP is saying that something needs to happen. Fortress mode, by default throws a ton of migrants at you and fills a rather high population cap quickly. At that point, your fortress will most likely already be slowed down to a crawl during relatively light activity, not even mentioning traders, sieges and all that fun stuff.

The game (by being played) essentially kills itself over the course of several years of game time. It's not about winning or losing, it's not about what aspect of the game is most important to the player. It's about being playable.

The sheer amount of stuff hogging the CPU in the background needs to be cut down to size. Whether that is through simplification, optimization or multithreading. As it stands, you have to restrict your playstyle to small embarks, low pop count, disabling features such as temperature, not being too prolific or long-lasting (!), not making too many goods or stockpiles and finding rather game-y pathing solutions that are lighter on CPU instead of building off imagination or aesthetics.

New CPUs are nice, but we're talking about an ASCII game whose immediate appeal is not only its depth but also its playability on laptops and low-power machines without GPU. Or so you would think, right?

[Geltor]

Single core performance will continue to improve.

  Amds zen architecture will be out sometime next year. They CLAIM a baseline 40% increase in instructions per cycle.

The cpu industry has been milking development of more cores because they are afraid to hit the limit of smallness for copper, and thus speed(smaller wire traces have less capacitance). But they can't keep that adding cores forever, sooner or later they will focus on the speed of each core again.

I been watching this thread cause the people pushing for multithreading are amusing about how "easy" it would be. I believe I speak for alot of the silent majority that would rather Toady work in cool new features, than an extra year of devtime in between each round. Once this thing is 1.0, then optimization can be done.

As soon as the cpu boys focus on deving raw core speed again, and they will, it will improve drastically in a few gen of chips.

wow, a whole 40%?! all that for a symbolic price of $1500! thats totally worth running a 200 dwarf fort at 70fps!

meanwhile at the other 15 cores....

(ps i dont think anyone here is saying that multithreading is easy, but im glad youre amused!)

[Veroule]

Single core performance will continue to improve.

  Amds zen architecture will be out sometime next year. They CLAIM a baseline 40% increase in instructions per cycle.

The cpu industry has been milking development of more cores because they are afraid to hit the limit of smallness for copper, and thus speed(smaller wire traces have less capacitance). But they can't keep that adding cores forever, sooner or later they will focus on the speed of each core again.

As soon as the cpu boys focus on deving raw core speed again, and they will, it will improve drastically in a few gen of chips.

Sure some instructions can be improved to reduce the number of clock cycles, but not many. Look up the 386 assembly reference and compare that to the reference on any modern processor based on the same instruction set. You will see that the very few instructions that have gotten shorter in clock cycles. In fact you can look at the references on many different processors and will find that it is rare for instructions to become faster. AMD has historically been slower than Intel for certain instructions and vice versa.

Where speed has been gained is with predictive branching and prefetching. Having the required data already in a CPU cache instead of having to wait 70ns for it arrive from RAM is huge. Programming in such a way that keeps the code working on a narrow section of data that stays in cache until done used to be a significant art.

Clock speeds can't go much higher without a radical change in the materials used to make the processors. The limit mostly comes from how fast a transistor can shift between states. Also raising clock speeds much higher has negligible effect without vastly different memory systems. A broad discussion of these limits can be found here: http://electronics.stackexchange.com/questions/122050/what-limits-cpu-speed

Long term, the best option for creation of faster CPUs is 3D IC. See here: https://en.wikipedia.org/wiki/Three-dimensional_integrated_circuit

[Tryble]

To anyone wondering about what kind of CPU to get, take a look at these benchmarks for single-threaded performance.  It's probably the best data for gauging DF performance we're going to get.

[Geltor]

To anyone wondering about what kind of CPU to get, take a look at these benchmarks for single-threaded performance.  It's probably the best data for gauging DF performance we're going to get.

i have the best one on the list, oc to that amount df still runs at around 60 fps with 200 dwarves on a 3x3 embark 

[Lightman]

To anyone wondering about what kind of CPU to get, take a look at these benchmarks for single-threaded performance.  It's probably the best data for gauging DF performance we're going to get.

i have the best one on the list, oc to that amount df still runs at around 60 fps with 200 dwarves on a 3x3 embark 

Personally, I don't think PassMark results are very compelling.  We need real-world data.  If no one else will do it, I'll try to set up a DF benchmark when I have time.