Live data from Hacker News

The One Billion Row Challenge

morling.dev

241–250 of 366 posts

Re: The One Billion Row Challenge

#241
post #228
post #168

Earlier quoted context omitted.

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.

There are not many alternatives that are truly general build tools (not limited to single language/repository, etc), and properly parallelize and cache.

So, besides gradle and bazel, what else is there?

Re: The One Billion Row Challenge

#242
post #224
post #197

Earlier quoted context omitted.

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

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

Re: The One Billion Row Challenge

#243

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…

You don't need the look up table. All you are asked for is min/mean/max which can all be computed in one pass without storing the data. All you need is a hash table with 400 entries and 3 floats (running min, mean and max) and and int (count, for updating running mean). That's just 16 bytes, if you use 16 bytes for name of station you can fit everything under 16K.

IO will dominate the running time for this, and JSON parsing will be second.

Re: The One Billion Row Challenge

#244

Earlier quoted context omitted.

That sounds like cheating. The exercise says to process a large file that's on disk. If the data is in RAM then that's a whole different game.

The benchmark is run 5 times without flushing file system caches. If you mmap it, it will still be in memory between process runs. The author intended this FWIW

If the cache is not flushed, it will still be in memory between runs whether you mmap it or not.

Re: The One Billion Row Challenge

#245
post #243

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…

You don't need the look up table. All you are asked for is min/mean/max which can all be computed in one pass without storing the data. All you need is a hash table with 400 entries and 3 floats (running min, mean and max) and and int (count, for updating running mean). That's just 16 bytes, if you use 16 bytes for name of station you can fit everything under 16K. IO will dominate the running time for this, and JSON…

s/JSON/string/

Re: The One Billion Row Challenge

#246

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…

> autogenerate a state machine that will map each of the above 160,000 things, at any rotation within a 4 byte register, to a unique bin in a hash table. The state machine will have one 32 bit state register (16 bits to output, 16 to carry over to the next cycle) where every cycle a lookup in the state transition table is done, and the next 4 bytes of data XOR'ed on top.

You are basically describing a perfect hash, right?

Re: The One Billion Row Challenge

#247

Earlier quoted context omitted.

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

Even simpler. Just have a Dictionary mapping place name to ID. The slow path is "I haven't seen this name before and I need to store it, making sure that I'm not racing any other thread doing the same."

You'd have an upper limit on how many place names you can have. But no hard coding of what they are.

Re: The One Billion Row Challenge

#248
post #223

Earlier quoted context omitted.

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?

Your code is submitted (per parent comment)

Re: The One Billion Row Challenge

#249

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…

[deleted]

Re: The One Billion Row Challenge

#250
post #243

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…

You don't need the look up table. All you are asked for is min/mean/max which can all be computed in one pass without storing the data. All you need is a hash table with 400 entries and 3 floats (running min, mean and max) and and int (count, for updating running mean). That's just 16 bytes, if you use 16 bytes for name of station you can fit everything under 16K. IO will dominate the running time for this, and JSON…

> IO will dominate the running time for this, and JSON parsing will be second.

Memory bandwidth might dominate, but probably not I/O. The input file is ~12GB, the machine being used for the test has 32GB, and the fastest and slowest of five runs are discarded. The slowest run will usually be the first run (if the file is not already cached in memory), after which there should be little or no file I/O.

Post reply on HN