8
\$\begingroup\$

The following code was written with the intent to be as efficient as possible, where efficiency includes speed of execution, memory usage, and lines of code, all in support of the primary design constraint that it can change the payload argument buffer in-place (from the calling function's perspective).

In its current state:
It does successfully change the buffer in place. This has been tested with a 20Kb text file, and removing all occurrences of up to 26 character values, all from the set of ASCII printable characters. There is no reason I can think of that prevents the sizes of these two arguments from being larger - I just have not run any that are larger.

Because the function uses strdup to create a working buffer, speed of execution is affected. And, I am pretty sure it is more verbose than it probably could be in terms of lines of code, which also potentially could affect speed of execution. I believe there could be some positive effects from compiler optimizations.

Recommendations for improvements in speed of execution, size of code and memory usage will be appreciated.

Code:

////////////////////////////////////////////////////////////////////////////
//
// Description:  Removes all occurrences of characters contained
//               in 'remove buffer' from 'str' buffer. 
 //               
//
// Inputs        char *str     - buffer containing text to be modified
//               char * remove - buffer containing characters to be removed
//
// Outputs       char *str     - modified in place. 
//
// returns       void
//
//  Example:     char buffer[] = {"some string with^ sev!eral ***ch###ar@ to& remove\n"};
//               char s_rem[]  = {"^@&*)(#!\n"};
//               remove_chars(buffer, s_rem);
//
////////////////////////////////////////////////////////////////////////////
void remove_chars(char *str, char *remove)
{
    const char *o = remove;//original location keeper
    const char *oStr = str;//original location keeper
    int found = 0;
    char *dup = strdup(str);
    if(dup)
    {
        const char *oDup = dup;
        while(*str)//walk through string
        {
            while(*remove)//walk through unwanted list for each string char
            {
                if(*str == *remove)//compare characters, one-by-one
                {
                    remove = o;//place unwanted list to beginning of array
                    found = 1;
                    break;
                }
                else
                {
                    remove++;
                }
            }
            if(found)
            {
                str++;//skip unwanted character if found
                found = 0;
            }
            else
            {
                *dup = *str;// move both pointers if unwanted not found
                dup++;
                str++;      
            }
            remove = o;
        }
        *dup = 0;//NULL terminate
        dup = oDup;//bring pointer to original location
        str = oStr;//bring pointer to original location
        strcpy(str, dup); //place updated string into original   
        free(dup);
    }
}
\$\endgroup\$
3
  • 7
    \$\begingroup\$ "efficiency includes [...] lines of code" -- really? What exactly do you mean with that? You could write most of your code in a single line, but that's nonsense in most contexts and so is optimizing LOC. \$\endgroup\$ – uli Jun 3 at 19:16
  • 2
    \$\begingroup\$ @uli - I tried to provide wording that would define the constraints without being overly restrictive. Perhaps I could have said reasonable and straight forward reductions in size of code, well shy of obfuscation. But unlike some of the other programming areas on Stackoverflow, there must be a little room left for opinion and interpretation on Code Review \$\endgroup\$ – ryyker Jun 4 at 15:29
  • 1
    \$\begingroup\$ "str is changed and returned", yet function returns void ;) \$\endgroup\$ – YSC Jun 4 at 16:22
16
\$\begingroup\$

Your execution time is \$O(len(str)*len(remove))\$ which is slow.

Since you're restricting yourself to ASCII you can create a LUT like so

bool remove_lut[256]= {false};
while(*remove) remove_lut[*((unsigned char*)remove++)] = true;

Then remove the entire section where you scan the input for all charges in remove. And replace found with remove_lut[*((unsigned char*)str)] == true.

This should give you a speed up of a factor \$O(len(remove))\$.

Also as was previously pointed out, your code is not really in-place... Typically you'd do something like:

unsigned char* in = str;
unsigned char* out = str;
while(*in){
  if(!remove_lut[*in]){
     *out = *in;
      out++;
  }
  in++;
}
*out = '\0';

Edit

So I called to memory this lovely question from SO about why sorting and then processing is faster than just processing. Branch prediction, or rather branch misprediction, can cost a significant amount of CPU time, especially if you're branching on input data.

So I wrote a branchless version of my code above:

static void remove_chars(char *restrict str, const char *restrict remove)
{
  signed char lut[256] = {0};
  for (; *remove; remove++)
    lut[(unsigned char)*remove] = -1;

  while(*str && !lut[(unsigned char)*str]){
    str++;
  }

  const char *in = str;
  char *out = str;
  while (*in)
    {
      signed char mask = lut[(unsigned char)*in];
      // Bit-fiddling here because GCC refuses to omit a CMOV
      // which would likely be faster than this ugly hack. 
      *out = (~mask & (*in)) | (mask & (*out));

      // This emits branching code unfortunately
      //*out = mask ? *out : *in;

      out += mask + 1;
      in++;
    }
  *out = *in;
}

Note that this code will have much a more consistent runtime but the best case is slightly slower than the code up top. However the worst case time is much improved.

\$\endgroup\$
3
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Mast Jun 5 at 11:10
  • \$\begingroup\$ I commented about this elsewhere, but this branchless version can actually go about twice as fast (thanks for actually testing it) if you just always store, and optimize the mask updates to avoid a latency bottleneck. See my answer on this question. (commenting here for future readers.) \$\endgroup\$ – Peter Cordes Jun 6 at 0:33
  • \$\begingroup\$ "...because GCC refuses to omit a CMOV" Did you mean emit? BTW, several parts of this post are novel to me. look up table, and methods to incorporate branchless among them. Also spurred lots of amazing side comments. Thanks. \$\endgroup\$ – ryyker Jun 7 at 15:02
7
\$\begingroup\$
Aside from the other comments about "for real actually in-place", which are true, I think the biggest miss here is that you should be using [strpbrk][1] rather than doing your own scanning.

This really depends on the expected number of bad characters in the string, and the size of the replacement table. If both are low, for large strings strpbrk can be fast. However, as the number of replacement characters increases, it is nowhere near as fast as Emily's LUT method. With this rudimentary testbed,

#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>


static void remove_orig(char *restrict str, const char *restrict remove)
{
    const char *o = remove;//original location keeper
    const char *oStr = str;//original location keeper
    int found = 0;
    char *dup = strdup(str);
    if (dup)
    {
        const char *oDup = dup;
        while(*str)//walk through string
        {
            while(*remove)//walk through unwanted list for each string char
            {
                if(*str == *remove)//compare characters, one-by-one
                {
                    remove = o;//place unwanted list to beginning of array
                    found = 1;
                    break;
                }
                else
                {
                    remove++;
                }
            }
            if(found)
            {
                str++;//skip unwanted character if found
                found = 0;
            }
            else
            {
                *dup = *str;// move both pointers if unwanted not found
                dup++;
                str++;
            }
            remove = o;
        }
        *dup = 0;//NULL terminate
        dup = oDup;//bring pointer to original location
        str = oStr;//bring pointer to original location
        strcpy(str, dup); //place updated string into original
        free(dup);
    }
}


static void remove_lut(char *restrict str, const char *restrict remove)
{
    bool lut[256] = {false};
    for (; *remove; remove++)
        lut[*remove] = true;

    const char *in = str;
    char *out = str;
    while (*in)
    {
        if (!lut[*in])
        {
            *out = *in;
            out++;
        }
        in++;
    }
    *out = '\0';
}


static void remove_branchless(char *restrict str, const char *restrict remove)
{
    signed char lut[256] = {0};
    for (; *remove; remove++)
        lut[(unsigned char)*remove] = -1;

    while(*str && !lut[(unsigned char)*str]){
        str++;
    }

    const char *in = str;
    char *out = str;
    while (*in)
    {
        signed char mask = lut[(unsigned char)*in];
        // Bit-fiddling here because GCC refuses to omit a CMOV
        // which would likely be faster than this ugly hack.
        *out = (~mask & (*in)) | (mask & (*out));

        // This emits branching code unfortunately
        //*out = mask ? *out : *in;

        out += mask + 1;
        in++;
    }
    *out = *in;
}


static void remove_strpbrk(char *restrict str, const char *restrict remove)
{
    char *out = str;
    const char *bad_end = str;
    do
    {
        const char *good_start = bad_end,
                   *good_end = strpbrk(good_start, remove);
        if (!good_end)
        {
            strcpy(out, good_start);
            return;
        }

        int n_good = good_end - good_start;
        if (out != good_start)
            memcpy(out, good_start, n_good);
        out += n_good;

        const char *bad_start = good_end;
        bad_end = bad_start + strspn(bad_start, remove);
    } while (bad_end);

    *out = '\0';
}


static void remove_chux1(char *restrict str, const char *restrict remove)
{
    // Form table of remove character flags
    unsigned char flags[UCHAR_MAX + 1] = { 0 };
    const unsigned char *uremove = (const unsigned char *) remove;
    while (*uremove) {
        flags[*uremove] = 1;
        uremove++;
    }

    const unsigned char *ustr = (const unsigned char *) str;
    unsigned char *target = ustr;
    while (*ustr) {
        if (flags[*ustr] == 0) {
            *target++ = *ustr;
        }
        ustr++;
    }
    *target = '\0';
}


static void remove_chux2(char *restrict str, const char *restrict remove)
{
    // Form table of remove character flags
    signed char flags[UCHAR_MAX + 1] = { 0 };
    const unsigned char *uremove = (const unsigned char *) remove;
    while (*uremove) {
        flags[*uremove] = -1;
        uremove++;
    }

    unsigned char *target = (unsigned char *) str;
    const unsigned char *ustr = target;
    do {
        *target = *ustr;
        target += 1 + flags[*ustr];
    } while (*ustr++);
}


static void remove_tspeight(char *restrict s, const char *restrict r)
{
    char *d = s + strcspn(s, r); /* destination pointer - start at first removal */
    const char *p = d;           /* source */

    while (*p) {
        p += strspn(p, r);         /* skip to next non-removed char */
        size_t n = strcspn(p, r);  /* count of characters to keep */
        memmove(d, p, n);
        d += n;
        p += n;
    }
    *d = *p;                    /* terminate the string */
    return s;
}


static void remove_pcordes(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++;
  }
  // uin points at first char to *not* keep (or the terminating 0)
  // either way, doesn't need to be copied
  // and we can potentially avoid dirtying cache or page on end-of-string

  if (!*uin)
    return (char*)uin;

  char *out = (char*)uin;  // overwrite the char to remove
  //++uin;            // with the *next* char... by doing pre-increment in the loop
  unsigned char c;
  do
    {  // clang / gcc: 7 uops branchless, should be only 6
      c = *++uin;
      //size_t inc = keep_lut[c];     // doing this 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).
}


typedef void(*method_t)(char *restrict, const char *restrict);
static const method_t methods[] =
{
    remove_orig,
    remove_lut,
    remove_branchless,
    remove_strpbrk,
    remove_chux1,
    remove_chux2,
    remove_tspeight,
    remove_pcordes,
};
const int n_methods = sizeof(methods)/sizeof(*methods);
static const char *names[] = {
    "orig", "lut", "branchless", "strpbrk", "chux1", "chux2", "tspeight", "pcordes",
};

static void test()
{
    for (int i = 0; i < n_methods; i++)
    {
        printf("Testing %s\n", names[i]);

        char in1[] = "abcdef";
        methods[i](in1, "dba");
        assert(!strcmp(in1, "cef"));

        char in2[] = "abcdef";
        methods[i](in2, "abc");
        assert(!strcmp(in2, "def"));

        char in3[] = "abcdef";
        methods[i](in3, "def");
        assert(!strcmp(in3, "abc"));
    }
}


static void compare(int percent_bad, int to_remove)
{
    printf("\nInitializing comparison for %d%% bad chars, %d to remove...\n", percent_bad, to_remove);
    const size_t n = 1048576;
    char *orig_input = malloc(n + 1), *input = malloc(n + 1), *bad_chars = malloc(to_remove + 1);
    assert(orig_input);
    assert(input);
    assert(bad_chars);

    for (size_t i = 0; i < to_remove; i++)
        bad_chars[i] = ' ' + i;
    bad_chars[to_remove] = '\0';

    const char first_good = ' ' + to_remove;

    for (size_t i = 0; i < n; i++)
    {
        if (rand() % 100 < percent_bad)
            orig_input[i] = bad_chars[rand() % to_remove];
        else
            orig_input[i] = first_good + rand() % 16;
    }
    orig_input[n] = '\0';

    for (int m = 0; m < n_methods; m++)
    {
        double total_s = 0;
        const int n_reps = 100;
        for (int i = 0; i < n_reps; i++)
        {
            memcpy(input, orig_input, n);
            struct timespec start, end;
            assert(!clock_gettime(CLOCK_MONOTONIC, &start));
            methods[m](input, bad_chars);
            assert(!clock_gettime(CLOCK_MONOTONIC, &end));
            total_s += end.tv_sec - start.tv_sec
                + 1e-9*(end.tv_nsec - start.tv_nsec);
        }
        printf("%10s %.1lf ms\n", names[m], total_s/n_reps * 1e3);
    }

    free(orig_input);
    free(input);
}


int main()
{
    test();
    srand(0);
    compare(1, 4);
    compare(80, 4);
    compare(1, 32);
    compare(80, 32);
    return 0;
}

in this environment (I'm too lazy to install clang):

  • Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
  • Linux manjaro 5.4.118-1-MANJARO #1 SMP PREEMPT Tue May 11 17:46:18 UTC 2021 x86_64 GNU/Linux
  • gcc -O3 -march=native --std=c18 -Wall -s -D_GNU_SOURCE
Initializing comparison for 1% bad chars, 4 to remove...
      orig 4.7 ms
       lut 0.8 ms
branchless 1.0 ms
   strpbrk 0.4 ms
     chux1 0.8 ms
     chux2 0.7 ms
  tspeight 0.4 ms
   pcordes 0.7 ms

Initializing comparison for 80% bad chars, 4 to remove...
      orig 8.2 ms
       lut 2.7 ms
branchless 1.2 ms
   strpbrk 3.2 ms
     chux1 2.6 ms
     chux2 0.7 ms
  tspeight 3.3 ms
   pcordes 0.6 ms

Initializing comparison for 1% bad chars, 32 to remove...
      orig 25.5 ms
       lut 0.8 ms
branchless 1.0 ms
   strpbrk 1.1 ms
     chux1 0.8 ms
     chux2 0.8 ms
  tspeight 1.1 ms
   pcordes 0.6 ms

Initializing comparison for 80% bad chars, 32 to remove...
      orig 20.2 ms
       lut 3.0 ms
branchless 1.2 ms
   strpbrk 11.1 ms
     chux1 2.5 ms
     chux2 0.7 ms
  tspeight 11.3 ms
   pcordes 0.6 ms

So for the purposes of this question, it's good to think about the existence of strpbrk / strspn but know why not to use them - basically the reasons that @PeterCordes has enumerated in the comments. The differences are exacerbated to varying degrees based on the density of bad characters in the text, as demonstrated above.

For some incidental review coverage,

  • Use const for the second argument
  • Use restrict for both
  • Mark your translation-unit-local methods static
\$\endgroup\$
6
  • 1
    \$\begingroup\$ Comments are not for extended discussion; the conversation has been moved to chat. \$\endgroup\$ – Peilonrayz Jun 4 at 14:27
  • \$\begingroup\$ Specifically, see comments for some details on how glibc strpbrk / strcspn works (in asm for a few ISAs, but unfortunately not SIMD except on POWER8), and some SIMD ideas that could be worth it for large strings (where more time to build the accept/reject set is worth it). Or for special cases like a small-enough accept/reject set with x86 SSE4.2 string instructions, either 16 chars or less, or 8 ranges or less. \$\endgroup\$ – Peter Cordes Jun 4 at 20:39
  • \$\begingroup\$ Interesting results, I expected my code to be faster but not by that big of a margin when bad characters was so small. Out of curiosity would you be willing to include a few data points with larger and smaller bad word strings? \$\endgroup\$ – Emily L. Jun 5 at 0:49
  • 2
    \$\begingroup\$ I posted an answer with a more efficient branchless version of @EmilyL.'s branchless code. If you're interested in throwing that into the mix, if compiled with clang it should run about 1.5 cycles per input byte on Intel Sandybridge-family (e.g. Haswell / Skylake), similar on Zen1, and maybe a bit faster on Zen2 or Ice Lake. GCC wastes an instruction, so 1.75 cycles per input byte (front-end bottleneck). I didn't test it, only looked at the asm on Godbolt. \$\endgroup\$ – Peter Cordes Jun 5 at 12:40
  • 1
    \$\begingroup\$ For posterity can you mention the environment in which you are running \$\endgroup\$ – ryyker Jun 5 at 21:04
6
\$\begingroup\$

all in support of the primary design constraint that it can change the payload argument buffer in-place

However, the current implementation is not in-place, it builds a string in temporary space and then copies that back over the input. From the point of view of the caller that is in-place, but it isn't really in-place. This algorithm could be totally in-place. That would mean that characters of the input are copied inside the input itself, to either a place before the current location or exactly at the current location (never to a location that's further along), neither of which is a problem (the characters that are modified are not needed again later in this function), so temporary working space is not necessary.

 remove = o;//place unwanted list to beginning of array
 ...
 remove = o;

The first one is redundant, the position gets reset later anyway. Personally I would do it like the code below, to make this logic "more local" (vs spread out) and also more like "not messing up values" (vs "making a mess and then cleaning it up"):

char *remove_tmp = remove;
while (*remove_tmp)
{
    etc
}
\$\endgroup\$
5
  • \$\begingroup\$ Suggested changes to moving the remove pointers are good, I will use that. But I do not follow what you are saying about This algorithm could be totally in-place.. Yes, this would be desirable, but can you please expound a little more on how to do that? \$\endgroup\$ – ryyker Jun 3 at 17:16
  • 2
    \$\begingroup\$ @ryyker well I'm not sure what to explain because you basically just do it. Nothing really needs to change in your implementation, you just take something out. This algorithm already has the property that it won't change data that it needs later, only data that it is already done with: the write pointer cannot overtake the read pointer (they can be the same, they start out the same, but them being the same is still OK) \$\endgroup\$ – harold Jun 3 at 17:23
  • \$\begingroup\$ The only nuance I'd add here is that after shrinking in-place, you should follow up with a realloc. The implementation is efficient enough to understand that for shrinks no copying needs to be done. \$\endgroup\$ – Reinderien Jun 3 at 17:27
  • 4
    \$\begingroup\$ @Reinderien I'm conflicted on that, as that also bars the function from being used on strings that weren't malloced (or calloced). It would be easy to return the new length though, that would make it convenient for the caller to realloc if it knows that's appropriate (and is potentially useful for other purposes of course) \$\endgroup\$ – harold Jun 3 at 17:38
  • \$\begingroup\$ yep, that's safer. \$\endgroup\$ – Reinderien Jun 3 at 17:44
5
\$\begingroup\$

Error Handling

If strdup() fails, your function fails but it doesn't signal failure in any way. To me, that's a complete no-go, because that means that you can't guarantee anything! In this case, the way to fix it is of course to modify the buffer in-place, as others suggested.

Flow Control

There is a section

void remove_chars(char *str, char *remove)
{
    ...
    if (...) {
       // many lines of code
    }
}

Returning early would make the code easier to understand, you don't have to skip down to see nothing happens if the condition is not met. Also, you don't need to indent the code in between giving you more space. This won't change the speed of your code. However, keeping things easy to understand is helpful when optimizing code without accidentally breaking it.

Unnecessarily Large Scope

Check out found, which is only ever used once per iteration of the outer loop. It could be declared and initialized there instead. You could then avoid the redundant reset of the variable to its initial value, overall making the code easier to understand. It might even make it faster, though this is so simple that any better compiler will figure that out itself.

Const

The second buffer isn't modified, right? So do make it char const* instead! This doesn't make the code faster, but makes it easier to get right when the compiler catches accidental modifications.

\$\endgroup\$
1
  • \$\begingroup\$ Good and straight forward points all around. It appears you're in good company with some of them. Thanks. \$\endgroup\$ – ryyker Jun 4 at 16:13
5
\$\begingroup\$

Include the correct headers

We're missing <string.h> for strcpy(). We're also missing <stlib.h> for free() (but see below).

Don't ignore compiler warnings

Ensure you have every reasonable warning enabled, and pay attention to what your compiler tells you. For example:

void remove_chars(char *str, char *remove)
{
    const char *oStr = str;
    …
    str = oStr;
}

You probably intended to write

    char *const oStr = str;

Stick to standard library functions

Unless you're writing code that only makes sense on POSIX platforms, don't use functions such as strdup() that are not portable Standard C.

Improve the interface

We have no reason to modify the contents of remove, so pass it as a const char*. And make life easier for the caller by returning the modified string, to enable more chaining of functions.

Modify the string in-place

Allocation functions such as strdup() can fail (and when that happens, we should report the failure, rather than surprising the user by doing nothing).

We don't need to allocate memory, and can write a function that always succeeds. That reduces the amount of error-handling required, eliminates the need for <stdlib.h>, and gives a significant speed boost: the allocation is the most time-consuming part of the function.

Use library functions

Instead of looping over remove manually, we could use strchr() to determine whether it contains a given character. Better yet, we can use strcspn() to find the next character to remove.


Modified function

#include <string.h>

// Removes from S all occurrences of characters contained in R
// Returns S after modification
char *remove_chars(char *const s, const char *const r)
{
    char *d = s + strcspn(s, r); /* destination pointer - start at first removal */
    const char *p = d;           /* source */

    while (*p) {
        p += strspn(p, r);         /* skip to next non-removed char */
        size_t n = strcspn(p, r);  /* count of characters to keep */
        memmove(d, p, n);
        d += n;
        p += n;
    }
    *d = *p;                    /* terminate the string */
    return s;
}

Demo:

#include <stdio.h>
int main(void)
{
    char s[] = "Code Review Stack Exchange";
    const char *vowels = "AEIOUaeiou";
    printf("%s\n", remove_chars(s, vowels));
}
\$\endgroup\$
2
  • \$\begingroup\$ Several excellent points, in particular those under_Modify the string in-place_. Very straight forward implementation. I will test/benchmark and comment. Thank you. \$\endgroup\$ – ryyker Jun 4 at 15:14
  • 1
    \$\begingroup\$ I wouldn't return the modified string; I'd 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. \$\endgroup\$ – Peter Cordes Jun 5 at 10:58
5
\$\begingroup\$

Use const and restrict

For linear improvements, restrict allows select optimizations as code can assume the two strings do not overlap.

// void remove_chars(char *str, char *remove)
void remove_chars(char * restrict str, const char * restrict remove)

const allows remove_chars() to be called with a const remove string.


Assuming ASCII makes for brittle code

Rather than assume ASCII (0-127), allow full range char.

As char may be signed, fold characters to the unsigned char range.


Avoid multiple trips down each string

Once each is enough.


Avoid O(strlen(str)*strlen(remove)) runtime

Instead O(strlen(str)+strlen(remove)) runtime.


Sample code

void remove_chars(char * restrict str, const char * restrict remove) {
  // Form table of remove character flags
  unsigned char flags[UCHAR_MAX + 1] = { 0 };
  const unsigned char *uremove = (const unsigned char *) remove;
  while (*uremove) {
    flags[*uremove] = 1;
    uremove++; 
  }

  const unsigned char *ustr = (const unsigned char *) str;
  unsigned char *target = ustr;
  while (*ustr) { 
    if (flags[*ustr] == 0) {
      *target++ = *ustr;
    }
    ustr++;
  }
  *target = '\0';
}

Note: Given internal remove table, restrict no longer needed.

Return value

Not a real performance issue, yet consider returning something useful. Easy to implement ideas include:

  • char *remove_chars() and return the original src. This mimics many str...().

  • char *remove_chars() and return the pointer to the null character. Useful to 1) know the length with a subtraction 2) know were to append in various string processing without another strlen().

  • size_t remove_chars() and return the string length.

  • bool remove_chars() and return length changed indication.


Too much fun

Another idea: The replacement loop can be simplified to one that always copies the the character. It is just if the destination pointer is incremented.

void remove_chars(char * restrict str, const char * restrict remove) {
  // Form table of remove character flags
  signed char flags[UCHAR_MAX + 1] = { 0 };
  const unsigned char *uremove = (const unsigned char *) remove;
  while (*uremove) {
    flags[*uremove] = -1;
    uremove++;
  }

  unsigned char *target = (unsigned char *) str;
  const unsigned char *ustr = target;
  do {
    *target = *ustr;
    target += 1 + flags[*ustr];
  } while (*ustr++);
}

int main() {
  char str[100] = "Hello World";
  remove_chars(str, " ");
  printf("<%s>\n", str);  // <HelloWorld>
  remove_chars(str,  "dH");
  printf("<%s>\n", str); // <elloWorl>
  return 0;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Wow, I'm going to enjoy dissecting this code for understanding. With this implementation (reduced complexity) et.al it appears to be a Ferrari in C. Several subtleties offered here that I don't yet understand, but will look them up before asking. I'll comment again after some research and benchmark tests. \$\endgroup\$ – ryyker Jun 4 at 14:31
  • 1
    \$\begingroup\$ I have a question concerning this implementation: Why do you convert the pointers (char* to unsigned char*) instead of converting the elements? Pointer casts usually have a smell to them, which I'd prefer to avoid. For the first loop, I would have used flags[(unsigned char)*remove] = 1; instead. \$\endgroup\$ – uli Jun 4 at 15:24
  • \$\begingroup\$ I think it's only the description that assumes ASCII - the program itself appears completely encoding-agnostic. \$\endgroup\$ – Toby Speight Jun 4 at 17:47
  • \$\begingroup\$ @TobySpeight OP's testing was self-described as "all from the set of ASCII printable characters" and so conveyed that emphasis. True that OP's code is fairly encoding-agnostic (aside from archaic non-2's complement oops with while(*str) mis-handling -0). \$\endgroup\$ – chux - Reinstate Monica Jun 4 at 18:01
  • 2
    \$\begingroup\$ @uli The standard library string functions have "For all functions in this subclause, each character shall be interpreted as if it had the type unsigned char (and therefore every possible object representation is valid and has a different value)." So I do likewise. Your suggestion differs from this answer concerning the soon to be gone (C2x) non-2's compliment encoding as (unsigned char)*remove incorrectly treats -0 as a null character. \$\endgroup\$ – chux - Reinstate Monica Jun 4 at 19:26
5
\$\begingroup\$

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++;
  }
  // uin points at first char to *not* keep (or the terminating 0)
  // either way, doesn't need to be copied
  // and we can potentially avoid dirtying cache or page on end-of-string

  if (!*uin)
    return (char*)uin;

  char *out = (char*)uin;  // overwrite the char to remove
  //++uin;            // with the *next* char... by doing pre-increment in the loop
  unsigned char c;
  do
    {  // clang / gcc: 7 uops branchless, should be only 6
      c = *++uin;
      //size_t inc = keep_lut[c];     // doing this 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:                                    #
        movzx   ecx, byte ptr [rdi]           # zero-extending byte load from input string
        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 hitting 2 loads per clock to check 1 char per clock. 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 zeroing 8x 256 = 2kiB of memory, and pollute that much more L1d cache.


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 remove 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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Interesting, did you benchmark the code? I would be interested in the results, I entertained the idea of a keep-lut but didn't try it because of time (it was 4 AM for me) and that I feared the memcpy would be too expensive as overhead for short inputs. I like the use of zero terminator in the LUT to elide the check for the string end from the loop. \$\endgroup\$ – Emily L. Jun 5 at 15:52
  • \$\begingroup\$ @EmilyL.: setting to 1 instead of 0 gets compilers to load a vector constant from .rodata instead of pxor xmm0,xmm0, but other than that the array init and loop are basically identical. (In hand-written asm, I would have used pcmpeqd xmm0,xmm0 / SSSE3 pabsb xmm0,xmm0 to make a vector of all-ones, or maybe rep stosq, but it's very hard (with intrinsics) to get compilers to not do constant propagation and thus not load a constant from memory). I haven't benchmarked it, just looked at the main loop to predict performance based on the front-end bottleneck and lack of other bottlenecks. \$\endgroup\$ – Peter Cordes Jun 5 at 21:19
  • 1
    \$\begingroup\$ I ran the benchmark by Reinderein with your version and it's about twice the speed of my hacky bit-fiddle version and extremely consistent (as expected). Interestingly it still loses out to strpbrk when the bad chars rate is low and bad chars count is low, which I guess is due to the large number of unconditional store instructions, or maybe there's some SIMD magic happening. Or up to 40x improvement under the test conditions over OP. \$\endgroup\$ – Emily L. Jun 5 at 22:03
  • \$\begingroup\$ @EmilyL.: possibly just to strpbrk's loop unrolling, which you don't get in compiler-generated code. Or to the front-end throughput bottleneck of doing a store and load+add, instead of just a search and then doing the copying with a high-performance SIMD memcpy. glibc strpbrk just builds a LUT and uses it with pure scalar code. (code.woboq.org/userspace/glibc/sysdeps/x86_64/strcspn.S.html#77). Note that it should probably be using movzbl loads: the movb loads merging into the low byte of RCX were copied from the IA32 version, which made sense for P5 Pentium's slow movzx. \$\endgroup\$ – Peter Cordes Jun 5 at 22:08
  • \$\begingroup\$ @EmilyL.: And BTW, using the LUT to handle the end-of-string detection in the read-only scan was inspired by glibc's strpbrk which does the same thing. \$\endgroup\$ – Peter Cordes Jun 5 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.