Multi-threading GeneratorPipeline

[Cyclonit]

Using the dependency system we can define minimum distance that need to be maintained when working on several cubes at once. For example, if cube A is currently being processed in the lighting stage, no cube within a radius of 2 around it must be altered from the outside. Leveraging this information workers could avoid each other without changing everything to be inherently thread-safe.

[Barteks2x]

While it may just work with vanilla, doing this is generally a very bad idea. And there are several reasons:

• Minecraft is inherently not thread safe and changing that is way beyond the scope of this mod. It would also be even more hell for mod compatibility. The goal is to keep as many things as possible as close to vanilla as possible. But if that isn't convincing enough there are several technical reasons
• First there is the OpacityIndex - it's not thread safe. So instead of cube distance, column distance would need to be used
• CubeCache, Which would be a lot of work. And it would be potentially slower. Even even if we use synchronization, there is one more issue: officially java doesn't allow to write/read to/from the same array with multiple threads. For primitive fields there is volatile keyword. There is no such thing for arrays. So AtomicArray would need to be used. Sure, it might just work without it. So let's ignore that for a while
• It would mess up theProfiler - World internally uses a profiler object. Using it from multiple threads at once is a bad idea.
• World.lightUpdateBlockList is used for lighting updates. It's not a local variable.
• All of the other World internal global structures - these would need to be made thread safe. Pending block ticks? Entities? Forge block snapshots? There are a lot of things that can go wrong.
• After profiling it turns out that most of the time is spent getting Chunk/Cube from CubeCache. And this is the part that needs to be synchronized. That's not a good thing.

Cuchaz also wanted to do it. After seing how worldgen and lighting works in minectraft - he agreed that it's not a good idea.

[Cyclonit]

First of all, let me point out that I do understand your reservation and I agree that this is a complicated issue to solve. But, I do think it is possible and I'd like to outline my basic plan of attack, such that we're on the same page.

The core of my plan is to remove cubes that are currently being generate from the CubeCache and to move them into a new WorldGenerator object. Whenever the CubeCache encounters a non-existing cube, it instructs the WorldGenerator to generate it and returns nothing. Inside of the WorldGenerator, workers will process the queue of cubes currently being generated. Any access to live cubes must be read-only. Periodically, the main thread will call a function taking all finished cubes from inside the WorldGenerator and move them into the CubeCache. This decouples the CubeCache from all parallel shenanigans going on inside the world generation code. To allow for the dependency system to work its magic, an additional GeneratorStage "ready" will be introduced. All cubes will remain in this stage until all other cubes which might affect them during their generation have reached this stage too.

Now your list:

1. mod compatibility Mods wishing to take part in world generation must use the dependency system. This will be the case with or without multi-threading. I think I can use this system as the basis for synchronization to a point where normal world generation mods won't be affected at all. All they see is the same as before: They tell the system which cubes they need and the system provides them in the required stage. Mods that do not play a role in world generation would not be affected at all.
2. OpacityIndex I'll need to read up on how it works first. You're right, it will affect any attempt at parallelization, but I don't yet know if parallelizing it is out of the question.
3. CubeCache The WorldGenerator would solve this problem as all multi-threaded access would happen in there.
4. Profiler I'll need to read up on this too. But worst case, the profiler won't receive data from within the worker threads. Does this matter? In my proposal the worker threads do not block the main-thread.
5. World.lightUpdateBlockList Again, something I need to read up on. But in general its the same problem as the one with OpacityIndex. I'll do some investigating tomorrow in how light updates could pass inbetween the WorldGenerator and the main thread.
6. Other global world structures In my proposed system, cubes that are currently being generated would neither receive block ticks nor would they have entities. Most global structures should not affect them by default.
7. Getting cubes from the CubeCache As I tried to explain at the beginning the CubeCache wouldn't do any blocking or other expensive operations.

[Barteks2x]

Your approach would work fine... if only world generation was as simple as it is now. But currently the whole huge section of the code - population - is disabled and mostly unimplemented.

So your idea would be to remove the cube from CubeCache temporarily... I guess FastCubeBlockAccess would be a useful thing there. It would work just fine for terrain stage and features stage. These operate directly on cube. But then we have lighting. And there World#checkLightFor method is used (if you have ran gradlew setupDecompWorkspace you should be able to just shift+click on it to see the code of that method).

First, checkLightFor (as many more methods) uses World#theProfiler object by calling startSection and endSection. And using the same method 2+ times simultaneously is going to mess with it. But this is not major problem as profiler is disabled by default.

There is a much bigger issue - the fact that it needs to access the Column that contains this cube through CubeCache. And there is no way around it other than rewriting checkLightFor. Which is a very complicated, hard to understand, optimized method. This method uses lightUpdateBlockList array as internal queue (to avoid creating the potentially very big array for each light update).

1. Mod compatibility - the goal is that as many mods as possible should work just fine completely unaware that there is a CubicChunks mod. This is why VanillaCubic world type exists - it should be probably called Vanilla on CubicChunks. So let's assume that we don't make VanillaCubic multithreaded and care only about CustomCubic. We may encounter a few problems - mods already have a lot of code to do various things, and the assumption that things are single threaded is very fundamental to how things work. Changing this would make it nearly impossible to make any mod with nontrivial worldgen compatible with CubicChunks.
2. OpacityIndex - it's basically 256 int arrays, one for each block column. And each of those arrays contains what is essentially run-length encoded block opacity array. Just look at test class for it to see how many corner cases there are. In fact, almost every possible case is a corner case. And even after everything I could come up with tested fine, things still didn't work so I came up with test that tries hundreds of thousands of possibilities and compares it against trivial array implementations.

3. I commented on it earlier.

   4, 5, 6, 7 - I explained it earlier. Even during worldgen, it is needed to do some expensive operations that involve getting data from different cubes and columns. There is also worldgen entity spawning. And there are tile entities, which somehow have to be added. There is also PlayerCubeMap. Once a cube is created, PlayerCubeMap knows about it It knows the generation stage and uses this information to determine of cube should be sent to client. And it has method that is called from World on each block set. And when it detects that after some tick a cube has some block changes it sends them to player. Now, again, population causes an issue.

Populator doesn't really populate the cube you think it populates. In fact, it actually populates 3d equivalent of area like this:

+----------------+----------------+----------------+
|                |                |                |
|       X-11     |       X01      |      X11       |
|                |                |                |
|                |        ********|********        |
|                |        ********|********        |
|                |        ********|********        |
+----------------+----------------+----------------+
|                |        ********|********        |
|                |        ********|********        |
|                |        ********|********        |
|      X-10      |       to       |                |
|                |    populate    |       X10      |
|                |       X00      |                |
+----------------+----------------+----------------+
|                |                |                |
|                |                |                |
|      X-1-1     |      X0-1      |      X1-1      |
|                |                |                |
|                |                |                |
|                |                |                |
+----------------+----------------+----------------+

And X01, X11 and X10 only need to have lighting calculated to populate the to populate cube. And after it's populated, it's sent to client. And assuming we directly call Cube methods when populating and somehow solve light issues, client would not receive updates from X00 when populating cubes X-1-1, X0-1 and X-10.

So now you have to implement non-linear generation states to fix it properly, so that X00 is LIVE only when X-1-1 and X0-1 and X-10 are also populated (and since it would be in 3d, there would be 8 instead of 4 cubes, so 256 possibilities. 256 different "stages"). Or you would need to make sure that no cube depends on the cube you want to send to client.

[Barteks2x]

Closing it for now, until I see a solid explanation of how it can be implemented, that wouldn't add way more work when updating the mod to next MC version.