C program to generate Seed programs from statically defined Befunge code

Question

My program takes static input, and then number crunches for a few hours. I am currently using Macros, but is there a better, more "user friendly" way to do this without losing on performance.

I have written a program in C to generate Seed programs from a Befunge program. It is a very long, brute force calculation. So that it can be heavily optimised, the input variables are hardcoded using Macros. However, I was wondering if there was a better way to do this that would lead to the same or better optimisation.

Here's the Mersenne Twister I used: math.sci.hiroshima-u.ac.jp/~m-mat/...

/*
Copyright wizzwizz4 (c) 2015
*/

#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include "mt19937ar.h"

/*Settings*/
#define PROGRAM_STRING "\"ck,@!dlroW ,olleH"
#define PROGRAM_LENGTH 18
#define   INITIAL_SEED 0
/*End settings*/

/*Meta settings*/
#define PROGRAM_LENGTH_TYPE char
/*End meta settings*/

unsigned long seed = INITIAL_SEED;
char prog[PROGRAM_LENGTH] = PROGRAM_STRING;

/*Ctrl-C Handlers*/
void ignore(int sig) {
    signal(SIGINT, ignore);
}
void panic(int sig) {
    printf("Quick! Copy the output. Something's trying to close me!");
    signal(SIGINT, ignore);
}
void stopped(int sig) {
    printf("We got to %u\nPress any key to quit...", seed);
    signal(SIGINT, panic);
    getchar();
    exit(1);
}
void finished(int sig) {
    printf("Copied the output? Great.\nPress any key to quit...");
    signal(SIGINT, panic);
    getchar();
    exit(0);
}
/*End Ctrl-C Handlers*/

int main(void) {
    signal(SIGINT, stopped);

    PROGRAM_LENGTH_TYPE x; /*The program loop character*/
    _Bool y; /*Seed === Program?*/

    /*Take 32 from the program characters*/
    for (x = 0; x < PROGRAM_LENGTH; x++)
        prog[PROGRAM_LENGTH] = prog[PROGRAM_LENGTH] - 32;

    /*Do the checking*/
    while (1) {
        init_genrand(seed);
        y = 1;
        for (x = 0; x < PROGRAM_LENGTH; x++) {
            /*Compares generated character to expected one*/
            if (prog[PROGRAM_LENGTH] != (char)(genrand_res53() * 96) ) {
                y = 0;
                break; /*Break if wrong; no sense in checking the rest!*/
            }
        }
        if (y) break; /*If the for loop didn't break, seed was right!*/
        seed++;
    }

    /*Output, and make sure nobody gets hurt*/
    printf("COMPLETE Seed program:\n%u %u\nMake sure you copy this down\nPress ^C to quit...", PROGRAM_LENGTH, seed);
}

Answer 1

[Is] there was a better way to do this that would lead to the same or better optimisation.

Yes: don't hardcode stuff the compiler can't do any optimizations about and that makes your program a pain to use. (And an eye-sore because of all those ALL_CAPS_MACROS everywhere.)

Hardcoding the Befunge program gives the compiler next to no useful information. All you're doing with it is comparing it with random data that the compiler can't reason about. (And you're doing that after modifying the string at runtime anyway - the compiler might see through this, but you're adding a tough layer there.)

The hardcoded length could potentially be used to control the amount of loop unrolling in the main loop that the compiler will attempt/choose, but I won't believe that has a significant impact until I see an actual benchmark.

Using char for the loop variables rather than the plain old int won't buy you anything, except the obfuscation you got through that macro - not desirable. Smaller doesn't always mean faster - you might actually incur a performance loss here compared to using a plain int.

What might give the compiler an advantage is having the RNG functions bodies visible when it compiles your main loop - that's the only "computationally expensive" step in your code. But you've put them in a different translation unit, so you've prevented inlining unless you use some form of whole-program optimization/link-time optimization.

So, if I were you, I would first keep this program as it is, and measure its performance on known input(s).

Then start a new one without any of those macros:

• read the parameters from command line arguments
• move the actual processing code to a function that takes those arguments and returns a seed if found

At this step, again, measure the performance. If there's a measurable difference either way, try to figure out why. Once you have the why, you can look further at what needs to be done to take advantage (or reject) that difference.

Then you can try again after move the relevant RNG functions into the main file.

Then you can check out your compiler's profile-guided optimization mode if it has it, and see if that changes things.

Measure, rinse, repeat.

Answer 2

Bug in indexing

This code:

for (x = 0; x < PROGRAM_LENGTH; x++)
    prog[PROGRAM_LENGTH] = prog[PROGRAM_LENGTH] - 32;

should be:

for (x = 0; x < PROGRAM_LENGTH; x++)
    prog[x] = prog[x] - 32;

and this code:

    for (x = 0; x < PROGRAM_LENGTH; x++) {
        /*Compares generated character to expected one*/
        if (prog[PROGRAM_LENGTH] != (char)(genrand_res53() * 96) ) {
            y = 0;
            break; /*Break if wrong; no sense in checking the rest!*/
        }
    }

should be:

    for (x = 0; x < PROGRAM_LENGTH; x++) {
        /*Compares generated character to expected one*/
        if (prog[x] != (char)(genrand_res53() * 96) ) {
            y = 0;
            break; /*Break if wrong; no sense in checking the rest!*/
        }
    }

Inefficient use of rng

Currently, after each failed seed, you reseed the Mersenne twister with the next seed. This requires two full passes over the internal array, or 624 * 2 operations. The first pass happens during seeding and the second pass happens when you generate the first random number.

Besides the slowness of this approach, you are also limiting yourself to only \$2^{32}\$ possible seeds. This means that you will probably never find a match given a program length of 18 characters (\$96^{18} = 2^{118}\$).

Edit: I didn't realize that "Seed" was an actual specification. I don't believe it can work given how most Mersenne twister implementations are seeded using a 32-bit value instead of a 19937-bit value. The below idea is something that I think could work better than "Seed" but would not be suitable for your program.

You would be better off if you didn't reseed and instead searched for the program within a fixed seed. So for example, you could use seed 0 as your fixed seed and attempt to find the program after N calls to the rng. You would return N as the result. This way, you will utilize the full rng period of \$2^{19937}\$ instead of just using \$2^{32}\$ possibilities by varying the seed.

However, even this approach would be doomed to fail. As mentioned earlier, the program length of 18 means about a 1 in \$2^{118}\$ chance of finding the program with each iteration. So you will probably not succeed within the lifetime of the universe.

No need to use floating point

Currently you use:

 (char)(genrand_res53() * 96)

to generate a random character in the range 0..95. This is actually pretty slow because it uses two 32-bit random numbers converted to a 53-bit double, then converted back to a character. It would be faster if you used the simpler:

(char)(genrand_int32() % 96)

Edit: Again, if the "Seed" spec requires the use of the floating point version, then you should keep using it. I could not find a definitive spec for "Seed" so it is unclear whether it is required.