Chunk Sparsing or Compression about cuberite HOT 41 CLOSED

This is a very nice article discussing some different approaches to shrinking minecraft worlds in memory.

from cuberite.

That's a nice read, but unless they actually tried that approach in real life, I'm not gonna take their word for it that it works. I'm still more inclined towards slice-based sparsing.

from cuberite.

IDK, just thought it might be helpful 😄

from cuberite.

I think this should get a bit more love :)

This would be a huge advantage over the competition if it was implemented - and might drive more people to MCServer.

from cuberite.

I have re-read the article and still I believe the very first comment is right on the spot - the article over-estimates the iteration, and most of the costs are actually in random access. So I do believe that interval trees won't provide any performance gains, on the contrary, since most of the chunk-block access in MCS is random reads and writes, the performance would suffer, and the memory savings don't justify it.

However, there's still an option out there worth exploring, and that is the one thought up the in the forum: Divide each chunk vertically into 16 sections (same as the network protocol does) and only allocate those sections if they contain any nonzero data. Since most worlds generate at heightmap levels of 60 - 95 blocks, this would mean a 75% to 62% savings in RAM usage with almost minimal performance hit for the random access operations. For regular Nether worlds the RAM savings will be exactly 50 %, again with minimal performance penalty.

I would like to see this implemented so that the details stay mostly inside the cChunk class. However, with the chunk-based callbacks (cChunkDataCallback) currently used throughout the code, it might be a good idea to expose the 16 separate sections in those callbacks.

Also note that there's a server console command chunkstats that prints the statistics on memory used by chunks, this will have to be modified, too, to account for the underlying allocation changes.

from cuberite.

What about the "virtual array" mentioned - hashmaps - it's almost as fast as a flat array and can deliver slightly less memory than just removing empty slices.

from cuberite.

That's what we already do - it means splitting the entire world's data into 16x16 chunks and loading only the needed chunks.
The flat array, which might have confused you, is from the very old Minecraft Classic approach, when the world size was fixed at some 256x128x256 blocks (not sure about the exact sizes) and all the data was present in the memory all the time as one huge array.

from cuberite.

Anyway - the the sparsing option you just proposed is good enough 😃

from cuberite.

A 62% to 75% RAM saving? That needs to be implemented :D

from cuberite.

It means saving up to that much RAM, but it also means slightly lower performance - each GetBlock and SetBlock need to additionally check if the block is in the "loaded" section; SetBlock needs to create a new such section if it doesn't exist yet. It shouldn't be too problematic, though.

from cuberite.

Performance could be up to 4-5% worse. GetBlock at the moment is so small that any addition is significant and it is called so often that it contributes to 2-3% of running time in my profiles.

from cuberite.

You can't really say, because it's an extra condition, and conditions are always unpredictable performance-wise. Especially for architectures that have branch-predictions.

from cuberite.

Then, you could make it configurable. I would reduce performance on my server for chunk compression.

from cuberite.

Configurable means even more conditions - "check if it's enabled, then ..."

from cuberite.

I don't think there's any better way of testing this other than actually implementing it.

from cuberite.

But so far I don't think the performance hit would be any significant.

from cuberite.

Then implement it :D

from cuberite.

Nope, because MCServer performs very well right now.
Can't say the same about ram use, it could be less.

from cuberite.

That's why I said up to - implying that it could be 0%. I just wanted to point out that a tiny change to GetBlock can have a relativity massive effect on overall performance

from cuberite.

However, 5% less chunks per cpu is great if we can have double (or more) the chunks per ram.

from cuberite.

Common tiger! :P

from cuberite.

Could someone examine the chunkysparsing branch and tell me how bad the code is? It currently compresses only blocktypes and uses the 16-section selective allocation approach suggested by xoft.

Unscientific benchmarks report as follows:

Savings/slowdown will probably vary with worlds.

from cuberite.

The sparsing should have saved much more memory. Without looking at the code I'd say there's something wrong :)

from cuberite.

Only blocktypes are compressed as of yet, so not nibbletypes; does that make up for it?

from cuberite.

If you're compressing only some data, then you're doing it wrong. You should have a structure containing the entire data for a 16x16x16 block area; these structures should either be present or NULL (full of air, not allocated)

from cuberite.

New data following recent nibble compression changes.

from cuberite.

That's better, but I think the usage should be even lower really.

from cuberite.

From 95 to 63 is a great memory saving.

from cuberite.

I'm not saying it isn't a great saving, just more would be expected. You
are losing about 2/3 of the data (avg chunk height is about 80 blocks
compared to 256 max) but only removing 1/3 of the ram..

from cuberite.

Okay okay I'm not xoft...

Skylight and blocklight arrays aren't compressed yet.

from cuberite.

For skylight, I'm presuming that most blocks would be 15, not 0, right?

Also, I can't find anything in LightingThread that would set skylight to anything less, because it seems that the whole chunk is populated with 15 without checks for block solidity, and therefore skylight doesn't spread or decrease, even to blocks without a view of the sky.

from cuberite.

I'm telling you, if you're compressing them separately, you're doing it wrong.

Have a look at how the protocol handles sending chunks over, that should inspire you on how you should do it.

from cuberite.

From what I can see, doesn't cProtocol17x::SendChunkData() always serialise with cChunkDataSerialiser::Serialise(cChunkDataSerialiser::RELEASE_1_3_2), which sets the 'ground-up-continuous' flag to 'whole chunk sent' (i.e. not split up into 16 sections and sent selectively)?

Also, isn't putting blocktype, meta, light, and skylight all into one vector bad for code readability?

from cuberite.

The chunk data serializer does that because it doesn't have the sections pre-calculated and calculating them would cost more CPU than sending just everything. IF the serializer received the data already sectionized, it could send them like that.

You won't be putting all of the data into one vector. You should be using something like this:

struct sChunkSectionData
{
  BLOCKTYPE m_BlockTypes[16 * 16 * 16];
  NIBBLETYPE m_BlockMetas[16 * 16 * 8];
  NIBBLETYPE m_BlockSkyLight[16 * 16 * 8];
  NIBBLETYPE m_BlockBlockLight[16 * 16 * 8];
} ;
typedef sChunkSectionData * pChunkSectionData;

class cChunk
{
  ...
  pChunkSectionData Sections[16];  // Either NULL or valid section
} ;

from cuberite.

Changes with blocklight and skylight compression.

from cuberite.

xoft, are you sure using C arrays with section splitting will have significant benefits over using vectors and not allocating until we reach an Index that is nonzero (changed compression algorithm recently)? I hope I don't have to rewrite everything...

from cuberite.

I'm not yet sure about this. My solution is better on the CPU side - no reallocations, minimal heap fragmentation, possibility to write a custom specific allocator. Your solution might allocate the memory more tightly and might be a bit easier to implement at the start. I guess I'll have to finally look at your code :P

Also with my solution it would be possible (although probably won't be done) to further compress Nether chunks - they will have many sections full of air in the middle of the chunk.

from cuberite.

Is this fixed by #863?

from cuberite.

No, #863 is temporary until we can actually get #956 done.

from cuberite.

Isn't this fixed now?

from cuberite.

Yes.

from cuberite.