How to Reduce Hash Computation Load

[yososs]

When parsing large source code and using

• org.antlr.v4.runtime.misc.MurmurHash.update ()

is a hotspot.

This is due to frequent container size expansion in Array2DHashSet.java and FlexibleHashMap.java.

During expansion, all hashes of items registered in the container are recomputed.

antlr4/runtime/Java/src/org/antlr/v4/runtime/misc/Array2DHashSet.java

Line 159 in f25a4f6

int b = getBucket(o);

antlr4/runtime/Java/src/org/antlr/v4/runtime/misc/FlexibleHashMap.java

Line 194 in f25a4f6

put(e.key, e.value);

In order to check how often the expansion is occurring, we have rewritten the log to output the following.

Array2DHashSet.java

   protected void expand() {
       T[][] old = buckets;
       currentPrime += 4;
       int newCapacity = buckets.length * 2;
// log
       System.out.println("set expand:"+ buckets.length+"->"+newCapacity);
       T[][] newTable = createBuckets(newCapacity);
       int[] newBucketLengths = new int[newTable.length];

FlexibleHashMap.java

   protected void expand() {
       LinkedList<Entry<K, V>>[] old = buckets;
       currentPrime += 4;
       int newCapacity = buckets.length * 2;

// log
       System.out.println("map expand:"+ buckets.length+"->"+newCapacity);
       LinkedList<Entry<K, V>>[] newTable = createEntryListArray(newCapacity);

It appears that the initial size of 16 is small, even for small input sources.
I think that this can be resolved in one of the following ways

• A. Use an appropriate initial size (depends on input source and syntax?)
• B. Save the hashCode value when the item is registered in the container and use it for expansion.

Java's HashMap and HashSet implement strategy B.

https://github.com/openjdk/jdk/blob/d4474b5816c2ec8daaf1c905b77d8ba4e23c9439/src/java.base/share/classes/java/util/HashMap.java#L282