What's the idea behind a column only sector implementation?

[CPlusPlus]

In Minecraft, the sectors (regions) are 32 x 32 blocks (chunks). But I noticed in Minetest, the sectors are just one column of the x,z sector with enumeration by y whenever you want to update a block or do anything with it. Was there a reason you went with this implementation rather than a large bulk load and unload? This includes the data representation in memory during the game run. I also assume that your save files are by sector, too, which again, are only one column per save.

[Blockhead]

Spoiler

<s>You assume an awful lot, but why assume when it's documented in world_format.txt? Well, it seems like you may have read some of it, but to be sure I thought I had better mention that file.

To rephrase what's said in the docs: Minetest is made out of 16x16x16 blocks (in full: mapblocks), which are cubic, not slices like Minecraft. This stands to reason because the coordinates are in the range [-30912,30912] on ALL axes, including vertical. We use the vertical space to hack in extra 'dimensions' in some games like Mineclone2. Each block is stored in the database according to its packed format coordinates, which gives us the +-30912 coordinate limit.

The other objects than mapblocks are chunks, which is one unit of the world generated at a time, and it is 5x5x5 mapblocks; and each mapblock is filled with nodes; 'blocks' in Minecraft terminology. You'll notice there is no intermediate step between the entire world and the mapblocks, which is regions are inside Minecraft IIRC. Why keep them in separate files at all to be honest? Isn't it better to leave it to the database backend to store your mapblocks efficiently?

Alright to get myself up to speed I skimmed over Minecraft wiki's "Anvil file format" article, which is where I think you get your ideas about sections and 'bulk loads', I assume referring to how Minecraft loads the entire vertical slice of 16x16x16 chunks. Well, the answer seems pretty obvious to me: Minecraft worlds are only 128 blocks tall, whereas in Minetest they are more than 60 thousand. Also, although Minecraft can leave out some y slices, most Minetest worlds will be missing most y slices; or again, there is little correspondence between y slices of say, the Nether and the Overworld, which are inside the same 3D coordinate space in Minetest unlike Minecraft.

Also, how does Minecraft distinguished unexplored and ungenerated areas from explored areas? In Minetest, the size of the mapblock will be quite small if it is just filled with air, because it is zstd (previously zlib) compressed. Or if it is at the edge of explored areas, it will be filled with mostly or entirely CONTENT_IGNORE, except for parts that spill over from a nearby chunk, such as a dungeon room or part of a tree that overhangs the chunk boundary.</s>

Disregard this, I hadn't read the source properly and shouldn't be commenting where I don't know proper knowledge.

[celeron55]

There used to be some metadata attached to each MapSector, but that's long gone now.

The reason the MapSector data structure has been kept is that for each sector it caches the pointer to the last used MapBlock, similarly to how the Map class (which is the voxel part of the world) caches the last used sector. This has turned out to be a really good optimization for the hot path that various map accesses would otherwise cause in the relatively slow coordinate -> pointer type mapping containers. If you remove the sector "middleman" and use 3-dimensional mappings, the whole becomes considerably slower, even if you attempt some simple caching at that level.

Why it isn't it a closer bunch of mapblocks instead of a vertical column? Well, I guess nobody has tried that. If you happen to try it out and it performs better, it could be a good alternative to the current in-memory data structure. The test case for the performance should be map generation, lighting calculations and liquid calculations, as those cause the heaviest use for these data structures. My guess will be that it will be slower because you will get more cache misses, because you effectively reduce the size of the cache for most operations. And if you make the cache larger, the cache becomes more complex than the current one, making it slower, again.

The reason for the efficiency of this cache is: Think of something that iterates through nodes in the X direction, then in the Y direction and then in the Z direction, which is internally optimal for each MapBlock and thus is the way it should be done. But it's not working inside a single MapBlock, rather it crosses the MapBlock boundary in each X, Y and Z. However, it will cross it in X 16 times more often than in Y. With the last-used MapBlock cache in each MapSector, that single cached MapBlock in the MapSector is practically always the one it wants. And it is only a single pointer where only the Y coordinate needs to be compared to the requested coordinate. If you change this caching method *at all*, it becomes less optimal.

It is this exact type of caching that allows many node-based algorithms inside MT (including mods) to be written without awareness of the MapBlock structure while still being quite fast.

Hope this makes sense.

[CPlusPlus]

There used to be some metadata attached to each MapSector, but that's long gone now.

The reason the MapSector data structure has been kept is that for each sector it caches the pointer to the last used MapBlock, similarly to how the Map class (which is the voxel part of the world) caches the last used sector. This has turned out to be a really good optimization for the hot path that various map accesses would otherwise cause in the relatively slow coordinate -> pointer type mapping containers. If you remove the sector "middleman" and use 3-dimensional mappings, the whole becomes considerably slower, even if you attempt some simple caching at that level.

Why it isn't it a closer bunch of mapblocks instead of a vertical column? Well, I guess nobody has tried that. If you happen to try it out and it performs better, it could be a good alternative to the current in-memory data structure. The test case for the performance should be map generation, lighting calculations and liquid calculations, as those cause the heaviest use for these data structures. My guess will be that it will be slower because you will get more cache misses, because you effectively reduce the size of the cache for most operations. And if you make the cache larger, the cache becomes more complex than the current one, making it slower, again.

The reason for the efficiency of this cache is: Think of something that iterates through nodes in the X direction, then in the Y direction and then in the Z direction, which is internally optimal for each MapBlock and thus is the way it should be done. But it's not working inside a single MapBlock, rather it crosses the MapBlock boundary in each X, Y and Z. However, it will cross it in X 16 times more often than in Y. With the last-used MapBlock cache in each MapSector, that single cached MapBlock in the MapSector is practically always the one it wants. And it is only a single pointer where only the Y coordinate needs to be compared to the requested coordinate. If you change this caching method *at all*, it becomes less optimal.

It is this exact type of caching that allows many node-based algorithms inside MT (including mods) to be written without awareness of the MapBlock structure while still being quite fast.

Hope this makes sense.

I see what you mean. That's a good explanation. I also felt that maybe I wasn't clarifying things enough.

I have a question: are chunks saved individually also in that column style in the database or is that only done in heap memory for said calculations of lighting and such? I always thought it was more efficient to save more than one column per save file to decrease IO frequency. At least from what I learned from current academia in programming. And am taking all these considerations for any future forking.

[Blockhead]

If you unhide the spoiler in the above post I gave a quick rundown on the database format as well, while not understanding you were talking about the in-memory format. You can refer to the helpful part of my post there, or just read world_format.txt in the doc directory of the Minetest source.

[CPlusPlus]

If you unhide the spoiler in the above post I gave a quick rundown on the database format as well, while not understanding you were talking about the in-memory format. You can refer to the helpful part of my post there, or just read world_format.txt in the doc directory of the Minetest source.

Yeah I didn't read it since you said it wasn't accurate, but if that's the case now, I'll go over it.

[Blockhead]

Just take it with the caveat that I only knew about the database format of MapBlocks, not about the memory format of MapSectors, which index the MapBlocks.