[Proposal] Transition away from LongHashMap to Java ConcurrentHashMap

[sameer]

Currently, KCauldron uses a gnu trove LongHashMap to store loaded chunks.

I have noticed that mods that frequently request getTileEntity() or chunkExists() or other such similar methods reach a bottleneck because of the inherent slowness of this hash map.

I propose transitioning away from a Long-based hashmap towards an integer based Java ConcurrentHashMap.

Yes, I know there is a possibility of collision in hashing. I have taken this into account as this following segment of code shows:

public static int chunk_hash(int x, int y)
{
    return ((x & 0xFFFF) << 16) | (y & 0xFFFF);
}

This hash elegantly fits the chunks into two 16 bit integers. This does introduce a limit: chunks beyond the 16-bit range [–32768,32767] will collide with other chunks in the map. However, most servers implement a world border or other feature to prevent players from ever traversing so far (consider the fact that this is over 500,000 blocks away from (0,0) ). As a preventative measure, chunks beyond these limits could simply not be loaded and players could be forced back from the "edge of the world" (as would be the case for chunks beyond the integer range in the LongHashMap).

I implemented this last night in KCauldron and have had a volume of 27 players today with no noticeable errors (except that I forgot to transition a few code segments away from long towards int).

If @Yive gives me the go-ahead and I receive no objections in the next week, I will start working on it here.

[sameer]

Update: I did not realize @Prototik had started working on prok.pw again. I do not wish to create any confusion between builds and have decided not to do this unless someone thinks it's a good idea. I have seen serious performance gains from using an integer hashmap on my server. I'm thinking of splitting the map up into 16 separate submaps to split the integer range down and boost map chunk-getting performance.
If someone is interested in this idea I will simply fork his repo on gitlab and publicly start working on it.

[Bogdan-G]

@robotia do it, the more people are involved in the development of the more general progress. A third-party libraries and true cause lag, almost all of the libraries that the server uses this sin.
The mod gregtech was some sort of optimization for chunks to coordinate 32k(-32k,+32k), but it's within the mod.

[sameer]

@Bogdan-G Awesome, I'll start work on it. @Yive I'm thinking we need to sync with the official prok.pw repository at some point, somehow.

[sameer]

@Bogdan-G
With the HashMap from Java, there is still some slowdown though. Here's what I was thinking:

Split the 4,294,967,296 possible integer values for the hash code into 256 different "buckets" or bins. Each of the buckets would be stored under an inner class in chunkproviderserver which would wrap them to handle chunk operations. 128 buckets for -2^31 to -1, 128 for 0 to 2^31-1. Some math magic (haven't though about it yet) would be used to select the proper bucket without fail.

Do you think this might be faster than using one global hashmap for all of the chunks in the world?

The bucket size could be configurable to any multiple of 2 by the user (not sure how safe trusting them to know how to use it is though).

[Bogdan-G]

@robotia
Do you think this might be faster than using one global hashmap for all of the chunks in the world?
likely depends on the situation, the answer will most likely be after realization of and tests. In tests out of the game itself, you can check the speed of the method.

[sameer]

@Bogdan-G Alright I'll see if I can get any more performance speedups.

[sameer]

@Bogdan-G put() and get() both end up slower, not sure why. I think it might be the extra math.

Use this for testing if you want to see.
Global = original, Bucket = new array of maps idea
Bucket add: 310.91ms, get: 104.15ms
Global add: 302.43ms, get: 78.95ms

[sameer]

@Bogdan-G Implemented java.util.concurrent.HashMap keeping global hashmap. See here. Compiled jar download here.

I don't know .patch files at all so not sure how to share the diff. :(

[Bogdan-G]

@robotia ok, I'll check in soon. Patches? By analogy, as others have done patches.

[sameer]

@Bogdan-G I do not know how to make .patch file properly.

[Bogdan-G]

@robotia read docs. And if you make a change?

I checked your version, I do not know any better than what stood before, I did not notice the difference. Bugs were not out of sync.

[sameer]

This proposal has been implemented, closing.