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

221–230 of 366 posts

Re: The One Billion Row Challenge

#221

Post by londons_explore »

jodrellblank wrote: post #218
londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

Where does your ~160,000 come from? There's a billion rows, couldn't there be a different place on every row giving a billion place names?

This code is only fast in the 'happy' case (ie. ~400 unique places, with no odd distributions, temperatures with a std dev of 10 from a mean between 0 and 40). It is still correct in the 'unusual' cases, but would be slow because it would revert to fallback code.

Re: The One Billion Row Challenge

#222

Post by lenkite »

pkolaczk wrote: post #150
wokwokwok wrote: post #44

Earlier quoted context omitted.

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

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.

Re: The One Billion Row Challenge

#223

Post by paxys »

rkangel wrote: post #198
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…

Have you considered having two datasets? The "development" dataset which is public, and the "competition" dataset which is private? That might help against algorithms that are (accidentally, or on purpose) tuned to the specific dataset.

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?

Re: The One Billion Row Challenge

#224

Post by kaba0 »

troupo wrote: post #197
kaba0 wrote: post #168

Earlier quoted context omitted.

It is your own failure if you beat the tool over yourself, for not having learnt it.

A tool 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 o…

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?

Re: The One Billion Row Challenge

#225

Post by floobertoober »

londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

I would ask for clarification about the rules - it isn't clear to me whether code that is special cased for the known 400 place names (even if it supports additional names via a slower path) would be considered valid:

> 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).

Re: The One Billion Row Challenge

#226

Post by londons_explore »

Jaxan wrote: post #215
londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

Go for it!

You nerd sniper you!

But more seriously, the JVM's support for vector intrinsics is very basic right now, and I think I'd spend far more time battling the JVM to output the code I want it to output than is fun. Java just isn't the right language if you need to superoptimize stuff.

Theoretically all of the above is super simple SIMD stuff, but I have a suspicion that SIMD scatter/gather (needed for the state lookup table) isn't implemented.

Re: The One Billion Row Challenge

#227

Post by dmoy »

londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

> run through all the data, at RAM speed,

Is the data given in RAM or do you have to wait for spinning rust I/0 for some GB amount of data?

Re: The One Billion Row Challenge

#228

Post by geodel »

kaba0 wrote: post #168
troupo wrote: post #156

Earlier quoted context omitted.

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

It is your own failure if you beat the tool over yourself, for not having learnt it.

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.

Re: The One Billion Row Challenge

#229

Post by londons_explore »

floobertoober wrote: post #225
londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

I would ask for clarification about the rules - it isn't clear to me whether code that is special cased for the known 400 place names (even if it supports additional names via a slower path) would be considered valid: > 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…

The code wouldn't be special cased... it would run through the first 10,000 or so rows to find out the dataset to generate the state transition table. If any invalid entry is found later, you'll end up in an invalid state, and can detect that case and fall back to slow code (or even theoretically update the state transition table and return to the fast path).

Re: The One Billion Row Challenge

#230

Post by londons_explore »

dmoy wrote: post #227
londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

> run through all the data, at RAM speed, Is the data given in RAM or do you have to wait for spinning rust I/0 for some GB amount of data?

The test procedure is to run the code 5 times. Even if it isn't in cache the first time, it will be in the OS cache (ie. RAM) for the 2nd-5th runs. The test machine has 32GB RAM, while the data file is only 12GB, so it ought to be fully cached.
Post reply on HN