I think the optimal strategy would be to use the "reduce" step in mapreduce. Have threads that read portions of the file and add data to a "list", 1 for each unique name. Then, this set of threads can "process" these lists. I don't think we need to sort, that'd be too expensive, just a linear pass would be good. I can't see how we can do SIMD since we want max/min which mandate a linear pass anyway.
The One Billion Row Challenge
101–110 of 366 posts
Re: The One Billion Row Challenge
#102Earlier quoted context omitted.
You wouldn't want to do this for a huge file. A very fast solution would use a small number of buffers and io_uring (or equivalent), keeping the page table and cache footprint small.
Yeah so I had a discussion on Twitter about this, turns out 12GB is small enough to fit into memory, and the author runs submissions by running a solution 5 times in a row, so using direct IO actually hurts because having the kernel cache is a way to enforce the file is in memory for the 4 runs after. I have a direct IO solution with SIMD string search and double parsing, just in C++ (using libraries). It runs in 6 s…
Wow, that's pretty fast considering how simple main.cc looks. I do love c++. Nice use of coroutines, too.
Re: The One Billion Row Challenge
#103Earlier quoted context omitted.
Perl would do it quite fast and it has the benefit of accessing posix primitives directly.
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.
Re: The One Billion Row Challenge
#104Single line solve using clickhouse-local or duckdb.
Re: The One Billion Row Challenge
#105Earlier quoted context omitted.
You wouldn't want to do this for a huge file. A very fast solution would use a small number of buffers and io_uring (or equivalent), keeping the page table and cache footprint small.
Dumb question. With io_uring, how do you handle lines that straddle between chunks? I'm asking since, AFAIU, the submitted requests are not guaranteed to be completed in order. (The easiest I can think of is submitting reads for "overlapped" chunks, I'm not sure there is an easier way and I'm not sure of how much performance overhead there is to it.)
You have to handle it manually. Remember the partial lines at the beginning/end of your chunks and merge them when their mates become available.
Re: The One Billion Row Challenge
#106first search result for averaging streaming data: https://nestedsoftware.com/2018/03/20/calculating-a-moving-a... so you just walk the file and read a chunk, update the averages and move on. the resource usage should be 0.000 nothing and speed should be limited by your disk IO.
Looking at some solutions they seem to include their own double parsing implementation. I built a home made serializer for csv files, I am using the default .net parsing functions and I find that parsing numbers/dates is by far the slowest part of the process on large files.
Re: The One Billion Row Challenge
#107Earlier 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.
[deleted]
Re: The One Billion Row Challenge
#108first search result for averaging streaming data: https://nestedsoftware.com/2018/03/20/calculating-a-moving-a... so you just walk the file and read a chunk, update the averages and move on. the resource usage should be 0.000 nothing and speed should be limited by your disk IO.
Yes, just read a file in chunks and spread the math across cores. How many ways could you possibly implement that?? :)
Re: The One Billion Row Challenge
#109Earlier quoted context omitted.
I think that would violate this rule > The computation must happen at application runtime, i.e. you cannot process the measurements file at build time (for instance, when using GraalVM) and just bake the result into the binary
Yeah, and I'd count caching results between runs into the same category, i.e. against the spirit of this challenge. Folks should keep in mind that the goal is to learn something new, rather than "winning" by cheating the rules.
Though the caching done by the OS (I/O for instance) is fair game
Re: The One Billion Row Challenge
#110The rule lawyer in me wants to spend the first run spinning up a background daemon that loads everything into memory, pins it there, and maybe even prefetches everything into cache as the subsequent runs perform basically a linear scan (you never have to pagemiss if you have an oracle!). > write a Java program for retrieving temperature measurement values from a text file and calculating the min, mean, and max temper…
I think the rules should stipulate each run is on its own tmpfs and all processes and pagecaches are cleared between runs.