Extract specific positions from a char array

Question

I have two arrays:

char input[] = "ughIuytLikeretC";

and

bool mask[] = {
    false, false, false, true, false,
    false, false, true, true, true,
    true, false, false, false, true,
};

My function takes these two arrays and returns the characters in input whose positions are true in mask such that in this example, the result being ILikeC.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

char *filtArray(char input[], bool mask[], char *filtered) {
    int j = 0;
    int i;
    for (i = 0; input[i]; i++) {
        filtered[j] = input[i];
        j += mask[i];
        }

    filtered[j] = 0;
    return filtered;
}

filtArray will run on billions of "input" strings of constant length and "mask" will be the same for all "input"s.

Answer 1

I see some things that may help you improve your code.

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. One good way to address that is by the use of comments. Another good technique is to include test code showing how your code is intended to be used. Here's the test main I used for your code:

int main() {
    const char *input[2] = {
        "ughIuytLikeretC", 
        "xxxExxxdwarxxxd",
    };
    const bool mask[] = {
        false, false, false, true, false,
        false, false, true, true, true,
        true, false, false, false, true,
    };
    char filt[100];
    char maskstr[100];
    // create the mask string
    pmask(mask, maskstr);

    printf("Orig: %s\nMask: %s\nFilt: %s\n", input[0], maskstr, filtArray(input[0], mask, filt));
    printf("Orig: %s\nMask: %s\nFilt: %s\n", input[1], maskstr, filtArray(input[1], mask, filt));
    for (int i = 0; i < 10000000; ++i) {
        int n = rand() > RAND_MAX/2 ? 1 : 0;
        printf("Orig: %s\nMask: %s\nFilt: %s\n", input[n], maskstr, filtArray(input[n], mask, filt));
    }
}

After it applies the function to two strings, it then iterates 10 million times, choosing one or the other test inputs randomly. This is for testing timing.

Use const where practical

The filtArray function does not (and should not) alter either the passed input or mask arrays and so both of those should be declared const.

char *filtArray(const char input[], const bool mask[], char *filtered) {

Consider bounds checking

If the input strings have already been validated for length, the function you have is OK, but in general, it's good to make sure there is enough room to copy the masked characters. If there isn't enough room, that's the recipe for a buffer overflow vulnerability and must be eliminated, either by the calling routine or by this one.

Consider a custom copy

If the same mask is used for billions of strings, it would probably make sense to do things differently. For example, one alternative might look like this:

#include <string.h>

char *filtArray(const char input[], char *filtered) {
    memcpy(&filtered[1], &input[7], 4);
    filtered[0] = input[3];
    filtered[5] = input[14];
    filtered[6] = '\0';
    return filtered;
}

Note that the mask is no longer used in this version, because the code has implemented it implicitly. This is less flexible but offers better performance. For 10 million strings on my machine, your original version takes about 1.3 seconds, while the version shown here takes around 1.0 seconds (redirecting the output to /dev/null on a Linux machine).

Use pointers rather than indexing for speed

Pointers are generally a faster way to access elements than using index variables. For example, your filtArray routine could be written like this:

char *filtArray(const char *input, const bool *mask, char *filtered) {
    char *beginning = filtered;
    for ( ; *input; ++input, ++mask) {
        if (*mask) {
            *filtered++ = *input;
        }
    }
    *filtered  = '\0';
    return beginning;
}

Because you're just beginning, this may seem strange to you, but this kind of use of pointers is a very common idiom in C.

Compilers are good, but not quite that good yet

Because there's a tendency to assume the compiler will take care of it, here's compiler output comparison of the two approaches using gcc for ARM using the on-line compiler explorer: https://godbolt.org/z/Y0TeVX

As can be seen in this case, the generated assembly code for the pointer version is much shorter. Shorter code is usually faster (and it is in this case according to my testing) but not always. For those who are expert in compiler design: The typical improvement is as likely to be the elimination of extra live variables as for the use of pointers per se, but the effect is nonetheless real.

Measured timings

For each of the three variations, original, pointer, and memcpy, here are the measured times for 10 million iterations and the variances of each set of samples and the relative speed measured as the average speed compared with the average speed of the original expressed as a percentage. With no optimization:

\$\begin{array}{l|c|c|c} {\bf name}&{\bf avg (s)}&{\bf var (s)}&{\bf relative}\\ \hline \text{original}&1.344&0.01853&100.00\% \\ \text{pointer}&1.244&0.01193&92.56\% \\ \text{memcpy}&0.998&0.01177&74.26\% \end{array}\$

With -O2 optimization:

\$\begin{array}{l|c|c|c} {\bf name}&{\bf avg (s)}&{\bf var (s)}&{\bf relative}\\ \hline \text{original}&1.038&0.01462&100.00\% \\ \text{pointer}&1.000&0.00135&96.34\% \\ \text{memcpy}&0.948&0.00692&91.33\% \end{array}\$

These results were on a 64-bit Linux machine using gcc version 8.2.1. I look forward to seeing other measured timing results. Time is user time as measured by time -f %U (See https://linux.die.net/man/1/time for man page).

Answer 2

The code compiled with no warnings and ran properly on first time which is great.

Let's see what can be improved.

Style

The indentation of the code seems a bit weird. I do not know if this is how it looked originally or if it got broken when it was copied here.

Also, it may be worth adding some documentation describing the inputs you are expecting (in your case, 3 arrays of same size, the first one being 0-terminated).

Do less

You use the mask only to know whether j is to be incremented. Actually, you could rewrite:

j += mask[i];

as

    if (mask[i])
        j++;

which is more explicit but less concise.

The real benefic is when you realize than updating filtered can be done only when we have mask[i]. We can write:

    if (mask[i])
    {
        filtered[j] = input[i];
        j++;
    }

or the equivalent:

    if (mask[i])
        filtered[j++] = input[i];

Null character

Instead of filtered[j] = 0;, you could use the Null Character which is equivalent here but more usual and write: filtered[j] = '\0';.

Signature

I am not sure if it is really useful to have the filtered value returned as it is already known by the calling function. Also, filterArray may be a better name.

Going further

Instead of definining a mask as an array of boolean, you could provide an array with the positions of the characters you are interested in.

In your case, you'd provide something like: {3, 7, 8, 9, 10, 14 }.

This could be less efficient because we'd perform a smaller number of iterations. Here, we'd iterate over 6 elements instead of 15.

The corresponding mask could be converted manually (which is what I did here) if it is for a known value or you could write a function to pre-process the mask. This seems to be relevant in your case as the same mask is used many times on different inputs.