Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 [2]

Author Topic: The days of multi-threading requests might soon be over...  (Read 4872 times)

Ampersand

  • Bay Watcher
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #15 on: August 25, 2010, 04:15:26 pm »

Multi-threading is not fairy dust that can be sprinkled onto a program to make it run faster. In a program like dwarf fortress, certain processes must be done sequentially. When you multithread programs that require sequential execution, you do not get any benefit at all. There is very little that I can think of in Dwarf Fortress that can be run in parallel to everything else, save for the Weather, as it isn't influenced by outside variables. Even temperature calculations would sequential analysis of the changing map or fortress layout, and the position of the creatures on it.
Logged
!!&!!

Beeskee

  • Bay Watcher
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #16 on: August 25, 2010, 06:19:41 pm »

Nobody thinks it's magic, and everyone knows he can't just rub his junk on the code and have it magically turn multi-threaded and fully optimized... :)
Logged
When a wizard is tired of looking for broken glass in his dinner, he is tired of life.

Jay

  • Bay Watcher
  • ☼Not Dead Yet☼
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #17 on: August 25, 2010, 06:55:43 pm »

Nobody thinks it's magic, and everyone knows he can't just rub his junk on the code and have it magically turn multi-threaded and fully optimized... :)
Of course, considering not only Toady's refuse to consider multi-threading (good decision for DF, bad in overall), but what works, better algorithms would help more.
This guy does.

Multi-threading is not something that can be added later.
Toady began developing DF before multi-core CPUs were even available on the consumer market.
It would require a rewrite of the entire code to have any benefit.
He's not refusing to add it, he's acknowledging that it is impossible.
Logged
Mishimanriz: Histories of Pegasi and Dictionaries

monk12

  • Bay Watcher
  • Sorry, I AM a coyote
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #18 on: August 25, 2010, 11:19:37 pm »

Nobody thinks it's magic, and everyone knows he can't just rub his junk on the code and have it magically turn multi-threaded and fully optimized... :)

Oh, so when people say DF is Toady's baby they don't mean literally...




must.....resist.............Rule 34

nbonaparte

  • Bay Watcher
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #19 on: August 26, 2010, 12:25:42 am »

Nobody thinks it's magic, and everyone knows he can't just rub his junk on the code and have it magically turn multi-threaded and fully optimized... :)

Oh, so when people say DF is Toady's baby they don't mean literally...




must.....resist.............Rule 34
Spoiler (click to show/hide)
Logged
A service to the forum: clowns=demons, cotton candy=adamantine, clown car=adamantine tube, circus=hell, circus tent=demonic fortress.

Footkerchief

  • Bay Watcher
  • The Juffo-Wup is strong in this place.
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #20 on: August 26, 2010, 12:06:22 pm »

As has been stated several times in the past, a faster path-finding algorithm would do far, far more to reduce Dwarf Fortress Lag than a marginal increase in processing speed.

Evidence?

Multi-threading is not something that can be added later.
Toady began developing DF before multi-core CPUs were even available on the consumer market.
It would require a rewrite of the entire code to have any benefit.
He's not refusing to add it, he's acknowledging that it is impossible.

Do you mean it's impossible to implement multithreading for the entire program, or impossible to implement it for small parts of the program?
Logged

MaDeR Levap

  • Bay Watcher
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #21 on: August 26, 2010, 12:30:23 pm »

Multi-threading is not something that can be added later.
Denied. It can be added later. Of course, it make things harder.

It would require a rewrite of the entire code to have any benefit.
Denied. It is possible to rewrite only some parts to code to reap benefits of multithreading.

There is very little that I can think of in Dwarf Fortress that can be run in parallel to everything else, save for the Weather, as it isn't influenced by outside variables. Even temperature calculations would sequential analysis of the changing map or fortress layout, and the position of the creatures on it.
Pathfinding. Main thread of course would wait for all pathfinding threads to end, to ensure consistent map data for each path.
Logged

Setharnas

  • Bay Watcher
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #22 on: August 26, 2010, 02:02:24 pm »

Why is it so important to worry so much about consistent path/map data, or pathfinding requests to return on the same frame as they were issued on? I rather like the thought of seeing my dwarves spending time thinking, i.e. have them flash a blue '?' for a frame or two. And if the path gets invalid between frames, that doesn't strike me as any different than a bridge raised just before Urist tries to cross it. Just have the path request work with a copy of the map segment that stays the same as long as that particular PF thread is searching.

The question that seems much more promising to me is how/if Toady uses any kind of partitioning for map data and (especially) item lists, beyond that connectivity map. For example, in the tile based game I'm developing solely in my head (:P) I'd use sectors of 8x8 tiles for PF, with HPA* (pathfinding algorithm using hierarchical levels of detail) and an index of all item resources in that sector for quick lookups. That should also lend itself to threaded PF. Map (sector) changes would keep a history of as many frames as needed for the PF threads to complete. At the same time, all the weather/temperature/liquid flowing could probably easily done in parallel influence maps, each of them a nicely sized chunk of workload for a thread pool (there are even GPU implementations of influence maps out there). Parallelizing an engine doesn't have to mean a number of permanent threads, you can just as well identify independent steps in your frame sequence and compute those in parallel.

Then again I know Toady has thought about this stuff far longer than I ever have, so his way of dealing with this stuff would really interest me.
Logged
(Appreciatingly stolen from thijser)
I'm not a native English speaker. Feel free to point out grammar/spelling mistakes. This way I can learn better English.

MaDeR Levap

  • Bay Watcher
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #23 on: August 26, 2010, 05:27:03 pm »

Why is it so important to worry so much about consistent path/map data
Sure, lets do not care about it. After playing a while like that, 0.31.01 will seem stable as rock in comparison. Sounds like good idea.

Just have the path request work with a copy of the map segment
You mispelled "whole map".

that stays the same as long as that particular PF thread is searching.
Yeah, lets do it:
1. Because DF take too little memory anyway. A dozen megabytes for each pathfinding entity at the moment is completely insignificant and sounds very efficient.
2. Because there will NOT be any problems with things seeping from one tick to another, no sireee, not problematic at all.
3. We all love esoteric and very hard to catch bugs.

And yes, I am honing my sarcastic skills. Another post, another 30 xp!
Logged

de5me7

  • Bay Watcher
  • urban spaceman
    • View Profile
Re: The days of multi-threading requests might soon be over...
« Reply #24 on: August 26, 2010, 06:10:34 pm »

What needs to be understood before people get carried away is that a program is only as fast as it's slowest calculation. As has been stated several times in the past, a faster path-finding algorithm would do far, far more to reduce Dwarf Fortress Lag than a marginal increase in processing speed. You could have 12-20 fps at 80 dwarfs, upgrade to the latest cpu, and get 12-20 fps at 90 dwarfs.

Even when we've managed to create the perfect, light speed, quantum entanglement driven CPUs, we'll still be getting 12-20 fps at 80 dwarfs because by then Dwarf Fortress will include molecular interaction and keep track of protein folding in every cell in the Dwarven body.

dwarf fortress laughs at mankinds puney attempts to clear the scared 30fps barrier
Logged
I haven't been able to get any vomit this release. Not any I can pick up, at any rate.
Swans, too. Swans are complete bastards.
Pages: 1 [2]