Print

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

[funkydwarf]

Heh, oh yeah that makes sense. The versioning information.

We should make this the general chat thread.

[Dirst]

Heh, oh yeah that makes sense. The versioning information.

I think we are more than 42% of the way there.  Some of the major features (the .01s) are bigger than others, and world activation was a really big one.  Another big one or two coming near then end will be cleaning up the interface.

We should make this the general chat thread.

I like corn chips.

[Shonai_Dweller]

Artifacts, magic and alternate dimensions will be big.
The world economy will be massive.
Laws, crime and punishment will have a pretty big effect.
Playable human, elf and goblin sites will need a whole lot of extra features to be anything other than 'dwarves in trees/pits/houses'.
Controllable armies/raiding squads will be big.

Honestly I'm surprised we're not still at version 0.25.

The one I'm looking forward to which isn't too huge and hopefully will get started with artifacts is the nemesis arc. A fantasy world simulator is a wonderful thing but it'll never truly make epic fantasy stories without totally evil bad guys acting out their dark ambitions to world shattering effect.

[Urist McVoyager]

I'm just looking forward to Toady adding plant based farming and processing to the ADVFort stuff he's got going on right now. Hands down if he adds in the ability to make and run a farm, I will playtest it myself until I can honestly say it's the best Harvest Moon sequel out there.

[khearn]

I just read through this, and boy, there are some misconceptions. I'm going to say some things a lot of DF fans don't want to hear, but that doesn't make them any less true. I'm a big DF fan. I've been playing for years, off and on (I just checked and my first post was back in 2011), and I don't particularly like writing this. But just ignoring reality because you don't want it to be true doesn't really make things better.

A little background: I work at Google as a Release Engineer, and I've been in the software engineering field since 1990 doing development for a while (compiler optimizers and kernel/NFS development) and then switching to Release Engineering for most of my career. I'm not an expert in multi-threading, but I know a pretty fair amount about the software life cycle and when you need to do certain tasks along the way. And I've seen a lot of mistakes made. I also have a tendency to make long sentences with too many commas in them. I apologize in advance for that.

1) CPUs will not magically continue to get faster and save us all from FPS death. Moore's law is pretty much dead. Single threaded CPU performance on consumer-grade CPUs has plateaued, and will not improve much unless someone figures out a way to change either the speed of light, the laws of thermodynamics, the size of a silicon atom, or the charge on an electron. We're up against some basic, low-level physics limitations and that's not likely to change. Ever.

2) Quantum computing will not magically make DF faster, because DF can't run on a quantum computer without a complete re-write that would make multi-threading look trivial. Quantum computers are weird, probability engines, that give me a headache just trying to figure out what they are capable of doing. They're not just magically faster CPUs that can run the same code as X86s. Same goes for most other non-silicon based future computer designs out there.

3) You can't just put off optimization until the code is feature complete and wave your magic wand of optimization (-O5) and make everything faster. You need to design in optimization from the start, because when it comes time to optimize, if you didn't plan on doing it, you'll probably have to make significant changes in your code to do it. And that will break other things, which will require significant changes, which will break other things, and so on. If you are going to have to do something with every object on the map, you'd better make sure from the start that what you do to one object doesn't affect what you will do with the next one, or you are doomed to having poor performance because you have to do them all sequentially. Once you have a situation like that, and at the end of the development cycle you decide to make it parallelizable because it's a major bottleneck (which it certainly will be), you now have to change they way things work at a very basic level, which will break other things. if nothing else, it will break every existing fort design that depends on that functionality, because you'll have to change how things actually function in the game, not just how they're implemented.

This is where I suspect Toady has currently gotten himself (but I obviously don't know for sure). He started writing DF when Moore's law was still going full steam, and making it multi-threadable didn't seem important at the time. Plus, I doubt he had much experience with multi-threading, so he probably didn't design for it from the start. It's non-trivial. I almost certainly wouldn't have done it either. And I'd be in the same state as he is now.

4) Saying "I'm not going to optimize this version because I may change things in the future and have to re-optimize" is just wrong. Because if you aren't thinking about optimization now, when will you start thinking about it? When you re-implement this feature? No, because you'll still be saying "I'm not going to optimize this version because I may change things in the future and have to re-optimize". Until you get to the end and you have a completely un-optimizable design and have to redesign lots of major parts. It might actually be easier at that point to start over from scratch (really, I'm completely serious).

The only way I can see to get significant speed improvements for DF is to implement multi-threading. There are just too many operations that are done on either every creature on the map, or every object, or even every tile (temperature, I'm looking at you), and doing that kind of thing sequentially is simply not scalable. This year's CPUs aren't more powerful than last year's because they do sequential things faster. They're faster because they do parallel things faster, and modern programs are designed to do things in parallel. And that's the way things are going to be for the foreseeable future. There may be some minor tweaks that can be done to make a sequential program like DF a little faster, but that will only take you so far. It won't get you past the very basic structural limitation of having to do everything in sequence,      one      thing       at      a      time.

Google isn't able to give you search results while you're still typing your query because they run it on one, super-fast CPU. I don't know off the top of my head what clock speed the current machines are running at (and even if I did know I couldn't tell you), but they're not something exotic that requires cryo-cooling. Google gives amazingly fast results because they shard the problem out to multiple threads on multiple, fairly ordinary, machines (that much, I can tell you). That's the way Deep Blue beat Kasparov at Chess, that's the way Watson beat Rutter and Jenning at Jeopardy, and that's the way AlphaGo beat Fan Hui at Go.

Putting multi-threading off until the end won't make it less work, it will make it more work. Designing things from the start for multi-threading, and making sure every re-design along the way supports multi-threading is actually the easiest way to do it. Taking a big, complex single-threaded program and making it multi-threaded is going to be nearly impossible. It's actually far, far easier to just make it multi-threaded as early as possible and just keep it multi-threaded as you go.  At some point he's just going to have to bite the bullet and do it and the longer he puts it off, the harder it's going to be. I just hope it's not already too late.

Frankly, I don't know what he can do at this point. He needs to either get some serious experience with multi-threading, which isn't going to happen while he's implementing single-threaded features in DF, or he needs to decide that he trusts someone who has experience in multi-threading with his code, which also seems unlikely. But either way, he's got to learn about multi-threading so he can continue coding without breaking things once it has been multi-threaded.

Trying to learn about multi-threading while implementing it on something as complex as DF is probably just going to result in a badly implemented multi-threaded DF. It's just too complicated to get it all right the first time you do it. Maybe he needs to start a side project. Some other program that he can work on with the idea of making it multi-threaded from the start. Maybe collaborating with someone experienced who would be willing to mentor him and teach him the ropes (threads?). So them he can take what he learns from the other project and apply it to DF. It would slow down DF development for a while, but he's got to learn it at some point, and the longer he puts it off, the worse it's going to be.

The other option I see is that he never gets around to optimization and DF just grinds to, well, not really a halt, but to the point where it's no longer able to do what he wants.

I'm sorry if the above ruffles some feathers. Those of you who hang around the Dwarf Mode Discussion board should know that I'm a fan of the game and generally know what I'm talking about, but am willing to be clear about it when I'm not sure of what I'm saying. I'm not someone who showed up, played a few times, and decided it's all wrong and needs to be changed to suit what I want from it. I know it's Toady's game, and I have great respect for him for keeping it as his game. I've made multiple donations over the years because I respect what he's doing. But that doesn't mean I think he's doing everything right, and I think I do him more of a favor by pointing out where I think he needs to make changes, rather than just saying "everything will be sunshine and unicorns."

Sorry this got so long.

[TheBiggerFish]

Makes sense...

[Orange Wizard]

Makes sense...

Yeah, but a lot of the principles apply to things that aren't DF.

1) CPUs will continue to get faster; ferex. AMD is working on a new line of processors optimising single-core performance. Moore's law may be dead, but we will see improvements until the end of time. That's how technology works. It's not something to rely upon, but saying technology won't improve is very strange.

3) You can of course put off optimisation until the code is feature-complete and then gut the entire thing to make it faster. It's not necessarily the best tactic, but it's the one Toady's following (presumably because the bulk of the engine was written ~10 years ago and Toady admits he was not the programmer then that he is now).

Multithreading is basically untenable for DF mechanics-wise. 90% of the stuff the game does requires things to be done in order, i.e. one thing at a time. It's like multithreading Minecraft - you can put chunk loading, rendering, and all these other things in separate threads, but you can't split up the core game (i.e. where most of DF's lag comes from) without buggering the core mechanics.

The other option I see is that he never gets around to optimization and DF just grinds to, well, not really a halt, but to the point where it's no longer able to do what he wants.

No, not at all. When .40 was released the world simulation was really really slow, so Toady spent a few days fixing it up to run faster. Now it's good enough that it has very little impact on gameplay. Toady is capable of optimising when he wants to.

[TheBiggerFish]

Aaaaand that ALSO makes sense.

[Libash_Thunderhead]

Multithreading is basically untenable for DF mechanics-wise. 90% of the stuff the game does requires things to be done in order, i.e. one thing at a time. It's like multithreading Minecraft - you can put chunk loading, rendering, and all these other things in separate threads, but you can't split up the core game (i.e. where most of DF's lag comes from) without buggering the core mechanics.

Either that, or put things like AI(include pathing) in other threads. Problem is you'll never get the same result even if you start the game with exactly the same RNG seed.

[cochramd]

Multithreading is basically untenable for DF mechanics-wise. 90% of the stuff the game does requires things to be done in order, i.e. one thing at a time. It's like multithreading Minecraft - you can put chunk loading, rendering, and all these other things in separate threads, but you can't split up the core game (i.e. where most of DF's lag comes from) without buggering the core mechanics.

Either that, or put things like AI(include pathing) in other threads. Problem is you'll never get the same result even if you start the game with exactly the same RNG seed.

That doesn't sound like a problem at all.

[Orange Wizard]

Pathing doesn't use random seeds anyway.

I could see AI/pathing stuff working if done multi-threadedly, in a fairly simplistic way. Trying to do asynchronous AI updates in DF would be nightmarish.

[Libash_Thunderhead]

Pathing doesn't use random seeds anyway.

I could see AI/pathing stuff working if done multi-threadedly, in a fairly simplistic way. Trying to do asynchronous AI updates in DF would be nightmarish.

What I was trying to say is you don't have the same result even if you stard with the same save.
One time, maybe the goblin out smart Urist and another time, Urist kills the goblin because the latter's thread fails to complete before his?

[Orange Wizard]

Oh, yeah, that's what I meant by asynchronous.

[khearn]

Makes sense...

Yeah, but a lot of the principles apply to things that aren't DF.

1) CPUs will continue to get faster; ferex. AMD is working on a new line of processors optimising single-core performance. Moore's law may be dead, but we will see improvements until the end of time. That's how technology works. It's not something to rely upon, but saying technology won't improve is very strange.

No. Once you get transistors so small that the charge from one starts causing the one next to it to fire (which is where they are now), you can't make them any smaller. If they can't get any smaller, they can't really get much faster. There is a smallest size something can be, and we're pretty much there. There may be room for a little more improvement, but you won't see the increases we've seen so far. My first PC had a clock in single-digit MHz, now there' in single digit GHz, about a thousand times faster. We won't ever see another thousand time improvement in single threaded performance. I doubt they'll even manage to double what they've got now, as far as single threaded goes. There's just no place to get it.

3) You can of course put off optimisation until the code is feature-complete and then gut the entire thing to make it faster. It's not necessarily the best tactic, but it's the one Toady's following (presumably because the bulk of the engine was written ~10 years ago and Toady admits he was not the programmer then that he is now).

Multithreading is basically untenable for DF mechanics-wise. 90% of the stuff the game does requires things to be done in order, i.e. one thing at a time. It's like multithreading Minecraft - you can put chunk loading, rendering, and all these other things in separate threads, but you can't split up the core game (i.e. where most of DF's lag comes from) without buggering the core mechanics.

It's only untenable because it wasn't designed to be multi-threaded. That's exactly my point. It shouldn't require stuff to be done in order. Are you familiar with Conway's game of Life? Every cell changes at the same effective moment, even though they may be calculated either sequentially or in parallel. If you implement it starting in the top left and changing cells as you go, it's ends up all wrong. You go through the entire array, calculating each cell independently, and creating a new array with the results. Then swap the arrays when everything is done.

The timing of mechanisms shouldn't depend on the build order (which indicates that he's just going sequentially through a list, making changes in place). If he just calculated each device based on the state of other devices at the start of the tick, then changed states of everything at once, then everything could be done in parallel.

Temperature calculations are also amenable to the same technique.

Most pathfinding and AI decisions could probably also be done in parallel, if they were written to be done so.

But changing them to be parallelizable will break other things that rely on the current behavior. And trying to change them all at the last minute will cause lots of breakages at once, which will be much harder to debug.

The other option I see is that he never gets around to optimization and DF just grinds to, well, not really a halt, but to the point where it's no longer able to do what he wants.

No, not at all. When .40 was released the world simulation was really really slow, so Toady spent a few days fixing it up to run faster. Now it's good enough that it has very little impact on gameplay. Toady is capable of optimising when he wants to.

There's only so much low-hanging fruit he can optimize. Every time it will take more effort to get less gain. Eventually he'll be spending a month to get a 1% gain. There's only so much he can get without dealing with the elephant in the room.

I'm not sure I've ever seen a program that screams out for multi-threading as much as DF. There are just so many places where he goes through a list or array, doing the exact same operation to every element. That's exactly the type of thing where multi-threading wins. if you go from one thread to 4, you get through the list almost 4 times as fast. And 4 threads is pretty low for a modern CPU. Most can probably handle more like 10-16 threads. He won't ever get that kind of improvement just optimizing single-threaded code.

[Orange Wizard]

No. Once you get transistors so small that the charge from one starts causing the one next to it to fire (which is where they are now), you can't make them any smaller. If they can't get any smaller, they can't really get much faster.

That's the same logic that says we'll never be able to go from Moscow to Beijing in a day or two because horses can only gallop so fast.

Anyway, re: multithreading:

The short answer is that I don't know how to do it [muktithreading], it'd probably break things and take forever, but there are definitely places where it would help.

Should it be done? Probably. Is it going to happen? Not any time soon.