9 ms·
Faster CRC32 on the Apple M1
- ntoskrnl 4y agoSo ARM64 has dedicated instructions for CRC32, but implementing it by hand using SIMD is still faster. Score another point for RISC.
- MichaelZuo 4y agoIt's very impressive someone messing around for a few hours could get the m1 chip to more than 2x the performance. Easy gains like that really shouldn't be possible, assuming Apple's silicon team are competent. Maybe there's some hidden gotcha here?
- deleted 4y ago[deleted]
- dzaima 4y agoCRC32X works on 8 bytes at a time and has a throughput of one invocation per cycle, whereas the SIMD operates on blocks in parallel (the chromium code does 64 bytes an iteration, with a lot of instruction-level parallelism too). Theoretically M1 could have thrown more silicon at it to allow more than one CRC32X invocation per cycle, but that's not very useful if you can achieve the same with SIMD anyway.
- AlotOfReading 4y agoIntel's algorithm is very clever and would take a lot of space to implement in hardware. The implementation underlying the CRC32** instructions is probably some set of shift registers. That's a pretty good space/speed tradeoff to make. My largely uninformed guess is that they added the instructions to get fast CRCs for the filesystem 'for free'. There aren't many other cases where software CRC can be a bottleneck that also use these polynomials.
- nicoburns 4y agoI feel like CRC32 may be simple enough (and close enough to the kind of operation like adding and bit-shifting that general-purpose CPUs are good at anyway, that perhaps it doesn't benefit as much from dedicated silicon as other algorithms would.
- Sirened 4y agoThis is way more common than you'd think, and it's not by accident. Engineering teams optimize the paths that are heavily used to get the biggest improvement across the platform as a whole. CRC32X is certainly not as heavily used as NEON and so if you're forced to decide between spending area on being able to fuse extra instructions for NEON and slightly improving throughput for CRC32X, the obvious choice is NEON. You see this way more obviously on Intel's x86-64 cores where many of the highly used instructions are fast path decoded but some of the weirder CISC instructions that nobody really uses are offloaded to very slow microcode.
- bee_rider 4y agoI wonder -- could CRC32X be something that would also, specifically, not as interesting for Apple? They are mostly optimizing for desktop workloads. I wonder if worrying about checksuming, especially maximizing the throughput of checksum operations, is more of a server thing. (Like we have to checksum when we download things on desktop, but that's a one-off, and I guess things get checksummed in the filesystem, but even the nice NVME drives are pretty slow from the CPUs point of view).
- astrange 4y agoMachO uses codesigning with adhoc signatures as a form of checksumming, and there’s also TCP and whatever drives do. So it’s the converse, it’s so common the dedicated hardware does it instead of the CPU. And it’s not all the same algorithm.
- Sirened 4y agoI think it's a little bit of that and also I suspect they have far more pressing concerns than CRC32X being relatively slow (it is still a throughput of one per clock which isn't at all bad). Branch prediction and prefetching seems to be the really important problem at least for Apple due to their very deep ROB [1]. A mispredicted branch being resolved late (i.e. a branch dependent on an outstanding DRAM fetch) can lead to hundreds of executed instructions being discarded (wasting tons and tons of power and cycles). I don't quite remember the exact figure, but I've heard a good metric in CPU arch is that about one of every six instructions is a control flow instruction in general purpose programs (i.e. non-scientific/ calculation heavy). Being just a little bit faster on CRC32X calculation may not have been worth it when they could spend that precious power budget elsewhere. It's really just design choices all the way down. They may very well be doing a lot of CRC32s but they're almost certainly doing more of everything else than CRC32s. [1] https://www.anandtech.com/show/16226/apple-silicon-m1-a14-deep-dive/2 https://www.anandtech.com/show/16226/apple-silicon-m1-a14-de...
- interestica 4y agoSaving it for M2 to have something to show off?
- naniwaduni 4y ago> Easy gains like that really shouldn't be possible, Easy gains are everywhere. The "gotcha", if you can call it that, is that optimizing particular operations comes with space tradeoffs that are more expensive when you do them in hardware.
- d_tr 4y agoI am not taking any hard stance on the usefulness of the specialized instruction, but M1 is a very wide and powerful core, so this won't be true everywhere. The single instruction might also be more power-efficient and keep other resources free for other stuff.
- athrowaway3z 4y agoAlso not taking hard stances, but both cases are suspect. Power efficiency because being 3 times faster means you're done 3 times earlier. Keeping other resources free because I suspect a CRC calculation is generally followed by an `if eq` statement. ( Even with out-of-order or speculative execution this creates a bottle neck that is nice to remove 3x faster )
- stingraycharles 4y agoIf you’re writing optimized code, hardly ever would you evaluate one CRC check at a time. You would process them in chunks, as the OP stated, but would just let a compiler do the auto-vectorization. This is even more true in the case of CRC, where there’s clearly almost always one branch that wins: this is perfect for branch prediction, which would mean the whole “if eq” condition is preemptively skipped.
- saagarjha 4y agoThe compiler probably isn’t going to be able to autovectorize a CRC unless you help it out.
- dottrap 4y agoI think power efficiency has a lot more variables now so it is not easy to know if consumption is linear with time. CPUs now dynamically throttle themselves, plus now Apple has advertised that its M1 cores are divided up between high-performance and high-efficiency efficiency cores, let alone how the underlying chip itself may consumer power differently for implementing different instructions. So for a hypothetical example, it could be that using general purpose SIMD triggers the system to throttle up the CPUs and/or move to the high performance CPUs, whereas the dedicated CRC instructions might exist on the high-efficiency cores and not trigger any throttling. I've forgotten all my computer architecture theory, but if I look back at Ohm's law and look at power, the equation is P = I^2 • R. Handwaving from my forgotten theory a bit here, ramping up the CPUs increases current, and we see that it is a squared factor. So by cutting the time by say a factor of 3 does mean you are done 3 times faster (which is a linear component), you still have to contend that you have a squared component in current which may have been increased. I have no clue if the M1 actually does any of this, but merely stating that it is not obvious what is happening in terms of power efficiency. We've seen other examples of this. For example, I've read that Intel's AVX family instruction generally increases the power consumption and frequency of when utilized, but non-obviously, it often runs at a lower frequency when in 256 or 512 wide forms compared to the lesser widths (which then requires more work on the developer to figure out what is the optimal performance path as wider isn't necessarily faster). And as another example, when Apple shipped 2 video cards in their Macbooks, some general purpose Mac desktop application developers who cared about battery life were tip-toeing around different high level Apple APIs (e.g. Cocoa, Core Animation, etc.) because some APIs under the hood automatically triggered the high performance GPU to switch on (and eat power), while these general purpose desktop applications didn't want or need the extra performance (at the cost of eating the user's battery).
- dragontamer 4y agoSIMD is a very powerful parallelization technique, with marvelous gains whenever I see it used. It seems like a fundamentally more efficient form of compute, but is very difficult to design algorithms for. I'd argue against "SIMD" as being "RISC", since you need all sorts of complicated instructions (ex: gather/scatter) to really support the methodology well in practice.
- tremon 4y agoBut scatter/gather is a primitive operation for SIMD, so if you want a RISC-based version of it, that's exactly what you would provide. Having dedicated instructions for specific operations (whether for crc/aes/nnp or whatever) feels like a CISC-based approach, so I think I agree with the GP. RISC vs CISC is about the simplicity of the instruction set, not about whether it's easy to use.
- mhh__ 4y agoThese days I'd argue risc vs cisc is more about regularity and directness than the size of the ISA as per se. I'd argue AArch64 isn't particularly RISC by the standards of the past but it sets the bar and tone for RISC today.
- dragontamer 4y agoAnd which SIMD instruction set should we be talking about? NEON-instructions or with the SVE instruction set? And if we're talking about multiple instruction-sets designed for the same purpose, is this thing really RISC anymore? Or do you really mean "just not x86" when you say RISC ??
- mhh__ 4y agoThat depends on how precisely you define the purpose. NEON and SVE seem to be aimed at different intensities of work.
- dragontamer 4y ago
- tlb 4y agoSimilarly, I wish that on x86, REP STOSB was the fastest way to copy memory. Because it only takes a few bytes in the icache. But fast memcpys end up being hundreds of bytes, to work with larger words while handling start and end alignment.
- saagarjha 4y agoWith ERMS it’s definitely not going to be slow, so it’s a good choice when you’re in a constrained environment (high instruction cache pressure, can’t use vector instructions).
- userbinator 4y agoIt still is in general situations (i.e. not the microbenchmarks where the ridiculously bloated unrolled "optimised" implementations may have a very slight edge.) I believe the Linux kernel uses it for this reason.
- jabl 4y agoThe kernel is a bit of a special case since very likely a syscall starts off with a cold I$, and also there's a lot of extra overhead if you insist on using SIMD registers. In general I agree with you though, optimizing memcpy implementations only against microbenchmarks is dumb.
- stncls 4y agoAlso, using SIMD registers is (generally) forbidden in kernel code, which heavily narrows down the competitors to "rep stosb".
- StillBored 4y agoThe real problem (and with the crc above) is that the fastest version for any given cpu may not be the fastest for any other. Its really short sighted to not spend the area on some of these features (aes, crc32, memcpy) because invariably one ends up with a long term optimization problem where in 5-10 years any given application has to run on on of a half dozen diffrent CPUs and optimizing for -mtune=native, and it likely results in suboptimal perf one the lastest CPUs because the micoarch designers can't be constrained to assuring that the the newer version runs any given instruction sequence proportionally faster than the previous. (aka the overall perf may go up but maybe something like the nontemporal store, or the polinomial mul doesn't keep up). And this is really the CISC vs RISC argument and why all these RISC cpus have these CISC like instructions. You want top perf in general code you assure the rep sto and mov sequences (or whatever) run the fastest microcoded version possible on a given core. But intel sorta messed this up in the p6->nehalem timeframe (IIRC when they added the fast string flag) until they rediscovered this fact. IIRC Andy Glew admitted it was a bit of an oversight combined with an release/area issue on the original PPro they intended to fix, but then it took 10 years.
- pclmulqdq 4y agoIt is not faster to use SIMD by hand - it is faster to use the vector unit alongside the integer unit, using both paths at the same time.
- adrian_b 4y agoNo, the faster implementation uses another dedicated instruction, which happens to be more general than CRC32, i.e. the multiplication of polynomials having binary coefficients. So this has little to do with RISC, except the general principle that the instructions that are used more frequently should be implemented to be faster, a principle that has been used by the M1 designers and by any other competent CPU designers. In this case, ARM has added the polynomial multiplication instruction a few years after Intel, with the same main purpose of accelerating the authenticated encryption with AES. There is little doubt that ARM was inspired by the Intel Westmere new instructions (announced by Intel a few years before the Westmere launch in 2010). The dedicated CRC32 instruction could have been made much faster, but the designers of the M1 core did not believe that this is worthwhile, because that instruction is not used often. The polynomial multiplication is used by many more applications, because it can implement CRC computations based on any polynomial, no only that one specified for CRC32, and it can also be used in a great number of other algorithms that are based on the properties of the fields whose elements are polynomials with binary coefficients. So it made sense to have a better implementation for the polynomial multiplication, which allows greater speeds in many algorithms, including the CRC computation.
- saagarjha 4y agoAmusingly the Rosetta runtime uses crc32x
- IshKebab 4y agoThat sounds like a point for RISC to me? Ok maybe it is just a point against really complex instructions. There's clearly an optimum middle ground.
- astrange 4y agoComplex instructions are often good ideas. They’re best at combining lots of bitshifting (hardware is good at that and it can factor things out) but even for memory ops it can be good (the HW can optimize them by knowing things like cache line sizes). They get a bad rap because the only really complex ISA left is x86 and it just had especially bad ideas about which operations to use its shortest codes on. Nobody uses BOUND to the point some CPUs don’t even include it. One point against them in SIMD is there definitely is an instruction explosion there, but I haven’t seen a convincing better idea, and I think the RISC-V people’s vector proposal is bad and shows they have serious knowing what they’re talking about issues.
- userbinator 4y agoThat's very shortsighted thinking. The dedicated instruction could be optimised by the hardware in a future revision to become much faster.
- rowanG077 4y agoIt's not really a fair comparison. There is only one CRC32 unit which means it can't make use of superscalar (at least if I understand the article correctly). If it would have more CRC32 units that would be the most efficient.
- terrelln 4y agoCould you combine both techniques to run both the SIMD version on some chunks and the crc32 instruction on other chunks, in parallel? Of course this would only work if they execute on different ports.
- sgtnoodle 4y agoIt seems like CRC inherently depends on results from earlier calculations, so it would be hard to parallelize like that. You could potentially do multiple independent CRC calculations in parallel, but then you're getting into more niche use cases.
- aaaaaaaaaaab 4y agoWrong. CRC is just polynomial division, which is simple to do in a divide and conquer fashion. It's pretty easy to derive CRC(A concat B) from CRC(A) and CRC(B). It needs a multiplication and a XOR.
- sgtnoodle 4y agoah, that's pretty cool! It looks like concatenation is a O(log(n)) operation involving appending a bunch of zeros rather than just a multiplication, though?
- aaaaaaaaaaab 4y agoIt depends. (A(x) mod Q(x)) * (B(x) mod Q(x)) = (A(x) * B(x)) mod Q(x) If the chunk size N is known beforehand you can pre-calculate x^N mod Q(x), so appending N zeros will be an O(1) multiplication. Only if the chunk size is not known, you have to calculate x^N mod Q(x) via modular exponentiation, which is O(log n). But you only need to do this once, and then you can reuse the value for all subsequent chunks.
- dougall 4y agoHmm, yeah, this might work out... Two SIMD uops process 16 bytes, so each SIMD uop is doing eight bytes of work - the same as CRC32X, but with more frontend pressure (and preferable because they can run on any of the four SIMD ports, not just the one distinct CRC32X port). It gets a bit messy, and we can't expect a ton from this approach - the same loop with only the loads only runs at ~86GB/s, but it'd be worth a shot.
- DeathArrow 4y agoI wonder how fast can someone get it to run on Intel's 12 generation core CPU. It seems a good idea to start a Code Golf competition.
- dragontamer 4y agohttps://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf https://www.intel.com/content/dam/www/public/us/en/documents...
- Twirrim 4y agoLikely as much noise as signal, but anyway: I'm using an 8th(?) generation Intel, i7-8665U. https://github.com/htot/crc32c https://github.com/htot/crc32c has some interesting implementations of CRC32 algorithms of different speeds, the highest I see is (function, aligned, bytes, MiB/s) : crc32cIntelC true 16 3907.613 crc32cIntelC true 64 15096.758 crc32cIntelC true 128 24692.803 crc32cIntelC true 192 22732.392 crc32cIntelC true 256 16233.397 crc32cIntelC true 288 16748.952 crc32cIntelC true 512 19862.039 crc32cIntelC true 1024 22373.350 crc32cIntelC true 1032 22482.031 crc32cIntelC true 4096 24690.531 crc32cIntelC true 8192 24992.827 So pushing 25GiB/s on a 3ish year old CPU.
- neurostimulant 4y agoI'm using i7-4790 (7 year old cpu) and the numbers are slightly better. Maybe because it's a desktop. crc32cIntelC true 16 4025.334 crc32cIntelC true 64 15749.095 crc32cIntelC true 128 26608.064 crc32cIntelC true 192 25828.486 crc32cIntelC true 256 17448.436 crc32cIntelC true 288 18336.381 crc32cIntelC true 512 22635.590 crc32cIntelC true 1024 24654.248 crc32cIntelC true 1032 24180.107 crc32cIntelC true 4096 28251.903 crc32cIntelC true 8192 28768.134
- jeffbee 4y agoCore i7-12700K: crc32cIntelC true 64 26210.561 crc32cIntelC true 128 35870.309 crc32cIntelC true 192 36850.224 crc32cIntelC true 256 30343.690 crc32cIntelC true 288 30671.327 crc32cIntelC true 512 32443.251 crc32cIntelC true 1024 34654.719 crc32cIntelC true 1032 34265.440 crc32cIntelC true 4096 38111.089 crc32cIntelC true 8192 38634.925
- 13of40 4y agoWeird, I talked to the guy who invented the crypto scheme for ZIP and he said he invented the CRC algorithm for it as well. I wonder if there's more backstory there. Edit: He invented the crypto not the CRC, which Phil Katz was already using.
- AlotOfReading 4y agoThat's a very strange claim. As far as I know, the same CRC has been used for ZIP since it was invented by the PKWARE guys in the 80s. Moreover, no one deeply understood the properties and tradeoffs of various CRCs the way we do now, so everyone used largely identical algorithms with only trivial variations. Phil Katz did the same and reused the same polynomial that was in ethernet and dozens of other standards, which in turn had originated from this 1975 report: https://apps.dtic.mil/sti/pdfs/ADA013939.pdf https://apps.dtic.mil/sti/pdfs/ADA013939.pdf He wasn't even the first to put a CRC in an archive format, as the predecessor format ARC had a CRC-16 doing the same thing.
- 13of40 4y agoAh, OK, I looked in my email and it was the guy who invented the encryption scheme, but he said "Yes, I invented it [referring to the encryption]. It wasn't based on anything else, except that it used the same CRC he [Phil] was already using in zip." (As a historical note, he also said the crypto scheme was intended to be exportable, which at that time meant "intentionally weak".)
- carbonbee 4y agoI think what OP meant to write: the zip encryption algorithm is a custom stream cypher that uses crc32 as the main building block. (It's a very bad cypher, vulnerable to known plaintext and other attacks, don't use it for anything except light scrambling).
- mappu 4y agoNowadays most zip programs will default to using AES (in the way WinZip invented) instead of ZipCrypto.
- DantesKite 4y agoI really like that the author gave some context at the top. So many times I struggle to read or realize the importance of a concept because there just isn't enough context for me to follow along. And certainly not all blogs have to, but it's nice when it is.
- parentheses 4y agoIt is very interesting that since the release of the M1 chip, CPU performance on Apple silicon has really come under a microscope. It leads me to ask: Was Apple silicon always this best-in-class and we weren’t looking this closely as a community?
- Aissen 4y agoEveryone was looking, and it was well known that it was best in-class; two random examples: https://www.anandtech.com/show/7335/the-iphone-5s-review/4 https://www.anandtech.com/show/7335/the-iphone-5s-review/4 https://twitter.com/codinghorror/status/912047023871860737 https://twitter.com/codinghorror/status/912047023871860737
- minhazm 4y agoApple's chips in their iPhones & iPads have been outperforming the competition (Qualcomm & Samsung) for a long time now in both power efficiency and performance. Apple has usually been around 2 yrs ahead of the competition. The Qualcomm Snapdragon 888 chip with 8 cores has a Geekbench multi-core score of 3592[1]. The six-score Apple A15 Bionic scored 4673. The Apple chip has ~30% better multi-core performance with 25% fewer cores than the Qualcomm chip. In single-core performance the difference is even larger, with the Apple chips performing ~47% faster. You can get the same A15 Bionic in both the $429 iPhone SE and the $1100+ iPhone 13 Pro Max. It hasn't really been a huge deal though because people don't develop directly on an iPhone, so it doesn't affect their every day productivity all that much. Also phone's have reached the point of "fast enough" a few years ago, it's hard to tell the difference between an iPhone 13 Pro and an 11 Pro unless you use them side by side. But with the release of the M1 chip, people are getting the performance & energy efficiency gains in their every day workflows. [1]. https://browser.geekbench.com/android-benchmarks https://browser.geekbench.com/android-benchmarks [2]. https://browser.geekbench.com/ios-benchmarks https://browser.geekbench.com/ios-benchmarks
- grishka 4y agoPhones also usually aren't designed to sustain a high CPU load for extended periods of time. Computers, on the other hand, are.
- IncRnd 4y agoIt's always important to know which crc you are using. Looking at https://developer.arm.com/documentation/ddi0596/2020-12/Base-Instructions/CRC32B--CRC32H--CRC32W--CRC32X--CRC32-checksum- https://developer.arm.com/documentation/ddi0596/2020-12/Base..., based upon the polynomial constant, the CRC32 class of instructions appear to calculate a CCITT 32 reversed polynomial. Are there any ARM developers who can help me out here? Does this apply in the same way to the M1?
- dougall 4y agoThe post glosses over it a bit - the CRC32X instruction always uses the common polynomial 0x04C11DB7 (matching zlib, commonly just called CRC-32), and there's a second instruction, CRC32CX, which is the same but uses the polynomial 0x1EDC6F41, known as CRC-32C (Castagnoli). The constants in the post are also for 0x04C11DB7, but the linked Intel article explains how to they can be calculated for arbitrary polynomials, so the faster method is also generic, which is nice.
- IncRnd 4y agoThank you! The Castagnoli polynomial, 0x1edc6f41, is used to compute a crc in Btrfs, Ext4, iSCSI and various other places.