Skip to main content

性能问题

啊，你终于看到了这里。优化，这个令无数开发者和玩家魂牵梦萦的问题，显然是不可能在这一篇小小的网页中讲完的——我也没有全部的知识。但不论怎么说，我在此尽力而为。

前言：开发与优化​

"Make it work, make it right, make it fast."

—— Kent Beck

如果你有专业学习过软件工程相关内容，那就不需要我多讲。不论你前期想到了之后可以做的多么绝妙的优化点子，也要把精力先集中在你的最初目标上。当然，这也是我自己惨痛的教训。

常见问题​

不要把long封装的BlockPos作为哈希Key​

只要接触Mod开发的时间稍长，你一定会发现BlockPos类有这几个方法：

public static final int PACKED_HORIZONTAL_LENGTH = 1 + Mth.log2(Mth.smallestEncompassingPowerOfTwo(30000000));
public static final int PACKED_Y_LENGTH = 64 - 2 * PACKED_HORIZONTAL_LENGTH;
private static final long PACKED_X_MASK = (1L << PACKED_HORIZONTAL_LENGTH) - 1L;
private static final long PACKED_Y_MASK = (1L << PACKED_Y_LENGTH) - 1L;
private static final long PACKED_Z_MASK = (1L << PACKED_HORIZONTAL_LENGTH) - 1L;

public static long asLong(int x, int y, int z) {
    long i = 0L;
    i |= (x & PACKED_X_MASK) << X_OFFSET;
    i |= (y & PACKED_Y_MASK) << 0;
    return i | (z & PACKED_Z_MASK) << Z_OFFSET;
}

public static int getX(long packedPos) {
    return (int)(packedPos << 64 - X_OFFSET - PACKED_HORIZONTAL_LENGTH >> 64 - PACKED_HORIZONTAL_LENGTH);
}

public static int getY(long packedPos) {
    return (int)(packedPos << 64 - PACKED_Y_LENGTH >> 64 - PACKED_Y_LENGTH);
}

public static int getZ(long packedPos) {
    return (int)(packedPos << 64 - Z_OFFSET - PACKED_HORIZONTAL_LENGTH >> 64 - PACKED_HORIZONTAL_LENGTH);
}

public static BlockPos of(long packedPos) {
    return new BlockPos(getX(packedPos), getY(packedPos), getZ(packedPos));
}

嗯，把一个BlockPos直接封装进64bits的long，看起来优雅又美妙。你当然还会需要存一些东西，比如说用HashMap<BlockPos, Short>来缓存光照；然后你不禁就会想到，要是用这个和BlockPos一一对应的long，既可以减少内存占用，又可以有更快的hashcode和equals，岂不是一举两得？

很可惜并不是这样。用long作为哈希键很容易产生大量哈希冲突，而java的HashMap在处理哈希冲突时——多么经典的面试八股，现在终于有用了——如果冲突元素小于8，则使用链表串在一起；如果有更多，就用红黑树把这些冲突元素装起来。

我们可以做一个简单的试验：

  1. 在X/Z ±1000、Y -64~320的范围内，随机取一个点；
  2. 遍历这个点附近 X/Z ±25，Y ±10的范围内，所有50000个点；
  3. 把各点坐标转换为long封装，对N=65536取余，收集结果。

结果由ChatGPT给出：一共只用到了65536中的320个桶；总冲突49680次；单桶大小约156.25，对于红黑树而言大约需要8次查询。

当然，HashMap对long还有额外的处理流程——重新计算hashcode、再扰动、最后取余。把这一点考虑上，我们重做试验：用到了17000~32000个桶，平均约19000；总冲突约30000次；桶大小为2~4，平均2.53，看起来比简单取模好多了。

如果我们直接用BlockPos作为哈希键，其哈希函数将使用父类Vec3i的hashcode方法：

@Override
public int hashCode() {
    return (this.getY() + this.getZ() * 31) * 31 + this.getX();
}

在这种情况下，平均用到了约31950个桶；总冲突约18050次，桶平均大小为1.565.

如果我们再把hashCode改成(Y + Z * 31) * 71 + X的形式，这种情况下平均用到约38000个桶；总冲突约11000次；平均桶大小为1.313——只比理想情况慢三分之一。

汇总一下：

哈希键和函数使用桶总冲突平均桶大小
long取余32049600156.25
long考虑Java处理19000300002.53
BlockPos#hashCode31950180501.565
BlockPos#hashcode 第二个常数改为7138000110001.313

显然，使用封装long作为哈希键会比使用BlockPos慢60%——这还只是平均情况。从一些开发者的反映来看，实际可能会有数倍的差异。