45 ms·
The One Billion Row Challenge
- worthless-trash 3y agoInteresting challenge, shame its only java. Can't wait till people start hand rolling their own JVM bytecode.
- kriskrunch 3y agoCheck out the discussion[0], looks like there are submissions in several languages. Go, Rust, Python, and C++, to name a few [0] https://github.com/gunnarmorling/1brc/discussions https://github.com/gunnarmorling/1brc/discussions
- Animats 3y agoIt looks like the problem is dominated by reading in the data file. Some fast solutions just read the whole file into memory.
- fny 3y agoRather than read the file into memory, memory mapping can be used.
- capitol_ 3y agoBut would that really be faster when you need to read every byte of a file? I thought memory mapping solved a different problem.
- pclmulqdq 3y agoYou wouldn't want to do this for a huge file. A very fast solution would use a small number of buffers and io_uring (or equivalent), keeping the page table and cache footprint small.
- rockwotj 3y agoYeah so I had a discussion on Twitter about this, turns out 12GB is small enough to fit into memory, and the author runs submissions by running a solution 5 times in a row, so using direct IO actually hurts because having the kernel cache is a way to enforce the file is in memory for the 4 runs after. I have a direct IO solution with SIMD string search and double parsing, just in C++ (using libraries). It runs in 6 seconds on my 24 core linux box (NVMe). Code: https://github.com/rockwotj/1brc https://github.com/rockwotj/1brc Discussion on Filesystem cache: https://x.com/rockwotj/status/1742168024776430041?s=20 https://x.com/rockwotj/status/1742168024776430041?s=20
- pclmulqdq 3y agoI missed the "5 times in a row." If you do that, yeah, keeping the whole thing in memory is far better.
- lifthrasiir 3y ago> double parsing In case you haven't noticed yet, the input format guarantees exactly one fractional digit, so you can read a single signed integer followed by `.` and one digit instead.
- rockwotj 3y agoYeah I missed this originally, and stuff could be faster with this assumption without a full double parser. The fastest java solution dies some near branchless decoding for these
- fragmede 3y agocould you just add the character values eg 49 for ascii 1, and then subtract off the offset once at the end instead of doing atoi on each line? edit: doh that works for min and max but the average overflows.
- gpvos 3y agoYes. I'm not sure it'll help, but def worth a try.
- eru 3y agoMemory mapping (at least on Linux) isn't actually faster than reading the file manually. Especially if you use appropriately sized buffers. (Of course, the five times in a row might mess with that.)
- Animats 3y agoRight, it's the five times in a row thing that makes an in-memory solution faster. Otherwise, this is a purely sequential one-pass problem, which is how you'd do it in practice. Parallelism with edge effects is pretty common. Weather simulation, finite element analysis, and big-world games all have that issue. The middle of each cell is local, but you have to talk to the neighbor cells a little.
- somat 3y agoIt would be a more interesting challenge if the data file were larger than the memory. I would love to see what people would come up with on some baby vm with 512 mb of ram. Even more interesting would be small ram, little local storage and a large file only available via network, I would like to see something other than http but realistically it would be http.
- throwaway167 3y agoSixteen thousand Excel 97 spreadsheets?
- anonymoushn 3y agoFor this problem, changing the file size to not fit in RAM doesn't really make the optimal solutions more interesting
- pas 3y agoAs the file-memory ratio changes the problem becomes more and more stream processing, right? If the number of cities becomes too much to keep in memory then it becomes a database with "let's see who can find a better index data structure fitting for these I/O patterns and HW" game.
- userbinator 3y agoAlternatively, "must be written in Java" can be interpreted to mean "must use the JVM to begin execution", and you can clearly spawn another process from Java...
- yardstick 3y agoAnother rule was no external dependencies I guess you could from Java itself write a new binary and then run that binary, but it would be against the spirit of the challenge.
- sweetjuly 3y agoThere's sun.misc.Unsafe which is a builtin that gives you raw read/write. Turn that into ROP, mmap your native program, and now you're full native :)
- nneonneo 3y agoJust use JNA to allocate an RWX buffer with mmap, unpack a bit of clever code into the buffer, and forge a native function pointer to call it :)
- LeoPanthera 3y ago[flagged]
- EspadaV9 3y agoDid you try and run it to see how will it performs? Could be an interesting data point on the leaderboard.
- LeoPanthera 3y ago[flagged]
- gerikson 3y agoI ran it, it was slower than the reference implementation and didn't format the output exactly as defined.
- scumola 3y agoThis is just a map/reduce problem. Use Hadoop. It's Java, isn't it?
- deleted 3y ago[deleted]
- kriskrunch 3y ago> No external dependencies may be used
- deleted 3y ago[deleted]
- baq 3y agoWhy would I use Hadoop for such a small number of rows…?
- jalino23 3y ago1 billion is small for hadoop?
- rapsey 3y agoIf it fits on one computer it's not a hadoop problem.
- quickthrower2 3y agoIt fits on a dusty ten year old USB stick
- badgersnake 3y agoSounds like an awk problem tbh.
- 8organicbits 3y agoA Hadoop submission may help people realize that. But since you only have one machine to work with it should be obvious that you're not going to get any speed-up via divide and conquer.
- lifthrasiir 3y ago> Q: Can I make assumptions on the names of the weather stations showing up in the data set? > A: No, while only a fixed set of station names is used by the data set generator, any solution should work with arbitrary UTF-8 station names (for the sake of simplicity, names are guaranteed to contain no `;` character). I'm unsure if it's intentional or not, but this essentially means that the submission should be correct for all inputs, but can and probably should be tuned for the particular input regenerated by `create_measurements.sh`. I can imagine submissions with a perfect hash function tuned for given set of stations, for example.
- Hugsun 3y agoGiven this requirement, they would be wise to have the test data be different from the example data. That would prevent overfitting optimizations.
- josephg 3y agoI'm not sure that it is overfitting to optimize your code for the test set. The requirement is just that you don't break compatibility for arbitrary names in the process. This sort of thing shows up all the time in the real world - where, for example, 90% of traffic will hit one endpoint. Or 90% of a database is one specific table. Discovering and microoptimizing for the common case is an important skill.
- lifthrasiir 3y agoThat's why I was so unsure. I think though, that it is generally better to have the input generator seeded and do not disclose the chosen seed in advance, which prevents overfitting to a single input and yet encourages overfitting to a much bigger class of inputs.
- rocqua 3y agoThat invites probing submissions to figure out a good hash for all names from that one seed. I think having the names for performance tests public is fine. But there should be correctness tests on sets with random names.
- pbh101 3y ago> Each contender will be run five times in a row. The slowest and the fastest runs are discarded. The mean value of the remaining three runs is the result for that contender and will be added to the leaderboard. Shouldn’t he take the single fastest time, assuming file (and JDK) being in file cache is controlled for?
- bayindirh 3y agoThis is done to simulate real-world performance. Your binary is not the only binary in the system and other services may be running as well. So fastest time is the happiest path and slowest is the unluckiest. The range of remaining three is what you expect to get 99% of the time on a real world system.
- cwillu 3y agoAny production where you're routinely scanning a text file with a million records is probably a batch process, and I'd be shocked if the usual performance wasn't much closer to the worst case than the average.
- deleted 3y ago[deleted]
- fragmede 3y ago> Your binary is not the only binary in the system and other services may be running as well. Technically yes, but these days most of my machines are single purpose VMs; database/load balancer/app server/etc, so it still seems weird not to take the fastest.
- bayindirh 3y agoThen, your VM is not the only VM sharing the bare metal. Same thing applies, only on a slightly higher level. As long as you share the metal with other stuff (be it containers, binaries, VMs), there's always competition for resources, and your average time becomes your real world time.
- lessbergstein 3y agoI don't understand, it should be pretty easy. A rolling average with BigDecimal would probably be sufficient but a scientific lib might be better for a rolling average or more than a hundred million numbers. https://stackoverflow.com/questions/277309/java-floating-point-high-precision-library https://stackoverflow.com/questions/277309/java-floating-poi...
- ako 3y agoThe difficulty is creating the fastest implementation. If you look at the results of the submissions so far you’ll see a big difference in duration, between 11 seconds and more than 4 minutes. 11 seconds seems pretty impressive for a 12Gb file. Would be interesting to know what programming language could do it faster. For a database comparison you’d probably want to include loading the data into your database for a fair comparrison.
- lessbergstein 3y agoPerl would do it quite fast and it has the benefit of accessing posix primitives directly.
- gerikson 3y agoA naive perl solution is really really slow compared to even the reference Java implementation. (I know, I've tried)
- lessbergstein 3y agoThat's strange, you should be able to stream the file right into a tiny perl executable at the same speed as the bottlenecking hardware. The kernel will take care of all the logistics. You're probably trying to do too much explicitly. Just use a pipe. Perl should be done before Jit completes.
- deleted 3y ago[deleted]
- brrrrrm 3y agolooking at the sample code I’m quite glad I’ve never really touched Java. What a clunky language
- wiseowise 3y agoOk, I’ll bite - why?
- winrid 3y agoIt looks like they mostly work in JS, so maybe it's the type definitions that look clunky. Java is explicit, yes. This is intentional :)
- brrrrrm 3y agoyea, I guess it's the lack of human-friendly default assumptions mixed with prescriptive design patterns. definitely an anachronistic design intent :(
- winrid 3y agohave you worked with any compiled languages? It's not much different. It can get a lot worse ^_^. Java's one of the best languages to work in IMO.
- promiseofbeans 3y ago
- deleted 3y ago[deleted]
- vessenes 3y agoOoh fun, Advent of Code chaser! A fair comparison between languages should include the make and build times. I haven't used Java / Maven for years, and I'm reminded why, heading into minute 2 of downloads for './mvnw clean verify'.
- kaba0 3y agoJava build times are very fast. You are just measuring your internet speed here. (Also, gradle is faster as a build tool for incremental compilation)
- occams_chainsaw 3y ago...very relative
- pkolaczk 3y agoGradle is faster than what? Than maven? Maybe. But not than Go or Cargo.
- wokwokwok 3y agoItself. > gradle is faster as a build tool for incremental compilation Implicit: > …than it is building from scratch, where it needs to download lots of stuff I mean, yes, saying Java builds are fast does seem a bit “rolls eyes, yes technically by loc when the compiler is actually running” …but, ^_^! let’s not start banging on about how great cargo/rust compile times are… they’re really terrible once procedural macros are used, or sys dependencies invoke some heinous c dependency build like autoconf and lots of crates do… and there’s still a subpar incremental compilation story. So, you know. Eh. Live and let live. Gradle isn’t that bad.
- pkolaczk 3y agoSo maybe I was just unlucky with gradle and lucky with cargo. A project that is a mixture of 20k LoC Scala and 300k LoC Java took 6 minutes to compile, and incremental was still several tens of seconds. Cargo/Rust cold compiles a project of 1M LoC (all dependencies) in about 1:30 on the same hardware and incremental is like 2-4 seconds. As for precedural macros - yes they can be slow to compile but so are Java annotation processors.
- justinl33 3y agobut… can I use pandas?
- tempay 3y agoFrom a pure performance perspective it’d probably be quite slow in comparison to a dedicated implementation for this task. Especially as it wouldn’t fit in memory.
- buybackoff 3y agoIt takes 330 seconds on a machine where the top OpenJDK version takes 5.75 secs and my .NET version takes 4.8 seconds. However it's just several lines of code and I used ChatGPT as a fun use case for how long it would take to have something working. It took around 5 mins. So if one needs to run this code only once Pandas would be a huge win considering development time. Interestingly the RAM usage was much more than 14 GB input file, probably 2-2.5x of that. BTW asking ChatGPT to utilize all cores did not yield anything working in reasonable time.
- justinl33 3y agohahaha... nice! Out of interest, could you share more about your .NET solution? (the specifics but not the code)
- buybackoff 3y ago
- wokwokwok 3y agoI suppose it defeats the spirit of the game to, knowing your worst run is discarded, calculate the results on the first run by whatever slow method you want, save them somewhere useful, and just read the results and print them out on the following runs? Or at the very least, convert the input into a more convenient binary format for the following runs.
- tutfbhuf 3y agoI thought the same, but to ensure fairness, I would suggest that the application should run in a stateless container without internet access, and the infrastructure (Hetzner VM) should be recreated from scratch for each run to eliminate all caches.
- pronoiac 3y agoI've idly been considering how to score this with more languages, with far less memory. I'm thinking, buildpacks on a Raspberry Pi.
- drusepth 3y agoThis would make for a really fun challenge in SQL, too.
- winrid 3y agoMay be of interest: https://benchmark.clickhouse.com https://benchmark.clickhouse.com
- asah 3y ago1:05 in PostgreSQL 16 but it was harder than I thought to saturate the CPUs and not be disk-bound. Also, I ran on GCP not Hetzner, so maybe different hardware. SQL in theory makes this trivial, handles many of the big optimizations and looking at the repo, cuts 1000+ LOC down to a handful. Modern SQL engines handle everything for you, which is the whole damned point of SQL. Any decent engine will handle parallelism, caching, I/O, etc. Some exotic engines can leverage GPU but for N=1 billion, I doubt GPU will be faster. Here's the basic query: SELECT city, MIN(temp), AVG(temp), MAX(temp) FROM temps GROUP BY 1 ORDER BY 1; In practice, generic SQL engines like PostgreSQL bloat the storage which is a Big Problem for queries like this - in my test, even with INT2 normalization (see below), pgsql took 37 bytes per record which is insane (23+ bytes of overhead to support transactions: https://www.postgresql.org/docs/current/storage-page-layout.html https://www.postgresql.org/docs/current/storage-page-layout....). The big trick is to use PostgreSQL arrays to store the data by city, which removes this overhead and reduces the table size from 34GB (doesn't fit in memory) to 2GB (which does). The first optimization is to observe that the cardinality of cities is small and can be normalized into integers (INTEGER aka INT4), and that the temps can as well (1 decimal of precision). Using SMALLINT (aka INT2) is probably not faster on modern CPUs but should use less RAM, which is better for both caching on smaller systems and cache hitrate on all systems. NUMERIC generally isn't faster or tighter on most engines. To see the query plan, use EXPLAIN: postgres=# explain SELECT city, MIN(temp), AVG(temp), MAX(temp) FROM temps_int2 GROUP BY 1 ORDER BY 1 limit 5; QUERY PLAN --------------------------------------------------------------------------------------------------------------- Limit (cost=13828444.05..13828445.37 rows=5 width=38) -> Finalize GroupAggregate (cost=13828444.05..13828497.22 rows=200 width=38) Group Key: city -> Gather Merge (cost=13828444.05..13828490.72 rows=400 width=38) Workers Planned: 2 -> Sort (cost=13827444.02..13827444.52 rows=200 width=38) Sort Key: city -> Partial HashAggregate (cost=13827434.38..13827436.38 rows=200 width=38) Group Key: city -> Parallel Seq Scan on temps_int2 (cost=0.00..9126106.69 rows=470132769 width=4) JIT: Functions: 8 Options: Inlining true, Optimization true, Expressions true, Deforming true (13 rows) Sigh, pg16 is still pretty conservative about parallelism, so let's crank it up. SET max_parallel_workers=16; set max_parallel_workers_per_gather=16; SET min_parallel_table_scan_size=0; set min_parallel_index_scan_size=0; SET parallel_setup_cost = 0; -- Reduce the cost threshold for parallel execution SET parallel_tuple_cost = 0.001; -- Lower the cost per tuple for parallel execution postgres=# explain SELECT city, MIN(temp), AVG(temp), MAX(temp) FROM temps_int2 GROUP BY 1 ORDER BY 1 limit 5; ... Workers Planned: 14 ... top(1) is showing that we're burying the CPU: top - 10:09:48 up 22 min, 3 users, load average: 5.36, 1.87, 0.95 Tasks: 169 total, 1 running, 168 sleeping, 0 stopped, 0 zombie %Cpu(s): 12.6 us, 4.8 sy, 0.0 ni, 7.8 id, 74.2 wa, 0.0 hi, 0.7 si, 0.0 st MiB Mem : 32084.9 total, 258.7 free, 576.7 used, 31249.5 buff/cache MiB Swap: 0.0 total, 0.0 free, 0.0 used. 30902.4 avail Mem PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 1062 postgres 20 0 357200 227952 197700 D 17.9 0.7 9:35.88 postgres: 16/main: postgres postgres [local] SELECT 1516 postgres 20 0 355384 91232 62384 D 17.6 0.3 0:08.79 postgres: 16/main: parallel worker for PID 1062 1522 postgres 20 0 355384 93336 64544 D 17.6 0.3 0:08.53 postgres: 16/main: parallel worker for PID 1062 1518 postgres 20 0 355384 90148 61300 D 17.3 0.3 0:08.53 postgres: 16/main: parallel worker for PID 1062 1521 postgres 20 0 355384 92624 63776 D 17.3 0.3 0:08.54 postgres: 16/main: parallel worker for PID 1062 1519 postgres 20 0 355384 90440 61592 D 16.6 0.3 0:08.58 postgres: 16/main: parallel worker for PID 1062 1520 postgres 20 0 355384 92732 63884 D 16.6 0.3 0:08.49 postgres: 16/main: parallel worker for PID 1062 1517 postgres 20 0 355384 91544 62696 D 16.3 0.3 0:08.55 postgres: 16/main: parallel worker for PID 1062 interestingly, when we match workers to CPU cores, we don't %CPU drops to 14% i.e. we don't leverage the hardware. OK enough pre-optimization, here's the baseline: postgres=# SELECT city, MIN(temp), AVG(temp), MAX(temp) FROM temps_int2 GROUP BY 1 ORDER BY 1 limit 5; city | min | avg | max ------+-----+----------------------+------ 0 | 0 | 276.0853550961625011 | 1099 1 | 0 | 275.3679265859715333 | 1098 2 | 0 | 274.6485567539599619 | 1098 3 | 0 | 274.9825584419741823 | 1099 4 | 0 | 275.0633718875598229 | 1097 (5 rows) Time: 140642.641 ms (02:20.643) I also tried to leverage a B-tree covering index (CREATE INDEX temps_by_city ON temps_int2 (city) INCLUDE (temp) ) but it wasn't faster - I killed the job after 4 minutes. Yes, I checked that it pg16 used a parallel index-only scan (SET random_page_cost =0.0001; set min_parallel_index_scan_size=0; set enable_seqscan = false; SET enable_parallel_index_scan = ON;) - top(1) shows ~1.7% CPU, suggesting that we were I/O bound. Instead, to amortize the tuple overhead, we can store the data as arrays: CREATE TABLE temps_by_city AS SELECT city, array_agg(temp) from temps_int2 group by city; $ ./table_sizes.sh ...total... | 36 GB temps_int2 | 34 GB temps_by_city | 1980 MB Yay, it now fits in RAM. -- https://stackoverflow.com/a/18964261/430938 adding IMMUTABLE PARALLEL SAFE CREATE OR REPLACE FUNCTION array_min(_data ANYARRAY) RETURNS NUMERIC AS $$ SELECT min(a) FROM UNNEST(_data) AS a $$ LANGUAGE SQL IMMUTABLE PARALLEL SAFE; SET max_parallel_workers=16; set max_parallel_workers_per_gather=16; SET min_parallel_table_scan_size=0; set min_parallel_index_scan_size=0; SET parallel_setup_cost = 0; -- Reduce the cost threshold for parallel execution SET parallel_tuple_cost = 0.001; -- Lower the cost per tuple for parallel execution postgres=# create table tmp1 as select city, min(array_min(array_agg)), avg(array_avg(array_agg)), max(array_max(array_agg)) from temps_by_city group by 1 order by 1 ; SELECT 1001 Time: 132616.944 ms (02:12.617) postgres=# explain select city, min(array_min(array_agg)), avg(array_avg(array_agg)), max(array_max(array_agg)) from temps_by_city group by 1 order by 1 ; QUERY PLAN ------------------------------------------------------------------------------------------------- Sort (cost=338.31..338.81 rows=200 width=98) Sort Key: city -> Finalize HashAggregate (cost=330.14..330.66 rows=200 width=98) Group Key: city -> Gather (cost=321.52..322.64 rows=600 width=98) Workers Planned: 3 -> Partial HashAggregate (cost=321.52..322.04 rows=200 width=98) Group Key: city -> Parallel Seq Scan on temps_by_city (cost=0.00..0.04 rows=423 width=34) (9 rows) Ah, only using 3 cores of the 8... --- CREATE TABLE temps_by_city3 AS SELECT city, temp % 1000, array_agg(temp) from temps_int2 group by 1,2; postgres=# explain select city, min(array_min(array_agg)), avg(array_avg(array_agg)), max(array_max(array_agg)) from temps_by_city3 group by 1 order by 1 ; QUERY PLAN --------------------------------------------------------------------------------------------------------- Finalize GroupAggregate (cost=854300.99..854378.73 rows=200 width=98) Group Key: city -> Gather Merge (cost=854300.99..854348.73 rows=2200 width=98) Workers Planned: 11 -> Sort (cost=854300.77..854301.27 rows=200 width=98) Sort Key: city -> Partial HashAggregate (cost=854290.63..854293.13 rows=200 width=98) Group Key: city -> Parallel Seq Scan on temps_by_city3 (cost=0.00..98836.19 rows=994019 width=34) JIT: Functions: 7 Options: Inlining true, Optimization true, Expressions true, Deforming true (12 rows) This 100% saturates the CPU and runs in ~65 secs (about 2x faster). --- Creating the data Here's a very fast lousy first pass for PostgreSQL that works on most versions - for pg16, there's random_normal(). I'm not on Hetzner so I used GCP (c2d-standard-8 with 16vCPU, 64GB, and 150GB disk, ubuntu 22.04 and CREATE TABLE temps_int2 (city int2, temp int2); -- random()*random() is a cheap distribution. 1100 = 110 * 10 to provide one decimal of precision. INSERT INTO temps_int2 (city, temp) SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp from generate_series(1,1e9)i;
- e63f67dd-065b 3y agoThe rule lawyer in me wants to spend the first run spinning up a background daemon that loads everything into memory, pins it there, and maybe even prefetches everything into cache as the subsequent runs perform basically a linear scan (you never have to pagemiss if you have an oracle!). > write a Java program for retrieving temperature measurement values from a text file and calculating the min, mean, and max temperature per weather station Depending on how far you want to stretch it, doesn’t precomputing the result on 1st run count too? Or pre-parsing the numbers into a compact format you can just slurp directly into rolling sums for subsequent runs. Not the slightest in the spirit of the competition, but not against the rules as far as I can tell. Edit: if we don't like pre-computation, we can still play with fancy out-of-the-box tricks like pre-sorting the input, pre-parsing, compacting, aligning everything, etc. Edit 2: while we're here, why not just patch the calculate_time script to return 0 seconds :) And return 9999 for competitors, for good measure
- yellow_lead 3y agoI think that would violate this rule > The computation must happen at application runtime, i.e. you cannot process the measurements file at build time (for instance, when using GraalVM) and just bake the result into the binary
- e63f67dd-065b 3y agoAh I didn't actually follow the link to the github repo. I don't think that percludes pre-processing the input into something that needs no parsing, however, or to spawn a background daemon that prefetches everything in the right order. The first run is indeed runtime, not build time, so technically I think I still count with pre-computation, sending that to the daemon (or just stashing it somewhere in /tmp, or even crazier patching the jarfile), and just printing it back out on the second run onwards.
- robertlagrant 3y ago> I don't think that percludes pre-processing the input into something that needs no parsing Why not preprocess it into a file that contains the answer? (-: My read of the description was just: you're meant to read the file as part of the run.
- sixlelyt321 3y agoYou had 32GB more than expected 16GB RAM but for Java I doubt that 32GB is fine enough. Java is aboslutely good on older days but nowadays there is lot of opportunities than that poor guy.
- EdwardDiego 3y agoMeaningless to talk about how much RAM you need for a JVM program as it will (obviously) depend on what the program is doing.
- countrymile 3y agoComparing solutions from the Rstats world: https://twitter.com/RandVegan/status/1742721195781267650 https://twitter.com/RandVegan/status/1742721195781267650
- deleted 3y ago[deleted]
- JohnKemeny 3y ago> The slowest and the fastest runs are discarded. The mean value of the remaining three runs is the result for that contender and will be added to the leaderboard. I think it's better to discard the two slowest, or simply accept the fastest as the correct. There's (in my opinion) no good reason to discard the best runs.
- mayank 3y agoThis is a pretty standard measure called the Trimmed Mean: https://statisticsbyjim.com/basics/trimmed-mean/ https://statisticsbyjim.com/basics/trimmed-mean/
- stabbles 3y agoFor performance benchmarking the minimal runtime is typically the best estimator if the computations are identical, cause it measures perf w/o interrupts. If the language is garbage collected, or if the test is randomized you obviously don't want to look at the minimum.
- mayank 3y ago> the minimal runtime is typically the best estimator Depends what you’re estimating. The minimum is usually not representative of “real world” performance, which is why we use measures of central tendency over many runs for performance benchmarks.
- ProblemFactory 3y agoVariability in software runtime arises mostly from other software running on the same system. If you are looking for a real-world, whole-system benchmark (like a database or app server), then taking the average makes sense. If you are benchmarking an individual algorithm or program and its optimisations, then taking the fastest run makes sense - that was the run with least external interference. The only exception might be if you want to benchmark with cold caches, but then you need to reset these carefully between runs as well.
- 3y ago
- planb 3y agoAs far as I see the currently best performing solution [0] does not account for hash collisions and therefore probably generates wrong results if enough different cities are in the dataset. Or am I missing something? [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_ebarlas.java https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
- gunnarmorling 3y agoYes, you are right. This came up yesterday and indeed two solutions were violating the "must work for all station names" rule by relying on specific hash functions optimized for the specific data set, which I unfortunately missed during evaluation. I've just removed these entries from the leaderboard for the time being. Both authors are reworking their submissions and then they'll be added back. [0] https://twitter.com/mtopolnik/status/1742652716919251052 https://twitter.com/mtopolnik/status/1742652716919251052
- thomaswue 3y agoWhat are the constraints on station names - i.e. min length, max length, maximum number of different names?
- gunnarmorling 3y agoJust clarified this in the README: * Input value ranges are as follows: - Station name: non null UTF-8 string of min length 1 character and max length 100 characters - Temperature value: non null double between -99.9 (inclusive) and 99.9 (inclusive), always with one fractional digit * Implementations must not rely on specifics of a given data set, e.g. any valid station name as per the constraints above and any data distribution (number of measurements per station) must be supported
- ykonstant 3y agoThe README says max length 100 bytes, which I suppose we can (?) assume are octets. Also, it mentions that you can assume the station string does not contain the separator ';'. I guess the station string is also supposed to be free of control characters like newlines, though spaces are allowed. This, however, is not stated.
- deleted 3y ago[deleted]
- mgoetzke 3y agoAnyone up to also do this in Rust ?
- gunnarmorling 3y agoSee the "Show & Tell", where folks are discussing solutions in different languages, including Rust: https://github.com/gunnarmorling/1brc/discussions/categories/show-and-tell https://github.com/gunnarmorling/1brc/discussions/categories....
- spullara 3y agoThis has been super fun. My current PR[1] is another 15% faster than my entry in the README. Sadly I haven't been able to make any progress on using SIMD to accelerate any part of it. I think the issues with hashing could be easily covered by having the 500 city names in the test data also be randomly generated at test time. There is no way to ensure there aren't hash collisions without doing a complete comparison between the names. [1] https://github.com/gunnarmorling/1brc/pull/56 https://github.com/gunnarmorling/1brc/pull/56
- londons_explore 3y ago1 billion rows, 500 unique values... It becomes very possible to find an instance of each unique value, then runtime-design a hash algorithm where those 500 values don't collide. Java allows self modifying code after all (and this challenge also allows native code, which can also be compiled-at-runtime)
- spullara 3y agoYou have to compare the keys in order to figure out if you have a hash collision or a new key. Without first scanning the entire file to know what the list of keys are there isn't a way around it. Even determining that list of keys involves doing key comparisons for every row.
- hknmtt 3y agofirst search result for averaging streaming data: https://nestedsoftware.com/2018/03/20/calculating-a-moving-average-on-streaming-data-5a7k.22879.html https://nestedsoftware.com/2018/03/20/calculating-a-moving-a... so you just walk the file and read a chunk, update the averages and move on. the resource usage should be 0.000 nothing and speed should be limited by your disk IO.
- cm2187 3y agoLooking at some solutions they seem to include their own double parsing implementation. I built a home made serializer for csv files, I am using the default .net parsing functions and I find that parsing numbers/dates is by far the slowest part of the process on large files.
- winrid 3y agoYes, just read a file in chunks and spread the math across cores. How many ways could you possibly implement that?? :)
- cm2187 3y agoCustom number parsing, minimising the number of memory allocations to not be punished by the garbage collector. All sort of micro optimisations that make those solutions a terrible way to showcase a language (i.e. you can write much clearer and concise code but obviously slower).
- winrid 3y agoI agree that the simplest solution in each language is the best way to compare - however this problem seems less about showing off java and more about challenging folks.
- hknmtt 3y agoactually i think you can also just average each chunk and then add it to existing data. like read N rows(say all have one location to keep it simple), average the data from the chunk, update/save min and max, move on to next chunk, do the same but now update the average by adding to existing/previously computed average and divide by two. the result will be the same - disk IO will be the most limiting aspect. this "challenge" is not really a challenge. there is nothing complicated about it. it just seems "cool" when you say "process 1 billion rows the fastest you can".
- jimmyed 3y agoI think the optimal strategy would be to use the "reduce" step in mapreduce. Have threads that read portions of the file and add data to a "list", 1 for each unique name. Then, this set of threads can "process" these lists. I don't think we need to sort, that'd be too expensive, just a linear pass would be good. I can't see how we can do SIMD since we want max/min which mandate a linear pass anyway.
- qsort 3y agoAgreed, the aggregations chosen here are embarrassingly parallel, you just keep the count to aggregate means. Would have been more interesting with something like median/k-th percentile, or some other aggregation not as easy.
- dist-epoch 3y agoNot sure if this what you meant, but there are SIMD min/max instructions. https://www.felixcloutier.com/x86/phminposuw https://www.felixcloutier.com/x86/phminposuw
- gigatexal 3y agoSingle line solve using clickhouse-local or duckdb.
- lars_francke 3y ago> No external dependencies may be used
- gigatexal 3y agothe whole premise is silly though. why would anyone use plain java to compute this when databases were built for this or at least are the most finely tuned for it
- gunnarmorling 3y agoIt's only silly if you miss the point of the challenge :) Which is to learn something new and have fun along the way.
- gigatexal 3y agoBut is it realistic at all? Also will I get pilloried if I just make it a big StreamOf thing? ;-)
- tatersolid 3y agoThe Java runtime is an external dependency, isn’t it?
- uwemaurer 3y agocorrect. like this: time duckdb -list -c "select map_from_entries(list((name,x))) as result from (select name, printf('%.1f/%.1f/%.1f',min(value), mean(value),max(value)) as x from read_csv('measurements.txt', delim=';', columns={'name': 'varchar', 'value':'float'}) group by name order by name)" takes about 20 seconds
- kebsup 3y agoAt the Czech technical university C course, we've had a very similar assignment. The submissions of all the course students were continuously evaluated on a leaderboard and many spent tens of hours optimizing to get the extra points for better grade (but mostly status points).
- solarized 3y agoJust for fun. Speed testing awk vs Java. awk -F';' '{ station = $1 temperature = $2 sum[station] += temperature count[station]++ if (temperature < min[station] || count[station] == 1) { min[station] = temperature } if (temperature > max[station] || count[station] == 1) { max[station] = temperature } } END { for (s in sum) { mean = sum[s] / count[s] printf "{%s=%.1f/%.1f/%.1f", s, min[s], mean, max[s] printf (s == PROCINFO["sorted_in"][length(PROCINFO["sorted_in"])] ? "}\n" : ", ") } }' measurement.txt
- arkh 3y agoI'd like to see it speed tested against an instance of Postgres using the file Foreign Data Wrapper https://www.postgresql.org/docs/current/file-fdw.html https://www.postgresql.org/docs/current/file-fdw.html CREATE EXTENSION file_fdw; CREATE SERVER stations FOREIGN DATA WRAPPER file_fdw; CREATE FOREIGN TABLE records ( station_name text, temperature float ) SERVER stations OPTIONS (filename 'path/to/file.csv', format 'csv', delimiter ';'); SELECT station_name, MIN(temperature) AS temp_min, AVG(temperature) AS temp_mean, MAX(temperature) AS temp_max FROM records GROUP BY station_name ORDER BY station_name;
- nathancahill 3y agoMan, Postgres is so cool and powerful.
- aargh_aargh 3y agoUsing FDWs on a daily basis I fully realize their power and appeal but at this exclamation I paused and thought - is this really how we think today? That reading a CSV file directly is a cool feature, state of the art? Sure, FDWs are much more than that, but I would assume we could achieve much more with Machine Learning, and not even just the current wave of LLMs. Why not have the machine consider the data it is currently seeing (type, even actual values), think about what end-to-end operation is required, how often it needs to be repeated, make a time estimate (then verify the estimate, change it for the next run if needed, keep a history for future needs), choose one of methods it has at its disposal (index autogeneration, conversion of raw data, denormalization, efficient allocation of memory hierarchy, ...). Yeah, I'm not focusing on this specific one billion rows challenge but rather what computers today should be able to do for us.
- mgaunard 3y agoIsn't this simply bound by the speed of the disk? Surely none of the suggested optimizations (SIMD, multi-threading) are relevant. It would also depend of how many different stations there are and what they are for the hash lookup, but seriously I doubt this will be anything measurable compared to I/O.
- deleted 3y ago[deleted]
- rockwotj 3y agoA few things: Disk access can certainly be parallelized, and NVMe is blazing fast, so the bottleneck is more the CPU than disk. There are systems that are built around around modern hardware that realize this (redpanda.com, where I work is one such example) Parsing is a lot of the compute time and some SIMD tricks like SWAR for finding delimiters can be helpful. Stringzilla is a cool library if you want to see a clean implementation of these algorithms: https://github.com/ashvardanian/StringZilla https://github.com/ashvardanian/StringZilla See my reply here about the file being cached completely in memory after the first run: https://news.ycombinator.com/item?id=38864034 https://news.ycombinator.com/item?id=38864034
- londons_explore 3y agoI would hope that any reasonably performant implementation would be faster not only than NVMe, but also faster than CPU to RAM data transfers. The AMD EPYC-Milan in the test server supports memory reads at 150 gigabytes/sec, but thats a 32 core machine, and our test only gets 8 of those cores, so we probably can't expect more than 37 gigabytes per second of read bandwidth. The total file is ~12 gigabytes, so we should expect to be able to get the task done in 0.3 seconds or so. There are only ~400 weather stations, so all the results fit in cache. It's unclear if it might be faster to avoid converting ascii to a float - it might be faster to add up all the ascii numbers, and figure out how to convert to a float only when you have the total.
- anonymoushn 3y ago
- Xophmeister 3y agoThis is an IO bound problem. Trying to "go faster" by using multiple threads or vectorisation isn't going to achieve much.
- frant-hartm 3y agoNo, it is not. The file is smaller than the available RAM, so will be cached in subsequent runs.
- brazzy 3y agoYou're not up to date with how fast IO can be these days. Nobody who cares primarily about performance uses spinning rust anymore.
- bufferoverflow 3y agoI'm pretty sure Hetzner servers (where the test is performed) have NVMe drives that can read at 4GB/s. So theoretically IO bound solution would be done in around 0.25 seconds. However the fastest current solution is around 12 seconds. So it's not IO-bound.
- unobatbayar 3y agoThis must be Decodale's engineering problem disguised as a challenge.
- brador 3y agoWould offering a cash prize increase or decrease the quality of submissions?
- weinzierl 3y agoUnfortunately I have no time to code this up but things that I would try to make it fast: - Read with O_DIRECT (but compare it with the mmap approach). I know O_DIRECT gets much hate, but this could be one of the rare cases where it helps. - Use a simple array with sentinel and linear search for the station names. This is dumb, but if the number of stations is small enough this could beat the hash. (In the back of my head I have a rule of thumb that linear search is faster for up to 1000 elements, but I'm not sure anymore where I got this from).
- londons_explore 3y agolinear search is never faster assuming your hash algorithm is cheap enough. However, if your list only contains 2 items, then your hash algorithm better be "Is first character > 'm'". When you want real speed like this and are happy with insane complexity, code that writes and self-compiles a hash function based on the data can make sense.
- gpderetta 3y ago> Read with O_DIRECT apparently the challenge explicitly allow for warming up the os cache on a prior run, so O_DIRECT would be disadvantaged here as the working set fits in memory. edit: also in my very simple tests a good hashmap can beat linear search already at <10 items. It depends a lot on the hash function cost.
- weinzierl 3y ago> beat linear search already at <10 items The sources I found corroborate this. My 1000 elements rule of thumb is apparently way off.
- dvko 3y agoI tried the linear search by station name in my first naive approach. Using a hashmap was at least 2-3x as fast with the ~415 distinct keys in the 1BRC dataset.
- atbpaca 3y agoWould have been nice to accept other JVM languages like Scala, Clojure, Kotlin, etc and compare against Java, which I expect to have slightly better performance.
- londons_explore 3y agoI believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup table of all temps and all place names. (~160,000) * autogenerate a state machine that will map each of the above 160,000 things, at any rotation within a 4 byte register, to a unique bin in a hash table. The state machine will have one 32 bit state register (16 bits to output, 16 to carry over to the next cycle) where every cycle a lookup in the state transition table is done, and the next 4 bytes of data XOR'ed on top. * run through all the data, at RAM speed, incrementing counters for each state the machine ends up in. (there will only be 65k). These counters fit fully in cache. * With just 32 bits of state, with AVX512 we can be running 512 copies of this in parallel if we like, per core! AKA, compute will not be the bottleneck. * from the values of the counters, you can calculate the answers. 65k is a far smaller number than 1 billion, so you don't need to do this bit fast. * for anything that doesn't map to a valid bin (higher/lower temperatures, unknown place names), just fallback to slow code (one state of the state machine can be reserved for 'escape to slow code'. Use these escapes for min/max handling too, since it will only happen a few thousand times). * I think this approach can operate at RAM speed with just one core with AVX512, so no benefit in splitting across cores.
- deleted 3y ago[deleted]
- Jaxan 3y agoGo for it!
- londons_explore 3y agoYou nerd sniper you! But more seriously, the JVM's support for vector intrinsics is very basic right now, and I think I'd spend far more time battling the JVM to output the code I want it to output than is fun. Java just isn't the right language if you need to superoptimize stuff. Theoretically all of the above is super simple SIMD stuff, but I have a suspicion that SIMD scatter/gather (needed for the state lookup table) isn't implemented.
- DeathArrow 3y agoThis can turn into a nice benchmark if done in multiple languages.
- jmclnx 3y agoIs there a way to create this file without having java ? This is for use on a BSD where Java may not work too well. Thanks
- dvko 3y agoYou can run the bin/create-sample program from this C implementation here: https://github.com/dannyvankooten/1brc https://github.com/dannyvankooten/1brc It’s just the city names + averages from the official repository using a normal distribution to generate 1B random rows.
- divbzero 3y agoI suspect Java is not the fastest language for this. I’d love to see unofficial contenders tackle this challenge using different languages.
- dvko 3y agoThere are a handful of implementations in other languages already. Here’s mine in C99: https://github.com/dannyvankooten/1brc https://github.com/dannyvankooten/1brc I’ve also seen versions in Rust, Go, Python, Clickhouse and DuckDB. The discussions tab on the GitHub repo lists some of these.
- daftego 3y agoAny elixir devs in here find this funny?
- dvko 3y agoVery fun challenge that nerd sniped me right away. Had to do a C version in standard C99 with POSIX threads. It[1] clocks in at just under 4 seconds on my AMD Ryzen 4800U Laptop CPU. Should run about 10-20% faster than that on the mentioned Hetzner hardware. - Since we only do one decimal of floating point precision it uses integer math right from the get-go. - FNV1-a hash with linear probing and a load factor well under 0.5. - Data file is mmap’d into memory. - Data is processed in 8 totally separate chunks (no concurrent data structures) and then those aggregations are in turn aggregated when all threads have finished. 1: https://github.com/dannyvankooten/1brc https://github.com/dannyvankooten/1brc
- wakasaka 3y agohow to make someone else to do your homework for free
- BeefWellington 3y agoI wonder why the choice to go with a shared compute for measuring this, given the variability that will introduce.
- andersrs 3y agoKind of a shame that median isn't included to make it tougher.
- deleted 3y ago[deleted]
- corlinpalmer 3y agoHere's my implementation in Go, which runs in under 5 seconds. It doesn't use anything too obscure, only the built-in maps and no external libraries. It's also the fastest solution I've tested on my M3 Pro Mac. Eager to see what beats it! https://gist.github.com/corlinp/176a97c58099bca36bcd5679e68f9708 https://gist.github.com/corlinp/176a97c58099bca36bcd5679e68f...
- bufferoverflow 3y agoLook at the leaderboard for the fastest solutions https://github.com/gunnarmorling/1brc#results https://github.com/gunnarmorling/1brc#results The fastest is currently at 12 seconds (not on M3 Pro though).
- guss_bro 3y agoThe fastest java solution from the current leaderboard runs within 2.6 seconds in my brand new M3 Mac.
- corlinpalmer 3y agoIs that `./calculate_average_royvanrijn.sh`? It runs in 6.7s for me. I would love it if you could run my solution and compare!
- dvko 3y agoThere’s an implementation in C which should run in well under 2 seconds on your M3. https://github.com/dannyvankooten/1brc https://github.com/dannyvankooten/1brc
- corlinpalmer 3y agoUnder 2 seconds seems rather impossible on my machine since the disk maxes out at 5.1 GB/s. This one ran in 7.4s on my M3: `bin/analyze measurements.txt 30.34s user 16.28s system 629% cpu 7.406 total`
- 3y ago
- PeterCorless 3y ago1 Billion Row Challenge with Apache Pinot https://hubertdulay.substack.com/p/1-billion-row-challenge-in-apache https://hubertdulay.substack.com/p/1-billion-row-challenge-i... 852 ms on an M1 Max
- yencabulator 3y agoNot including ingestion is cheating; the core challenge is parsing the text input.
- AUnterrainer 3y agoMy one liner solution runs in 76ms on my 10 year old mac. q)\ts exec (min;max;avg)@\:measurement by city from flip `city`measurement!("SF";";") 0: `:weather_stations.csv 76 8720688
- anonymoushn 3y agoYour 10 year old mac can ingest the input at 157GB/s? Is that from RAM or from disk?
- AUnterrainer 3y agoActually I only had a partial file :/ didn't realise that the file in the data folder was only a sample
- Ellipsis753 3y agoInterestingly, because your program runs on Linux and is run 5 times, Linux will almost certainly cache the 12gb file to RAM on the first invocation. This means that future invocations don't have to load the file from disk. This also makes it pretty critical that your program doesn't use more than 16gb of ram itself (out of the server's 32gb) or it'll push the file out of cache making future invocations of your program slower.