4
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ Did you ever crack the seed for that specific Befunge program? \$\endgroup\$ – mbomb007 Dec 1 '16 at 22:34
  • \$\begingroup\$ @mbomb007 No, unfortunately. I cracked the seed for a shorter program but not for this one. \$\endgroup\$ – wizzwizz4 Dec 2 '16 at 7:22
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ What I don't understand is how having functions in a separate file prevents inlining, when they are included along with the header. \$\endgroup\$ – wizzwizz4 Dec 30 '15 at 11:17
  • \$\begingroup\$ You only included a header in your code. If you modified that header to include the function bodies, then inlining is possible just as if you'd pasted the whole code in your .c file. If it's just the header with prototype (as the .h file that is provided on the site you linked), the compiler can't inline at that step - it doesn't have the code for the functions, so it can't possibly insert the code directly instead of inserting a function call. \$\endgroup\$ – Mat Dec 30 '15 at 11:21
  • \$\begingroup\$ So how does it end up doing the function call if it can't find it? \$\endgroup\$ – wizzwizz4 Dec 30 '15 at 11:25
  • \$\begingroup\$ It knows what arguments must be passed in and what to expect in return from the signature. So it sets that up at the call site and insert a "call @foo" instruction. The linker does some magic at the end to resolve foo to an actual address. (This is horribly simplified.) \$\endgroup\$ – Mat Dec 30 '15 at 11:28
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Changing the RNG changes the "semantics" of Seed. I'm not sure what you propose is a valid transformation. \$\endgroup\$ – Mat Dec 30 '15 at 12:41
  • \$\begingroup\$ @Mat I didn't even realize that "Seed" was an actual spec. I thought OP made it up. Having read more about it, it is doomed because of what I said about the seed being 32-bit. \$\endgroup\$ – JS1 Dec 30 '15 at 12:42
  • \$\begingroup\$ "Actual spec" might be stretching it a bit :-) Interesting point about the search space, I hadn't even considered that. Or the bugs for that matter. \$\endgroup\$ – Mat Dec 30 '15 at 12:48
  • \$\begingroup\$ I made it work like the previous python implementation. \$\endgroup\$ – wizzwizz4 Dec 30 '15 at 13:04

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.