Brute Force Algorithm in C

Question

This is a simple brute force algorithm that I have programmed in C. All the program does is print out every possible combination of the given alphabet for the given length.

I would prefer suggestions on how to improve the algorithm, or decrease run-time. Any other suggestions are acceptable though.

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

static const char alphabet[] =
"abcdefghijklmnopqrstuvwxyz"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"0123456789";

static const int alphabetSize = sizeof(alphabet) - 1;

void bruteImpl(char* str, int index, int maxDepth)
{
    for (int i = 0; i < alphabetSize; ++i)
    {
        str[index] = alphabet[i];

        if (index == maxDepth - 1) printf("%s\n", str);
        else bruteImpl(str, index + 1, maxDepth);
    }
}

void bruteSequential(int maxLen)
{
    char* buf = malloc(maxLen + 1);

    for (int i = 1; i <= maxLen; ++i)
    {
        memset(buf, 0, maxLen + 1);
        bruteImpl(buf, 0, i);
    }

    free(buf);
}

int main(void)
{
    bruteSequential(3);
    return 0;
}

Answer 1

I'm going to skip reviewing the OP's code, which has already been reviewed quite nicely by others. Instead I'm just going to show a much faster version and explain it.

What is the algorithm?

Basically the way the algorithm works is that a buffer is created that holds alphaLen^2 patterns, where alphaLen is the length of the alphabet. A pattern is one combination, such as "aaaaa\n". The reason that alphaLen^2 patterns are used is because the buffer is prepopulated with the last 2 letters already set to all possible combinations. So for example, the buffer initially looks like (for length 5 patterns):

"aaaaa\naaaab\naaaac\n ... aaa99\n" (62*62 patterns, 23064 bytes in length)

On every iteration, the function uses write() to output the buffer, and then increments the third to last letter. This involves writing that letter alphaLen^2 times (once per pattern). So the first iteration goes like:

"aabaa\naabab\naabac\n ... aab99\n"
   ^      ^      ^           ^
   |      |      |           |
   +------+------+-----------+----- Characters written to buffer (62*62 changes)

Whenever the third to last character wraps around, then we also need to update the fourth to last letter. If that wraps around, the fifth to last letter is also updated, etc. This continues until the first letter wraps around, at which point we are done.

How fast is it?

For all testing, I outputted to /dev/null so that my hard drive speed would not be the limiting factor. I tried the OP's program for 5 letter patterns but for me it took way too long (203 seconds). So I'll use Edward's estimate of 18 seconds for the OP's program instead. I also tested Edward's program on my machine, as well as a second program I wrote where I extended the algorithm to hardcode the last 3 characters instead of 2. I am using Cygwin gcc (32-bit) with -O4 on a Windows desktop. Here are the results:

Time (secs)  Length   Program
-----------  ------   -------
    18.0       5      syb0rg
     9.6       5      Edward
     0.4       5      JS1 (2 characters)
     0.4       5      JS1 (3 characters)

   665.0       6      Edward
    26.0       6      JS1 (2 characters)
    24.2       6      JS1 (3 characters)

  1513.7       7      JS1 (3 characters)

As you can see, this algorithm is very fast.

The code

Both programs are available here on GitHub. I'll show the 2 character variation below:

static void generate(int maxlen)
{
    int   alphaLen = strlen(alphabet);
    int   len      = 0;
    char *buffer   = malloc((maxlen + 1) * alphaLen * alphaLen);
    int  *letters  = malloc(maxlen * sizeof(int));

    if (buffer == NULL || letters == NULL) {
        fprintf(stderr, "Not enough memory.\n");
        exit(1);
    }

    // This for loop generates all 1 letter patterns, then 2 letters, etc,
    // up to the given maxlen.
    for (len=1;len<=maxlen;len++) {
        // The stride is one larger than len because each line has a '\n'.
        int i;
        int stride = len+1;
        int bufLen = stride * alphaLen * alphaLen;

        if (len == 1) {
            // Special case.  The main algorithm hardcodes the last two
            // letters, so this case needs to be handled separately.
            int j = 0;
            bufLen = (len + 1) * alphaLen;
            for (i=0;i<alphaLen;i++) {
                buffer[j++] = alphabet[i];
                buffer[j++] = '\n';
            }
            write(STDOUT_FILENO, buffer, bufLen);
            continue;
        }

        // Initialize buffer to contain all first letters.
        memset(buffer, alphabet[0], bufLen);

        // Now in buffer, write all the last 2 letters and newlines, which
        // will after this not change during the main algorithm.
        {
            // Let0 is the 2nd to last letter.  Let1 is the last letter.
            int let0 = 0;
            int let1 = 0;
            for (i=len-2;i<bufLen;i+=stride) {
                buffer[i]   = alphabet[let0];
                buffer[i+1] = alphabet[let1++];
                buffer[i+2] = '\n';
                if (let1 == alphaLen) {
                    let1 = 0;
                    let0++;
                    if (let0 == alphaLen)
                        let0 = 0;
                }
            }
        }

        // Write the first sequence out.
        write(STDOUT_FILENO, buffer, bufLen);

        // Special case for length 2, we're already done.
        if (len == 2)
            continue;

        // Set all the letters to 0.
        for (i=0;i<len;i++)
            letters[i] = 0;

        // Now on each iteration, increment the the third to last letter.
        i = len-3;
        do {
            char c;
            int  j;

            // Increment this letter.
            letters[i]++;

            // Handle wraparound.
            if (letters[i] >= alphaLen)
                letters[i] = 0;

            // Set this letter in the proper places in the buffer.
            c = alphabet[letters[i]];
            for (j=i;j<bufLen;j+=stride)
                buffer[j] = c;

            if (letters[i] != 0) {
                // No wraparound, so we finally finished incrementing.
                // Write out this set.  Reset i back to third to last letter.
                write(STDOUT_FILENO, buffer, bufLen);
                i = len - 3;
                continue;
            }

            // The letter wrapped around ("carried").  Set up to increment
            // the next letter on the left.
            i--;
            // If we carried past last letter, we're done with this
            // whole length.
            if (i < 0)
                break;
        } while(1);
    }

    // Clean up.
    free(letters);
    free(buffer);
}

Answer 2

In this program, bruteImpl is a tight loop. I wouldn't bother optimizing anything else, even if it would save some time, because most of time will be wasted running bruteImpl anyway. Running memset one time won't save your time, as it's ran... length times. However, with length set to 5, bruteImpl is called... 15264777 times. This is definitely something worth optimizing.

The biggest limitation in performance is printf in my opinion. Console output is usually somewhat slow. If I remove printf, and instead make small loop counter, I get 2 seconds for length set to 5 (I added global count variable to force the loop to do anything, increased every time you would use puts).

The other problem is recursion that cannot be removed by compiler. However, in this case recursion appears to be needed (iterative algorithm that doesn't use the stack suggested by @200_success is 9 times slower than yours), so it's not worth removing it (you would have to simulate stack structure anyway). Recursion is slower than iteration in many algorithms, but sometimes it's just needed.

Also, the biggest problem is actually using the variables (it's not problem with your algorithm, just something worth mentioning). Practically doing anything involving values from your algorithm is slower. For example, I tried to add memcmp and strcmp in place of puts. memcmp makes your algorithm 6 times slower, and strcmp makes your algorithm 10 times slower. Your algorithm is already fast enough, if memcmp is already rather slow. Sometimes optimizing is just not worth it - compilers already do that really well.

Answer 3

I would say that this is pretty much impeccable as a recursive solution.

In bruteSequential(), I would rename i to len for clarity. As a slightly hackish optimization, you could move the memset() call before the for-loop, since you know that the output string lengths will never decrease. You could then combine it with the malloc() for

char* buf = calloc(maxLen + 1, sizeof(char));

As a helper function, bruteImpl() should be declared static.

Answer 4

There are some things I've seen that may help you improve your code.

Prefer iterations to recursion

Recursive functions are often a good way to approach a programming task, but there is a tradeoff in terms of memory and time. Specifically, one can often reduce or eliminate the computational cost of a function call and reduce or eliminate the memory overhead as well by converting from a recursive to an interative function.

Use pointers rather than indexing

Code that uses indexing often has the benefit that it's easy to read and understand:

for (int i = 0; i < alphabetSize; ++i) {
    str[index] = alphabet[i];
    // ...

However, code is often faster to use pointers instead. So for example, that code might be rendered like this:

for (const char *a = alphabet; *a; ++a) {
    str[index] = *a;
    // ...

It's likely that one could obtain even more time savings by converting the left hand side to use pointers as well.

Use the lowest level I/O that's practical

Using library functions like printf is convenient, but they aren't necessarily the most efficient. Something like printf("%s\n", str); has to go through the memory of str looking for the terminating NUL character which might not be needed if you already know the length.

Reduce I/O if practical

The usual bottleneck in programs like this is the input/output part. When you can replace I/O with memory access instead, it may lead to time savings. However, the underlying operating system might buffer I/O already, so the only way to check for sure is to measure it.

Putting it all together

Here's what I came up with as an alternative implementation that uses all of these suggestions:

// create a large buffer
static const int BUFFLEN=1024*100;

void brute2(int maxLen)
{
    char* indices = malloc(maxLen + 1);
    char* terminal = indices+maxLen;
    char *printbuff = malloc(BUFFLEN);
    char *pbend = &printbuff[BUFFLEN-1];
    char *b = printbuff;
    *pbend = '\0';
    ++indices[0];
    char *p;

    while (*terminal == 0) {
        // print value
        for (p = indices; *p; ++p)
            ;
        for (--p ; p >= indices; --p) {
            *b++ = alphabet[*p-1];
            if (b == pbend) {
                fwrite(printbuff, 1, b-printbuff, stdout);
                b = printbuff;
            }
        }
        *b++ = '\n';
        if (b == pbend) {
            fwrite(printbuff, 1, b-printbuff, stdout);
            b = printbuff;
        }
        // increment values
        int carry = 1;
        for (++p ; carry; ++p) {
            if ((*p += carry) > alphabetSize) {
                *p = 1;
                carry = 1;
            } else {
                carry = 0;
            }
        }
    }
    fwrite(printbuff, 1, b-printbuff, stdout);

    free(indices);
    free(printbuff);
}

Results

I modified your original driver program as follows:

int main(int argc, char *argv[])
{
    if (argc != 3) {
        puts("Usage: brute iterations old|new\n");
        return 1;
    }
    int iterations = atoi(argv[1]);
    if (argv[2][0] == 'o')
        bruteSequential(iterations);
    else
        brute2(iterations);
}

This allowed me to time various combinations. For example, on my computer, calculating all of the 5-character combinations took 55 seconds with this version and over 65 seconds for the original. Redirecting the output to /dev/null eliminates the overhead of actual disk I/O (5.2 gigabytes in this case) and reveals that the new version takes about 8.9 s on my machine, and the original version takes 18 seconds or about twice as long.

Answer 5

you don't need the memset in the for of bruteSequential you just need to add a '\0' to the end when max depth has been reached:

void bruteImpl(char* str, int index, int maxDepth)
{
    for (int i = 0; i < alphabetSize; ++i)
    {
        str[index] = alphabet[i];

        if (index == maxDepth - 1) 
            printf("%s\n", str);
        else bruteImpl(str, index + 1, maxDepth);
    }
}

void bruteSequential(int maxLen)
{
    char* buf = malloc(maxLen + 1);

    for (int i = 1; i <= maxLen; ++i)
    {
        buf[i]='\0';
        bruteImpl(buf, 0, i);
    }

    free(buf);
}

frankly you don't even need that as a simple buf[i]='\0'; in the for of bruteSequential will suffice, but that may over simplify it

Answer 6

This part of the code has a common beginner error:

    char* buf = malloc(maxLen + 1);

    for (int i = 1; i <= maxLen; ++i)
    {
        memset(buf, 0, maxLen + 1);
        bruteImpl(buf, 0, i);
    }

    free(buf);

It's undefined behaviour to pass a null pointer to memset(), so we need to make sure we only reach that point if malloc() returns a non-null pointer. That could be as simple as

    char* buf = malloc(maxLen + 1);
    if (!buf) {
        fputs("Out of memory\n", stderr);
        exit(EXIT_FAILURE);
    }