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

151–160 of 366 posts

Re: The One Billion Row Challenge

#151

Post by vintermann »

londons_explore wrote: post #144
rockwotj wrote: post #128

Earlier quoted context omitted.

A few things: Disk access can certainly be parallelized, and NVMe is blazing fast, so the bottleneck is more the CPU than disk. There are systems that are built around around modern hardware that realize this (redpanda.com, where I work is one such example) Parsing is a lot of the compute time and some SIMD tricks like SWAR for finding delimiters can be helpful. Stringzilla is a cool library if you want to see a clea…

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…

Are you sure that would give the same result? The first thing that struck me about this challenge is that there's going to be floating point precision issues.

Re: The One Billion Row Challenge

#152

Post by kaba0 »

troupo wrote: post #113
kaba0 wrote: post #32

Earlier quoted context omitted.

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)

Gradle and fast should not be in the same sentence. I have no idea what gradle and its daemon do except spending orders of magnitude more time starting up than running the actual build. You're much better off running javac directly. Then it's fast.

Then someone in your team failed learning the bare minimum to write a sane gradle file, and are putting imperative stuff into the configuration phase.

For big projects, compiling only what’s necessary is a huge time win.

Re: The One Billion Row Challenge

#153

Post by Dylan16807 »

Someone wrote: post #122
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'.

> A fair comparison between languages should include the make and build times if you do that, you should also include programming time, and divide both by the number of runs the code will have over its lifetime. Also add an appropriate fraction of the time needed to learn to program. In such a challenge, that likely would make a very naive version win. Apart from being impractical, I think that would be against the i…

> In such a challenge, that likely would make a very naive version win.

Not if you give a realistic number for an actual database of this scale. Tens of hours of dev time isn't much after you divide it by a few million.

Re: The One Billion Row Challenge

#154

Post by londons_explore »

camkego wrote: post #87
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…

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.

Re: The One Billion Row Challenge

#155

Post by pkolaczk »

kaba0 wrote: post #75
pkolaczk wrote: post #39

Earlier quoted context omitted.

Gradle is faster than what? Than maven? Maybe. But not than Go or Cargo.

What step are we talking about? Javac itself is absolutely on the same order of magnitude speed as Go per loc, while rust is significantly slower (which makes sense, the latter is a properly optimizing compiler with heavy static analysis, while the former two just spews out java byte code/machine code). Gradle with a daemon is also pretty fast, you are just probably used to some complex project with hundreds of depen…

> Javac itself is absolutely on the same order of magnitude speed as Go per loc

Not really when it has to run on a cold JVM. And before it warms up, it’s already done.

Then you are in territory of keeping the compiler process between the runs, but that is a memory hog and also not always realiable (gradle often decides to run a fresh daemon for whatever reason).

So theoretically, in lab conditions yes, in practice no.

> while rust is significantly slower

Everybody repeats that but there is surprisingly little evidence in form of benchmarks. I can see rustic compiles over 50k Loc per second on average on my M2, which is roughly the same order of magnitude as Java. And checking without building is faster.

Re: The One Billion Row Challenge

#156

Post by troupo »

kaba0 wrote: post #152
troupo wrote: post #113

Earlier quoted context omitted.

Gradle and fast should not be in the same sentence. I have no idea what gradle and its daemon do except spending orders of magnitude more time starting up than running the actual build. You're much better off running javac directly. Then it's fast.

Then someone in your team failed learning the bare minimum to write a sane gradle file, and are putting imperative stuff into the configuration phase. For big projects, compiling only what’s necessary is a huge time win.

> Then someone in your team failed learning the bare minimum to write a sane gradle file

Then someone in over 15 years and 8 versions gradle failed to make a system that doesn't require "learning to write sane gradle files" to make sure that it's only two orders of magnitude and not five orders of magnitude slower than it can be.

> and are putting imperative stuff into the configuration phase

Has nothing to do with the slowness that is gradle.

> For big projects, compiling only what’s necessary is a huge time win.

It is, and no one is arguing with that

Re: The One Billion Row Challenge

#157

Post by kaba0 »

School-Cotton wrote: post #117
kaba0 wrote: post #75

Earlier quoted context omitted.

What step are we talking about? Javac itself is absolutely on the same order of magnitude speed as Go per loc, while rust is significantly slower (which makes sense, the latter is a properly optimizing compiler with heavy static analysis, while the former two just spews out java byte code/machine code). Gradle with a daemon is also pretty fast, you are just probably used to some complex project with hundreds of depen…

Just a nitpick, but the static analysis in Rust doesn’t account for most of why compilation is slow, as proven by the fact that cargo check is much faster than cargo build.

Yeah, I know. I believe it’s mostly the amount of LLVM IR that is the problem (e.g. each generic instantiation outputs by default a new copy of roughly the same code), isn’t it?

Re: The One Billion Row Challenge

#158

Post by throwaway167 »

somat wrote: post #78
Animats wrote: post #15

Earlier quoted context omitted.

It looks like the problem is dominated by reading in the data file. Some fast solutions just read the whole file into memory.

It would be a more interesting challenge if the data file were larger than the memory. I would love to see what people would come up with on some baby vm with 512 mb of ram. Even more interesting would be small ram, little local storage and a large file only available via network, I would like to see something other than http but realistically it would be http.

Sixteen thousand Excel 97 spreadsheets?

Re: The One Billion Row Challenge

#159

Post by troupo »

kaba0 wrote: post #75
pkolaczk wrote: post #39

Earlier quoted context omitted.

Gradle is faster than what? Than maven? Maybe. But not than Go or Cargo.

What step are we talking about? Javac itself is absolutely on the same order of magnitude speed as Go per loc, while rust is significantly slower (which makes sense, the latter is a properly optimizing compiler with heavy static analysis, while the former two just spews out java byte code/machine code). Gradle with a daemon is also pretty fast, you are just probably used to some complex project with hundreds of depen…

> Gradle with a daemon is also pretty fast

I've yet to see a project where Gradle daemon a) does anything useful and b) is acutally used by gradle itself (instead of seemingly doing everything from scratch, no idea what it does in the seconds it takes for it to start up).

Re: The One Billion Row Challenge

#160

Post by londons_explore »

spullara wrote: post #96

This has been super fun. My current PR[1] is another 15% faster than my entry in the README. Sadly I haven't been able to make any progress on using SIMD to accelerate any part of it. I think the issues with hashing could be easily covered by having the 500 city names in the test data also be randomly generated at test time. There is no way to ensure there aren't hash collisions without doing a complete comparison be…

1 billion rows, 500 unique values...

It becomes very possible to find an instance of each unique value, then runtime-design a hash algorithm where those 500 values don't collide.

Java allows self modifying code after all (and this challenge also allows native code, which can also be compiled-at-runtime)

Post reply on HN