You 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.
Yeah 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).
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.
Yeah 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
So you are basically at the mercy of the OS caching algorithm. That sounds like a bad plan for a benchmark. You are not measuring what you think you are (your code), you are measuring the OS caching policy.
What is the downside of memory mapping in this scenario? Shouldn't the page table properly handle the case of doing a single sequential read over a range of pages? Accessing the contents of a file doesn't seem like something caching would matter for. Do you mean that reading of sequential pages will keep adding to the cache compared to reading from a single page? That seems like a similar thing as before where they will be the first things gone from the cache anyways.
Caching and paging almost always matter, even on things like this. The core problem is that the filesystem won't prefetch for you, and you will be waiting to page fault several times over the length of the file. Another problem of the size of the working set is that you will be seeing several slow calls to (essentially) malloc in the kernel to hold all of that data, while using a small, preallocated structure will give you none of that trouble.
Dumb question. With io_uring, how do you handle lines that straddle between chunks? I'm asking since, AFAIU, the submitted requests are not guaranteed to be completed in order.
(The easiest I can think of is submitting reads for "overlapped" chunks, I'm not sure there is an easier way and I'm not sure of how much performance overhead there is to it.)
Right, 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.
It 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.
As 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.
Alternatively, "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...
A 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.
Anything that fits in RAM on one machine is easily too small for Hadoop. In those cases, the overhead of Hadoop is going to make it get destroyed by a single beefy machine. The only times where this might not be the case is when you're doing a crazy amount of computation relative to the data you have.
Note that you can easily reach 1TB of RAM on (enterprise) commodity hardware now, and SSDs are pretty fast too.
> 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.
I'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.
That'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.
Their should be no optimizations which rely on a-priori knowledge of the dataset. I.e. if you calculate a perfect hash function at runtime by inspecting the dataset, that's fine (not sure whether it's beneficial), but hard coding it, is not.
That is a tricky rule to enforce. For example, some solutions assume that the temperature values fit into an int, which could be interpreted as relying on a priori knowledge.
That's true. Some assumptions always have to be made.
In this case, we can assume place names that can be arbitrary strings and temperatures that occur naturally on earth.
Optimizing around those constraints should be fine. We could probably limit the string length to something like 100 characters or so.
Bad assumptions would for example be to assume that all possible place names are found within the example data.
UTF-8 makes this far harder... But if you stick to the letter but not spirit of the rules, you can simply fall back to a slow implementation if you ever detect any byte > 127 (indicating a multibyte UTF-8 character).
Only if you validate the UTF-8 as being valid. If you just accept that it is you can treat it as just some bytes. Nothing in the spec I see requires processing UTF-8 as an actual Unicode string.
The easiest way to handle Unicode is to not handle it at all, and just shove it down the line. This is often even correct, as long as you don't need to do any string operations on it.
If the author wanted to play Unicode games, requiring normalization would be the way to go, but that would turn this into a very different challenge.
Since the tail of the line has a known format I guess we are rescued by the fact that the last 0x3B is the semicolon as the rest is just a decimal number. We can’t know the first 0x3B byte is the semicolon since the place names are only guaranteed to not contain 0x3B but can contain 0x013B. So a parser should start from the rear of the line and read the number up to the semicolon and then it can treat the place name as byte soup. Had two places shared line this challenge would have required real utf parsing and been much harder.
Yes, sorry, I'm so used to this sort of thing with the work I've been doing lately I forgot to lay it out like that. Thank you for filling it in for me.
I'm not sure scanning backwards this helps. Running in reverse you still need to look for a newline scanning over an UTF-8 string which might plausibly contain a newline byte.
I'm no UTF-8 guru, but I think you might be possible to do this sort of a springboard for skipping over multi-byte codepoints, since as far as I understand the upper bits of the first byte encodes the length:
It's easier than you think... utf-8 guarantees that all bytes of a multi-byte character have the high bit set. 0x3B (semicolon) does not have the high bit set. Therefore 0x3B is guaranteed to be your seperator.
The same logic applies to newline - therefore, you can jump into the middle of the file anywhere and guarantee to be able to synchronize.
> 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?
This 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.
Any 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.
> 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.
Then, 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.
Physical memory is not fungible like that across VMs. So, you can expect stuff loaded into memory to stay there unless your kernel inside the VM decides it not to.
No, it's. VirtIO's balooning device can "inflate" to pseudo-allocate memory on a VM to free physical memory for other hosts.
Moreover, even if your files in memory, you cannot reserve "memory controller bandwidth". A VM using tons of memory bandwidth or a couple of cores in the same NUMA node with your VM will inevitably cause some traffic and slow you down.
There's logrotate and other cleanup tasks, monitoring, dns, a firewall, and many more stuff running on that server. No matter how much you offload to the host (or forego), there's always a kernel and supporting deamons running alongside or under your app.
But this is a contrived test, and looking for the fastest solution, so your arguments point to taking the fastest: the one with the least interference.
Yes, the one works the fastest in average case will be the fastest in the real world, and will be the one least affected by general noise present in the system.
Not necessarily. A good code with nice parallelization and efficient code path will always win. If the code is inefficient to begin with, having no cron jobs at the same time won't help.
I agree that this method will produce a better estimate of expected mean real world performance under certain load conditions, but still contend it just muddies the waters about which solution is in fact the fastest.
I 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.
The 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.
That'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.
Using cat to redirect the file to /dev/null takes 18s on my machine (a low-end NUC). Just running a noop on the file in Perl (ie. feeding it into a `while (<>)` loop but not acting on the contents) takes ~2 minutes.
Why are you using cat at all? Use a pipe. This isn't hard stuff. Don't use <>, feed the file into a scalar or array. it should only take a few seconds to process a billion lines.
It's really not. We're talking about gigahertz CPUs and likely solid state storage that can stream many gb/s.. running through a perl script. There really isn't much that is faster than that.
Weird to think typescript is similar to a language that requires a class definition for “hello world” lol. You can’t even fit it on a single 80 character line…
Putting everything in a class has some really nice benefits.
For example, for performance monitoring/debugging, it's really nice to see memory usage and thread creation by package/class. Whereas, I've seen teams spend weeks trying to find memory leaks in NodeJS applications, because you just get "here's general usage by object-shape". Would literally take me less than a minute with Java...
it feels like the characters-typed to functionality ratio is quite low. at the same time, the code isn't much cleaner and there's a lot of mental overhead in deciphering the abstractions (in this case Collector).
Java is probably the language I use the most but I hate how much boilerplate it has. Something I’ve found to help with that is using Java Records instead of classes, a record is kind of like a struct, but I don’t think it’s exactly the same, there’s no boilerplate and something I quite like about them is that their fields are immutable (more specifically “private final”) which works well with more functional programming, something that can be quite clunky with classes in java
Anyway I’m not a software engineer so take what I say about software with a grain of salt. Also I feel like other java programmers will hate you if they need to read or use your code. For example lets say you had a 2D point data type that is a record. instead of things being like “pos.add(5)” if pos is a record you need to reassign it like “pos = pos.add(5)” where add returns the pos as an object. Similar to how BigInteger works in java.
Anyway I love records because there’s zero boilerplate, it feels very similar to me to how structs are written in rust and go, or how classes are done in scala. I just never see anyone talk about it. I guess that might be because most people programming new projects on JVM are probably not programming in java?
> instead of things being like “pos.add(5)” if pos is a record you need to reassign it like “pos = pos.add(5)”...
That's just mutable vs immutable data structures
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'.
> 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.
So 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.
Scala is a much different case, it has one of the most advanced type systems, many implicit scoping rules etc. Even a java change that might affect the scala codebase could result in a slow incremental build. Also, the build system may not have been as modular as it could.
In my experience, java annotations gets processed very fast.
Well, that's a bit of a stretch. It is definitely one of the most complex type systems due to interactions between nominal sub-typing and type classes which is a bit hairy. But in terms of what this type system can express or prove, it's both inferior (cannot express lifetimes or exclusive access) and superior (HKTs, path dependent types) to Rust in some aspects. Let's say they are close.
Scala is the problem here. Scala has several issues filed for slow compilation.
300K LOC Java should be done within ~1.5 minutes flat from zero. Can be even faster if you are running maven daemon for example. Or even within ~30 seconds if everything is within one module and javac is only invoked once.
What step are we talking about? Javac itself is absolutely on the same order of magnitude speed as Go per loc, while rust is significantly slower (which makes sense, the latter is a properly optimizing compiler with heavy static analysis, while the former two just spews out java byte code/machine code).
Gradle with a daemon is also pretty fast, you are just probably used to some complex project with hundreds of dependencies and compare it to a cargo file with a single dependency.
Just a nitpick, but the static analysis in Rust doesn’t account for most of why compilation is slow, as proven by the fact that cargo check is much faster than cargo build.
Yeah, I know. I believe it’s mostly the amount of LLVM IR that is the problem (e.g. each generic instantiation outputs by default a new copy of roughly the same code), isn’t it?
> Javac itself is absolutely on the same order of magnitude speed as Go per loc
Not really when it has to run on a cold JVM. And before it warms up, it’s already done.
Then you are in territory of keeping the compiler process between the runs, but that is a memory hog and also not always realiable (gradle often decides to run a fresh daemon for whatever reason).
So theoretically, in lab conditions yes, in practice no.
> while rust is significantly slower
Everybody repeats that but there is surprisingly little evidence in form of benchmarks. I can see rustic compiles over 50k Loc per second on average on my M2, which is roughly the same order of magnitude as Java. And checking without building is faster.
I've yet to see a project where Gradle daemon a) does anything useful and b) is acutally used by gradle itself (instead of seemingly doing everything from scratch, no idea what it does in the seconds it takes for it to start up).
This. Gradle wastes tremendous amounts of time on non-compile tasks. So even if Java takes a few seconds to compile, the whole build is often much, much longer. Interestingly, my impression is that maven is significantly more snappy.
>I've yet to see a project where Gradle daemon a) does anything useful
Also my experience.
Only using Gradle deamon does not help making a multi-project setup much faster. You also have to enable build cache, configuration cache and configure on demand with `--configuration-cache --configure-on-demand` and hope nobody in the project breaks the ability for Gradle to use these caches. But then it still took at least 10 seconds to build and start my services (and that's with incremental builds, like you changed one line of code after the first slow build). I spend two days and more after release to speed this stuff up, before it was 30 seconds sometimes 60 seconds.
And the protobuf Gradle plugin sometimes did not update the generated code, so you had force-delete the files on every build. And then other stuff in the caches broke and you had to delete `.gradle` directory and sometimes even the `~/.gradle` directory. And sometimes the Gralde daemon hangs so you have to force it to stop with `--stop.
Go build, deno and bun are so much more reliable and faster. Something that was surprisingly fast was using the Gradle setup with skaffolding. Java hot code swapping is very fast.
> Then someone in your team failed learning the bare minimum to write a sane gradle file
Then someone in over 15 years and 8 versions gradle failed to make a system that doesn't require "learning to write sane gradle files" to make sure that it's only two orders of magnitude and not five orders of magnitude slower than it can be.
> and are putting imperative stuff into the configuration phase
Has nothing to do with the slowness that is gradle.
> For big projects, compiling only what’s necessary is a huge time win.
Build systems are a complex problem. Like, you can compare it to cargo/go’s build system etc, but these forget about 90% of the problem, and come up with a hard-coded for the happy-path rust/go project, with zero non-native dependency, all downloaded from the repository. This is not a bad thing, don’t get me wrong. But it is not enough to compile, say, a browser.
Meanwhile, there are only a couple, truly general build systems, all of them quite complex — as you can’t get away with less. Gradle and bazel are pretty much the only truly generic build systems (I’m sure there are a couple more, but not many). You can actually compile a mixed java, c++, whatever project with gradle, for example, just fine, with proper parallelism, caching, etc.
As for your points:
> in 15 years is still slow by default
Absolutely false. A 3-4 lines gradle build file for java will be fast, and correctly parallelize and maximally utilize previously built artifacts.
> in 15 years could not acquire any sensible defaults that shouldn't need extra work to configure
It’s literally 4 lines for a minimal project, maybe even less. I’m getting the feeling that you have zero idea about what you talk about.
> is written in an esoteric language with next to zero tools to debug and introspect
I somewhat agree, though nowadays kotlin is also an alternative with strong typing, proper auto-complete, the only trade off is a tiny bit slower first compile of the config file. Also, both could/can be debugged by a normal java debugger.
> randomly changes and moves thing around every couple of years for no discernible reason
There is some truth to this. But the speed has definitely improved.
> has no configuration specification
Kotlin is statically typed. Also, the API has okayish documentation, people just like to copy-paste everything and wonder why it fails. You wouldn’t be able to fly a plane either from watching 3 sitcoms showing a cockpit, would you?
> Absolutely false. A 3-4 lines gradle build file for java will be fast, and correctly parallelize and maximally utilize previously built artifacts.
I've never seen this on any project that utilizes gradle. Every time, without fail, it's a multi-second startup of gradle that eventually invokes something that is actually fast: javac.
> I’m getting the feeling that you have zero idea about what you talk about.
Only 7 years dealing with java projects, both simple and complex
>> has no configuration specification
> Kotlin is statically typed.
Kotlin being statically typed has literally nothing to do with a specification.
Becuase Gradle doesn't have a configuration. It has a Groovy/Kotlin module that grew organically, haphazardly and without any long term plans. So writing gradle configuration is akin to reverse-engineering what the authors intended to do with a particular piece of code or API.
> Also, the API has okayish documentation
"okayish" is a synonim for bad. You'd think that a 15-year project in its 8th major version would have excellent API documentation
> people just like to copy-paste everything and wonder why it fails. You wouldn’t be able to fly a plane either from watching 3 sitcoms
So, a project with no specification to speak of, with "okayish" API that is slow as molasses by default out of the gate [1] keeps blaming its users for its own failure because somehow it's a plane, and not a glorified overengineered Makefile.
[1] A reminder, if you will, that gradle managed to come up with caching configs to speed up its startup time only in version 8, after 15 years of development.
It has always been “an imperative code that outputs the declarative configuration that can be used for the build”. Which is a very reasonable thing to do, but unfortunately most people fail to understand that a println in the config file’s global scope is different than inside a closure for a task description.
> but unfortunately most people fail to understand that a println in the config file’s global scope is different than inside a closure for a task description.
Literally no one complaining about gradle being slow is doing that. Allmost all of gradle's problems come not from people using it, but from Gradle itself.
I mean, you said it yourself: in 15 years the state of their API docs is "okayish". But somehow people are still expected to make sense of this shit because apparently it's a plane? But planes famously have extensive documentation, and procedures, and decades of expertise available. Exactly unlike gradle.
It could be if tool is work of good design and engineering. But not when tool's claim to fame is that it does not use XML to describe build config like Maven/Ant.
There are not many alternatives that are truly general build tools (not limited to single language/repository, etc), and properly parallelize and cache.
> A fair comparison between languages should include the make and build times
if you do that, you should also include programming time, and divide both by the number of runs the code will have over its lifetime. Also add an appropriate fraction of the time needed to learn to program.
In such a challenge, that likely would make a very naive version win.
Apart from being impractical, I think that would be against the idea behind this challenge.
From 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.
It 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.
I 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.
I 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.
1: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....). 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 postgre...
FWIW, you can make the data loading a decent bit faster:
1) use the integer version of generate_series, the 1e9 leads to the floating point version being chosen
2) move the generate_series() to the select list of a subselect - for boring reasons, that we should fix, the FROM version materializes the result first
3) using COPY is much faster, however a bit awkward to write
psql -Xq -c 'COPY (SELECT (1000random())::int2 as city, (random()random()*1100)::int2 temp FROM (SELECT generate_series(1,1e9::int8))) TO STDOUT WITH BINARY' | psql -Xq -c 'COPY temps_int2 FROM STDIN WITH BINARY'
psql -c 'create table temps_int2_copy as select * from temps_int2_copy where 1=0;'
psql -Xq -c 'COPY (SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp FROM (SELECT generate_series(1,1e8::int8))) TO STDOUT WITH BINARY' | psql -Xq -c 'COPY temps_int2_copy FROM STDIN WITH BINARY'
==> 32sec
psql -c 'create table temps_int2_copy2 as select * from temps_int2_copy where 1=0;'
psql -c 'INSERT INTO temps_int2_copy2 (city, temp) SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp from generate_series(1,1e8::int)i;'
==> 90sec
psql -c 'create UNLOGGED table temps_int2_copy3 as select * from temps_int2_copy where 1=0;'
psql -c 'INSERT INTO temps_int2_copy3 (city, temp) SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp from generate_series(1,1e8::int)i;'; date
==> 45sec (still not faster!)
Of course, if we really want to "go fast" then we want parallel loading, which means firing up N postgresql backends and each generate and write the data concurrently to different tables, then each compute a partial summary in N summary tables, and finally merge them together.
echo "COPY temps_int2_copy_p1 from '/var/lib/postgresql/output100m.txt' with csv;" | /usr/lib/postgresql/16/bin/postgres --single -D /etc/postgresql/16/main/ postgres
==> 32sec (saturates one core)
The ultimate would be to hack into postgres and skip everything and just write the actual filesystem files in-place using knowledge of the file formats, then "wire in" these files to the database system tables. This normally gets hairy (e.g. TOAST) but with a simple table like this, it might be possible. This is a project I've always wanted to try.
> wow! awesome tips. I knew COPY rocks but didn't realize it would win vs INSERT INTO SELECT FROM !
We (postgres) should fix that at some point... The difference basically is that there's a dedicated path to insert many tuples at once that's often used by COPY that isn't used by INSERT INTO ... SELECT. The logic for determining when that optimization is correct (consider e.g. after-insert per-row triggers, the trigger invocation for row N may not yet see row N+1) is specific to COPY right now. We need to generalize it to be usable in more places.
To be fair, part of the reason the COPY approach is faster is that the generate_series() query actually uses a fair bit of CPU on its own, and the piped psql's lead to the data generation and data loading being run separately. Of course, partially paying for that by needing to serialize/deserialize the data and handling all the data in four processes.
When doing the COPYs separately to/from a file, it actually takes longer to generate the data than loading the data into an unlogged table.
# COPY (SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp FROM (SELECT generate_series(1,1e8::int8))) TO '/tmp/data.pgcopy' WITH BINARY;
COPY 100000000
Time: 21560.956 ms (00:21.561)
# BEGIN;DROP TABLE IF EXISTS temps_int2; CREATE UNLOGGED TABLE temps_int2 (city int2 NOT NULL, temp int2 NOT NULL); COPY temps_int2 FROM '/tmp/data.pgcopy' WITH BINARY;COMMIT;
BEGIN
Time: 0.128 ms
DROP TABLE
Time: 0.752 ms
CREATE TABLE
Time: 0.609 ms
COPY 100000000
Time: 18874.010 ms (00:18.874)
COMMIT
Time: 229.650 ms
Loading into a logged table is a bit slower, at 20250.835 ms.
> Of course, if we really want to "go fast" then we want parallel loading, which means firing up N postgresql backends and each generate and write the data concurrently to different tables, then each compute a partial summary in N summary tables, and finally merge them together.
With PG >= 16, you need a fair bit of concurrency to hit bottlenecks due to multiple backends loading data into the same table with COPY. On my ~4 year old workstation I reach over 3GB/s, with a bit more work we can get higher. Before that the limit was a lot lower.
If I use large enough shared buffers so that IO does not become a bottleneck, I can load the 1e9 rows fairly quickly in parallel, using pgbench:
c=20; psql -Xq -c "COPY (SELECT (1000*random())::int2 as city, (random()*random()*1100)::int2 temp FROM (SELECT generate_series(1,1e6::int8))) TO '/tmp/data-1e6.pgcopy' WITH BINARY;" -c 'DROP TABLE IF EXISTS temps_int2; CREATE UNLOGGED TABLE temps_int2 (city int2 NOT NULL, temp int2 NOT NULL); ' && time pgbench -c$c -j$c -n -f <( echo "COPY temps_int2 FROM '/tmp/data-1e6.pgcopy' WITH BINARY;" ) -t $((1000/${c})) -P1
real 0m26.486s
That's just 1.2GB/s, because the bottleneck is the per-row and per-field processing, due to their narrowness.
> The ultimate would be to hack into postgres and skip everything and just write the actual filesystem files in-place using knowledge of the file formats, then "wire in" these files to the database system tables. This normally gets hairy (e.g. TOAST) but with a simple table like this, it might be possible. This is a project I've always wanted to try.
I doubt that will ever be a good idea. For one, the row metadata contain transactional information, that'd be hard to create correctly outside of postgres. It'd also be too easy to cause issues with corrupted data.
However, there's a lot we could do to speed up data loading performance further. The parsing that COPY does, uhm, show signs of iterative development over decades. Absurdly enough, that's where the bottleneck most commonly is right now. I'm reasonably confident that there's at least 3-4x possible ...
thx! Indeed, upon reading the source and sleeping on it, I agree, and in fact it looks like a single-user postgres backend with COPY FROM <filename> BINARY is approximately the same architecture as writing the database files in-place, and of course includes support for default values, triggers, constraints, TOAST and more.
I've reproduced the speed difference between pg COPY vs various cases.
Some results (middle result of 3 stable runs) from 1.4GB BINARY dump:
echo "drop table if exists tbl; create table tbl(city int2, temp int2);copy tbl FROM '/citydata.bin' binary;" | ./pg/bin/postgres --single -D tmp -p 9999 postgres;
real 0m34.508s
# switching to unlogged table
real 0m30.620s
# hardcoding heap_multi_insert() to be a NOOP (return early if ntuples>100)
# fyi, heap_multi_insert() gets called with n=1000 tuples per call
real 0m11.276s
# hardcoding skip_tuple = true in src/backend/commands/copyfrom.c:1142
real 0m6.894s
# after testing various things
time sh -c "tar cf - citydata.bin | (cd /tmp; tar xf -)"
real 0m2.811s
Note: I tried increasing the blocksize (--with-blocksize) and also MAX_BUFFERED_TUPLES (copyfrom.c:65) but as expected they didn't help, I guess n=1000 tuples amortizes the overhead.
I think it actually shows that you're IO bound (the 'D' in the 'S' column). On my workstation the query takes ~10.9s after restarting postgres and dropping the os caches. And this is a four year old CPU that wasn't top of the line at the time either.
> 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 ;
Note that you dropped the limit 5 here. This causes the query to be a good bit slower, the expensive part here is all the array unnesting, which only needs to happen for the actually selected cities.
On my workstation the above takes 1.8s after adding the limit 5.
Exactly. The issue is that postgresql takes 37 bytes per row normally, which then causes it to spill out of RAM on the limited VM specified for this challenge, causing the query to be I/O bound, hence the array representation and unnesting to fit it back into RAM. I'm guessing your machine has more RAM ?
> Exactly. The issue is that postgresql takes 37 bytes per row normally, which then causes it to spill out of RAM on the limited VM specified for this challenge, causing the query to be I/O bound, hence the array representation and unnesting to fit it back into RAM. I'm guessing your machine has more RAM ?
It does, but I restarted postgres and cleared the OS cache.
Btw, the primary bottleneck for the array-ified query is the unnest() handling in the functions. The minimal thing would be to make the functions faster, e.g. via:
CREATE OR REPLACE FUNCTION array_avg(_data anyarray)
RETURNS numeric IMMUTABLE PARALLEL SAFE LANGUAGE sql AS
$$
select avg(a)
from (SELECT unnest(_data) as a)
$$;
But that way the unnest is still done 3x. Something like
SELECT a_min, a_max, a_avg FROM temps_by_city, LATERAL (SELECT min(u) a_min, max(u) a_max, avg(u) a_avg FROM (SELECT unnest(array_agg) u)) limit 5;
The 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
> 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
Ah 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.
Yeah, and I'd count caching results between runs into the same category, i.e. against the spirit of this challenge. Folks should keep in mind that the goal is to learn something new, rather than "winning" by cheating the rules.
There is a real issue with providing the contestant the real exact file that will be used in the contest. Because there are 1e9 shades of gray between hard coding the correct answer in a single line program which doesn't even read the input, and processing the file as if we don't know what it contains.
This might become a contest of judging what is fair pre-computing and what is not.
That's why machine learning contests don't let participants see the final data.
* I generate random measurements with the provided script, which will be stored in a readonly file.
* I run your program to calculate the results (and time it).
* I run my baseline program and your entry is valid if my baseline program calculates the same results.
The filesystem has to be read-only as well, otherwise the first run can simply write the results to ~/.me_cheater and the program first reads that file before attempting to read the dataset.
You 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.
> 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.
For 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.
> 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.
Variability 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.
There are good reasons to discard the best runs. If you think of your system as having predictable behavior that's slowed down by background processing happening on the machine, it might make sense to use the best run. But if there are any intrinsic sources of non-determinism in the program (and it's far more likely than you might think), taking the best time is likely to be unrepresentative.
Because there can be outliers in terms of slowness; perhaps the CPU gets a hickup, the GC runs an abnormal amount of extra times, the kernel decides to reschedule stuff, whatever, I don't know much about these things.
There can't be outliers in terms of fastness; the CPU doesn't accidentally run the program much faster.
It's the same logic both ways. The OS runs 10 background tasks on average at any given time. On one of your runs it was doing 15 things, while on another it was doing 5 things. They are both outliers.
As 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?
Yes, 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.
- 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
The 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.
The next obvious solution is to have something that works fast for non-colliding station names, but then falls back to another (slow) implementation for colliding station names.
It's very cheap to detect station name collisions - just sample ~10,000 points in the file, and hope to find at least one of each station. If you find less stations than the full run, you haven't yet seen them all, keep hunting. If you find two that collide, fall back to the slow method. Checking 0.00001% of the dataset is cheap.
Cuckoo doesn't aid in detecting collisions, the algorithm is about what happens IF a collision is found. The whole reason we're hashing in the first place is to not have to linearly compare station names when indexing.
In other words: Cuckoo is a strategy to react to the case if two values map to the same hash. But how to know weather you have two different values, or two of the same, if they have an identical hash?
Yeah if you are releasing the competition dataset then it can and will 100% be gamed. What is to stop me from just hardcoding and printing the result without any computation?
This 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.
You 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.
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.
Looking 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.
Custom 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).
I 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.
actually 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".
say you load 1 million records and you average them at 5.1. you then load another million and average them at 4.5. so you 5.1+4.5=9.6/2=4.8. rinse and repeat. as long as you keep the amount of records processed per each run about the same, your numbers will not be skewed. only the last chunk will most likely be smaller and it will introduce small rounding error, like if it has only 10k records instead of 1M. but still it is the simplest solution with good enough outcome.
essentially that is how integrals are calculated in mathematics if i remember correctly. you take a curve and divide it into columns, the thinner the column the smaller the deviation(because the curve has round edges so your bar will have inherent error) and you simply calculate each column and then total it and you get the body/volume of the function. same principle like radians with circle. you are merely splitting the work into smaller pieces that you can process.
I 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.
the 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
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)"
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;
Using 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.
Just modified the original post to add the file_fdw. Again, none of the instances (PG or ClickHouse) were optimised for the workload https://ftisiot.net/posts/1brows/
In the first one, the table is dropped, recreated, populated and queries.
In the second example, the table is created from a file FDW to the CSV file.
In both examples the loading time is included in the total time
time clickhouse local -q "SELECT concat('{', arrayStringConcat(groupArray(v), ', '), '}')
FROM
(
SELECT concat(station, '=', min(t), '/', max(t), '/', avg(t)) AS v
FROM file('measurements.txt', 'CSV', 'station String, t Float32')
GROUP BY station
ORDER BY station ASC
)
SETTINGS format_csv_delimiter = ';', max_threads = 8" >/dev/null
real 0m15.201s
user 2m16.124s
sys 0m2.351
365 comments
[ 3.4 ms ] story [ 281 ms ] thread[0] https://github.com/gunnarmorling/1brc/discussions
I thought memory mapping solved a different problem.
Code: https://github.com/rockwotj/1brc
Discussion on Filesystem cache: https://x.com/rockwotj/status/1742168024776430041?s=20
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.
edit: doh that works for min and max but the average overflows.
That's what I used to think, too. But the kernel ain't that smart.
(The easiest I can think of is submitting reads for "overlapped" chunks, I'm not sure there is an easier way and I'm not sure of how much performance overhead there is to it.)
(Of course, the five times in a row might mess with that.)
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.
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.
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.
Note that you can easily reach 1TB of RAM on (enterprise) commodity hardware now, and SSDs are pretty fast too.
Old but gold post from 2014: https://adamdrake.com/command-line-tools-can-be-235x-faster-...
> 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.
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.
I think having the names for performance tests public is fine. But there should be correctness tests on sets with random names.
In this case, we can assume place names that can be arbitrary strings and temperatures that occur naturally on earth. Optimizing around those constraints should be fine. We could probably limit the string length to something like 100 characters or so.
Bad assumptions would for example be to assume that all possible place names are found within the example data.
The easiest way to handle Unicode is to not handle it at all, and just shove it down the line. This is often even correct, as long as you don't need to do any string operations on it.
If the author wanted to play Unicode games, requiring normalization would be the way to go, but that would turn this into a very different challenge.
I'm no UTF-8 guru, but I think you might be possible to do this sort of a springboard for skipping over multi-byte codepoints, since as far as I understand the upper bits of the first byte encodes the length:
The same logic applies to newline - therefore, you can jump into the middle of the file anywhere and guarantee to be able to synchronize.
Shouldn’t he take the single fastest time, assuming file (and JDK) being in file cache is controlled for?
The range of remaining three is what you expect to get 99% of the time on a real world system.
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.
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.
Moreover, even if your files in memory, you cannot reserve "memory controller bandwidth". A VM using tons of memory bandwidth or a couple of cores in the same NUMA node with your VM will inevitably cause some traffic and slow you down.
There's logrotate and other cleanup tasks, monitoring, dns, a firewall, and many more stuff running on that server. No matter how much you offload to the host (or forego), there's always a kernel and supporting deamons running alongside or under your app.
The test is very well designed, we may say.
And here is Andrei Alexandrscu arguing the same in 2012: https://forum.dlang.org/thread/mailman.73.1347916419.5162.di...
The author does explicitly want all the files to be cached in memory for the later runs: https://x.com/gunnarmorling/status/1742181941409882151?s=20
https://stackoverflow.com/questions/277309/java-floating-poi...
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.
This is really a small, trivial task for a perl script. Even with a billion lines this is nothing for a modern cpu and perl.
https://www.reddit.com/r/perl/comments/18ygpsi/1_billion_row...
1B lines is a lot, and Java ain't a slouch.
https://www.perl.com/pub/2003/11/21/slurp.html/#:~:text=Anot....
Java is explicit, yes. This is intentional :)
I find Python to be the most pleasant personally.
For example, for performance monitoring/debugging, it's really nice to see memory usage and thread creation by package/class. Whereas, I've seen teams spend weeks trying to find memory leaks in NodeJS applications, because you just get "here's general usage by object-shape". Would literally take me less than a minute with Java...
Anyway I’m not a software engineer so take what I say about software with a grain of salt. Also I feel like other java programmers will hate you if they need to read or use your code. For example lets say you had a 2D point data type that is a record. instead of things being like “pos.add(5)” if pos is a record you need to reassign it like “pos = pos.add(5)” where add returns the pos as an object. Similar to how BigInteger works in java.
Anyway I love records because there’s zero boilerplate, it feels very similar to me to how structs are written in rust and go, or how classes are done in scala. I just never see anyone talk about it. I guess that might be because most people programming new projects on JVM are probably not programming in java?
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'.
(Also, gradle is faster as a build tool for incremental compilation)
> 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.
As for precedural macros - yes they can be slow to compile but so are Java annotation processors.
In my experience, java annotations gets processed very fast.
Well, that's a bit of a stretch. It is definitely one of the most complex type systems due to interactions between nominal sub-typing and type classes which is a bit hairy. But in terms of what this type system can express or prove, it's both inferior (cannot express lifetimes or exclusive access) and superior (HKTs, path dependent types) to Rust in some aspects. Let's say they are close.
That’s what I meant mostly. Though if I’m being honest, I’m not familiar with the implementation of either language’s type system.
300K LOC Java should be done within ~1.5 minutes flat from zero. Can be even faster if you are running maven daemon for example. Or even within ~30 seconds if everything is within one module and javac is only invoked once.
Gradle with a daemon is also pretty fast, you are just probably used to some complex project with hundreds of dependencies and compare it to a cargo file with a single dependency.
Not really when it has to run on a cold JVM. And before it warms up, it’s already done.
Then you are in territory of keeping the compiler process between the runs, but that is a memory hog and also not always realiable (gradle often decides to run a fresh daemon for whatever reason).
So theoretically, in lab conditions yes, in practice no.
> while rust is significantly slower
Everybody repeats that but there is surprisingly little evidence in form of benchmarks. I can see rustic compiles over 50k Loc per second on average on my M2, which is roughly the same order of magnitude as Java. And checking without building is faster.
Wiki citation for good measures https://en.wikipedia.org/wiki/Javac.
Maybe you're thinking of Hotspot, which is written in C++.
I've yet to see a project where Gradle daemon a) does anything useful and b) is acutally used by gradle itself (instead of seemingly doing everything from scratch, no idea what it does in the seconds it takes for it to start up).
Also my experience.
Only using Gradle deamon does not help making a multi-project setup much faster. You also have to enable build cache, configuration cache and configure on demand with `--configuration-cache --configure-on-demand` and hope nobody in the project breaks the ability for Gradle to use these caches. But then it still took at least 10 seconds to build and start my services (and that's with incremental builds, like you changed one line of code after the first slow build). I spend two days and more after release to speed this stuff up, before it was 30 seconds sometimes 60 seconds.
And the protobuf Gradle plugin sometimes did not update the generated code, so you had force-delete the files on every build. And then other stuff in the caches broke and you had to delete `.gradle` directory and sometimes even the `~/.gradle` directory. And sometimes the Gralde daemon hangs so you have to force it to stop with `--stop.
Go build, deno and bun are so much more reliable and faster. Something that was surprisingly fast was using the Gradle setup with skaffolding. Java hot code swapping is very fast.
I have no idea what gradle and its daemon do except spending orders of magnitude more time starting up than running the actual build.
You're much better off running javac directly. Then it's fast.
For big projects, compiling only what’s necessary is a huge time win.
Then someone in over 15 years and 8 versions gradle failed to make a system that doesn't require "learning to write sane gradle files" to make sure that it's only two orders of magnitude and not five orders of magnitude slower than it can be.
> and are putting imperative stuff into the configuration phase
Has nothing to do with the slowness that is gradle.
> For big projects, compiling only what’s necessary is a huge time win.
It is, and no one is arguing with that
- in 15 years is still slow by default
- in 15 years could not acquire any sensible defaults that shouldn't need extra work to configure
- is written in an esoteric language with next to zero tools to debug and introspect
- randomly changes and moves thing around every couple of years for no discernible reason and making zero impact on reducing its slowness
- has no configuration specification to speak of because the config is written in that same esoteric programming language
And its zealots blame its failures on its users
Meanwhile, there are only a couple, truly general build systems, all of them quite complex — as you can’t get away with less. Gradle and bazel are pretty much the only truly generic build systems (I’m sure there are a couple more, but not many). You can actually compile a mixed java, c++, whatever project with gradle, for example, just fine, with proper parallelism, caching, etc.
As for your points:
> in 15 years is still slow by default
Absolutely false. A 3-4 lines gradle build file for java will be fast, and correctly parallelize and maximally utilize previously built artifacts.
> in 15 years could not acquire any sensible defaults that shouldn't need extra work to configure
It’s literally 4 lines for a minimal project, maybe even less. I’m getting the feeling that you have zero idea about what you talk about.
> is written in an esoteric language with next to zero tools to debug and introspect
I somewhat agree, though nowadays kotlin is also an alternative with strong typing, proper auto-complete, the only trade off is a tiny bit slower first compile of the config file. Also, both could/can be debugged by a normal java debugger.
> randomly changes and moves thing around every couple of years for no discernible reason
There is some truth to this. But the speed has definitely improved.
> has no configuration specification
Kotlin is statically typed. Also, the API has okayish documentation, people just like to copy-paste everything and wonder why it fails. You wouldn’t be able to fly a plane either from watching 3 sitcoms showing a cockpit, would you?
I've never seen this on any project that utilizes gradle. Every time, without fail, it's a multi-second startup of gradle that eventually invokes something that is actually fast: javac.
> I’m getting the feeling that you have zero idea about what you talk about.
Only 7 years dealing with java projects, both simple and complex
>> has no configuration specification
> Kotlin is statically typed.
Kotlin being statically typed has literally nothing to do with a specification.
Becuase Gradle doesn't have a configuration. It has a Groovy/Kotlin module that grew organically, haphazardly and without any long term plans. So writing gradle configuration is akin to reverse-engineering what the authors intended to do with a particular piece of code or API.
> Also, the API has okayish documentation
"okayish" is a synonim for bad. You'd think that a 15-year project in its 8th major version would have excellent API documentation
> people just like to copy-paste everything and wonder why it fails. You wouldn’t be able to fly a plane either from watching 3 sitcoms
So, a project with no specification to speak of, with "okayish" API that is slow as molasses by default out of the gate [1] keeps blaming its users for its own failure because somehow it's a plane, and not a glorified overengineered Makefile.
[1] A reminder, if you will, that gradle managed to come up with caching configs to speed up its startup time only in version 8, after 15 years of development.
But for time being maven is way easier to configure and understand.
Literally no one complaining about gradle being slow is doing that. Allmost all of gradle's problems come not from people using it, but from Gradle itself.
I mean, you said it yourself: in 15 years the state of their API docs is "okayish". But somehow people are still expected to make sense of this shit because apparently it's a plane? But planes famously have extensive documentation, and procedures, and decades of expertise available. Exactly unlike gradle.
I actually really like Mill, but it is very small still. I’m unaware of too many playing in the same categories as Gradle.
I know of at least one project who just wrote everything in Python because current build tools invariably suck: https://tonsky.me/blog/python-build/
So, besides gradle and bazel, what else is there?
> No external dependencies may be used
But the real meaning is that you're not allowed to use external libraries, rather than build tool related dependency.
“I discard cache and it is so slow, aarghhh”
if you do that, you should also include programming time, and divide both by the number of runs the code will have over its lifetime. Also add an appropriate fraction of the time needed to learn to program.
In such a challenge, that likely would make a very naive version win.
Apart from being impractical, I think that would be against the idea behind this challenge.
Not if you give a realistic number for an actual database of this scale. Tens of hours of dev time isn't much after you divide it by a few million.
https://news.ycombinator.com/item?id=38866073
BTW asking ChatGPT to utilize all cores did not yield anything working in reasonable time.
Multiple languages: https://github.com/gunnarmorling/1brc/discussions My repo: https://github.com/buybackoff/1brc
Or at the very least, convert the input into a more convenient binary format for the following runs.
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:
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....). 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:
(13 rows)Sigh, pg16 is still pretty conservative about parallelism, so let's crank it up.
top(1) is showing that we're burying the CPU:1) use the integer version of generate_series, the 1e9 leads to the floating point version being chosen
2) move the generate_series() to the select list of a subselect - for boring reasons, that we should fix, the FROM version materializes the result first
3) using COPY is much faster, however a bit awkward to write
psql -Xq -c 'COPY (SELECT (1000random())::int2 as city, (random()random()*1100)::int2 temp FROM (SELECT generate_series(1,1e9::int8))) TO STDOUT WITH BINARY' | psql -Xq -c 'COPY temps_int2 FROM STDIN WITH BINARY'
1/10th scale tests:
==> 32sec ==> 90sec ==> 45sec (still not faster!)Of course, if we really want to "go fast" then we want parallel loading, which means firing up N postgresql backends and each generate and write the data concurrently to different tables, then each compute a partial summary in N summary tables, and finally merge them together.
==> 32sec (saturates one core)The ultimate would be to hack into postgres and skip everything and just write the actual filesystem files in-place using knowledge of the file formats, then "wire in" these files to the database system tables. This normally gets hairy (e.g. TOAST) but with a simple table like this, it might be possible. This is a project I've always wanted to try.
We (postgres) should fix that at some point... The difference basically is that there's a dedicated path to insert many tuples at once that's often used by COPY that isn't used by INSERT INTO ... SELECT. The logic for determining when that optimization is correct (consider e.g. after-insert per-row triggers, the trigger invocation for row N may not yet see row N+1) is specific to COPY right now. We need to generalize it to be usable in more places.
To be fair, part of the reason the COPY approach is faster is that the generate_series() query actually uses a fair bit of CPU on its own, and the piped psql's lead to the data generation and data loading being run separately. Of course, partially paying for that by needing to serialize/deserialize the data and handling all the data in four processes.
When doing the COPYs separately to/from a file, it actually takes longer to generate the data than loading the data into an unlogged table.
Loading into a logged table is a bit slower, at 20250.835 ms.> Of course, if we really want to "go fast" then we want parallel loading, which means firing up N postgresql backends and each generate and write the data concurrently to different tables, then each compute a partial summary in N summary tables, and finally merge them together.
With PG >= 16, you need a fair bit of concurrency to hit bottlenecks due to multiple backends loading data into the same table with COPY. On my ~4 year old workstation I reach over 3GB/s, with a bit more work we can get higher. Before that the limit was a lot lower.
If I use large enough shared buffers so that IO does not become a bottleneck, I can load the 1e9 rows fairly quickly in parallel, using pgbench:
That's just 1.2GB/s, because the bottleneck is the per-row and per-field processing, due to their narrowness.> The ultimate would be to hack into postgres and skip everything and just write the actual filesystem files in-place using knowledge of the file formats, then "wire in" these files to the database system tables. This normally gets hairy (e.g. TOAST) but with a simple table like this, it might be possible. This is a project I've always wanted to try.
I doubt that will ever be a good idea. For one, the row metadata contain transactional information, that'd be hard to create correctly outside of postgres. It'd also be too easy to cause issues with corrupted data.
However, there's a lot we could do to speed up data loading performance further. The parsing that COPY does, uhm, show signs of iterative development over decades. Absurdly enough, that's where the bottleneck most commonly is right now. I'm reasonably confident that there's at least 3-4x possible ...
I've reproduced the speed difference between pg COPY vs various cases.
Some results (middle result of 3 stable runs) from 1.4GB BINARY dump:
Note: I tried increasing the blocksize (--with-blocksize) and also MAX_BUFFERED_TUPLES (copyfrom.c:65) but as expected they didn't help, I guess n=1000 tuples amortizes the overhead.I think it actually shows that you're IO bound (the 'D' in the 'S' column). On my workstation the query takes ~10.9s after restarting postgres and dropping the os caches. And this is a four year old CPU that wasn't top of the line at the time either.
> 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 ;
Note that you dropped the limit 5 here. This causes the query to be a good bit slower, the expensive part here is all the array unnesting, which only needs to happen for the actually selected cities.
On my workstation the above takes 1.8s after adding the limit 5.
It does, but I restarted postgres and cleared the OS cache.
Btw, the primary bottleneck for the array-ified query is the unnest() handling in the functions. The minimal thing would be to make the functions faster, e.g. via:
CREATE OR REPLACE FUNCTION array_avg(_data anyarray) RETURNS numeric IMMUTABLE PARALLEL SAFE LANGUAGE sql AS $$ select avg(a) from (SELECT unnest(_data) as a) $$;
But that way the unnest is still done 3x. Something like
should be faster.> 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
> 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
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.
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.
This might become a contest of judging what is fair pre-computing and what is not.
That's why machine learning contests don't let participants see the final data.
A run consists of:
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.
If the language is garbage collected, or if the test is randomized you obviously don't want to look at the minimum.
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.
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.
https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... is a good piece on the subject.
There can't be outliers in terms of fastness; the CPU doesn't accidentally run the program much faster.
But then again, what the hell do I know...
[0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
[0] https://twitter.com/mtopolnik/status/1742652716919251052
* 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
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.
It's very cheap to detect station name collisions - just sample ~10,000 points in the file, and hope to find at least one of each station. If you find less stations than the full run, you haven't yet seen them all, keep hunting. If you find two that collide, fall back to the slow method. Checking 0.00001% of the dataset is cheap.
In other words: Cuckoo is a strategy to react to the case if two values map to the same hash. But how to know weather you have two different values, or two of the same, if they have an identical hash?
Simply add up all the bytes of all seen placenames while running your fast algorithm. This is effectively a checksum of all bytes of placename data.
Then at the end, calculate the 'correct' name-sum (which can be done cheaply). If it doesn't match, a collision occurred.
That might help against algorithms that are (accidentally, or on purpose) tuned to the specific dataset.
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
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)
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.
I.e. avg of {22.5, 23, 24} = 23.17... But:
1. 22.5
2. (22.5 + 23)/2 = 22.75
3. (22.75 + 24)/2 = 23.375
Would have been more interesting with something like median/k-th percentile, or some other aggregation not as easy.
https://www.felixcloutier.com/x86/phminposuw
Also will I get pilloried if I just make it a big StreamOf thing? ;-)
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
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.
In the first one, the table is dropped, recreated, populated and queries. In the second example, the table is created from a file FDW to the CSV file. In both examples the loading time is included in the total time
Very nice! Is this time for the first run or second? Is there a big difference between the first and second run, please?
https://stats.stackexchange.com/a/235151/1036
I am not sure if `n*old_mean` is a good idea. Wellford's is typically something like inside the loop
count += 1; delta = current - mean; mean += delta/count;