5 ms·
One Billion Row Challenge Shows Java Can Process 1B Rows File in 2 Seconds
- thecleaner 3y agoIs this considered abnormal for Java ? I presume this was without GC pauses
- treffer 3y agoThe whole problem is solvable with a single hashtable or a fixed set of memory. The solution use mmap over the input file. So no need for a GC run or a large heap. The solutions also mostly used graalvm and ahead of time compilation.
- dbacar 3y ago..and all solutions use unsafe
- borissk 3y agoSo it's better to write this sort of code in a language that's unsafe by default (e.g. C), rather than try to abuse Java. Reminds me of the code that Microsoft produced when they were trying to prove their new .NET Core is one of the fastest web runtimes - it was quite fast, but had nothing to do with the way C# code is written out there.
- coldpie 3y ago> So it's better to write this sort of code in a language that's unsafe by default (e.g. C), rather than try to abuse Java. I'm not necessarily disagreeing, but can you elaborate on why it's better? Using unsafe for some parts of the code doesn't throw out safety guarantees about all of the rest of the code.
- anonymoushn 3y agoIn this case it's better because C users have access to vector intrinsics that are much cheaper than the ones Java users have access to.
- pron 3y ago> Using unsafe for some parts of the code doesn't throw out safety guarantees about all of the rest of the code. That's actually hard to prove because you don't know which guarantees the unsafe code can break; being unsafe, it could potentially, say, mutate arbitrary final fields of any object in the program. So while such code doesn't necessarily break invariants, there's no easy way to tell whether and which it does. Once unsafe is used, no guarantee can be fully trusted. But the direction we're going with "integrity by default" (https://openjdk.org/jeps/8305968 https://openjdk.org/jeps/8305968) is that the application will need to acknowledge and approve the use of unsafe code by libraries, and so the author of the application could choose to more closely inspect the unsafe code and try to determine its blast radius.
- freecodyx 3y agoIf we are using mmap and unsafe, then better use c
- papercrane 3y agoAll the sub-2 second ones are. There is an impressive 3.2s solution that uses neither AOT or Unsafe. It's using the in-preview foreign memory and vector operations APIs. Browsing the solutions it looks like that the Unsafe solutions are winning because Unsafe lets them bypass bounds checks. The current fastest safe version: https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
- anonymoushn 3y agoIt's sort of wild that there's no vector load or store that doesn't include bounds checks. Even if you make a MemorySegment from 0 to 2^63-1 (~2^15 times larger than addressable memory on x64!) you'll pay for bounds checks on every load and every store.
- pron 3y agoOnly for random access. The compiler will hoist bounds checks out of more regularly-accessed loops (when the inlining is right). In fact, given that the top safe result was very close to the top unsafe result (especially considering the standard deviation), it looks like you need to write truly exceptional code to feel the cost of the random-access bounds checks. So it doesn't seem wild at all that the default is to give everyone safety at the expense of a performance cost that will only be felt by very few (and who can then enable unsafe code if they feel they need that last extra boost).
- anonymoushn 3y agoBounds checks in a MemorySegment that contains the whole addressable range 2^15 times provide no safety. Obviously. You've posted that users can use unsafe to avoid the bounds checks, but you're posting specifically about methods provided for MemorySegment that have no equivalent for Unsafe, so you're just incorrect. "Only for random access" is probably also incorrect. We could maybe have a look at the codegen for any of the top openjdk submissions which currently perform sequential access but increment the read pointer by ctz(movemask(eq(*ptr, c)))+k at each step. It's trivial for a person to prove that the bounds checks are redundant with the loop termination condition given the MemorySegment's length and given that ctz is at most 64, but it seems unlikely that the runtime manages it. It is of course also trivial for a person who knows that the MemorySegment is so large that it only disallows addresses that differ from allowed addresses by up to two bits not used for addressing to prove that all possible addresses are allowed, or at least that they address memory which is allowed to be accessed by a different address if the user masks off the high two bits first.
- vincnetas 3y ago3.2 seconds for fastest safe solution. So not bat i'd say.
- hocuspocus 3y agoNot all and from what I remember the top ranking hasn't changed that much since everyone started to update their solution with unsafe/mmap, rather showing that the gain is fairly marginal.
- anonymoushn 3y agoI think this instead shows that there are many other popular techniques that achieve much more pessimization than the best-case use of MemorySegment over Unsafe or read over mmap.
- pron 3y agoWhile not directly related to this benchmark, Java doesn't really have meaningful GC pauses anymore (https://openjdk.org/jeps/439 https://openjdk.org/jeps/439). With the new ZGC, the worst-case GC pause is under 1ms (and usually far below that).
- mike_hearn 3y agoYou actually want GC pauses in a challenge like this, because it's a pure batch problem with no latency constraints at all (like a compiler). When that's the case you can use GC algorithms that are optimized for throughput rather than pause times, and things will go faster. It probably won't make much difference on this problem for various reasons, but normally that's the case.
- gunnarmorling 3y agoTurns out you don't need GC for processing that 13 GB file, with relatively small heap sizes even: some folks have disabled GC by means of using EpsilonGC (i.e. a no-op collector). That said, the right collector will give you sub-ms pause times these days (at the cost of lower through-put).
- reaperhulk 3y agoPreviously discussed here: https://news.ycombinator.com/item?id=38851337 https://news.ycombinator.com/item?id=38851337
- aeonik 3y agoLink to the Git Repo for those that want to try the challenge: https://github.com/gunnarmorling/1brc/ https://github.com/gunnarmorling/1brc/
- bradhe 3y agoI haven't read the article, just the headline, and what a strange...challenge...this is. Like, 1bil rows of CSV? JSON objects? Billion XML records? What does "process" mean? Parse and toss? Transform? Who cares of Java can read 1bil "rows"? Why not describe it in terms of MB/s or something more reasonable?
- anonymoushn 3y agoThat's a bit less than 1GB/s/core, mostly parsing, for a fairly constrained format
- Valodim 3y agoThe article lists specific requirements that do make sense.
- bheadmaster 3y ago> I haven't read the article Well, you should've - it's very clearly explained: The text file has a simple structure with one measurement value per row: Hamburg;12.0 Bulawayo;8.9 Palembang;38.8 St. John's;15.2 Cracow;12.6 ... The program should print out the min, mean, and max values per station, alphabetically ordered like so: { Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, Abéché=12.1/29.4/35.6, Accra=14.7/26.4/33.1, Addis Ababa=2.1/16.0/24.3, Adelaide=4.1/17.3/29.7, ... }
- agilob 3y agoThanks for commenting :)
- rakoo 3y agoThe official challenge is in Java, but there are unofficial solutions in the "Show and tell" categories, using other languages, databases, and stuff (even a Fortran solution that takes 3 seconds without going too far in optimization): https://github.com/gunnarmorling/1brc/discussions/categories/show-and-tell https://github.com/gunnarmorling/1brc/discussions/categories... I like this discussion because while the original is about "what can you do in 2024 stock java", I'm more interested in "what can you do if you use naive, obvious solutions". AWK does this in 6 minutes but, as pointed in this comment: https://github.com/gunnarmorling/1brc/discussions/171#discussioncomment-8055461 https://github.com/gunnarmorling/1brc/discussions/171#discus... > It's either 6 minutes with 20 lines of AWK written in five minutes. Or 6 seconds in 300 lines of java written in five days. Classic "XKCD: Is It Worth the Time?".
- 7thaccount 3y ago>"It's either 6 minutes with 20 lines of AWK written in five minutes. Or 6 seconds in 300 lines of java written in five days. Classic "XKCD: Is It Worth the Time?" It's exactly this. Is it going to be run many times or just once or a few times? Is it going to be run in production where it impacts customers or runs up the AWS bill? If it's a throwaway script, the Linux terminal and some Awk is hard to beat. There are always tradeoffs.
- elteto 3y agoFor a one off thing, use awk. For the production pipeline spend the time writing the Java one (or Rust, or C++, or… etc). Or use the awk one in production if you want. Nothing wrong with awk ;)
- pizzafeelsright 3y agowhich one scales is the question for those trying to optimize.
- quadrature 3y ago> It's either 6 minutes with 20 lines of AWK written in five minutes. Or 6 seconds in 300 lines of java written in five days. Classic "XKCD: Is It Worth the Time?". Not quite, it runs in 3 minutes written in java in 5 minutes. The official baseline is quite simple and runs in about ~3min https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java#L65-L90 https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
- mattlondon 3y agoSo go on then - let's hear how fast rust can do it? Based on the trends of "<something something> so we rewrote our entire production stack in rust!" I am surprised there is not already a comment here! I'd also be interested in how fast JavaScript/V8 executes by comparison.
- jabart 3y agoThe .NET community started their own version and included some other languages. I think I saw Rust at 1.4s or so but was disqualified because it was optimized to that dataset (no idea how they determined that). Someone wrote some SIMD code for c# and was like 1s. Shaving some milliseconds between c#, c++, and rust in the final end for 1 billion rows is still impressive.
- anonymoushn 3y agoI think you're talking about a Rust solution that works by reading a small prefix of the input and generating a perfect hash with no handling for misses. So it will be wrong for any input that contains station names that do not occur in that prefix.
- buybackoff 3y agoI maintain cross-language results. There will be a huge update soon, including AWS metal instances running on many combinations of cores/HT-threads. What you mention from Rust is this: https://github.com/RagnarGrootKoerkamp/1brc/ https://github.com/RagnarGrootKoerkamp/1brc/ The author says himself that his solution is not compliant in the readme. So far the top place is not clear. .NET with noahfalk, C/C++ from lehuyduc, dzaima and austindonisan require more tests. The last looks the fastest so far on the default dataset, but has issues. Here is my blog post with details: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-fastest-on-linux-my-optimization-journey/# https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
- za3faran 3y agoDo you have a link to the .NET community work?
- throwawaaarrgh 3y agoI imagine an indexed RDBMS could do this in a fraction of a second? I get that this is more of an academic exercise, but it also kind of explains why you might prefer one solution over another for a given task.
- anonymoushn 3y agoMost RDBMS are not that fast at string parsing.
- WJW 3y agoMaybe it could answer the question for an already indexed data set, but it probably couldn't INSERT 1 billion rows and then answer the question within that time. The ingestion is part of the challenge.
- mnw21cam 3y agoI would like to discourage the use of the word "billion". It means different things to different people. For reference, this title uses it to mean 10^9, but it can also mean 10^12. The official word for 10^9 is milliard, but hardly anyone knows what you mean when you say that, so I'd encourage the phrase "thousand million" - everyone will know what you mean when you say that and it's unambiguous. Or use scientific notation.
- Workaccount2 3y agoGenerally if it is written in English, it's safe to assume it's short scale.
- globular-toast 3y agoIt's off topic, but worth knowing about: https://www.youtube.com/watch?v=C-52AI_ojyQ https://www.youtube.com/watch?v=C-52AI_ojyQ
- tourist2d 3y ago[dead]
- Xeamek 3y agoDunno if either system other can be called the official one, but it (as usual) comes down to Americans creating solutions for non-existing problems :P https://en.wikipedia.org/wiki/Long_and_short_scales https://en.wikipedia.org/wiki/Long_and_short_scales
- Sanzig 3y agoEssentially the entirety of the anglophone world uses short scale numbering. I highly doubt anyone would interpret "billion" as anything other than 10^9 in English text.
- abhinavk 3y agoNobody in a casual English (and Asian too from my experience) conversation will mean billion to be 10^12. English sphere predominantly uses the short scale. That being said, there is no official word but two globally used scales. https://en.wikipedia.org/wiki/Long_and_short_scales#Current_usage https://en.wikipedia.org/wiki/Long_and_short_scales#Current_...
- bheadmaster 3y agoI've tried building the project on my machine, but I got an error that some library used doesn't support Java 21. On the other hand, compiling with a lower version got me an error that only Java 21 is supported. ¯\_(ツ)_/¯
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- NortySpock 3y agoAs a SQL-head, I enjoyed following along with Robin Moffatt's blog on doing the challenge with DuckDB. I got slightly slower numbers than he did (I have different hardware), but definitely in the same order of magnitude. He got 28 seconds to ingest the CSV, then 6 seconds to aggregate and calculate. Maybe 2 hours of coding, tops https://rmoff.net/2024/01/03/1%EF%B8%8F%E2%83%A3%EF%B8%8F-1brc-in-sql-with-duckdb/ https://rmoff.net/2024/01/03/1%EF%B8%8F%E2%83%A3%EF%B8%8F-1b...
- gunnarmorling 3y agoResults actually have improved quite a bit since I've answered the questions for that interview. Fastest contenders now are below two seconds, and that's running on 8 CPU cores of the evaluation machine. When I ran the entries on all 32 cores / 64 threads two weeks ago, the fastest one was at 0.8 sec, and it should be quite a bit faster by now.
- apapapa 3y agoSQL can't do it faster ?
- y42 3y agoProbably, but not including the required previous step: Getting it into the database.