9 ms·
Base64 encoding and decoding at almost the speed of a memory copy
- emirp 7y agoGreat use of AVX-512 VBMI! Note that not many Intel processors support the two specific CPU instructions used (vpermb and vpmultishiftqb). Cannon Lake Core i3 (not many of these around due to delays with intel's 10nm fabrication) Ice Lake Core i3, i5 and i7: Released in September 2019
- darkwater 7y agoWhy do they say then "We use the SIMD (Single Instruction Multiple Data) instruction set AVX-512 available on commodity processors" ?
- PudgePacket 7y agoThey're technically not wrong.. just not available on many commodity processors.
- brazzy 7y agoBecause those are commodity processors nonetheless. The distinction relevant for a research paper is between mainstream processors you can just buy vs. custom made ones, not about market penetration.
- dickeytk 7y agoI still think "commodity" is not the correct word even in that context. Mass-market, or commercially available might be better. How can it be a commodity when there is only one manufacturer?
- penagwin 7y agoJust going off wikipedia (also other sources support the definition): > In economics, a commodity is an economic good or service that has full or substantial fungibility: that is, the market treats instances of the good as equivalent or nearly so with no regard to who produced them. Basically it's a common good, that is sold and purchased, with no other modifications required for this use-case. This commodity is currently low in supply, but is still a commodity.
- bloomer 7y agoIt’s missing the fungibility where it is produced by multiple suppliers and can be treated equivalently by the end buyer. Large grade A eggs are a commodity as it doesn’t matter which farm produced them. A specific set of processors from Intel are not a commodity since there are no fungible equivalents. Widely available would probably be a better description in this case.
- dickeytk 7y agoI would argue processors are never commodities anymore (maybe back in the 486 days it was closer). You can't swap an intel for an amd processor into the same motherboard ever today. They don't have the same performance characteristics from one to another. You could have 2 "3.5Ghz 4-core processors" that have wildly different real-world performance. IMO this is the opposite of "fungible" I think hard drives, memory, power supplies are much closer to being fungible.
- onion2k 7y agoIt's a slightly awkward way of saying they didn't use custom hardware.
- jng 7y agoPlus, if my knowledge is properly up-to-date, no AMD processor supports those instructions, not even any member the recent and famously super efficient Ryzen family processors.
- loeg 7y agoNone of the AMD CPUs have AVX-512. The new ones have full-width AVX-256.
- ArtWomb 7y agoLooks like model number 06/66 or better in cpuinfo. Both AWS and Gcloud standard vm instances appear to be Skylake ;( Honestly, base64 has always been pretty fast for me, even large bitmaps >100kb. Compared to net latency it may be imperceptible to end user. But it still makes a terrific reference paper!
- jason0597 7y agoNow this is the programming I like, low-level assembly optimisation of long operations, none of this web development rubbish
- sophiebits 7y agoYou can certainly enjoy assembly programming, but that doesn’t make web development rubbish.
- deleted 7y ago[deleted]
- diminoten 7y agoI'm the opposite! Yin and yang, we need one another. :D
- panic 7y agoThis is relevant to webdev, though -- binary data in JSON is often encoded as a Base64 string.
- wingi 7y agoWhy use 6-bit data, if JSON can transport 8-bit (-1 for quoting the ") ?
- cryptonector 7y agoByte values that are ASCII control characters need to be escaped, and byte values that are not valid UTF-8 can't be represented in JSON strings.
- Vrixam 7y agoWould this always be valid UTF8?
- conradfr 7y agoAs an anecdote I have a Phoenix LiveView project where I've discovered that loading, converting and sending an (uncacheable) image as base64 via the websocket connection feels quicker and smoother (I didn't benchmark it) than only updating the src path and letting the browser load it (with http1, I would have to compare with http2).
- zuck9 7y agoAlso worth checking out: https://github.com/superhuman/fast64 https://github.com/superhuman/fast64 That is what Superhuman uses for decoding base64 in browser.
- vardump 7y agoI don't see how that's relevant, it looks pretty standard approach for base64 decoding. You can find thousands of similar examples.
- lifthrasiir 7y agoNot only it is just a standard approach, it even misses a relatively common optimization for base64 decoding: instead of computing `(lut[a] << 6) | lut[b]` etc., one can precompute `lut6[x] = lut[x] << 6` and compute `lut6[a] | lut[b]` to avoid shifting. This optimization is famously used by Nick Galbreath's MODP_B64 decoder, which is used by Chromium [1] and turns out to be the most performant non-SIMD decoder according to Lemire et al. [2] [1] https://github.com/chromium/chromium/tree/master/third_party/modp_b64 https://github.com/chromium/chromium/tree/master/third_party... [2] https://github.com/lemire/fastbase64 https://github.com/lemire/fastbase64
- powturbo 7y agoYou can do better, without SIMD: https://github.com/powturbo/TurboBase64 https://github.com/powturbo/TurboBase64 The simple base64 scalar version is also faster the chromium implementation.
- taspeotis 7y agoThe authors have been doing good work in this area for a while: https://arxiv.org/abs/1704.00605 https://arxiv.org/abs/1704.00605
- cperciva 7y agoThe code: https://github.com/WojciechMula/base64-avx512 https://github.com/WojciechMula/base64-avx512
- usr1106 7y agoWhy is that an achievement? Isn't it so that during a memory copy the CPU is basically idling because memory is so much slower than the CPU? Weren't that hundreds of instructions per memory access? So instead of having it wait it can also do computations (just standard instructions). Or is base64 computationally so heavy that it cannot fit into the "gaps"? I certainly have not tried, just thinking from the high level view that CPUs are incredibly fast and main memory is incredibly slow in comparison. And of course assuming that the data does not fit into any cache.
- vardump 7y agoYou're mostly right. It's often not that hard to completely saturate memory bus. However, base64 has weird mappings that take some processing to undo in SIMD – can't use lookup tables and need to regroup bits from 8 bit to 6 bit width. That does take a lot of cycles without specialized bit manipulation instructions. Also the data you'll need to process is often probably already hot in the CPU caches. Disk/network I/O can be DMA'd directly into L3 cache. So I think this decoder is a useful contribution. But also somewhat no-brainer once you have those AVX-512 instructions available.
- mytailorisrich 7y ago> However, base64 has weird mappings that take some processing to undo in SIMD – can't use lookup tables and need to regroup bits from 8 bit to 6 bit width. That does take a lot of cycles without specialized bit manipulation instructions. Base64 uses lookup tables and the bit manipulations required are standard shifts and 'and', which are basic, fast instructions on any CPU. That seems exactly what they do here with an efficient use of AVX512 to make it fast(er).
- londons_explore 7y agoWhy can't you use lookup tables?
- vardump 7y agoBecause table lookups don't vectorize. You could try to use vectorized gather (VPGATHERDD [0]), but so far in my experience it's been just as slow as using scalar code. (Then again, even gather instructions operate just on 32-bit data, so it wouldn't help anyways.) So to perform multiple operations in parallel per core (SIMD), you'll have to write some code to perform the "lookup" transformation instead. [0]: https://www.felixcloutier.com/x86/vpgatherdd:vpgatherqd https://www.felixcloutier.com/x86/vpgatherdd:vpgatherqd
- vardump 7y agoNow show me memory speed SIMD uint8_t histogram, and I'll be happy. Computing histogram is slow and it doesn't really vectorize. Yet it's required by many important algorithms like data compression.
- powturbo 7y agoNot memory speed but extremely fast: https://github.com/powturbo/TurboHist https://github.com/powturbo/TurboHist
- vardump 7y agoYeah, it's nice, about what you can achieve. I'd be happy if it was about 8 times faster. Less than 0.2 cycles per byte would be good. Unfortunately, that's just not achievable with current x86 instruction set.
- powturbo 7y agoThere is new AVX512 instruction (_mm512_conflict_epi32) supposed to solve this, but it can't make the histogram construction faster than the scalar functions.
- powturbo 7y agoTurbobase64: A portable scalar implementation can beat SIMD and saturates the fastest networks and fastest SSDs. It is faster than SSE on Intel/AMD and SIMD NEON on ARM see benchmark at Turbo Base64: https://github.com/powturbo/TurboBase64 https://github.com/powturbo/TurboBase64
- bluesign 7y agoBenchmark at the README says it is 4x slower than memcpy.
- powturbo 7y agoThere is no claim about memcpy. The memcpy is used as indication in the benchmark.
- cperciva 7y agoTurboBase64 runs at 3-4 GB/s. The authors' work runs at over 40 GB/s. Not to say that Turbobase64 isn't impressive, but it's not at all the same level of performance.
- powturbo 7y ago40 GB/s in L1 cache. The TurboBase64 benchmark is more practical. It is impossible to have the speed of a good memcpy when you're copying 33% more like in base64.
- bluesign 7y agoI think 40GB/s result when it is not fitting L1 cache. If you check result graph, On L1 cache fitting data memcpy is ahead with big difference, then they are almost head to head
- powturbo 7y agoL1 cache is 64k for this cpu. A benchmark with large files is more realistic, because it's unlikely that the data already be in the L1 cache.
- m0zg 7y agoMany people don't realize this but today's memory is dramatically underpowered for today's CPU. Consider the following: you can, theoretically, get ~80GB/sec of memory bandwidth from a modern Intel CPU (assuming you use all channels, and there are no interrupts, etc). That's 20 billion floats or int32s per second. The same CPU can do ~2.3 fp32 TFLOPS. That's 115 ops for every fp32. And it's getting worse as more and more cores are put on the same memory bus.
- satanspastaroll 7y agoThis should change soon, as EPYCs can do 204GB/s of memory throughput (plus tons of pcie4.0). They also aren't cpu tied, all of the SKUs get all of the lanes
- m0zg 7y agoIt's a NUMA though. You'll have to write software specifically for NUMA to get anywhere close to that number. To make matters worse, EPYC also doubles the number of cores. To be fair, though, it also has a substantial amount of cache, but cache is not a panacea if you need something in the main RAM. And if you're churning through gigabytes of stuff per second, you'll be needing that very, very often.
- gmueckl 7y agoYes, NUMA and large numbers of core will pose completely new challenges for software optimization. Applications will have to become aware of the memory architecture of the underlying machine. They will have to make explicit assignments of memory allocations and threads to NUMA nodes based on their domain specific needs. In some cases, even duplicating data structures may be the right call. This is going to challenge how most developers write fast software. The other thing is that even seemingly trivial things like spawning and synchronizing with lots of threads will be much more complex on CPUs with many cores. At some point, naively looping over all threads is going to be too slow. I think that the limit is going to be around 64 cores. Past that, you should actually parallelize your worker thread management to stay efficient. There is precendent for this in HPC, e.g. MPI implementations.
- robocat 7y agoUnfortunately using AVX512 instructions only gets a speedup in very specific situations and for many real world use cases it actually underperforms due to oddities of scaling and switching delays. Profiling for more than a few milliseconds is one place you see phantom gains, so take care not to be deceived. See https://blog.cloudflare.com/on-the-dangers-of-intels-frequency-scaling/ https://blog.cloudflare.com/on-the-dangers-of-intels-frequen... https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-use-these-new-instructions/ https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-us... https://news.ycombinator.com/item?id=21029417 https://news.ycombinator.com/item?id=21029417 Edit: not saying this isn't a true benefit here, just that claims of speed when using AVX512 need to be treated with fair scepticism for actual use cases.
- cperciva 7y agohttps://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-use-these-new-instructions/ https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-us... Considering that the author of that blog is one of the authors of this paper, I think he's very aware of the benchmarking issues.
- rurban 7y agoHe is aware, but sidestepped these issues. so this code is only recommended on the newest Cannon Lake processors, but we really want to know for which CPU which method is best. What about AMD Rome e.g.?
- justin66 7y agoSince AVX-512 does not exist on AMD Rome, that question answers itself.
- robocat 7y agoI didn't realise that. My original post was just to warn that AVX512 benchmarks can be highly misleading. Everyone has troubles measuring AVX512 performance: "In GROMACS, transitions in and out of AVX-512 code can lead to differences in boost clocks which can impact performance. We are just going to point out the delta here." - from https://www.servethehome.com/intel-performance-strategy-team-publishing-intentionally-misleading-benchmarks/ https://www.servethehome.com/intel-performance-strategy-team...
- londons_explore 7y agoIf base64 decoding speed makes a difference in your application, you should be considering why you are transmitting data in base64, a neat hack from the 1970's, which is non-human-readable, wastes 30% of the network bandwidth, kills compression, wastes RAM, is typically hard to random-access, and is generally a bad idea all round.
- _pmf_ 7y agoHow does it kill compression?
- londons_explore 7y agoTry it... wget http://mattmahoney.net/dc/enwik8.zip -O - | gunzip | head -c 1000000 | gzip -9 | wc -c 355350 wget http://mattmahoney.net/dc/enwik8.zip -O - | gunzip | head -c 1000000 | base64 | gzip -9 | wc -c 528781 base64 is 48.8% larger after compression on english text, whereas it would only be 33.3% larger without compression. The reason is because compression finds and eliminates repeating patterns, but base64 can make the same input data look totally different depending on which of the 4 input alignments it has.
- xxs 7y agooddly enough lz/deflate are as ancient as base64. 16bit deflate is quite poor and slow, yet predominant.
- alboy 7y agoMost compression algos operate on single-byte chunks of data and base64 encoding messes up the original byte alignment making the input appear more random than it is.
- CamperBob2 7y agoFor one thing, it removes opportunities for more efficient content-aware compression elsewhere in the data path.
- nathell 7y agoWojciech Muła really groks SIMD. It's well worth exploring his other work in that area: http://0x80.pl/articles/index.html http://0x80.pl/articles/index.html
- rurban 7y agoNot yet usable asis. Normally AVX-512 instructions are subject to downclocking. Now they tried a very recent CPU which is not subject to downclocking anymore. They didn't add code to test for the CPU revision which stopped downclocking, and they didn't benchmark with those older CPU's. We can only guess the older AVX256 code is faster there, but not how much.
- wmu 7y agoSpeaking of benchmarking against older CPUs: the paper falls into the "short communication" category, we didn't want to discuss all possible hardware configurations.
- mensetmanusman 7y agoiOS 13 allows the Shortcuts app to encode/decode information as Base64 as part of the scripting language. People are using this to do clever things like encoding a watermark image to overlay on a picture, because the Shortcuts app does not allow file attachments as part of the scripting language.
- ZeikJT 7y agoSo this could've been done in the past with a manually written decoder but now it's a built in? That's great
- pabs3 7y agoI wonder if the authors plan to get this merged into commonly used implementations of base64 so that folks can benefit from their research.
- wmu 7y agoFor instance our SSE/AVX2 algorithms have been included in a great, mature library written and maintained by Alfred Klomp: https://github.com/aklomp/base64 https://github.com/aklomp/base64 (the library includes also vectorized code for ARM CPUs).
- pabs3 7y agoIs that library widely used, for example is it used by Firefox or Chromium?
- vagab0nd 7y agoQuestion: with this kind of optimization, how does the program run different functions on different CPUs? Like the ones that don't support AVX512? Some kind of runtime dispatch based on CPU ID?
- deleted 7y ago[deleted]