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

231–240 of 366 posts

Re: The One Billion Row Challenge

#231

Post by dist1ll »

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 think this approach can operate at RAM speed with just one core with AVX512, so no benefit in splitting across cores.

A single core can't saturate RAM bandwidth. Cores are limited by memory parallelism and latency. Most modern x86 server chips can retire 2 SIMD loads per clock cycle (i.e. 32GB/s @ 1GHz using AVX2), so AVX-512 is not necessary to max out per-core bandwidth - but if you're loading from DRAM you'll likely cap out much, much earlier (closer to 10-16GB/s on commodity servers).

As long as the majority of your data spills into RAM, you'll see a massive throughput cliff on a single core. With large streaming use-cases, you'll almost always benefit from multi-core parallelism.

It's very easy to test: allocate a large block of memory (ideally orders of magnitude larger than your L3 cache), pre-fault it, so you're not stalling on page faults, and do an unrolled vector load (AVX2/AVX-512) in a tight loop.

Re: The One Billion Row Challenge

#232

Post by weinzierl »

gpderetta wrote: post #205
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.

> beat linear search already at

The sources I found corroborate this. My 1000 elements rule of thumb is apparently way off.

Re: The One Billion Row Challenge

#233

Post by mikewarot »

mgaunard wrote: post #125

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

Clearly the fastest way to parse this is to load it all into RAM, and work backwards from the end. That has the advantage of putting the digits in ascending order, and then the delimiter, then the string... until EOF or NL is encountered.

Re: The One Billion Row Challenge

#234

Post by Jaxan »

lessbergstein wrote: post #183
mgaunard wrote: post #125

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

Yes, this is an extremely trivial problem. Anybody who knows how to program in more than one language is going to find this silly. awk or perl would finish it before jit compilation gets started.

Please try it out in awk. It would be interesting to see whether awk can do this in a few seconds.

Re: The One Billion Row Challenge

#235

Post by londons_explore »

dist1ll wrote: post #231
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 think this approach can operate at RAM speed with just one core with AVX512, so no benefit in splitting across cores. A single core can't saturate RAM bandwidth. Cores are limited by memory parallelism and latency. Most modern x86 server chips can retire 2 SIMD loads per clock cycle (i.e. 32GB/s @ 1GHz using AVX2), so AVX-512 is not necessary to max out per-core bandwidth - but if you're loading from DRAM you'll…

The goal is that none of the intermediate data spills - the only user of RAM is reading the input data.

But for that, you're right, the workload must be split across as many cores as necessary to keep DRAM maxed out or you're throwing away performance. Luckily this problem is easily split.

Re: The One Billion Row Challenge

#236

Post by brrrrrm »

wiseowise wrote: post #94
brrrrrm wrote: post #16

looking at the sample code I’m quite glad I’ve never really touched Java. What a clunky language

Ok, I’ll bite - why?

it feels like the characters-typed to functionality ratio is quite low. at the same time, the code isn't much cleaner and there's a lot of mental overhead in deciphering the abstractions (in this case Collector).

Re: The One Billion Row Challenge

#237

Post by lelanthran »

londons_explore wrote: post #154
camkego wrote: post #87

Earlier quoted context omitted.

There is a real issue with providing the contestant the real exact file that will be used in the contest. Because there are 1e9 shades of gray between hard coding the correct answer in a single line program which doesn't even read the input, and processing the file as if we don't know what it contains. This might become a contest of judging what is fair pre-computing and what is not. That's why machine learning conte…

Fix: A run consists of: * I generate random measurements with the provided script, which will be stored in a readonly file. * I run your program to calculate the results (and time it). * I run my baseline program and your entry is valid if my baseline program calculates the same results.

The filesystem has to be read-only as well, otherwise the first run can simply write the results to ~/.me_cheater and the program first reads that file before attempting to read the dataset.

Re: The One Billion Row Challenge

#238

Post by throwaway2037 »

mgaunard wrote: post #125

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

I agree. From here: https://news.ycombinator.com/item?id=38865942

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

If we assume worst case entries: -99.9;

That is 106 chars plus newline (1 or 2 chars). That could be 108 GB of data! And, I want to be so picky here: The README says "UTF-8" and "max length 100 characters". Eh, we could start a holy war here arguing about what does a character mean in UTF-8. Let's be generous and assume it means one (8-bit) byte (like C). I have good faith in the original author!

Some Googling tells me that the current fastest PCIe Gen5 NVMe drive is Crucial T700 w/ Sequential read (max., MB/s) @ 12,400. That is 8.7 seconds to read 108 GB of data. A few other comments mentioned that the sample file is only 12 GB, so that is 1 second, and 100% can be cached by Linux kernel for 2nd and later reads. However, if the test file is greater than 32 GB, you are definitely screwed for file system caching. You will have to pay a multi-second "I/O tax" to read the file each time. This seems to far outweigh any computation time.

Thoughts?

Last, I still think this is a great challenge. I think I just found my next interview question. This question is easy to understand and program a basic implementation. Further discussion can be fractally complex about the myriad of optimizations that could be applied.

No trolling: Can you imagine if someone tries this exercise in Python? There are a goofy amount of optimizations to deal with huge data in that language thanks to SciPy, Pandas and other friends. I am sure someone can write an insanely performant solution. (I know, I know: The original challenge says no external dependencies.)

Re: The One Billion Row Challenge

#240

Post by brrrrrm »

winrid wrote: post #97
wiseowise wrote: post #94

Earlier quoted context omitted.

Ok, I’ll bite - why?

It looks like they mostly work in JS, so maybe it's the type definitions that look clunky. Java is explicit, yes. This is intentional :)

yea, I guess it's the lack of human-friendly default assumptions mixed with prescriptive design patterns. definitely an anachronistic design intent :(
Post reply on HN