serkan-ozal's 6th submission

gunnarmorling / 1brc

1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java

https://www.morling.dev/blog/one-billion-row-challenge/

Apache License 2.0

6k stars 1.8k forks source link

serkan-ozal's 6th submission #667

Closed serkan-ozal closed 6 months ago

serkan-ozal commented 7 months ago

process multiple lines at a time to get the benefit of ILP (Instruction Level Parallelism) better

Check List:

[x] You have run ./mvnw verify and the project builds successfully
[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
[ ] For new entries, or after substantial changes: When implementing custom hash structures, please point to where you deal with hash collisions (line number):
Execution time: 2.8s (It was 3.0s in the 5th submission in my testing env)
Execution time of reference implementation: 5m 54.1s

gunnarmorling commented 6 months ago

Very cool, the first non-native one under 2 sec!

Benchmark 1: timeout -v 300 ./calculate_average_serkan-ozal.sh 2>&1
  Time (mean ± σ):      1.953 s ±  0.035 s    [User: 0.003 s, System: 0.005 s]
  Range (min … max):    1.916 s …  2.020 s    10 runs

Summary
  serkan-ozal: trimmed mean 1.9487076010000002, raw times 1.9501265130000003,2.01967111,1.9164937450000001,1.9205261070000001,1.9473746550000002,1.9300241900000001,1.921169114,1.9479884370000002,1.9762582010000003,1.9961935910000002

Leaderboard
grep: ./src/main/java*/dev/morling/onebrc/CalculateAverage_serkan-ozal.java: No such file or directory

| # | Result (m:s.ms) | Implementation     | JDK | Submitter     | Notes     |
|---|-----------------|--------------------|-----|---------------|-----------|
|   | 00:01.948 | [link](https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_serkan-ozal.java)| 21.0.1-open | [Serkan ÖZAL](https://github.com/serkan-ozal) |  |

thomaswue commented 6 months ago

Congratulations @serkan-ozal ! This is some really sophisticated vector code.

Given the shell script approach using the native exec app to start the subprocess, it is imho JVM + native combined.

serkan-ozal commented 6 months ago

Thanks @thomaswue. It is indeed! I think still there might be points to improve for making it JIT escape analysis friendly, but this is the best one I have now.

thomaswue commented 6 months ago

Yes. It is a pity that native image does not sufficiently intrinsify the Vector API yet. Otherwise you could just go AOT and no need for CDS or these JIT flag tunings.

serkan-ozal commented 6 months ago

Yep, I wish. You're right. I did ugly things and all other things what ever I can do.