MC-12964Server performance issue: Chunk coordinates use a bad hash function
Minecraft stores all loaded chunks in a hash table. The hash function used starts by XOR'ing the chunk's X and Z coordinates, so that many nearby chunks will get the same hash. This causes chunk lookups - and block updates, block lookups, tile entity lookups, etc - to take O(sqrt(N)) time instead of O(1), where N is the number of loaded chunks.
For a server with 10 players and a view-distance of 10, there will be 4410 loaded chunks, and chunk lookups will be up to 66 times slower than they should be, or 20 times slower in the best case.
Created Issue:
Performance issue: Chunk coordinates use a bad hash function
Minecraft stores all loaded chunks in a hash table. The hash function used starts by XOR'ing the chunk's X and Z coordinates, so that many nearby chunks will get the same hash. This causes chunk lookups - and block updates, block lookups, tile entity lookups, etc - to take O(sqrt(N)) time instead of O(1), where N is the number of loaded chunks.
For a server with 10 players and a view-distance of 10, there will be 4410 loaded chunks, and chunk lookups will be about 66 times slower than they should be.
Performance issue: Chunk coordinates use a bad hash functionServer performance issue: Chunk coordinates use a bad hash function
Minecraft stores all loaded chunks in a hash table. The hash function used starts by XOR'ing the chunk's X and Z coordinates, so that many nearby chunks will get the same hash. This causes chunk lookups - and block updates, block lookups, tile entity lookups, etc - to take O(sqrt(N)) time instead of O(1), where N is the number of loaded chunks.
For a server with 10 players and a view-distance of 10, there will be 4410 loaded chunks, and chunk lookups will be
about66 times slower than they should be.Minecraft stores all loaded chunks in a hash table. The hash function used starts by XOR'ing the chunk's X and Z coordinates, so that many nearby chunks will get the same hash. This causes chunk lookups - and block updates, block lookups, tile entity lookups, etc - to take O(sqrt(N)) time instead of O(1), where N is the number of loaded chunks.
For a server with 10 players and a view-distance of 10, there will be 4410 loaded chunks, and chunk lookups will be up to 66 times slower than they should be, or 20 times slower in the best case.
![[Mojang] Grum (Erik Broes)](../../../data/assets/gravatar/grum.png){kind=small}
[Mojang] Grum (Erik Broes)Server chunk ticking is extremely slow, especially when loading new chunks. This slow chunk ticking (around 1-3 ticks per second) occurs even with normal exploration. When in singleplayer, this can cause the "ticking" to use an abnormally large amount of CPU.
Seed 1, render distance 8, travel from spawn to x=2000, v1.7.2: 19.94 ticks/sec
Seed 1, render distance 8, travel from spawn to x=2000, v1.7.4: 11.03 ticks/sec
I suspect it is a side-effect of MC-12964 , in part, as well as the recent changes made to the rendering and network code in 1.7.
This is a Minecraft forum thread discussing the same effects: http://www.minecraftforum.net/topic/2218534-graphics-quality-and-performance-in-164-172-and-174/
Related: MC-43395
I think that 42088 is an effect. However, if I am correct and this is caused by MC-12964 , then the chunk ticking is actually too fast, and it is clogging the server, especially with 32-bit java. (but even with 64-bit the ticks per second are cut in half)
Hmm that's pretty bad. What hash is being applied to X ^ Y? Is it just a Java built-in? Are X and Z floats?
An affine transform like AX + Z mod N would probably do a lot better. Have you tested various options?
after X ^ Z the rest of the function is:
private static int hash(int par0)
{
par0 ^= par0 >>> 20 ^ par0 >>> 12;
return par0 ^ par0 >>> 7 ^ par0 >>> 4;
}
X and Z are ints. I haven't tested any alternative options.
Is this still a concern in the current Minecraft version 1.6.2 / Launcher version 1.1.3 ? If so, please update the affected versions in order to best aid Mojang ensuring bugs are still valid in the latest releases/pre-releases.
Yes.
Is this still a concern in the current Minecraft version 1.7.2 / Launcher version 1.3.4 ? If so, please update the affected versions in order to best aid Mojang ensuring bugs are still valid in the latest releases/pre-releases.
I was going to check whether this still affects 1.7.2.
But then I realised - this is Mojang's job, not mine. If Mojang want to improve the quality of Minecraft, they should make some effort to do stuff themselves, instead of asking random community members to do it for free. That might be a good strategy to increase profits, but it's definitely not a good strategy to get bugs fixed.
If I tell you that this bug still affects 1.7.2, nothing will happen. It will not make the bug more likely to get fixed. You'll ask me again in 1.8 and 1.9 and 1.10.
Why should I expend effort to keep a bug report open that's not even likely to be resolved (except, perhaps, as WONTFIX)?
Why should I expend effort to do Mojang's job for them, without being paid or compensated in any way? (According to a very quick and unscientific Google search, the average salary of a software tester is over $75000/year.)
Why is it expected that I do Mojang's job for them?
If Mojang was not a largish for-profit company - if Minecraft was still developed by a single person in his spare time - then there would at least be a viable excuse for asking users to do your work for you.
But according to Wikipedia, Mojang is about 1/10 the size of Valve. That's not tiny. Mojang has 36 people, and not a single one is able to go through and re-verify bug reports?
Would you charge $1 per month a bug report is open? No, because that's utterly stupid. This is the same, just less extreme.
Your math is flawed. Minecraft == Mojang != Minecraft. We have 4 people working on Minecraft. The reason why mods ask if this issue is still valid is because we do changes not based on bug-reports and might not realize there are bugreports for things we inadvertently change.
Do you by any chance have a suggestion for a better hashcode? Other than what most IDEs generate by default (X + 31*Z)
And thanks for reporting, it IS appreciated eventhough we might not always be around to say this
Hi Grum, please ignore how rude Alex was.
These days, most programming languages are using SipHash (Google it) for their hashtables / associate arrays / dictionaries. It's secure against even malicious manipulation.
Since your input to the hash is very small (an int) this is overkill. Instead I'd suggest a simple affine transform on X and Z and then XOR them together. If look up "Linear congruential generator" the Xn = (A* X(n-1) + C) mod M transform works well, especially if you choose A and C so that the transform is a bijective mapping. You can use the "Numerical Recipies" constants of A = 1664525; C = 1013904223; M = 2^32
I'd suggest XORing X and Y before the transform, and then XORing the transformed results:
hash = ((1664525 * (X ^ 0xdeadbeef) + 1013904223) & 0xFFFFFFFF) ^ ((1664525 * (Y ^ 0xbabecafe) + 1013904223) & 0xFFFFFFFF)
You can truncate this hash to however many bits you actually need for your table.
Well, Grum's presence in this thread changes the "unlikely to be fixed" part. I still think it should be Mojang's job to see if bug reports are still valid.
The problem with X^Z is that nearby chunks tend to get the same hash. X^Z is the first stage of the hashing function, so no matter how good the rest of the function is, chunks 0,5 and 1,4 and 2,7 and 3,6 and 4,1 and 5,0 and 6,3 and 7,2 will always get the same hash.
A Python simulation of the existing hash function on a 65x65 chunk area centred on random coordinates showed that this creates an 8192 slot hashmap, with 272 slots used, and an average chain length of 15. If centred around the (0,0) chunk instead, the average chain length is 25.6.
Using Grum's suggestion to replace X^Z, the average chain length was 1.03 for a 65x65 area, 4.08 for a 257x257 area, and 8.14 for a 513x513 area.
Using Brandon's suggestion to replace X^Z, the average chain length was 1.28 for a 65x65 area, 1.31 for a 257x257 area, and 1.32 for a 513x513 area, .
I doubt anyone has a loaded region of 257x257 chunks (or even 65x65), so while Brandon's hash function generates a low, predictable rate of collisions (edit: bucket collisions, not hash collisions), Grum's may be a bit better for typical Minecraft usage. Grum's is also simpler.
After some testing we'll be using the normal LCG one.
private static final int HASH_A = 0x19660d; private static final int HASH_C = 0x3c6ef35f; private static final int HASH_Z_XOR = 0xDEADBEEF; @Override public int hashCode() { final int xTransform = HASH_A * x + HASH_C; final int zTransform = HASH_A * (z ^ HASH_Z_XOR) + HASH_C; return xTransform ^ zTransform; }You may be modifying the wrong method. Chunk coordinates are hashed in the (MCP names) LongHashMap.getHashedKey and LongHashMap.hash methods. MCP code follows:
Don't undo what you did already, but make sure to change it in LongHashMap (above) as well.
This might be an effect, but:
Seed 1, render distance 8, travel from spawn to x=2000, v1.7.2: 19.94 ticks/sec
Seed 1, render distance 8, travel from spawn to x=2000, v1.7.4: 11.03 ticks/sec
The extra chunk ticking seems to have slowed down the server. You can see debug files, etc. at
MC-41874Alex Campbell:
You're a modder yourself, right? Do you check if every bug reported to you about your mods is valid from version to version? Do you really think it's even possible to do so, for all reports?
You're smart enough to identify a bad hash function. You're obviously a reasonably skilled programmer. So why isn't it obvious to you that:
Mojang cannot determine what is happening on a user's computer. Depending on how clear the report is, they may not actually understand what the problem is. So unless you're suggesting they fly out to the user's home and see the problem in person (which would scale particularly poorly as a solution), I don't really understand what you're getting at.
From another angle, when Mojang does check reports, and closes them because they think they've fixed it, someone tends to come along and complain that it isn't fixed, and the report was closed prematurely. As the saying goes, damned if you do, damned if you don't.