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

201–210 of 366 posts

Re: The One Billion Row Challenge

#201

Post by londons_explore »

anonymoushn wrote: post #194
londons_explore wrote: post #147

Earlier quoted context omitted.

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

It seems like you have to run the slow collision-resistant thing over the whole file.

Collision detection is far cheaper. One method:

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.

Re: The One Billion Row Challenge

#202

Post by londons_explore »

menaerus wrote: post #192
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…

> The total file is ~12 gigabytes, so we should expect to be able to get the task done in 0.3 seconds or so. How? EPYC-Milan features PCIe 4.0 and theoretical maximum throughput of x4 sequential read is ~8GB/s. In bare-metal machines, this figure is rather closer to 5-6GB/s, and in cloud environments such as CCX33, I imagine it could be even less. So, unless I am missing something you'd need ~2 seconds only to read t…

This assumes the file is already in page cache, and therefore already in RAM. The 0.3 seconds is the time to get it from RAM to the CPU L3 cache.

Re: The One Billion Row Challenge

#203

Post by anonymoushn »

londons_explore wrote: post #201
anonymoushn wrote: post #194

Earlier quoted context omitted.

It seems like you have to run the slow collision-resistant thing over the whole file.

Collision detection is far cheaper. One method: 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.

You can design inputs that defeat this scheme though. I thought the point was to be correct for all valid inputs.

Re: The One Billion Row Challenge

#205

Post by gpderetta »

weinzierl wrote: post #162

Unfortunately I have no time to code this up but things that I would try to make it fast: - Read with O_DIRECT (but compare it with the mmap approach). I know O_DIRECT gets much hate, but this could be one of the rare cases where it helps. - Use a simple array with sentinel and linear search for the station names. This is dumb, but if the number of stations is small enough this could beat the hash. (In the back of my…

> Read with O_DIRECT

apparently the challenge explicitly allow for warming up the os cache on a prior run, so O_DIRECT would be disadvantaged here as the working set fits in memory.

edit: also in my very simple tests a good hashmap can beat linear search already at <10 items. It depends a lot on the hash function cost.

Re: The One Billion Row Challenge

#206

Post by sobellian »

lessbergstein wrote: post #177
gerikson wrote: post #173

Earlier quoted context omitted.

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

If it isn't hard, then perhaps you could demonstrate with a complete perl program that you think should beat java.

Re: The One Billion Row Challenge

#207

Post by londons_explore »

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 table of all temps and all place names. (~160,000)

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

* run through all the data, at RAM speed, incrementing counters for each state the machine ends up in. (there will only be 65k). These counters fit fully in cache.

* With just 32 bits of state, with AVX512 we can be running 512 copies of this in parallel if we like, per core! AKA, compute will not be the bottleneck.

* from the values of the counters, you can calculate the answers. 65k is a far smaller number than 1 billion, so you don't need to do this bit fast.

* for anything that doesn't map to a valid bin (higher/lower temperatures, unknown place names), just fallback to slow code (one state of the state machine can be reserved for 'escape to slow code'. Use these escapes for min/max handling too, since it will only happen a few thousand times).

* I think this approach can operate at RAM speed with just one core with AVX512, so no benefit in splitting across cores.

Re: The One Billion Row Challenge

#208

Post by mgaunard »

londons_explore wrote: post #202
menaerus wrote: post #192

Earlier quoted context omitted.

> The total file is ~12 gigabytes, so we should expect to be able to get the task done in 0.3 seconds or so. How? EPYC-Milan features PCIe 4.0 and theoretical maximum throughput of x4 sequential read is ~8GB/s. In bare-metal machines, this figure is rather closer to 5-6GB/s, and in cloud environments such as CCX33, I imagine it could be even less. So, unless I am missing something you'd need ~2 seconds only to read t…

This assumes the file is already in page cache, and therefore already in RAM. The 0.3 seconds is the time to get it from RAM to the CPU L3 cache.

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.

Re: The One Billion Row Challenge

#209

Post by jdthedisciple »

sudodudeo wrote: post #169
hknmtt wrote: post #129

Earlier quoted context omitted.

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

Wouldn't this end up reducing the weight of earlier records by repeatedly dividing them into smaller chunks? 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

you have to weight the previous results appropriately then it works

Re: The One Billion Row Challenge

#210

Post by Hugsun »

johndough wrote: post #112
gunnarmorling wrote: post #95

Earlier quoted context omitted.

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.

Post reply on HN