4 ms·

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, bu

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup table of all temps and all place names. (~160,000) * autogenerate a state machine that will map each of the above 160,000 things, at any rotation within a 4 byte register, to a unique bin in a hash table. The state machine will have one 32 bit state register (16 bits to output, 16 to carry over to the next cycle) where every cycle a lookup in the state transition table is done, and the next 4 bytes of data XOR'ed on top. * run through all the data, at RAM speed, incrementing counters for each state the machine ends up in. (there will only be 65k). These counters fit fully in cache. * With just 32 bits of state, with AVX512 we can be running 512 copies of this in parallel if we like, per core! AKA, compute will not be the bottleneck. * from the values of the counters, you can calculate the answers. 65k is a far smaller number than 1 billion, so you don't need to do this bit fast. * for anything that doesn't map to a valid bin (higher/lower temperatures, unknown place names), just fallback to slow code (one state of the state machine can be reserved for 'escape to slow code'. Use these escapes for min/max handling too, since it will only happen a few thousand times). * I think this approach can operate at RAM speed with just one core with AVX512, so no benefit in splitting across cores.

deleted 3y ago
[deleted]
Jaxan 3y ago
Go for it!
- londons_explore 3y ago
  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 table) isn't implemented.
  - switchbak 3y ago
    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.
  - anonymoushn 3y ago
    It sounds like you're unfamiliar with vectorized string processing tasks, so you could surely learn a lot by working on an implementation of the proposed approach. I think it's fine to make it in C++ and then port to Java. For more such tasks you could go to highload.fun.
jodrellblank 3y ago
Where does your ~160,000 come from? There's a billion rows, couldn't there be a different place on every row giving a billion place names?
- londons_explore 3y ago
  There are only ~400 place names in the generated data. 160,000 = 400*400 The state machine generation would need to know all 400 - but it's easy enough to scan the first few hundred thousand rows to find them all, and have a fallback incase a name is seen that has never been seen before. (the fallback would be done by having the state machine jump to an 'invalid' state, and then at the end you check that that invalid state's counter is zero, and if it isn't, you redo everything with slow code).
  - tzs 3y ago
    > There are only ~400 place names in the generated data The README says the maximum number of unique place names is 10 000, so you should probably design for the fast case to handle that many instead of just going by what is in the database that it happens to be measuring with at the moment.
- londons_explore 3y ago
  This code is only fast in the 'happy' case (ie. ~400 unique places, with no odd distributions, temperatures with a std dev of 10 from a mean between 0 and 40). It is still correct in the 'unusual' cases, but would be slow because it would revert to fallback code.
floobertoober 3y ago
I would ask for clarification about the rules - it isn't clear to me whether code that is special cased for the known 400 place names (even if it supports additional names via a slower path) would be considered valid: > Q: Can I make assumptions on the names of the weather stations showing up in the data set? > A: No, while only a fixed set of station names is used by the data set generator, any solution should work with arbitrary UTF-8 station names (for the sake of simplicity, names are guaranteed to contain no ; character).
- londons_explore 3y ago
  The code wouldn't be special cased... it would run through the first 10,000 or so rows to find out the dataset to generate the state transition table. If any invalid entry is found later, you'll end up in an invalid state, and can detect that case and fall back to slow code (or even theoretically update the state transition table and return to the fast path).
  - btilly 3y ago
    Even simpler. Just have a Dictionary mapping place name to ID. The slow path is "I haven't seen this name before and I need to store it, making sure that I'm not racing any other thread doing the same." You'd have an upper limit on how many place names you can have. But no hard coding of what they are.
dmoy 3y ago
> run through all the data, at RAM speed, Is the data given in RAM or do you have to wait for spinning rust I/0 for some GB amount of data?
- londons_explore 3y ago
  The test procedure is to run the code 5 times. Even if it isn't in cache the first time, it will be in the OS cache (ie. RAM) for the 2nd-5th runs. The test machine has 32GB RAM, while the data file is only 12GB, so it ought to be fully cached.
dist1ll 3y ago
> I think this approach can operate at RAM speed with just one core with AVX512, so no benefit in splitting across cores. A single core can't saturate RAM bandwidth. Cores are limited by memory parallelism and latency. Most modern x86 server chips can retire 2 SIMD loads per clock cycle (i.e. 32GB/s @ 1GHz using AVX2), so AVX-512 is not necessary to max out per-core bandwidth - but if you're loading from DRAM you'll likely cap out much, much earlier (closer to 10-16GB/s on commodity servers). As long as the majority of your data spills into RAM, you'll see a massive throughput cliff on a single core. With large streaming use-cases, you'll almost always benefit from multi-core parallelism. It's very easy to test: allocate a large block of memory (ideally orders of magnitude larger than your L3 cache), pre-fault it, so you're not stalling on page faults, and do an unrolled vector load (AVX2/AVX-512) in a tight loop.
- londons_explore 3y ago
  The goal is that none of the intermediate data spills - the only user of RAM is reading the input data. But for that, you're right, the workload must be split across as many cores as necessary to keep DRAM maxed out or you're throwing away performance. Luckily this problem is easily split.
- menaerus 3y ago
  > A single core can't saturate RAM bandwidth. I was also intrigued by the same statement and was wondering about it as well. For AMD I don't know but on Intel I believe that each L1 cache-miss is going to be routed through the line-fill-buffers (LFB) first before going to L2/L3. Since this LFB is only 10-12 entries large, this number practically becomes the theoretical limit on the number of (load) memory operations each core can issue at a time. > Most modern x86 server chips can retire 2 SIMD loads per clock cycle (i.e. 32GB/s @ 1GHz using AVX2), I think in general yes but it appears that ALU on Alderlake and Saphire Rapids has 3 SIMD load ports so they can execute up to 3x SIMD AVX2 mm256_load_si256 per clock cycle.
toth 3y ago
You don't need the look up table. All you are asked for is min/mean/max which can all be computed in one pass without storing the data. All you need is a hash table with 400 entries and 3 floats (running min, mean and max) and and int (count, for updating running mean). That's just 16 bytes, if you use 16 bytes for name of station you can fit everything under 16K. IO will dominate the running time for this, and JSON parsing will be second.
- toth 3y ago
  s/JSON/string/
  - Twirrim 3y ago
    I took a few shots at this in rust (following on from https://www.reddit.com/r/rust/comments/18ws370/optimizing_a_one_billion_row_challenge_in_rust/ https://www.reddit.com/r/rust/comments/18ws370/optimizing_a_...), and every single time the bottleneck was down to the string parsing, everything else was largely irrelevant. You can do this whole thing in about 24 seconds, as long as you're smart about how you chunk up the text and leverage threading. https://github.com/coriolinus/1brc/blob/main/src/main.rs https://github.com/coriolinus/1brc/blob/main/src/main.rs
    - toth 3y ago
      Interesting, I guess that makes sense. Having a quick look at your code, couple of thoughts: - You shouldn't bother with parsing and validating UTF-8. Just pretend it's ASCII. Non ASCII characters are only going to show up in the station name anyway, and all you are doing with it is hashing it and copying it. - You are first chopping the file into line chunks and then parsing the line. You can do it it one go, just look at each character byte by byte until you hit a semicolon, and compute a running hash byte by byte. You can also parse the number into an int (ignoring decimal point) using custom code and be faster than the generic float parser. - If instead of reading the file using standard library, you mmap it, should also speed things up a bit.
- usefulcat 3y ago
gpderetta 3y ago
> autogenerate a state machine that will map each of the above 160,000 things, at any rotation within a 4 byte register, to a unique bin in a hash table. The state machine will have one 32 bit state register (16 bits to output, 16 to carry over to the next cycle) where every cycle a lookup in the state transition table is done, and the next 4 bytes of data XOR'ed on top. You are basically describing a perfect hash, right?
- londons_explore 3y ago
  nearly but not quite - you can deliberately 'collide' when there is no data you need to keep going forward (the obvious example being when you end on a '\r' character). This is necessary to keep an upper bound on the state space. Remember that in the extreme, a state could mean "city A, temp zero, city b" - "0\rB" so it isn't a direct mapping from state machine state to city.
spullara 3y ago
You have to read and parse the entire file to find the place names.
LegionMammal978 3y ago
> With just 32 bits of state, with AVX512 we can be running 512 copies of this in parallel if we like, per core! AKA, compute will not be the bottleneck. How can the state machine be run in parallel, when the next state always has a dependency on the previous state? Also, how exactly would the state register be decoded? After you XOR it with 4 bytes of input, it could be practically any of the 4.7 billion possible values, in the case of an unexpected place name. And even for expected place names longer than 4 bytes, wouldn't they need several states each, to be properly distinguished from other names with a common prefix?

deleted 3y ago

[deleted]

Jaxan 3y ago

Go for it!

londons_explore 3y ago
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 table) isn't implemented.
- switchbak 3y ago
  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.
- anonymoushn 3y ago
  It sounds like you're unfamiliar with vectorized string processing tasks, so you could surely learn a lot by working on an implementation of the proposed approach. I think it's fine to make it in C++ and then port to Java. For more such tasks you could go to highload.fun.

jodrellblank 3y ago

Where does your ~160,000 come from? There's a billion rows, couldn't there be a different place on every row giving a billion place names?

londons_explore 3y ago
There are only ~400 place names in the generated data. 160,000 = 400*400 The state machine generation would need to know all 400 - but it's easy enough to scan the first few hundred thousand rows to find them all, and have a fallback incase a name is seen that has never been seen before. (the fallback would be done by having the state machine jump to an 'invalid' state, and then at the end you check that that invalid state's counter is zero, and if it isn't, you redo everything with slow code).
- tzs 3y ago
  > There are only ~400 place names in the generated data The README says the maximum number of unique place names is 10 000, so you should probably design for the fast case to handle that many instead of just going by what is in the database that it happens to be measuring with at the moment.
londons_explore 3y ago
This code is only fast in the 'happy' case (ie. ~400 unique places, with no odd distributions, temperatures with a std dev of 10 from a mean between 0 and 40). It is still correct in the 'unusual' cases, but would be slow because it would revert to fallback code.

floobertoober 3y ago

I would ask for clarification about the rules - it isn't clear to me whether code that is special cased for the known 400 place names (even if it supports additional names via a slower path) would be considered valid: > Q: Can I make assumptions on the names of the weather stations showing up in the data set? > A: No, while only a fixed set of station names is used by the data set generator, any solution should work with arbitrary UTF-8 station names (for the sake of simplicity, names are guaranteed to contain no ; character).

londons_explore 3y ago
The code wouldn't be special cased... it would run through the first 10,000 or so rows to find out the dataset to generate the state transition table. If any invalid entry is found later, you'll end up in an invalid state, and can detect that case and fall back to slow code (or even theoretically update the state transition table and return to the fast path).
- btilly 3y ago
  Even simpler. Just have a Dictionary mapping place name to ID. The slow path is "I haven't seen this name before and I need to store it, making sure that I'm not racing any other thread doing the same." You'd have an upper limit on how many place names you can have. But no hard coding of what they are.

dmoy 3y ago

> run through all the data, at RAM speed, Is the data given in RAM or do you have to wait for spinning rust I/0 for some GB amount of data?

londons_explore 3y ago
The test procedure is to run the code 5 times. Even if it isn't in cache the first time, it will be in the OS cache (ie. RAM) for the 2nd-5th runs. The test machine has 32GB RAM, while the data file is only 12GB, so it ought to be fully cached.

dist1ll 3y ago

> I think this approach can operate at RAM speed with just one core with AVX512, so no benefit in splitting across cores. A single core can't saturate RAM bandwidth. Cores are limited by memory parallelism and latency. Most modern x86 server chips can retire 2 SIMD loads per clock cycle (i.e. 32GB/s @ 1GHz using AVX2), so AVX-512 is not necessary to max out per-core bandwidth - but if you're loading from DRAM you'll likely cap out much, much earlier (closer to 10-16GB/s on commodity servers). As long as the majority of your data spills into RAM, you'll see a massive throughput cliff on a single core. With large streaming use-cases, you'll almost always benefit from multi-core parallelism. It's very easy to test: allocate a large block of memory (ideally orders of magnitude larger than your L3 cache), pre-fault it, so you're not stalling on page faults, and do an unrolled vector load (AVX2/AVX-512) in a tight loop.

londons_explore 3y ago
The goal is that none of the intermediate data spills - the only user of RAM is reading the input data. But for that, you're right, the workload must be split across as many cores as necessary to keep DRAM maxed out or you're throwing away performance. Luckily this problem is easily split.
menaerus 3y ago
> A single core can't saturate RAM bandwidth. I was also intrigued by the same statement and was wondering about it as well. For AMD I don't know but on Intel I believe that each L1 cache-miss is going to be routed through the line-fill-buffers (LFB) first before going to L2/L3. Since this LFB is only 10-12 entries large, this number practically becomes the theoretical limit on the number of (load) memory operations each core can issue at a time. > Most modern x86 server chips can retire 2 SIMD loads per clock cycle (i.e. 32GB/s @ 1GHz using AVX2), I think in general yes but it appears that ALU on Alderlake and Saphire Rapids has 3 SIMD load ports so they can execute up to 3x SIMD AVX2 mm256_load_si256 per clock cycle.

toth 3y ago

You don't need the look up table. All you are asked for is min/mean/max which can all be computed in one pass without storing the data. All you need is a hash table with 400 entries and 3 floats (running min, mean and max) and and int (count, for updating running mean). That's just 16 bytes, if you use 16 bytes for name of station you can fit everything under 16K. IO will dominate the running time for this, and JSON parsing will be second.

toth 3y ago
s/JSON/string/
- Twirrim 3y ago
  I took a few shots at this in rust (following on from https://www.reddit.com/r/rust/comments/18ws370/optimizing_a_one_billion_row_challenge_in_rust/ https://www.reddit.com/r/rust/comments/18ws370/optimizing_a_...), and every single time the bottleneck was down to the string parsing, everything else was largely irrelevant. You can do this whole thing in about 24 seconds, as long as you're smart about how you chunk up the text and leverage threading. https://github.com/coriolinus/1brc/blob/main/src/main.rs https://github.com/coriolinus/1brc/blob/main/src/main.rs
  - toth 3y ago
    Interesting, I guess that makes sense. Having a quick look at your code, couple of thoughts: - You shouldn't bother with parsing and validating UTF-8. Just pretend it's ASCII. Non ASCII characters are only going to show up in the station name anyway, and all you are doing with it is hashing it and copying it. - You are first chopping the file into line chunks and then parsing the line. You can do it it one go, just look at each character byte by byte until you hit a semicolon, and compute a running hash byte by byte. You can also parse the number into an int (ignoring decimal point) using custom code and be faster than the generic float parser. - If instead of reading the file using standard library, you mmap it, should also speed things up a bit.
usefulcat 3y ago

gpderetta 3y ago

> autogenerate a state machine that will map each of the above 160,000 things, at any rotation within a 4 byte register, to a unique bin in a hash table. The state machine will have one 32 bit state register (16 bits to output, 16 to carry over to the next cycle) where every cycle a lookup in the state transition table is done, and the next 4 bytes of data XOR'ed on top. You are basically describing a perfect hash, right?

londons_explore 3y ago
nearly but not quite - you can deliberately 'collide' when there is no data you need to keep going forward (the obvious example being when you end on a '\r' character). This is necessary to keep an upper bound on the state space. Remember that in the extreme, a state could mean "city A, temp zero, city b" - "0\rB" so it isn't a direct mapping from state machine state to city.

spullara 3y ago

You have to read and parse the entire file to find the place names.

LegionMammal978 3y ago

> With just 32 bits of state, with AVX512 we can be running 512 copies of this in parallel if we like, per core! AKA, compute will not be the bottleneck. How can the state machine be run in parallel, when the next state always has a dependency on the previous state? Also, how exactly would the state register be decoded? After you XOR it with 4 bytes of input, it could be practically any of the 4.7 billion possible values, in the case of an unexpected place name. And even for expected place names longer than 4 bytes, wouldn't they need several states each, to be properly distinguished from other names with a common prefix?