(new submission) melgenek: ~top 15 on 10k. Buffered IO, VarHandles, vectors, custom hashtable

[melgenek]

Check List:

• [x] Tests pass (./test.sh <username> shows no differences between expected and actual outputs)
• [x] All formatting changes by the build are committed
• [x] Your launch script is named calculate_average_<username>.sh (make sure to match casing of your GH user name) and is executable
• [x] Output matches that of calculate_average_baseline.sh
• [x] For new entries, or after substantial changes: When implementing custom hash structures, please point to where you deal with hash collisions (line number):

The implementation:

• reads a file with buffered IO
• uses VarHandles to get longs/ints from a byte array
• delimiter search is vectorized
• there is a custom hash function, that provides a low collision rate and short probe distances in hash tables
• has 2 custom open addressing hash tables with quadratic probing: one for strings <=8 bytes in length, and one more for strings of any length

Collision checks:

• hash table for strings <=8 bytes: lines 270-307
• hash table for other strings: lines 380-405

• Execution time on 10k for some of the non-native graal implementations on Mac M2 Max(12 cores):

#	Result (m:s.ms)	Implementation	JDK	Submitter	Notes
	00:02.244	link	21.0.1-graal	Jaromir Hamala	uses Unsafe
	00:03.183	link	21.0.1-graal	Marko Topolnik	uses Unsafe
	00:03.542	link	21.0.2-open	Yevhenii Melnyk	This pr
	00:06.145	link	21.0.1-open	yourwass	uses Unsafe

• Execution time of reference implementation:

> time ./calculate_average_baseline.sh
180.49s user 
4.79s system 
98% cpu 
3:07.96 total

[gunnarmorling]

OOM-s for the 1B file when run on 32 cores:

Terminating due to java.lang.OutOfMemoryError: Java heap space

[melgenek]

OOM-s for the 1B file when run on 32 cores:

@gunnarmorling The GC is Epsilon, and the solution allocates memory per core. So the hardcoded 64MB heap was not enough. I've adjusted the heap to be proportional to the number of cores.

[gunnarmorling]

Gotcha. Looking good now. 00:05.971, nice!