1BRC – Nerd Sniping the Java Community by Gunnar Morling

Gunnar Morling dives into the tricks that the fastest 1BRC solutions used to process the challenge’s 13 GB input file within less than 2 secs -- including parallelization and efficient memory access, optimized parsing routines using SIMD and SWAR, and custom map implementations.

1. A ScyllaDB Community
1BRC – Nerd Sniping
the Java Community
Gunnar Morling
Senior Staff Software Engineer at Decodable

6. #1BRC | @gunnarmorling
The Goals
Learn something
new
Have some fun
along the way
Inspire others to
do the same

7. is slow?!

8. #1BRC | @gunnarmorling
Is It Really a Problem, Though?

10. #1BRC | @gunnarmorling
The Rules
●Java-only; Version of your choice
●No dependencies
●10K stations, -99.9°C - +99.9°C
●Copying allowed
●Five runs, slowest and fastest
discarded

11. #1BRC | @gunnarmorling
Baseline
⌛
04:49.679

12. #1BRC | @gunnarmorling
The First Submission
Roy Van Rijn
??????

13. Parallelization
Ozzy Delaney https://flic.kr/p/pMsvzE (CC BY-SA 2.0 DEED)

14. #1BRC | @gunnarmorling
Parallelization–Chunking the File
We Have
CoresMany

15. #1BRC | @gunnarmorling
Parallelization
⌛ 71 sec.

16. #1BRC | @gunnarmorling
JEP 454
Foreign Function & Memory API
https://openjdk.org/jeps/454
Introduce an API by which Java programs can
interoperate with code and data outside of the Java
runtime. By efficiently invoking foreign functions
(i.e., code outside the JVM), and by safely accessing
foreign memory (i.e., memory not managed by the
JVM), the API enables Java programs to call native
libraries and process native data without the
brittleness and danger of JNI.

17. #1BRC | @gunnarmorling
Parallelization–Chunking the File

18. #1BRC | @gunnarmorling
1BRC Mythbusters

19. #1BRC | @gunnarmorling
1BRC—A Trivial Task?

20. Parsing
jjmusgrove https://flic.kr/p/2mJbA8S (CC BY 2.0 DEED)

21. #1BRC | @gunnarmorling
Parsing – Byte by Byte

22. #1BRC | @gunnarmorling
Parsing – Byte by Byte
⌛ 20 sec.

23. #1BRC | @gunnarmorling
Parsing – SIMD
Single Instruction, Multiple Data
https://speakerdeck.com/gunnarmorling/to-the-moon-and-beyond-with-java-17-apis

24. #1BRC | @gunnarmorling
Parsing – SWAR
SIMD Within a Register

25. #1BRC | @gunnarmorling
Parsing – SWAR
SIMD Within a Register

26. #1BRC | @gunnarmorling
Parsing
Branchless Programming
https://en.wikipedia.org/wiki/Branch_predictor

27. #1BRC | @gunnarmorling
Don’t Try This At Home!
Hacker’s Delight

28. Bookkeeping
R. D. Barry https://flic.kr/p/P5RWWR (CC BY-SA 2.0 DEED)

29. #1BRC | @gunnarmorling
Custom Maps – Linear Probing

30. #1BRC | @gunnarmorling
JIT and AOT Compiler

31. #1BRC | @gunnarmorling
Further Tricks & Techniques
●The “spawn trick”
●Unsafe
●Super-scalar execution
●Perfect value hashing

32. The Results
Clint Budd https://flic.kr/p/2m6F7hw (CC BY 2.0 DEED)

33. #1BRC | @gunnarmorling
Results

34. #1BRC | @gunnarmorling
Results – 32 Cores / 64 Threads

35. #1BRC | @gunnarmorling
The 1BRC Community
●TCK
●Environment
●Evaluation Scripts

36. #1BRC | @gunnarmorling
Should You Do Any of This?
It
Depends

37. #1BRC | @gunnarmorling
Getting the Basics Right Gets You Very Far
CalculateAverage_MeanderingProgrammer.java

38. #1BRC | @gunnarmorling
If You’re Building a Database
Or Want To Get This Coffee Mug…

39. #1BRC | @gunnarmorling
If You’re Building a Database
Or Want to Get Hired Into the GraalVM Team...

40. #1BRC | @gunnarmorling
1BRC—Distracting Developers Around the World ??????

41. #1BRC | @gunnarmorling
Show & Tell

42. is slow?

43. is slow?
rocks!

44. Thank you! Let’s connect.
Gunnar Morling
[email protected]
@gunnarmorling
https://www.morling.dev