Single line solve using clickhouse-local or duckdb.
> No external dependencies may be used
The One Billion Row Challenge
141–150 of 366 posts
Re: The One Billion Row Challenge
#142Isn'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.
Daniel Lemire has an interesting talk on this: https://www.youtube.com/watch?v=wlvKAT7SZIQ. They key takeaway is that the disk is rarely the bottleneck.
Re: The One Billion Row Challenge
#143Earlier quoted context omitted.
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 s…
> 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.
could 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.
Re: The One Billion Row Challenge
#144Isn'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.
A 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 clea…
I 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.
Re: The One Billion Row Challenge
#145Would offering a cash prize increase or decrease the quality of submissions?
Re: The One Billion Row Challenge
#146Earlier quoted context omitted.
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.
That 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.
Of course, I assume names are also randomly generated. But it might be the case that they are all ASCII-only, which can be exploited.
Re: The One Billion Row Challenge
#147As 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/jav...
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. [0] https://twitter.c…
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.
Re: The One Billion Row Challenge
#148Earlier quoted context omitted.
> 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.
could 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.
Yes. I'm not sure it'll help, but def worth a try.
Re: The One Billion Row Challenge
#149Single line solve using clickhouse-local or duckdb.
correct. 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
Re: The One Billion Row Challenge
#150Earlier quoted context omitted.
Gradle is faster than what? Than maven? Maybe. But not than Go or Cargo.
Itself. > 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 macro…
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.