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

61–70 of 366 posts

Re: The One Billion Row Challenge

#61

Post by sweetjuly »

yardstick wrote: post #30
userbinator wrote: post #23

Earlier quoted context omitted.

Alternatively, "must be written in Java" can be interpreted to mean "must use the JVM to begin execution", and you can clearly spawn another process from Java...

Another rule was no external dependencies I guess you could from Java itself write a new binary and then run that binary, but it would be against the spirit of the challenge.

There's sun.misc.Unsafe which is a builtin that gives you raw read/write. Turn that into ROP, mmap your native program, and now you're full native :)

Re: The One Billion Row Challenge

#62

Post by rockwotj »

lifthrasiir wrote: post #42
rockwotj wrote: post #34

Earlier quoted context omitted.

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…

> double parsing In case you haven't noticed yet, the input format guarantees exactly one fractional digit, so you can read a single signed integer followed by `.` and one digit instead.

Yeah I missed this originally, and stuff could be faster with this assumption without a full double parser. The fastest java solution dies some near branchless decoding for these

Re: The One Billion Row Challenge

#63

Post by e63f67dd-065b »

yellow_lead wrote: post #59
e63f67dd-065b wrote: post #55

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

Ah I didn't actually follow the link to the github repo. I don't think that percludes pre-processing the input into something that needs no parsing, however, or to spawn a background daemon that prefetches everything in the right order.

The first run is indeed runtime, not build time, so technically I think I still count with pre-computation, sending that to the daemon (or just stashing it somewhere in /tmp, or even crazier patching the jarfile), and just printing it back out on the second run onwards.

Re: The One Billion Row Challenge

#65

Post by sixlelyt321 »

kaba0 wrote: post #32
vessenes wrote: post #31

Ooh fun, Advent of Code chaser! A fair comparison between languages should include the make and build times. I haven't used Java / Maven for years, and I'm reminded why, heading into minute 2 of downloads for './mvnw clean verify'.

Java build times are very fast. You are just measuring your internet speed here. (Also, gradle is faster as a build tool for incremental compilation)

But run time is slow, is that you want to convey?

Re: The One Billion Row Challenge

#67

Post by [deleted] »

cwillu wrote: post #33
bayindirh wrote: post #29

Earlier quoted context omitted.

This is done to simulate real-world performance. Your binary is not the only binary in the system and other services may be running as well. So fastest time is the happiest path and slowest is the unluckiest. The range of remaining three is what you expect to get 99% of the time on a real world system.

Any production where you're routinely scanning a text file with a million records is probably a batch process, and I'd be shocked if the usual performance wasn't much closer to the worst case than the average.

[deleted]

Re: The One Billion Row Challenge

#68

Post by vinay_ys »

bayindirh wrote: post #56
fragmede wrote: post #54

Earlier quoted context omitted.

> Your binary is not the only binary in the system and other services may be running as well. Technically yes, but these days most of my machines are single purpose VMs; database/load balancer/app server/etc, so it still seems weird not to take the fastest.

Then, your VM is not the only VM sharing the bare metal. Same thing applies, only on a slightly higher level. As long as you share the metal with other stuff (be it containers, binaries, VMs), there's always competition for resources, and your average time becomes your real world time.

Physical memory is not fungible like that across VMs. So, you can expect stuff loaded into memory to stay there unless your kernel inside the VM decides it not to.

Re: The One Billion Row Challenge

#69

Post by tutfbhuf »

wokwokwok wrote: post #47

I suppose it defeats the spirit of the game to, knowing your worst run is discarded, calculate the results on the first run by whatever slow method you want, save them somewhere useful, and just read the results and print them out on the following runs? Or at the very least, convert the input into a more convenient binary format for the following runs.

I thought the same, but to ensure fairness, I would suggest that the application should run in a stateless container without internet access, and the infrastructure (Hetzner VM) should be recreated from scratch for each run to eliminate all caches.

Re: The One Billion Row Challenge

#70

Post by JohnKemeny »

> The slowest and the fastest runs are discarded. The mean value of the remaining three runs is the result for that contender and will be added to the leaderboard.

I think it's better to discard the two slowest, or simply accept the fastest as the correct. There's (in my opinion) no good reason to discard the best runs.

Post reply on HN