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

281–290 of 366 posts

Re: The One Billion Row Challenge

#281

Post by ykonstant »

codeflo wrote: post #184
londons_explore wrote: post #144

Earlier quoted context omitted.

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…

> any reasonably performant implementation would be faster not only than NVMe Saturating NVMe bandwidth is wicked hard if you don't know what you're doing. Most people think they're I/O bound because profiling hinted at some read() function somewhere, when in fact they're CPU bound in a runtime layer they don't understand.

Can you elaborate on the runtime layers and how to affect them?

Re: The One Billion Row Challenge

#282

Post by marginalia_nu »

alkonaut wrote: post #217
jerf wrote: post #172

Earlier quoted context omitted.

Only if you validate the UTF-8 as being valid. If you just accept that it is you can treat it as just some bytes. Nothing in the spec I see requires processing UTF-8 as an actual Unicode string. The easiest way to handle Unicode is to not handle it at all, and just shove it down the line. This is often even correct, as long as you don't need to do any string operations on it. If the author wanted to play Unicode game…

Since the tail of the line has a known format I guess we are rescued by the fact that the last 0x3B is the semicolon as the rest is just a decimal number. We can’t know the first 0x3B byte is the semicolon since the place names are only guaranteed to not contain 0x3B but can contain 0x013B. So a parser should start from the rear of the line and read the number up to the semicolon and then it can treat the place name…

I'm not sure scanning backwards this helps. Running in reverse you still need to look for a newline scanning over an UTF-8 string which might plausibly contain a newline byte.

I'm no UTF-8 guru, but I think you might be possible to do this sort of a springboard for skipping over multi-byte codepoints, since as far as I understand the upper bits of the first byte encodes the length:

    byte utfByte1 = (byte) (val & 0xF0);

    if (utfByte1 == (byte) 0xF0) { // 4 byte codepoint 
      // ignore 3
    }
    else if (utfByte1 == (byte) 0xE0) { // 3 byte codepoint
      // ignore 2
    }
    else if (utfByte1 == (byte) 0xC0) { // 2 byte codepoint
      // ignore 1
    }

Re: The One Billion Row Challenge

#283

Post by switchbak »

londons_explore wrote: post #226
Jaxan wrote: post #215

Earlier quoted context omitted.

Go for it!

You nerd sniper you! But more seriously, the JVM's support for vector intrinsics is very basic right now, and I think I'd spend far more time battling the JVM to output the code I want it to output than is fun. Java just isn't the right language if you need to superoptimize stuff. Theoretically all of the above is super simple SIMD stuff, but I have a suspicion that SIMD scatter/gather (needed for the state lookup ta…

If you really want to nerd snipe, write an optimized version in a non-JVM language to compare to the fastest Java one. But that's kind of boring anyway, we've seen this play out a thousand times.

I still appreciate the intention of seeing how far we can squeeze performance of modern Java+JVM though. Too bad very few folks have the freedom to apply that at their day jobs though.

Re: The One Billion Row Challenge

#284

Post by spullara »

londons_explore wrote: post #160
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)

You have to compare the keys in order to figure out if you have a hash collision or a new key. Without first scanning the entire file to know what the list of keys are there isn't a way around it. Even determining that list of keys involves doing key comparisons for every row.

Re: The One Billion Row Challenge

#285

Post by dvko »

Very fun challenge that nerd sniped me right away. Had to do a C version in standard C99 with POSIX threads. It[1] clocks in at just under 4 seconds on my AMD Ryzen 4800U Laptop CPU.

Should run about 10-20% faster than that on the mentioned Hetzner hardware.

- Since we only do one decimal of floating point precision it uses integer math right from the get-go.

- FNV1-a hash with linear probing and a load factor well under 0.5.

- Data file is mmap’d into memory.

- Data is processed in 8 totally separate chunks (no concurrent data structures) and then those aggregations are in turn aggregated when all threads have finished.

1: https://github.com/dannyvankooten/1brc

Re: The One Billion Row Challenge

#286

Post by dvko »

divbzero wrote: post #274

I suspect Java is not the fastest language for this. I’d love to see unofficial contenders tackle this challenge using different languages.

There are a handful of implementations in other languages already. Here’s mine in C99: https://github.com/dannyvankooten/1brc

I’ve also seen versions in Rust, Go, Python, Clickhouse and DuckDB. The discussions tab on the GitHub repo lists some of these.

Re: The One Billion Row Challenge

#287

Post by refulgentis »

CamperBob2 wrote: post #273
refulgentis wrote: post #251

Earlier quoted context omitted.

I don't have a CS background and when I eventually had to do interviews for Google, "Calculate mean/median/mode of temperatures" was the interview question I went with, intending to avoid BS leetcode* I always worried it was too easy, but I'm heartened by how many comments miss the insight I always looked for and you named: you don't need to store a single thing. I do wonder if it'll work here, at least as simply as…

Streaming calculation of the exact median with no storage at all is non-trivial at best in the general case, and I'm not aware of any way to calculate the mode at all. Any pointers to the methods you used in your interview answers? If you came up with them on the fly, then... well, sign here for your bonus. Can you start Monday?

I am silly and wrote 'mode' and shouldn't have :P (wetware error: saw list of 3 items corresponding to leetcode and temperature dataset, my 3 were min/max/average, their 3 are mean/median/mode)

Re: The One Billion Row Challenge

#288

Post by dvko »

jmclnx wrote: post #263

Is there a way to create this file without having java ? This is for use on a BSD where Java may not work too well. Thanks

You can run the bin/create-sample program from this C implementation here: https://github.com/dannyvankooten/1brc

It’s just the city names + averages from the official repository using a normal distribution to generate 1B random rows.

Re: The One Billion Row Challenge

#289

Post by dvko »

weinzierl wrote: post #162

Unfortunately I have no time to code this up but things that I would try to make it fast: - Read with O_DIRECT (but compare it with the mmap approach). I know O_DIRECT gets much hate, but this could be one of the rare cases where it helps. - Use a simple array with sentinel and linear search for the station names. This is dumb, but if the number of stations is small enough this could beat the hash. (In the back of my…

I tried the linear search by station name in my first naive approach. Using a hashmap was at least 2-3x as fast with the ~415 distinct keys in the 1BRC dataset.
Post reply on HN