7 ms·
tolower() in bulk at speed
- babelfish 4y agoGreat article. Have been brushing up on bit manipulation for interview prep lately and I love finding easy to digest, real-world use cases like this.
- dragontamer 4y agoSeems a bit odd to stop at SWAR on today's systems. Every system I'm aware of has 128-bit SIMD implemented: either SSE (x86), NEON (ARM), or AltiVec (POWERPC). As such, 128-bit SIMD is the "reliably portable" SIMD operation. Of course, for fastest speeds, you need to go to the largest SIMD-register size for your platform: 512-bit for some Intel processors, rumored AMD Zen4 and Centaur chips. 256-bit for most Intel / AMD Zen3 chips. 128-bit for Apple ARMs, 512-bit for Fujitsu A64 ARMs, etc. etc. > And these are the fastest kinds of instructions :-) And it should be noted that modern SIMD instructions execute at one-per-clock-tick. So the 64-bit instructions certainly are fast, but the SIMD instructions tie if you're using simple XOR or comparison operations. -------- This style of code might even be "reliably auto-vectorizable" on GCC and CLANG actually. I wonder if I could get portable auto-vectorizing C from these examples.
- sedatk 4y ago"labels are frequently less than 8 bytes long, and therefore fit inside a 64-bit register. So it probably isn’t worth dealing with the portability issues of working with wide vector registers (Especially since I could not find a quick way to load an arbitrary number of bytes into a vector register with AVX2 nor with NEON.)"
- dragontamer 4y agoDNS labels like "ycombina" (tor) you mean? :-)
- fanf2 4y agoTwo out of three ain’t bad :-) news.ycombinator.com
- cratermoon 4y agoJust off the top of my head, I'm betting that 9 out 10 of the most visited internet domains are 8 bytes or less. google, facebook, twitter, youtube, baidu, yahoo. I think instagram might be one of the few that isn't 8 bytes. That's not counting URL shorteners, either.
- fanf2 4y agoIs there a good way to load an arbitrary number of bytes (up to the vector size) into a vector register? As I said in the article, I could not find one when looking at AVX2 or NEON reference manuals. Getting the data from RAM is the main bottleneck for short strings, which DNS names usually are.
- dragontamer 4y agoYou're not thinking in terms of SIMD. If you load 5 bytes into a 128-bit register (16-bytes) you'll have 5-bytes of data + 11-bytes of garbage. Perform the calculation over all 16-bytes. Yes, this makes 11-bytes of garbage at the end. Once you're done, just write back the first 5 bytes and you're set. The 11-bytes of garbage are "free". They didn't cost you anything. > Getting the data from RAM is the main bottleneck for short strings Your L1 and L2 cache-lines are 64-byte minimum read / write anyway (actually, some systems were 128-byte minimum IIRC). A 16-byte read is literally smaller than what your cache does on the path into your registers. EDIT: More importantly, modern CPUs only have 2x or 3x load/store units. Meaning a modern CPU can only perform ~2ish load/stores per clock tick. The SSE (16-byte / 128-bit) read / write to L1 cache will perform the same speed as a 8-byte /64-bit read/write to L1 cache in practice.
- fanf2 4y agoIn fact the code that I left out of the blog post does almost exactly what you suggest :-) It’s the “load 5 bytes” and “store 5 bytes” that I don’t have a good solution for. At the moment I am using memmove() and relying on the compiler developers to have better ideas about optimizing it than I do… The bottleneck comes from the number of instructions and the branchiness, not the data bandwidth. I briefly considered playing games with overlong reads, but then asan gave me a slap and I reconsidered the path to wisdom.
- dragontamer 4y ago> It’s the “load 5 bytes” and “store 5 bytes” that I don’t have a good solution for. You build that out of "load 16 bytes" and "store 16 bytes" operations. register = [news.YCOMBINATOR] isValid = [00000FFFFFFFFFFF]; // "F" is really 0xFF, but you get the gist // isValid was generated because you were focusing on the YCOMBINATOR part // of the DNS entry: news . YCOMBINATOR . com. YCOMBINATOR there to focus // upon the current data being considered, while "news." and "com" should // remain untouched register = (register | ((register >= 'A' & register <='Z') << 5)); register = register & isValid; toWrite = writeLocation & (~isValid); toWrite = toWrite | register; writeLocation = toWrite; If you're doing things in-place, then writeLocation could be a copy of "register" from the 1st step.
- moonchild 4y ago> modern SIMD instructions execute at one-per-clock-tick Or even two, or four on apple arm, plus load and store which can be done in parallel.
- dragontamer 4y agoYeah, good point. SIMD is also superscalar on most systems. For x86, Intel can do 3x AVX512 instructions per clock tick as long as each instruction is simple enough (add, AND, OR, NOT, XOR, maybe even multiply if you're not counting the latency issue)
- moonchild 4y agoOnly port 5 and port 0/1 can do avx512 instructions on skylake/icelake, so I don't think you can get better throughput than 0.5 on current parts. Unless you count load & store as well, like I mentioned.
- dietrichepp 4y agoNaive version to explore autovectorization: https://gcc.godbolt.org/z/bcefvznG3 https://gcc.godbolt.org/z/bcefvznG3 Yes, there's some amount of autovectorization here. Seems like a mess of a function. Here's something more like tolower8(): https://gcc.godbolt.org/z/h8GTanodd https://gcc.godbolt.org/z/h8GTanodd The generated code definitely looks funny to me. Here is a manual vectorization, which is shorter: https://gcc.godbolt.org/z/1e4odEsKq https://gcc.godbolt.org/z/1e4odEsKq The issue of loading into your vector register... well, there are some dirty tricks for that. The 16-byte slice containing the first byte, and the 16-byte slice containing the last byte, can both be loaded into registers and then shifted around in order to construct the desired value. Note the careful wording here... these slices might be the same slice. Or you can iterate over the 16-byte slices containing the array, and shift as you go, if you're storing into a different location. Or you can use various masked load/store operations on various architectures.
- dragontamer 4y ago> The issue of loading into your vector register... well, there are some dirty tricks for that. Good discussion. I think the only method you haven't talked about is the simple "unaligned load" instructions (which might be the simplest, and most portable way, to do this). I know that ARM and x86 both can do unaligned loads no problem, but at a possible performance penalty.
- dietrichepp 4y agoThe reason I didn’t mention unaligned load is because it can cross a page boundary and fault. With aligned loads, you can avoid this. (Edit: The idea is that with an aligned load, you only load 16-byte blocks that contain valid data. This can’t page fault, but you can load data you didn’t want, which is ok. Writing is trickier because the write may have to be atomic and can’t spill.)
- zen_1 4y agoAnother (admittedly quite niche) gotcha I've experienced with aarch64 unaligned SIMD loads specifically is that they will fail (raising a data abort exception) if they access memory that isn't specifically designated as "normal ram" by the MMU. This can happen if you're writing code for an embedded system, or even if you're calling memcpy with a too-smart-for-it's-own-good libc (such as Newlib, that ships with the aarch64-none-elf toolchain ARM provides...) implementation without first setting the MMU up.
- nimish 4y ago> Every system I'm aware of has 128-bit SIMD implemented These still come in handy on embedded systems where there isn't a vector unit
- cratermoon 4y ago> on today's systems BIND still supports critical internet infrastructure on less capable hardware.
- Marat_Dukhan 4y agoLinux-capable RISC-V cores often have 64-bit architecture and no SIMD/vector processing capabilities.
- fulafel 4y agoThere's some uncovered ground between the processors having SIMD support and being able to use it portably from C. Also a compiler could compile this code to use SIMD instructions.
- adrian_b 4y agoActually most modern SIMD instructions have a throughput of more than one per clock cycle. Simple SIMD instructions, like integer addition, comparison, XOR, have a throughput of 2 per cycle (many ARM cores), 3 per cycle (most Intel CPUs) or even 4 per cycle (AMD Zen 3). Similar simple 64-bit instructions have a higher throughput in instructions per cycle, from 3 per cycle up to 5 per cycle (Alder Lake), but when considering the register size the total throughput of the SIMD instructions is always higher.
- kristianp 4y agoGoogle and wikipedia tell me that SWAR is: SIMD within a register, also known by the name "packed SIMD".
- londons_explore 4y agoAll those arithmetic calculations depend on the previous... You should get much more throughput if you can interleave them with other instructions... I wonder if that's what the benchmarks did?
- fanf2 4y agoHmm, yes, there are only 2 or 3 instructions that can execute concurrently - but your observation made me realise I can eke out another by masking is_ascii more thoroughly. Thanks! Bulk throughput isn’t really my aim, it’s just a convenient way to get numbers big enough to be easily measurable :-)
- dzaima 4y agoAn out-of-order CPU will interleave things for you. Any modern CPU should have no issues running many iterations of the loop in parallel, as nothing should depend on the previous iteration. But, given that the task at hand usually deals with very short inputs, there's not much to interleave with anyway.
- londons_explore 4y agoWorth patching libc?
- vinkelhake 4y agolibc tolower() works on a single char at a time. This post is about the gains you can get by converting multiple chars at once.
- londons_explore 4y agoPresumably with the right __inline stuff it could be vectorized by a compiler, since tolower is normally called from a loop? Although I guess since it's often a dynamically linked library, said optimizations would have to happen at load time, and the dynamic loader doesn't do such things... :-(
- mananaysiempre 4y agoThe standard tolower() / toupper() take a single character only; bulk strlwr() / strupr() are nonstandard (if commonly present) and—more importantly—virtually unused. I suppose implementing this technique in the C/POSIX-locale version of nonstandard stricmp() / POSIX strcasecmp() might be helpful in some cases, because people do use that one, but I still expect that any situations that truly call for an ASCII-only case-insensitive comparison (parsers?) will be doing much more work per byte for other reasons (state machine, perfect hash, etc.).
- stabbles 4y agoIt's not the same, libc's tolower takes an int as an individual character
- Findecanor 4y agoAlthough ... the existence of a libc with SIMD versions of its functions is not implausible. There are compilers that would produce such functions beside the normal ones if the source is decorated with the right #pragma. Such functions would be called only from within vectorised loops (or other SIMD versions of functions).
- mananaysiempre 4y agoThis technique of SWAR (“SIMD within a register”) with very narrow elements and no hardware support is explained very well in an SO answer[1] (and the linked slides) about the mythical (and useless) “fusion trees”. [1] https://stackoverflow.com/a/56604876 https://stackoverflow.com/a/56604876
- charcircuit 4y agoSince domains are UTF-8 doesn't the assumption of ASCII breakdown?
- jimmygrapes 4y agoAbsolutely. This article is reminiscent of the type of brief tutorials from the mid/late 90s in QBASIC newsletters introducing how to use ASM to get speed gains, with all the associated assumptions. The concept of "lowercase" breaks down terribly once you go beyond simple A-Z. You can apply similar rules to certain limited code sets, but a universal tolower() won't work so well with this method.
- jandrese 4y ago"Universal tolower()" doesn't even make sense. What would you expect from tolower("Σ"), "σ" or "ς"? If you assume tolower(toupper(mychar)) == tolower(mychar) then your code is going to break.
- jimmygrapes 4y agoyes that is my point
- sveiss 4y agoDomain names are limited to a small subset of ASCII; the DNS protocol doesn’t support UTF-8. To work around this, the international domain name standard defines an encoding called Punycode which maps Unicode to the limited character set DNS supports. The server is unaware of this, and so this optimised tolower() implementation works without any Unicode considerations.
- asveikau 4y agoLower case is locale-sensitive, however. For example, tolower('I') in Turkish should be 'ı'. And within unicode, doing it in a "dumb ascii" way probably needs some normalization of diacritics. Eg. 'é' should be U+0065 U+0301 ("e\xcc\x81"), not U+00E9 ("\xc3\x89"). Not sure how punycode handles this, I did once look deeply into it but that was years ago.
- deleted 4y ago[deleted]
- MrYellowP 4y agoHad I known anyone cares about this ... Anything else anyone cares about, that could use a speedup... ?
- moonchild 4y agoProduce a fast, in-place, ideally parallel implementation of the generalised transpose, which arbitrarily rearranges the axes of a multidimensional array (potentially duplicating some of them).
- MrYellowP 4y agoWow! Okay, but does it have to be a general transpose? And if so, why? I have no idea about this (which is PERFECT!) so I've started looking: > In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix A by producing another matrix, often denoted by AT (among other notations). I ask, because I need to know if it matters how the solution works, or if all that matters is that the solution works as it should. Thank you! Edit: Do you have a compiled benchmark I can run, for comparison with other solutions?
- moonchild 4y ago> does it have to be a general transpose? And if so, why? There are two answers to this, one less interesting, and one more interesting. The less interesting answer is that it's a primitive in APL, and I have a vested interest in making APL fast. Then, it needs to be a general transpose because the specific case of a 2-d transpose is already well-studied and has high-quality solutions already. As a language feature, the transpose can be thought of as a calculus on indices. This suggests a fairly straightforward implementation strategy where no actual data is moved around; instead, a 'strided representation' is used, storing additional information about the array layout, and the indexing procedure is made aware of this. This seems to be effectively free. So why am I asking you to move data around? This leads into the second interpretation of the transpose, which is as a permutation. Interestingly, this is almost opposite the index-calculus interpretation, because it primarily acts to change the way the data are represented; it doesn't actually need to change how the data are interpreted at all. And this is useful because, when taking into account access patterns, laying the same data out differently can significantly improve locality and therefore performance. If you're familiar with column/row stores, or 'soa'/'aos', these are applications of the 2-d transpose. The general transpose, then, performs the obvious analogue function for higher-dimensional data and is interesting for the same reasons. (The duplicating-axes part is just a novelty, then.) As a starting point, I suggest looking at libfft; as I recall, it has some good 2-d transpose implementations, and links to relevant papers. (Fft is, not-so-coincidentally, an application that can benefit from transposing.) Also interesting may be this paper, and any relevant links that result therefrom: https://www.researchgate.net/publication/273912700_In-Place_Matrix_Transposition_on_GPUs https://www.researchgate.net/publication/273912700_In-Place_... > I need to know if it matters how the solution works, or if all that matters is that the solution works as it should The interface is: I give you a buffer, an element size (probably 1/2/4/8 bytes), a shape projecting a multidimensional interpretation onto that buffer, and a permutation of that shape; you move around the elements of the buffer according to the permutation. How you implement that is up to you (though I will also say that I am also more curious about the general approach you come up with than with the specifics of the implementation). > Do you have a compiled benchmark I can run, for comparison with other solutions? The only place I know of to find implementations is inside of apls; the fast apl implementations are dyalog apl[0] and j[1]. I don't know how optimised their transposes are, though; they might or might not be a good baseline. Here's a simple example to get you started benchmarking inside j: a=. 27 1000 40 77?@$0 NB.declare a to be an array of shape 27 1000 40 77 NB. contents are randomised; this is a memory-heavy algorithm, and apparently writing lots of zeroes can have weird cache effects NB. elements are double-precision floats; so, 8 bytes timex'2 1 0 3|:a' NB. see how long it takes to apply the permutatio 2 1 0 3 to the shape of a 0.34551 10 timex'2 1 0 3|:a' NB. do 10 runs, and take their average 0.301104 Dyalog is similar, but the permutation is specified in a weird way and I don't feel like looking it up atm; poke me about it later if you care to, as they do have better algorithms in some cases. 0. https://www.dyalog.com/ https://www.dyalog.com/ 1. https://www.jsoftware.com/ https://www.jsoftware.com/
- dzaima 4y agoHere's an AVX-2 implementation that assumes it can read up to 31 bytes past the end of the input: https://godbolt.org/z/r33h75j5h https://godbolt.org/z/r33h75j5h (yes, that's autogenerated C) Requires -fno-unroll-loops as otherwise clang gets overly unroll-y; the code is fast enough. Tail is dealt with by blending the originally read value with the new one.
- zX41ZdbW 4y agoClickHouse has SIMD implementation for lower/upper for ASCII and UTF-8. It can easily make ~20 GB/sec with 48 cores: https://pastila.nl/?0f15f812/179361234a6b79d27e18c8db7050bd07 https://pastila.nl/?0f15f812/179361234a6b79d27e18c8db7050bd0... Although it is only using SSE2. And the UTF-8 variant is using a shortcut with SSE2, another shortcut for a subset of code points and a slow path for a generic case.
- dylan604 4y agoAt the end of the day, I'm very thankful that other people are working/solving things like this so that I just write whatever high-level code I want to get something I need done now. I have lots of respect for this level of dev'ing effort so I can use the system as a tool like a person driving a car without knowing how internal combustion works. I consider it a version of standing on the shoulders of giants.
- mrlonglong 4y agoIf UTF-8 is used, this will not work.
- arthur2e5 4y agoNo UTF-8 in DNS. Well, not any more.
- Groxx 4y agoWhat is the canonical lower case form for domains anyway? Lowercasing is locale-sensitive.... or does it just lowercase the punycode and call it "done"?
- conradludgate 4y agoA few weeks ago I optimised[0] the Rust lower/upper case conversion methods to use more SIMD features. In the end, we took a very conservative level of unrolling since we deemed it unlikely that large inputs would need case conversions. [0]: https://github.com/rust-lang/rust/pull/97046 https://github.com/rust-lang/rust/pull/97046
- Aissen 4y agoI see you used criterion here on your own repo, but it really shows that rust is missing the benchmark testing (I know there's one in unstable); having the tests you wrote alongside the code would prevent future hotpath regressions.
- rep_movsd 4y agoWould it not be simpler to bitwise OR every 5th bit to one based on a byte mask for uppercase chars? Also, use SIMD - I think even AVX can do byte level paralellism for 256 and 512 bits at a time?