Printing out all possible combination of printable ASCII 7-bit characters to stdout

Question

This takes over 60 minutes to execute. The program is small in size, about 16kb. I am thinking that the repeated calls to printf slows it down significantly, rather than the nested for loops.

I used:

gcc -Wall -o charsprint charsprint.c ./charsprint

Without removing the printf call: How could this source code be smaller and/or faster? Can the nested for loops be condensed using pointers?

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

/*
* print out all combinations of chars between 1 and 5 chars
* 88 keys
* char combinations:
* basic a-f[26+] 0-9[10+] SPACE TAB CAPSLK ,./;'[]\-=`[14+]
* SHIFT A-F[26+] <>?:"{}|~!@#$%^&*()_+[21+]
* 52+35 = 87 chars available
* 87^5 = 4 984 209 207 possible combinations
*/

char ascii[] = {0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
        0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
        0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
        0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,
        0x20,0x21,0x22,0x23,0x24,0x25,0x26,0x27,
        0x28,0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f,
        0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,
        0x38,0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f,
        0x40,0x41,0x42,0x43,0x44,0x45,0x46,0x47,
        0x48,0x49,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f,
        0x50,0x51,0x52,0x53,0x54,0x55,0x56,0x57,
        0x58,0x59,0x5a,0x5b,0x5c,0x5d,0x5e,0x5f,
        0x60,0x61,0x62,0x63,0x64,0x65,0x66,0x67,
        0x68,0x69,0x6a,0x6b,0x6c,0x6d,0x6e,0x6f,
        0x70,0x71,0x72,0x73,0x74,0x75,0x76,0x77,
        0x78,0x79,0x7a,0x7b,0x7c,0x7d,0x7e,0x7f
        };

int main(void){
    int i,j,x,y,z;
    i = j = x = y = z = 0x00;
    char result[] = {0x00,0x00,0x00,0x00,0x00,0x00};
    for (i=0x20; i<0x7e; i++){
        result[0] = ascii[i];
        for (j=0x20; j<0x7e; j++){
            result[1] = ascii[j];
            for (x=0x20; x<0x7e; x++){
                result[2] = ascii[x];
                for (y=0x20; y<0x7e; y++){
                    result[3] = ascii[y];
                    for (z=0x20; z<0x7e; z++){
                        result[4] = ascii[z];
                        printf("%s\n", result);
                    }
                }
            }
        }
    }
    printf("\nDone...\n");
    return 0;
}

Answer 1

It can be smaller if you remove the pointless ascii array, like this:

int main(void){
    int i,j,x,y,z;
    i = j = x = y = z = 0x00;
    char result[] = {0x00,0x00,0x00,0x00,0x00,0x00};
    for (i=0x20; i<0x7e; i++){
        result[0] = i;
        for (j=0x20; j<0x7e; j++){
            result[1] = j;
            for (x=0x20; x<0x7e; x++){
                result[2] = x;
                for (y=0x20; y<0x7e; y++){
                    result[3] = y;
                    for (z=0x20; z<0x7e; z++){
                        result[4] = z;
                        printf("%s\n", result);
                    }
                }
            }
        }
    }
    printf("\nDone...\n");
    return 0;
}

And, it would seem logical that puts(result) should be faster than printf("%s\n", result), though the compiler might optimize both to the same thing anyway.

Answer 2

Doing IO certainly slows a process down but have you looked at the numbers?

You want to print about 5 billion lines presumably to the console. You state it takes (over) 60 minutes at your place. This means you are printing (at most) 23k lines per second to produce a total of 30GB of data (6 Byte per line).

I used janos' code to test this on my machine with -O3 and got 123k lines per second. Then I redirected the output to /dev/null and got 27M lines per second which finished your program in 3 minutes.

So the reason your program is slow is twofold: The program

1. creates an awful lot of data
2. is (presumably) outputting to a slow sink (the terminal)

The solutions are rather obvious:

1. Create less data, which might not be possible
2. Use a faster write target; options are:
   • memory
   • files

The terminal is so slow because it must display the data you are outputting, thus doing all kinds of additional work that slows down the process.

Answer 3

I recently answered this very similar question here, which basically asked the same question except they limited it to a-z A-Z 0-9 (62 characters) instead of this question which uses 96 characters (that I counted). So I took my program from that question and just added the extra characters. When I ran it, I was able to output all 5 character combinations to /dev/null in 3.6 seconds. Of course, outputting to an actual file takes a lot longer, but it really only measures the speed of your hard drive.

By the way, I also tested using printf and puts instead of write. Using either printf or puts caused the program to take 13.1 seconds instead of 3.6 seconds using write.

See my original answer to the other question here, where I explained my algorithm. The modified program is as follows:

// Print all combinations of the given alphabet up to length n.
//
// The best way to test this program is to output to /dev/null, otherwise
// the file I/O will dominate the test time.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

const char *alphabet = "abcdefghijklmnopqrstuvwxyz"
                       "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                       " \t,./;'[]\\-=`<>?:\"{}|~!@#$%^&*()_+"
                       "0123456789";

static void generate(int maxlen);

int main(int argc, char *argv[])
{
    if (argc < 2) {
        fprintf(stderr, "Usage: %s Length\n", argv[0]);
        exit(1);
    }

    generate(atoi(argv[1]));
    return 0;
}

/**
 * Generates all patterns of the alphabet up to maxlen in length.  This
 * function uses a buffer that holds alphaLen * alphaLen patterns at a time.
 * One pattern of length 5 would be "aaaaa\n".  The reason that alphaLen^2
 * patterns are used is because we prepopulate the buffer with the last 2
 * letters already set to all possible combinations.  So for example,
 * the buffer initially looks like "aaaaa\naaaab\naaaac\n ... aaa99\n".  Then
 * on every iteration, we write() the buffer out, and then increment the
 * third to last letter.  So on the first iteration, the buffer is modified
 * to look like "aabaa\naabab\naabac\n ... aab99\n".  This continues until
 * all combinations of letters are exhausted.
 */
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 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 4

Using puts(result); certainly must be faster (or a fast) than printf("%s\n", result);.

A very good compiler would optimize that.