return something useful that you already calculate, in case the caller has a use for it. In this case, return a pointer to the new 0 terminator in the string (or the new length): that's information the caller might have to recalculate if you threw it away. Don't repeat the design mistakes of C standard library functions like strcpy / strcat.
Branchless in-place filtering, about 2x speedup over Emily's version
In-place filtering should actually be in-place: don't copy any characters that don't need to move, and don't write at all if there are no characters in the remove set present. Besides the obvious saving in work, this avoids dirtying any cache lines that don't need to change. (And potentially setting the "dirty" bit on a whole page, or even saving a copy-on-write, e.g. on a mmap(MAP_PRIVATE) mapping of a file, or even causing I/O on a MAP_SHARED in-place modification of a file mapping, if the first 4k for example don't contain any chars to remove.)
But once you do need to write (to copy later characters over into place, to fill the gap from characters you're omitting), you can actually do less work by unconditionally storing, and just incrementing the destination pointer or not. (By adding a 0 or 1 from a lookup table). Emily's version is branchless, but does quite a bit of work to select which character to store back. But that doesn't matter; we're going to eventually overwrite it, with the terminating 0 if we won't find another keeper character first.
This version compiles to 6 µops in the inner loop (on a modern x86-64) with clang 12 -O3, so should run at about 1.5 cycles per char for large strings (after building the LUT) on a CPU like Skylake. It's branchless other than the loop-exit condition, so it shouldn't suffer from mispredicts when encountering a random mix of keep / remove characters. Or 7 µops with GCC because it wastes an instruction. (At least I got it not to load twice: I found and reported GCC bug #100922 while working on this.)
Repeated stores to the same address is something that CPUs can absorb pretty handily. Modern x86 has fully efficient byte stores, and microarchitectures that don't (for other ISAs) often can do merging in the store buffer to coalesce multiple stores into the same word into one full-word commit to L1d cache. It's likely that store coalescing hardware can handle overlaps efficiently.
Building a lookup table is the same idea that glibc strcspn / strspn use internally.
(I used @Emily's code as a starting point, but independently had the idea of making it branchless. Aggressive use of unsigned char was already my choice from looking at the asm, and @chux's answer and comments point out that it's actually better (more portable) to read char data through an unsigned char*, avoiding the possibility of a DeathStation 9000 where while(*ptr++) can be false for a non-2's-complement -0 if char is a signed type.)
I'm not sure I like unsigned char *uin as a variable name (unsigned input). I probably should have called it ustr.
#include <stddef.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
// returns a pointer to the (new) terminating zero in str
char *remove_chars_unconditional_write(char *restrict str, const char *restrict remove)
{
static_assert(UCHAR_MAX <= 65536, "Huge CHAR_BITS would use too much stack space for our lookup table");
unsigned char keep_lut[UCHAR_MAX+1]; // increment output pointer or not after storing this char
// be careful to only index with unsigned char: on some implementations (including x86), char is signed and thus can be negative.
memset(keep_lut, 1, sizeof(keep_lut));
const unsigned char *uremove = (const unsigned char*)remove;
do {
keep_lut[*uremove] = 0;
}while(*uremove++); // including terminating 0
const unsigned char *uin = (const unsigned char*)str;
while(keep_lut[*uin]) { // lut[0] = 0 catches end of string
uin++;
}
// Read-only scan may avoid dirtying some cache lines for early parts of the string, maybe even get to exit without dirtying it at all. And does less work per char.
// uin points at first char to *not* keep (or the terminating 0)
// either way, doesn't need to be copied
if (!*uin)
return (char*)uin;
char *out = (char*)uin; // overwrite the char to remove
// with the *next* char... by doing pre-increment in the loop
unsigned char c;
do { // x86-64 clang / gcc: 7 uops branchless, should be only 6
c = *++uin;
//size_t inc = keep_lut[c]; // Early LUT load? Doing it after the store helps clang; hopefully doesn't hurt CPU that can do memory disambiguation to see that it's not a reload of the recent store.
*out = c;
out += keep_lut[c]; // non-kept characters get overwritten next iter.
} while(c);
//*out = *in; // done as part of the final iteration
return out; // pointer to the terminating 0 (because lut[0] = 0).
}
(My code often ends up littered with performance-tuning alternatives and notes on compiler output. That's probably not something you want in your actual final code long-term. I left it in because how it compiles now, with current compiler versions, is relevant for performance comparisons with other answers.)
The final loop compiles like this (Godbolt) with clang 12 -O2 -march=haswell, also shown compiling nicely for AArch64.
.LBB0_4: # do {
movzx ecx, byte ptr [rdi] # zero-extending byte load from input string (avoids false dependency)
mov byte ptr [rax], cl # store it to the output position
movzx edx, byte ptr [rsp + rcx] # index the LUT with it
add rax, rdx # add the LUT result to the output pointer
inc rdi # unconditionally increment the input pointer
test rcx, rcx
jne .LBB0_4 # }while( (uint64_t)c != 0 );
...
ret # with char *out in RAX
With fusion of the test+jne, that's 6 uops for the front-end. Skylake is 4-wide, Zen is 5 instructions / 6 uops wide, whichever is narrower. IceLake is 5-wide. So we're not quite achieving 1 character per cycle even on the widest x86 cores (although the back-end could keep up with that: 2 loads + 1 store per clock on Haswell and later, and on Zen2 and later.)
(For very sparse occurrences of remove characters, read-only scan and memcpy can save enough front-end bandwidth to be worth it, actually achieving 2 loads per clock to check 1 char per clock during the scan part. strpbrk / memcpy loops can achieve that, at the cost of rebuilding the LUT on every call to strpbrk. memcpy internally uses wide 16 or 32-byte copies. glibc's x86-64 asm strpbrk just uses scalar code, but with some loop unrolling.)
Using a size_t keep_lut[UCHAR_MAX+1] would allow a memory-source add (which can remain as a single uop even with an indexed addressing mode on Haswell and later, and AMD), instead of movzx/add, but would require memsetting 8x 256 = 2kiB of memory on init, and pollute that much more L1d cache. So it would be much worse for short strings where startup overhead is significant, only worth it for very long strings.
Speaking of LUT init costs: initializing the elements to 1 instead of 0 doesn't cost any extra since its on the stack anyway. char lut[256] = {0}; compiles about the same as char lut[256]; memset(lut,0,256); Storing zeros makes it slightly cheaper to initialize a SIMD register to that on x86, but that's negligible. (AMD's clzero cache-line-zero instruction is like an NT store so only useful for large writes you're not going to read again soon.) Also some Intel non-server CPUs can optimize stores of zeros, not dirtying a cache line if it was already all-zero, when writing back from L2 to L3 on Skylake-client and Ice Lake-client. But that's unlikely to help here; at least one of the four cache lines (or 5 if not 64-byte aligned) will be non-zero, and it's only a few lines, and it's stack space anyway so it will likely get dirtied again by some other function call after this returns.
SIMD
If you wanted to make a version specifically for x86-64 with SSE4.2 string instructions, you could check for remove being either <= 16 bytes, or for being expressible as up to 8 ranges. Then you can find how many contiguous keep characters there are, 16 bytes at a time. https://www.strchr.com/strcmp_and_strlen_using_sse_4.2 explains the match-any and ranges functionality, and aggregation, of _mm_cmpistrz (asm pcmpistri). That gives you the index of the first match / non-match, so you can do a vector store and increment your output pointer by that much. (Assuming the read pointer is far enough ahead of your write pointer if you're not just storing single bytes. So probably you want to read the next input vector before storing this one.)
(Or even better, only 1 range or even a single character can be done with SSE2 or AXV2.)
With a really high removal percentage, you might switch strategy to looking for contiguous remove characters.
AVX512VBMI2 (Ice Lake) has vpcompressb which is a byte shuffle that left-packs a vector according to a compare mask. So if you can get any kind of SIMD compare to detect accept vs. reject, you could use it to do all the work of filtering a whole vector of 16, 32, or 64 chars at once. In only 2 uops. (Or 6 or 8 for a masked store to memory).
For the more general case of strcspn, I commented (moved to chat) with some ideas about what one might be able to do with SIMD. (And what glibc's strcspn actually does do, including POWER8 where it can make a 256-bit bitmap in a vector, instead of byte array, because vector instructions are useful for selecting a bit from a 256-bit vector. But on x86-64 it's just building and using a LUT with unrolled scalar loops, so building the LUT once yourself and amortizing that over multiple spans for keep characters is a big win.)
I also found a C-with-Intel-intrinsics implementation of some C standard string algorithms using SIMD, getting a speedup for large strings for strcspn by brute-force looping SSE4.2 _mm_cmpistri over the LUT checking 16 bytes at a time for any matches.
https://github.com/novemberizing/eva/blob/main/docs/extension/string/README.md
That could probably be adapted for this, and might do well if the distance between removed elements is long enough.
Actually developing a SIMD version is outside the scope of this code review; ask on Stack Overflow if you get stuck.
stris changed and returned", yet function returns void ;) \$\endgroup\$