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

91–100 of 366 posts

Re: The One Billion Row Challenge

#91

Post by stabbles »

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/

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.

Re: The One Billion Row Challenge

#93

Post by gunnarmorling »

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

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.

Re: The One Billion Row Challenge

#95

Post by gunnarmorling »

josephg wrote: post #26
Hugsun wrote: post #18

Earlier quoted context omitted.

Given this requirement, they would be wise to have the test data be different from the example data. That would prevent overfitting optimizations.

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.

Re: The One Billion Row Challenge

#96

Post by spullara »

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 between the names.

[1] https://github.com/gunnarmorling/1brc/pull/56

Re: The One Billion Row Challenge

#97

Post by winrid »

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 looks like they mostly work in JS, so maybe it's the type definitions that look clunky.

Java is explicit, yes. This is intentional :)

Re: The One Billion Row Challenge

#99

Post by xoranth »

pclmulqdq wrote: post #27
fny wrote: post #17

Earlier quoted context omitted.

Rather than read the file into memory, memory mapping can be used.

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

Post reply on HN