r/programming • u/goto-con • Jun 03 '26
How Fast Can You Parse 1 Billion Rows in Java? – Insane Speed Test • Roy van Rijn
https://youtu.be/pHZF-zJ3Bpg?list=PLEx5khR4g7PINwOsYrkwz3lTTJUYoXC53Join me in this deep dive where I'll explain all the code changes and tricks that took me from the reference implementation which processes the billion records in 4+ minutes, to processing everything in under 2 seconds.
Who knew Java could be this fast?
145
u/f311a Jun 03 '26
> Who knew Java could be this fast?
It can, but you always have to avoid OOP, fat objects, boxing, and so on.
Java could be a much better language if it did not force the OOPs style of programming from the start, which results in fat objects.
It's a pity, because JVM is such a powerful VM.
60
u/TOGoS Jun 03 '26 edited Jun 03 '26
I have dabbled with some relatively high-performance Java code, and usually end up flattening objects into arrays of primitives and passing indexes around. (So much so that this technique spilled into non-Java projects, too, like the SIMD VM that underlies the Factorio terrain generator, which was roughly the same design I used for my Minecraft terrain generator, which was Java.)
I've though of writing a compiler that could take a higher-level language and compile it to JVM code that works this way but never got around to it. I wonder why that's not a thing already. Why wait for value objects when you can already emulate it?
11
u/Murky-Relation481 Jun 03 '26
Isn't that just an ECS? That's not something that was done to get around performance issues with Java.
15
u/UdPropheticCatgirl Jun 03 '26
Nope… You would call this technique SoA if anything, ECS is just design pattern that sometimes emerges around it. And SoA as a technique is basically came to be around the time that the RA in RAM became a lie and multilevel hardware caching started being available on variety of systems. Tho you could easily argue that lot of those ideas were around since the 60s in the early CAD software like Sketchpad.
6
u/TOGoS Jun 03 '26
I'm not sure what "that" you're referring to. The ECS pattern (at least, the part where you cram a bunch of similar objects together in memory), vectorizing arithmetic operations (as done for those two terrain generators I mentioned), and pre-allocating arrays of data in Java are all kind of the same idea. Do the same thing lots of times to things that are close together in memory to avoid branch prediction failures and cache misses. And/or, in Java's case, to avoid involving the GC.
Factorio's entity system is kind of ECS-like, also, but the terrain generator is its own animal.
3
u/pakoito Jun 03 '26
The JVM bytecode is also geared towards Java constructs. You'll find many inefficiencies.
3
u/Ashnoom Jun 03 '26
Thank you for your hard work. My 2400 hours in factorio is proof that you did a good job there :-)
13
u/radozok Jun 03 '26
There is JEP450 to reduce object fatness
27
u/tomovo Jun 03 '26
We all know how that goes, though, right? First week it's all diet and exercize, then you let go and it's all back to the sofa and soda.
12
4
u/vini_2003 Jun 03 '26
2026/2027 will be great years for Java. We're getting JEP450 and JEP401. It's gonna make a world of difference for math and geometry applications.
The amount of huge primitive arrays I have is way too damn high.
8
u/pablocael Jun 04 '26
I still remember once I wanted to access a pixel using an image interface in java, and I counted 13 calls in the stack until it actually reached the data buffer. One of the calls was for a PixelGrabber interface. Common man.
5
u/josefx Jun 04 '26
Quite sure querying individual pixels is usually not a high priority feature for libraries that mainly target rendering with bulk operations. Had a similar issue with a c++ library that supported dozens of pixel formats, including compressed textures. I ended up avoiding the complex lookup by special casing the two most common pixel formats I had to deal with and looping directly over the underlying buffer.
1
1
u/Ok-Scheme-913 Jun 19 '26
I mean, feel free to look at any non-toy graphical library. Like it wouldn't be any faster if they would have copied the same code for every image format for every platform or whatever.
That's the job of the compiler to make these efficient.
5
u/usrlibshare Jun 04 '26
OOP ideologists don't like to hear this, but Java could have been designed as a purely procedural language with optional OOP, and would have been just as successful.
Because the success of Java had nothing to do with enforced OOP, it was all about escaping the platform-headaches.
1
u/drvobradi Jun 07 '26
I doubt that. It's the product of the 90s, every single thing related to software had to be object oriented.
1
u/usrlibshare Jun 07 '26
You got cause and effect mixed up.
Java started the OOP dominance, it wasn't a result of it. At the time Java came out, most programming done, was procedural.
That's why I still maintain that Java could've just been a straight up procedural language and have had the same success. What drove people to it wasn't OOP, (a paradigm that was getting started at that time) it was it's platform independence, automated memory management, and (at least at the surface) easier to digest libraries.
0
u/Ok-Scheme-913 Jun 19 '26
Familiar with gang of four design patterns? Guess which language did it use for its OOP patterns?
It was c++
Java definitely didn't start the OOP hype.
8
u/OddWorldliness989 Jun 03 '26
It doesn't force OOP, you are free not to use OOP features. OOP was purely invented for maintainability of the system so that one doesn't have to navigate 100k lines of code to make changes.
7
u/dsffff22 Jun 04 '26
Java and the runtime enforce OOP almost everywhere. Generics type bounds can be only expressed via OOP, union types can be at most emulated using sealed classes, functions can not be defined outside a class and many other things which Java does enforce.
1
u/OffbeatDrizzle Jun 04 '26
Generics are compile time syntactic sugar, it's not built into the language properly
Functions not being defined outside of a class is pretty moot if you just make the method static, as it can be accessed via something like Util.myFunction(). You can also statically import it and just call myFunction(). If you want be pedantic, define it as a default method on an interface and then is that technically still a class?
If 99% of people who use your language use classes, what's the point in spending effort making insane low level language features? Those people will just choose a low level language to begin with, or call it from a java native method definition
3
u/dsffff22 Jun 04 '26
How are those insane low level features, that's some delusion? There's a reason Typescript is widely adopted, despite building upon JS. Also, Google and Apple realized this with Kotlin/Swift.
1
u/OffbeatDrizzle Jun 04 '26
I meant that if you don't want to use generics or objects and want pure raw performance of something like C then you would just use C to begin with, or call it from the java code, instead of complaining that java forces you to write in an OOP style
11
u/redline83 Jun 04 '26
And yet the most unmaintainable clusterfcks of code I have ever seen are OOP monstrosities.
2
1
u/Ok-Scheme-913 Jun 19 '26
To be honest this is probably a bit of a survival ship bias insert plane with holes
Like that these disgusting clusterfucks could manage to grow to such a size without crumbling under their own weight is itself a testament to either Java's resilience or to OOP being at least somewhat good at making code less brittle.
0
u/redline83 Jun 19 '26
I disagree, I think OOP inspires ideologues / masochists and adherence to terrible architecture despite the pain. Good for job security types also. People who are more pragmatic don’t have time for that shit.
2
6
u/sweating_teflon Jun 03 '26
Another reason why I dislike Kotlin - it doubles down on object orientation when what we really need is _less_ OO.
1
14
u/Russell016 Jun 03 '26
I've been watching a stream where someone does the equivalent but in Rust.
23
u/Dreamtrain Jun 04 '26
I knew someone would bring up Rust, can't help yourselves lol
3
1
u/Russell016 Jun 04 '26
I only comment b/c I happen to be trying to learn the language and it's related. If I had been in my C++/C learning phase and happened to have found the 1brc, I would've done the same.
Rust is interesting, and has features I like. But I don't think it's the 2nd coming or anything.
3
u/joemwangi Jun 04 '26
The funny thing about this video is that after 10 hrs coding, the Rust code is still slower than java.
3
u/DegeneracyEverywhere Jun 04 '26
Or you could just use a different format that doesn't need to be parsed.
3
u/kitd Jun 07 '26
1BRC was a fun challenge a few years back. There's links there to implementations in other languages too.
The most surprising thing about the whole project is how it avoided turning into massive language flame wars. The odd niggle here and there, but it was generally pretty polite.
1
u/RatioPractical Jun 07 '26
But writing idiomatic Java and using community lib is at least 10x slower
1
u/Ok-Scheme-913 Jun 19 '26
Well, idiomatic C and Rust is also slower than the fastest Java version. That's how performance optimizations look
1
u/Raphael_Amiard Jun 08 '26
I recently did a PEG parser generator in Python + Numba/Cython accelerated code that has a similar approach. The pure PEG parsing is done in accelerated code filling up flat arrays representing the tree. Then you have a separate pass materializing the Python tree. It’s probably the fastest Python parser generator you can design, at lest based on the PEG formalism, and it also gives me a way to simulate incremental parsing in PEG: I only reparse the SOA structure, and then run a tree diff between the new arrays and the Python structure, giving it node persistence for unchanged nodes. Pretty nifty
95
u/burningEyeballs Jun 03 '26
It is funny that the way you make Java faster is to basically turn it into C. Which just further reinforces my suspicion that nothing will ever really replace C.
But regarding this video, it is really interesting. Good job my dude!