Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The One Billion Row Challenge

morling.dev

Post reply on HN
Print view View original

171–180 of 366 posts

Re: The One Billion Row Challenge

#171

Post by londons_explore »

vintermann wrote: post #151
londons_explore wrote: post #144

Earlier quoted context omitted.

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 shoul…

Are you sure that would give the same result? The first thing that struck me about this challenge is that there's going to be floating point precision issues.

All the data is only to one decimal place. You can shift the decimal place and do the whole thing with int's and get a 100% precise result.

Re: The One Billion Row Challenge

#172

Post by jerf »

londons_explore wrote: post #164
lifthrasiir wrote: post #11

> 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…

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.

Re: The One Billion Row Challenge

#173

Post by gerikson »

lessbergstein wrote: post #103
gerikson wrote: post #80

Earlier quoted context omitted.

A naive perl solution is really really slow compared to even the reference Java implementation. (I know, I've tried)

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.

1B lines is a lot, and Java ain't a slouch.

Re: The One Billion Row Challenge

#174

Post by lessbergstein »

gerikson wrote: post #119
lessbergstein wrote: post #103

Earlier quoted context omitted.

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.

I profiled my attempt, actually reading each line is the bottleneck.

Perl is always going to be much faster than Java at tasks like this. Use stdin and chomp() instead of reading each line explicitly.

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.

Re: The One Billion Row Challenge

#175

Post by aargh_aargh »

nathancahill wrote: post #139
arkh wrote: post #131

Earlier quoted context omitted.

I'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 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(temper…

Man, Postgres is so cool and powerful.

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.

Re: The One Billion Row Challenge

#176

Post by vintermann »

londons_explore wrote: post #171
vintermann wrote: post #151

Earlier quoted context omitted.

Are you sure that would give the same result? The first thing that struck me about this challenge is that there's going to be floating point precision issues.

All the data is only to one decimal place. You can shift the decimal place and do the whole thing with int's and get a 100% precise result.

You can, but will it be the same result? :) binary floating point can't represent 0.1 or 0.2 exactly.

To be fair, with only additions, and only a billion of them, you're probably fine working in floating point and rounding to one decimal in the end.

Re: The One Billion Row Challenge

#177

Post by lessbergstein »

gerikson wrote: post #173
lessbergstein wrote: post #103

Earlier quoted context omitted.

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. 1B lines is a lot, and Java ain't a slouch.

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.

https://www.perl.com/pub/2003/11/21/slurp.html/#:~:text=Anot....

Re: The One Billion Row Challenge

#178

Post by gigatexal »

lars_francke wrote: post #141
gigatexal wrote: post #104

Single line solve using clickhouse-local or duckdb.

> No external dependencies may be used

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

Re: The One Billion Row Challenge

#179

Post by lessbergstein »

petters wrote: post #60
lessbergstein wrote: post #14

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. https://stackoverflow.com/questions/277309/java-floating-poi...

It’s easy to solve but even fizzbuzz becomes complicated if you want double digit GB/s output.

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.

Re: The One Billion Row Challenge

#180

Post by gunnarmorling »

thomaswue wrote: post #136
gunnarmorling wrote: post #89

Earlier quoted context omitted.

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…

What are the constraints on station names - i.e. min length, max length, maximum number of different names?

Just 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

Post reply on HN