[MC-12964] Server 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.

Comments 13

Brandon Enright 2013-03-30T00:21:18Z

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?

Alex Campbell 2013-03-30T00:33:29Z

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.

Tails 2013-07-29T15:52:25Z

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.

Alex Campbell 2013-08-01T05:23:50Z

Yes.

Talven81 2013-11-26T22:44:31Z

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.

3 more comments

Alex Campbell 2013-12-08T00:56:11Z

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.

Erik Broes 2013-12-08T13:38:32Z

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 🙂

Brandon Enright 2013-12-08T21:54:41Z

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.

Alex Campbell 2013-12-09T01:38:53Z

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.

Erik Broes 2013-12-09T13:57:29Z

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;
    }

Alex Campbell 2013-12-10T02:43:55Z

You may be modifying the wrong method. Chunk coordinates are hashed in the (MCP names) LongHashMap.getHashedKey and LongHashMap.hash methods. MCP code follows:

private static int getHashedKey(long par0)
{
    return hash((int)(par0 ^ par0 >>> 32)); // <-- this is the part where I noticed the inefficient hashing. Every chunk lookup uses this hash function.
}

private static int hash(int par0)
{
    par0 ^= par0 >>> 20 ^ par0 >>> 12;
    return par0 ^ par0 >>> 7 ^ par0 >>> 4;
}

Don't undo what you did already, but make sure to change it in LongHashMap (above) as well.

Christie N 2013-12-10T19:12:09Z

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-41874

Torabi 2013-12-11T15:16:54Z

@unknown:

I still think it should be Mojang's job to see if bug reports are still valid.

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:

Number of employees checking bug reports cannot possibly scale with the number of users reporting them.
The user is the one person best situated to verify whether or not their own experience has changed.

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.