7 ms·
1BRC merykitty's magic SWAR: 8 lines of code explained in 3k words
- majke 3y agoCan you vectorize this with SSE. Most of the magic could be done with vector of four 32 bit integers. The question is if the cost of setting up the initial vector and extracting the result isnt prohibitive.
- gfody 3y agoI imagine code like this gets auto-vectorized either right from the start or after Hotspot detects a hotspot
- haxen 3y agoI wonder what you mean here. What code exactly would get auto-vectorized? Parsing the temperature surely not, since it's not in an array of fixed-size fields.
- gfody 3y agoonce you've done the work to implement parsing as branchless bitwise operations on integers I think that code can be extended automatically to operate on larger registers
- haxen 3y agoI think it would work if that was the only code in the loop. But the loop spans several more nontrivial operations, including hashtable insertion.
- dzaima 3y agoIt can, and various other 1BRC implementations have (though I doubt hotspot would manage to do it itself, never mind that most 1BRC submissions were run with Graal for the lower startup overhead). The 32×32→64-bit multiplication poses an issue on the default SSE2 as it has no 32-bit or 64-bit multiplication, but SSE4.1 adds exactly the needed thing, pmuldq (although, as that returns a 64-bit result, you'd need two of such to process a full vector of 32-bit ints).
- RaisingSpear 3y agoDid the challenge limit submissions to only using SSE2? Seems odd, given the prevalence of SSE4.2 support. PMULUDQ is in SSE2, though I haven't checked if that's usable for the problem here. There's also PMULLD in SSE4.1 if you only need a 32-bit result. But for summing digits, perhaps SSE2's PMADDWD could be sufficient?
- dzaima 3y agoThe official 1BRC was Java-only, so no using any architecture-specific SIMD at all; the test system did have AVX2 though, and that's what most non-competing native solutions (including mine) targeted. Completely forgot about pmuludq, that works too for SSE2. But a 32-bit result is insufficient for the magic number method, needs to be at least 36-bit. I originally used vpmaddubsw+vpmaddwd, but switched to vpmuldq for the reduced register pressure, and I was already only parsing 4 numbers in ymm registers so the 64-bit result didn't affect me (after parsing 4 temperatures I immediately did the respective hashmap stuff for each).
- haxen 3y agoThe temperature fields are interleaved with name fields, so I don't think you'd get any extra benefit from SSE. Also, since the temperature field is variable-sized, it would probably not pay off even if it was stored by column. SSE was successfully applied to finding the delimiter between the name and the temperature, though.
- dzaima 3y agoIt can still be beneficial - yes you need to load the temperatures individually, but there's enough operations afterward to make it worth it.
- deleted 3y ago[deleted]
- readthenotes1 3y agoWhy does they compute and throw away nextLineStart? long nextLineStart = ...
- robin_reala 3y agoThat’s explained at the end of the post: in the real code, that’s the most efficient place to calculate it, and it was passed back out as well.
- __float 3y agoThat was some key context lost in the simplification of the original code[1] for this blog post, though. The blog post's code returns the temperature (throwing away the next line), whereas the original adds it to a map and returns the next line. [1] https://github.com/gunnarmorling/1brc/blob/dfec2cdbe6a0334cff054f333ec4b4d9e4d775cf/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java#L165-L195 https://github.com/gunnarmorling/1brc/blob/dfec2cdbe6a0334cf...
- haxen 3y agoThere are many variations of the original code used in different solutions. Many of them return the temperature like the variant used in the post, but they split out the part that finds the decimal dot into a separate function. Then you can reuse that twice: to finish parsing the temperature, and to advance the cursor to the next row.
- pacaro 3y agoWe used to use the BCD opcodes for this kind of thing. Masking off the 0x30, shift digits (if you want packed BCD) I can't imagine that has been efficient for decades tho
- jsheard 3y agoThe BCD instructions are one of the few things that was dropped in the x86-64 transition, so it wouldn't work at all anymore.
- kragen 3y agothey'd never been extended to work on more than 8 bits, even in the 8086; they only really existed for 8080 compatibility, and arguably the 8080 primarily had them to ease the path from earlier intel processors designed for, if i'm not mistaken, literal pocket calculators in pocket calculators you have to display the result in decimal after performing a single arithmetic operation, so it's much more efficient to do the arithmetic in bcd than to convert from decimal to binary, perform the arithmetic operation, and then convert back
- pacaro 3y agoYeah, if you wanted numbers greater than 99 you had to use them in the x87 (if you had one)
- pcwalton 3y agoAgner says that AAA has latency 5 on Cannon Lake, so using that instruction is a bit faster than doing the operations manually. But if you vectorize (or use SWAR) I imagine you can start to beat the legacy instructions with larger numbers.
- jdright 3y ago> the real mystery is how a single guy working alone could come up with all this in just a few days Really not a mystery. This is not that complex for people with low level programming experience (embedded, (older) games, demoscene, performance systems, etc.). Knowing these tricks and knowing how to apply them is basically a requirement on these areas.
- AtlasBarfed 3y agoImo the most important class in comp sci is computer architecture, specifically one that takes you from gates to a rudimentary alu, registers, to microcode, to some form of assembly coding. There is nothing magical in computers once you can do that deconstruction in your head.
- AlotOfReading 3y agoBit twiddling hacks are increasingly becoming a lost art even in the embedded/low level space. There's relatively few people around with any day-to-day need for them and I've found myself deleting a lot of the legacy ones I find because the compiler situation has changed so much from when they were originally written. I think this is an excellent skills showcase, even if I don't think it's magical.
- at_a_remove 3y agoBack when the word "nanotechnology" used to mean itty-bitty robots* rather than some extremely fine chemical processes done in sequence, or extremely small particle size, I had wondered if we could get to the point of said itty-bity robots before all of the brilliant people who made playable games for restricted consoles like the Atari had retired. * More specifically, miniaturized robots consisting of one or more robot arms with multiple degrees of freedom, a CPU, some kind of storage (perhaps something like wound-up DNA serving as tape on reels), executing programs written by humans.
- MichaelZuo 3y agoThat concepts sounds like fantasy, cells are shaped like cells because 'itty-bitty robots', and most other configurations, don't work thermodynamically or physically or chemically at such small scales.
- WoodenChair 3y agoFor context on why you should read this: this is a well written article that explains in detail how some bitwise operations work to parse a temperature (think -10.3, or 3.4) with no conditionals (no if-statements or switches). This results in very fast parsing. The language used is Java but it could just as easily be C or Swift.
- mnau 3y agoResult is fast parsing with no error checking. If the input wasn't in expected format (e.g. different decimal separator), the result would be incorrect. Fun ss an exercise, but hard to understand, maintain.
- deleted 3y ago[deleted]
- plokhotnyuk 3y agoWhat an amazing step by step explanation! More than 2 years ago I found that byte array view var handles are quite suitable to cook efficient SWAR routines with Java/Scala. See a lot of other examples of SWAR usage, like parsing Base16/64 strings, java.time.* and number values directly from byte arrays: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/jsoniter-scala-core/jvm/src/main/scala/com/github/plokhotnyuk/jsoniter_scala/core/JsonReader.scala https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...
- quercusa 3y agoAs per the article: SWAR is "SIMD Within A Register"
- teo_zero 3y agoI remember the first time I read about this technique used by the Linux kernel to find the \0 at the end of the string. If course XORing with another char will detect that char instead. But before you run to implement it as a drop-in replacement for strlen() all over your code, please note that in real-world cases the string length is not guaranteed to be a multiple of 8. When you read the last long, you might overrun your memory buffer and trigger a page fault.
- Karellen 3y ago> When you read the last long, you might overrun your memory buffer and trigger a page fault. You know that page boundaries are always on a `PAGE_SIZE` alignment, which you can get with `getpagesize()` or `sysconf(_SC_PAGESIZE)`. ...but overrunning the declared size of a memory allocation is still UB, even if you don't trigger a page fault, so YMMV ;-)
- o11c 3y agoAlso, as I learned recently: UB minor faults are allowed to change under you. You're not guaranteed to get the same value next time you access them, even if nothing else in your process is touching that memory.
- Karellen 3y agoAnything is allowed to happen if your program invokes UB. All bets are off (according to the C standard/abstract machine) for the rest of the runtime of your program, from the first time it happens. In fact, because the compiler is allowed to re-order your program provided that the end result of any non-UB computation is the same (the "as-if" rule[0]), if part of your program invokes UB, it's possible for that to "reach backwards" and invalidate computations that appear to happen before the UB is/was invoked (by a straightforward reading of the source code). [0] https://en.wikipedia.org/wiki/As-if_rule https://en.wikipedia.org/wiki/As-if_rule
- o11c 3y ago
- winwang 3y agoIf people like stuff like this, the simdjson paper uses similar techniques, is extremely well-written and has great examples. Paper: https://arxiv.org/abs/1902.08318 https://arxiv.org/abs/1902.08318 Github: https://github.com/simdjson/simdjson https://github.com/simdjson/simdjson
- djmips 3y agoThis isn't SWAR though but I get how it might appeal.
- deleted 3y ago[deleted]
- teucris 3y agoGreat article and given the context of the code this is a brilliant solution, but note that this assumes that the data is well-formed. Much of the value in an effective, battled-worn parser is efficient error checking and recovery.
- Karellen 3y agoIt would be interesting to see a breakdown of the ways in which ill-formed inputs could affect the output. And how much work it would be to detect such inputs and return some kind of sentinel error value - in the same style as the current code. (Not quite interesting enough for me to do it myself though ;-)
- tayo42 3y agoPretty cool. I'll have to come back to this But can't someone just ask merry kitty where they got the idea from?
- Terretta 3y agoNot saying the idea came from this, but if you were coding in late 70s to mid 80s, you may well have written lots of code using these techniques because 6502 assembly was fun and manageable enough to just write your software in it, especially if you had a Beagle Bros book at hand.
- qingcharles 3y agoAnyone who coded in the demoscene too was writing oodles of weird bit-twiddling guff like this, from experience...
- mihaic 3y agoI think something like this was a lot more common knowledge around 20 years ago, and now seems like mystic arts. It just takes a mindset of thinking that everything is bytes and binary, and after you've seen a couple SWAR snippets of stuff like popcount or first significant bit you're able do it these inferences yourself.
- djmips 3y agoUsed to do SWAR on the 68000 to good effect. 4 bytes operated on in parallel in a single instruction. Tricky to handle the overflow IIRC. I really like this article!
- gigatexal 3y agoThis article helped me understand bit fiddling better than any before it. Thanks to the author and the author of the really novel Java solution to the 1BRC challenge.
- stavros 3y agoCan someone explain to me how the BRC isn't bottlenecked on I/O? I don't understand how the CPU is the bottleneck.
- benhoyt 3y agoLocal disk I/O is no longer the bottleneck on modern systems: https://benhoyt.com/writings/io-is-no-longer-the-bottleneck/ https://benhoyt.com/writings/io-is-no-longer-the-bottleneck/ In addition, the official 1BRC explicitly evaluated results on a RAM disk to avoid I/O speed entirely: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#evaluating-results https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva... "Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)"
- davidmurdoch 3y agoI was surprised by this recently when optimizing a build process that uses an intermediate write-to-disk step. I replaced the intermediate filesystem API with an in-memory one and it was not measurably faster. Not even by a single millisecond.
- 10000truths 3y agoHow much data were you writing? If you don't fill the OS's page cache and the SSD controller's DRAM cache, and you're not blocking on fsync() or O_DIRECT or some other explicit flushing mechanism, then you're not going to see much of a difference in throughput.
- davidmurdoch 3y agoOnly a few MB written then read, so that is a likely explanation.
- deleted 3y ago[deleted]
- stavros 3y ago
- kwillets 3y agoMultiplying digit bitfields by their respective powers of 10 and shift/adding via MUL is a (well?) known technique, see Lemire https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-quickly/ https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui... .
- MrYellowP 3y ago> the real mystery is how a single guy working alone could come up with all this in just a few days of casually doing an online challenge with a T-shirt and a coffee mug as a reward. Why is that a mystery? There's still people out there who actually know how to program a CPU and actually understand what they're doing. The real mystery is the lack of deeper understanding of most people who call themselves programmers, combined with the fact that they don't appear to be knowing that they're seriously lacking.
- londons_explore 3y agoThis algorithm could be done 32x in parallel with AVX instructions... But Java doesn't really support SIMD use of the CPU except in a very few specific cases, which is sad.
- haxen 3y agoCan you provide more details on how that would work? Given that the input is CSV rows and not an array of integers alone, and the fact that getting to the next row is dependent on finding the delimiter in the current row.
- anonymoushn 3y agoThere isn't really a dependency there. You can scan for a bunch of delimiters and save a bunch of row start and end positions and process the rows from there. If (unlike the solutions that won this challenge) you would like to use a hash that consumes all the bytes in the input, then scanning for all the delimiters and bucketizing strings by length also lets you avoid branch mispredictions caused by random lengths.
- londons_explore 3y agoYou could choose 32 start points approximately evenly through the file, and process starting at each point in parallel.
- dzaima 3y agoNot quite 32x as there's a 3-5 bytes of input per number, and a range of -999…999 for the output (and you'd generally want to load those consecutive bytes at the same time). 4x or 8x is certainly possible though; and you can even do that in Java with jdk.incubator.vector to some extent, although the available operations are somewhat limited, and Hotspot's codegen leaves enough to be desired.
- londons_explore 3y agoBut there are 1 billion rows... So plenty of parallelism. Your 32 lanes can be working on totally different parts of the dataset.
- neonsunset 3y agoYou don't need to do such SWAR tricks in C# - it offers first-class cross-platform SIMD API instead. Evidently, it works really well which can be observed on the example of a C# solution being the fastest at 1BRC that has been publicly seen so far: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-fastest-on-linux-my-optimization-journey/#results https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
- EE84M3i 3y agoThis state space is pretty small - is there a super-optimizer that will just spit out a similar result?