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

111–120 of 366 posts

Re: The One Billion Row Challenge

#111

Post by qsort »

jimmyed wrote: post #101

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.

Agreed, the aggregations chosen here are embarrassingly parallel, you just keep the count to aggregate means.

Would have been more interesting with something like median/k-th percentile, or some other aggregation not as easy.

Re: The One Billion Row Challenge

#112

Post by johndough »

gunnarmorling wrote: post #95
josephg wrote: post #26

Earlier quoted context omitted.

I'm not sure that it is overfitting to optimize your code for the test set. The requirement is just that you don't break compatibility for arbitrary names in the process. This sort of thing shows up all the time in the real world - where, for example, 90% of traffic will hit one endpoint. Or 90% of a database is one specific table. Discovering and microoptimizing for the common case is an important skill.

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.

Re: The One Billion Row Challenge

#113

Post by troupo »

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)

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.

Re: The One Billion Row Challenge

#114

Post by ProblemFactory »

mayank wrote: post #86
JohnKemeny wrote: post #70

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

This is a pretty standard measure called the Trimmed Mean: https://statisticsbyjim.com/basics/trimmed-mean/

Variability in software runtime arises mostly from other software running on the same system.

If you are looking for a real-world, whole-system benchmark (like a database or app server), then taking the average makes sense.

If you are benchmarking an individual algorithm or program and its optimisations, then taking the fastest run makes sense - that was the run with least external interference. The only exception might be if you want to benchmark with cold caches, but then you need to reset these carefully between runs as well.

Re: The One Billion Row Challenge

#115

Post by mayank »

stabbles wrote: post #91
mayank wrote: post #86

Earlier quoted context omitted.

This is a pretty standard measure called the Trimmed Mean: https://statisticsbyjim.com/basics/trimmed-mean/

For performance benchmarking the minimal runtime is typically the best estimator if the computations are identical, cause it measures perf w/o interrupts. If the language is garbage collected, or if the test is randomized you obviously don't want to look at the minimum.

> the minimal runtime is typically the best estimator

Depends what you’re estimating. The minimum is usually not representative of “real world” performance, which is why we use measures of central tendency over many runs for performance benchmarks.

Re: The One Billion Row Challenge

#116

Post by rocqua »

lifthrasiir wrote: post #28
josephg wrote: post #26

Earlier quoted context omitted.

I'm not sure that it is overfitting to optimize your code for the test set. The requirement is just that you don't break compatibility for arbitrary names in the process. This sort of thing shows up all the time in the real world - where, for example, 90% of traffic will hit one endpoint. Or 90% of a database is one specific table. Discovering and microoptimizing for the common case is an important skill.

That's why I was so unsure. I think though, that it is generally better to have the input generator seeded and do not disclose the chosen seed in advance, which prevents overfitting to a single input and yet encourages overfitting to a much bigger class of inputs.

That invites probing submissions to figure out a good hash for all names from that one seed.

I think having the names for performance tests public is fine. But there should be correctness tests on sets with random names.

Re: The One Billion Row Challenge

#117

Post by School-Cotton »

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…

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.

Re: The One Billion Row Challenge

#118

Post by gunnarmorling »

cm2187 wrote: post #109
gunnarmorling wrote: post #93

Earlier quoted context omitted.

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

Yes, exactly. Retrieving the source data file from the page cache != storing and reloading precomputed results.

Re: The One Billion Row Challenge

#119

Post by gerikson »

lessbergstein wrote: post #103
gerikson wrote: post #80

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

I profiled my attempt, actually reading each line is the bottleneck.

Re: The One Billion Row Challenge

#120

Post by cm2187 »

winrid wrote: post #108
hknmtt wrote: post #100

first 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?? :)

Custom number parsing, minimising the number of memory allocations to not be punished by the garbage collector. All sort of micro optimisations that make those solutions a terrible way to showcase a language (i.e. you can write much clearer and concise code but obviously slower).
Post reply on HN