1BRC – Nerd Sniping the Java Community (JavaZone)

Your mission, should you decide to accept it, is the following: aggregate temperature values from a CSV file and group them by weather station name. There’s only one caveat: the file has one 1,000,000,000 rows!

This is the task of the "One Billion Row Challenge" which went viral within the Java community earlier this year. Come and join me for this talk where I’ll dive into some of the tricks employed by the fastest solutions for processing the challenge’s 13 GB input file within less than two seconds. Parallelization and efficient memory access, optimized parsing routines using SIMD and SWAR, as well as custom map implementations are just some of the topics which we are going to discuss.

I will also share some of the personal experiences and learnings which I made while running this challenge for and with the community.

Transcript

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 • No caching • 10K stations, -99.9°C - +99.9°C • Copying allowed
11. #1BRC | @gunnarmorling Evaluation Environment • 32 core AMD EPYC™ 7502P (Zen2), 8 Cores used • 128 GB RAM • File on RAM disk • Five runs, slowest and fastest discarded Image © Joe Haupt https://flic.kr/p/2mG3vWA (CC BY-SA 2.0)
12. #1BRC | @gunnarmorling Baseline ⌛ 04:49.679
13. #1BRC | @gunnarmorling The First Submission Roy Van Rijn 🙌
14. Parallelization Ozzy Delaney https://flic.kr/p/pMsvzE (CC BY-SA 2.0 DEED)
15. #1BRC | @gunnarmorling Parallelization–Chunking the File We Have Cores Many
16. #1BRC | @gunnarmorling Parallelization ⌛ 71 sec.
17. #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.
18. #1BRC | @gunnarmorling Parallelization–Chunking the File
19. #1BRC | @gunnarmorling 1BRC Mythbusters
20. #1BRC | @gunnarmorling 1BRC—A Trivial Task?
21. Parsing jjmusgrove https://flic.kr/p/2mJbA8S (CC BY 2.0 DEED)
22. #1BRC | @gunnarmorling Parsing – Byte by Byte
23. #1BRC | @gunnarmorling Parsing – Byte by Byte ⌛ 20 sec.
24. #1BRC | @gunnarmorling Parsing – SIMD Single Instruction, Multiple Data https://speakerdeck.com/gunnarmorling/to-the-moon-and-beyond-with-java-17-apis
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. #1BRC | @gunnarmorling And Then… Disaster Struck!
29. #1BRC | @gunnarmorling Standing On the Shoulders Of Giants
30. #1BRC | @gunnarmorling The 1BRC Community • TCK • Environment • Evaluation Scripts
31. #1BRC | @gunnarmorling The 1BRC Community TCK, Evaluation Machine Set-Up, Scripting
32. Bookkeeping R. D. Barry https://flic.kr/p/P5RWWR (CC BY-SA 2.0 DEED)
33. #1BRC | @gunnarmorling Custom Maps – Linear Probing
34. #1BRC | @gunnarmorling Custom Maps – Hash Collisions!
35. #1BRC | @gunnarmorling JIT and AOT Compiler
36. #1BRC | @gunnarmorling Further Tricks & Techniques • The “spawn trick” • Unsafe • Super-scalar execution • Perfect value hashing
37. #1BRC | @gunnarmorling It’s 2024… Can We Have Some AI, Pretty Please?
38. The Results Clint Budd https://flic.kr/p/2m6F7hw (CC BY 2.0 DEED)
39. #1BRC | @gunnarmorling Results
40. #1BRC | @gunnarmorling Results – 32 Cores / 64 Threads
41. #1BRC | @gunnarmorling Results – 10K Key Set
42. #1BRC | @gunnarmorling It’s a Long Journey…
43. #1BRC | @gunnarmorling It’s a Long Journey… …Taken By a Community!
44. #1BRC | @gunnarmorling It’s a Long Journey…
45. #1BRC | @gunnarmorling Should You Do Any of This? It Depends
46. #1BRC | @gunnarmorling Getting the Basics Right Gets You Very Far CalculateAverage_MeanderingProgrammer.java
47. #1BRC | @gunnarmorling If You’re Building a Database Or Want To Get This Coffee Mug…
48. #1BRC | @gunnarmorling 1BRC—Distracting Developers Around the World 🤓
49. #1BRC | @gunnarmorling Show & Tell
50. #1BRC | @gunnarmorling Some Stats
51. #1BRC | @gunnarmorling Lessons Learned
52. #1BRC | @gunnarmorling Lessons Learned • Precise rules, covering corner cases • Automate, automate, automate • Build a community • Use dedicated hardware
53. is slow?
54. is slow? rocks!
55. #1BRC | @gunnarmorling What’s Next? ?
56. #1BRC | @gunnarmorling gunnar@decodable.co @gunnarmorling morling.dev 📧 Get In Touch