Print

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

[Draco18s]

quote:Originally posted by Derakon:
<STRONG>Each thread would have its own RNG; they don't interfere with each other. And since this solution wouldn't actually touch the worldgen code (it more wraps around it), the process of generating a given world would be identical to what's currently happening. You'd just be making two (or more, depending on how many cores you have) in parallel.</STRONG>

Except that the seed for the second world is the state the RNG is in after the first reject.

[Derakon]

quote:Originally posted by Draco18s:
<STRONG>

Except that the seed for the second world is the state the RNG is in after the first reject.</STRONG>

I guess I wasn't making myself clear. Say you run two worldgen threads A and B in parallel, one starting from the seed 8 and the other from the seed 5. Here's a hypothetical worldgen from this, showing the RNG after each attempt at creating a world in each thread:

code:

Iteration A   B
1         8   5
2        15  99
3         2  64
4         X  18
5         X   1
6         X   X

At the end, you have one world from A, with a starting seed of 8 and three rejections, and another world from B, with a starting seed of 5 and five rejections. If you were to run singlethreaded worldgen with one of those seeds, you'd get the respective world out again.

Make sense now?

[Keldor]

You'd just have to give each thread its own RNG state.

By the way, running two threads in parallel gives you no guarantee whatsoever that they will operate with any sort of synchrony.  You might have one thread go through 6 worlds, while the other mostly sleeps because Windows is doing something in the background, or maybe not.  That's the root of difficulties with multithreaded programing - another thread can come in at any place and at any time and run any number of operations before the other thread completes its next operation.  The solution is to make it so that threads can't possibly interfere with each other simply because they never write into each other's data.  When this is impossible, like if they have to share something, you can put something in the relevant section of code called a critical section that basically says to all other threads "Don't do anything until I finish this bit".

[ April 24, 2008: Message edited by: Keldor ]

[Nadaka]

this would actually slow down world gen on all single processor machines. even if mass generating worlds as the overhead in creating and switching a thread is far higher than it is to loop iteratively.

[irmo]

quote:Originally posted by Nadaka:
<STRONG>this would actually slow down world gen on all single processor machines. even if mass generating worlds as the overhead in creating and switching a thread is far higher than it is to loop iteratively.</STRONG>

You wouldn't do it on single processor machines.

[Idles]

The theory behind threading worldgen seems to be roughly correct in this thread--it may be less beneficial to gameplay than threading pathfinding or something else, but it might be a good simple lesson for Toady; I think he's admitted he doesn't have any experience doing multithreaded programming.  Even with the most complicated solutions, multithreaded worldgen is still a relatively simple system, because they don't require synchronization or much cross-thread communication.

About memory concerns, I'd like to expand on something that was mentioned earlier.  The vast amount of rejects appear long before worldgen gets to the state where it runs histories and begins hogging hundreds of megabytes.  So, you would probably want to make a modification to worldgen, by splitting it in two: phase one is the initial generation of the world, running rivers, making lakes, etc, which seems more processor intensive than memory intensive.  Phase two is the history stuff, which probably won't trigger any rejects.  Once worldgen is divided into phases, you implement multiple worldgen threads. Finally, as soon as a thread successfully completes phase one, it notifies the main thread to stop the other generation threads, so it can begin rapaciously using all of your computer's memory to make funny historical stuff happen.

If Toady wants to get experience multithreading, this is probably where he should start.  I've implemented simple threading in Java (relatively easy) for pathfinding, and  I can imagine it would be a months long challenge in C, what with the complexity of the DF engine.

[numerobis]

If I read the utilities' memory hacking documentation correctly, I am led to believe that there are a number of global variables (including the RNG state).  You'd have to make sure to shunt them all off into thread-local storage.  This would overall be a moderate pain in the butt, and a not-unlikely source of mistefying bugs at first.  It probably is indeed an "easy" project though, since two worldgens don't have to talk to each other at all.

That said, a simpler solution is to run the command-line version of DF with different -gen arguments.  If you're paranoid, just make a couple copies of the DF directory tree first.

[Button]

I believe necroing is the expected/proper behavior in this subforum, yes?

I've been using some parameter sets that have 10k+ rejects before I get a usable world, so this suggestion is relevant to my interests.

It also seems like it would be a great way for Toady to break into multithreading.