Print

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

[Vulcanius]

No, the algorithm and the threading are separate.

I guess I'm thinking of things like not writing to static/shared memory and instead using working data structures that are per task.  I realise this is difficult with a map as big as DFs, which is why I'm suggesting thinking about it in advance may prevent another lengthy rewrite.

The major problem with that approach is you are duplicating data, which not only takes up additional memory but adds on execution overhead. So you end up reducing the efficiency instead of improving it.

Some stuff, like jobs queue, would still be easier with locks, but its not a problem to have global lock for it and use it for writes on the queue.

A global lock on something like a queue might seem like a nice/easy approach but it ends up being a bottleneck on scaling due to lock contention if that queue is accessed frequently. A job queue would likely be one of those frequently accessed structures. In all but rare cases you want to avoid using global locks.

[Eugenitor]

If you have multiple threads reading from one source of memory and never writing to it, you don't need to worry about data duplication. Each thread gets its own compartment ("what does this dwarf do next") to write to.

With synchronous execution (e.g. no pathfinding between frames), the memory being modified isn't a problem.

[devek]

the memory being modified isn't a problem.

Well... no matter how you do it you're going to need synchronization.

You still need a queue to put in tasks for the worker threads to do, and you need another queue to get the results out of.

[Vulcanius]

This is only indirectly related to the thread but I think the people partaking here might find it interesting. If you frequent Slashdot you might have already seen it.

http://www.economist.com/node/16789226

[devek]

Potentially fun derail, but why use AI when the real thing exists?

We have been combining rat brains and computers for awhile, in the future you'll have real organic brains inside of the computers you use

[nbonaparte]

This is only indirectly related to the thread but I think the people partaking here might find it interesting. If you frequent Slashdot you might have already seen it.

http://www.economist.com/node/16789226

ooh, now I want to make a pathing algorithm based on ant behaviors.

[MaDeR Levap]

I'm not sure you fully understand the concept of refactoring. My point of refactoring in the context of Toady and DF is to improve previously written code which obviously suffers from atrocious scalability issues (e.g. it works fine when you have 1,000 items, but fails horribly with 100,000). The pathfinding algorithm is very likely only a small portion of the problem. You correctly said that the functionality of the game would remain the same, however, the performance could be significantly improved.

We seem to have difference in definitions. What you described (modifying code to get performance gain) I call optimisation. Refactoring for me is tool to make easier to work with code. It is entirely internal, technical issue "under the hood". I sometimes modify code to make it easier to use, more extendable, move part of code to separate class (because, for example, part of problem is sufficiently complex to warrant separate class or other code could get benefits from this) etc. I call it refactoring. It is for me (or fellow programmer), not for end user.

End user usually will notice (sufficiently large) optimisation, but he wil not - should not - ever notice refactoring.

[Vulcanius]

Regardless of the semantics you apply, the point remains the same.

[MaDeR Levap]

Yeah, I love nitpicking.

[Shadowlord]

There's a lot of useful programming tips in this thread. Unfortunately there's also a lot of ego stroking and... er  .... measuring contests.   (Also a lot of posts don't really contribute at all, like this one.) It would be nice if we could condense the thread down to useful information for Toady to read.

There is nothing useful for him to read in this thread. It isn't like he is just learning to program, lol.

I didn't think he was, but even the most experienced programmer can learn new things.

I can see it now: Toady reads the thread, and this happens: "You have gained 0.1 skill in trolling."

[Fuco]

Well, you're making computers more efficient but there is still a wall that will be reached.

Once 100% of the power/energy that goes into a computer is used for computations, you can't go further

The good news is, that computer wouldn't require a heatsink or any cooling...

Actually, you could go further. There's always MOAR POWER

I'll just leave this here http://arxiv.org/pdf/quant-ph/9908043v3 (Ultimate physical limits to computation)


I also find quite amusing how people talking about quantum computers obviously have no idea how that would actually work. It won't allow you to play 100000x100000 embark or quake3 at 1 billion FPS...

[madk]

I'm actually writing a game that I aim to pretty much be DF in a much different setting and with a significantly friendlier UI. So here's my thoughts on what I'll be doing to optimize it.

A game will take place on a procedurally generated planet. A seed is chosen when you start the game. The map will wrap horizontally but not vertically. The portion of map close to the player's settlement and survivors will be simulated completely, and the rest of the world will use the best prediction algorithms I can come up with to generate results on a larger scale. When the player moves into these areas, the terrain will be generated with the procedural generation algorithm then the information gathered by the macrosimulation will be applied. When the player moves out, the larger scale information will continue to be collected and applied if the player comes back. This is if I make large-scale migration possible; I don't know yet. It'd be a huge challenge.

On the smaller scale of things, each 32*32 or so square of tiles, and these regions would likely dynamically conform to the map and player activities, would essentially be its own data structure. When a survivor is looking for an item, it'd first look through the list of items in its current region, then move on to adjacent ones, for several iterations. To spread the workload a bit, a single region would be scanned in each frame. If nothing is found nearby, it'll give up, maybe try to craft the item if possible.

And no multithreading. Oh, and it's going to be fully top-down 2D; I might make it 3D like DF later. I'm unsure; digging is not going to be the game's focus.

[helf]

I may have missed this since I didn't bother to read all 17 pages of replies, but... What family of processor is your "3.2ghz dual core" ? If its netburst then THERES your problem :p My Q9550 I just recently sold kept the FPS meter pegged at 300FPS no matter what (was capped at 300). Granted, I'm not the most involved player, but still.

DF is, sadly, one of those games that if you intend to play heavily, then I'd suggest building a computer around it.

1. Fast CPU with a goodly amount of cache and fast memory access
2. Low latency ram. The lower the memory latency, the better.
3. Maybe have a partition with a stripped down XP install that is just running DF :p

[zarmazarma]

Well, you're making computers more efficient but there is still a wall that will be reached.

Once 100% of the power/energy that goes into a computer is used for computations, you can't go further

The good news is, that computer wouldn't require a heatsink or any cooling...

Actually, you could go further. There's always MOAR POWER

I'll just leave this here http://arxiv.org/pdf/quant-ph/9908043v3 (Ultimate physical limits to computation)


I also find quite amusing how people talking about quantum computers obviously have no idea how that would actually work. It won't allow you to play 100000x100000 embark or quake3 at 1 billion FPS...

Well... 10^51 process per second would satisfy me, thanks. Especially considering modern day processors are impressive a 4ghz.

Anyway, I'm sure there is optimization to be done with the code that will greatly benefit the speed at which dwarf fortress runs. If this is not the case, give it 10 years, we'll probably have moved over to graphene processors by then, and I don't believe dwarf fortress will present much of a challenge for them.

[jei]

... since most of slowdown comes from item count, not dorfs ...

Indeed.
I once made "hax" reaction to create 250 coke out of thin air. And made mistake setting it on repeat for few seconds.
Fortress went from triple digit fps to single digit fps pretty much instantly.

I suspect there may be similar bugs in DF itself as well, as the FPS loss is rather progressive irrespective of what you do and it is nigh impossible to regain any FPS.
Items or the path finding resources they take are not released properly back into the game.

Toady should quit smoking the Adventure-pot and make Fortress mode playable again, or no more bug reports. I'm on strike!