Fork Exec Overhead

The other day I was trying to solve Day 4 - Advent of Code 2015.

My initial brute force approach looked something like this (but written in C):

for result in {1..1000000}; do
    echo -n "${puzzle_input}${result}" | md5sum
done

That is, compute the input for increasing numbers and send it to md5sum to compute the hash. (And stop if the hash matches the criteria.)

This took a very long time, but eventually I got the correct result.

This didn't feel like the right solution. What did I do wrong? I had a conversation with my friend, and he couldn't see a more clever solution either. Somehow we decided to try the same brute force approach but instead of computing the MD5 hash by using an external program, md5sum, we used a library. And now it was much faster. Even if we wrote that version in Python. Later I rewrote it in C using the openssl library to compute the MD5 sum. Even brute forcing part 2 finishes in around a second.

Perhaps that was what we were supposed to learn from this day? That spawning processes is expensive. Or there is a more clever solution yet to be found.

I had not thought that spawning process would create so much overhead. So I decided to dig a little deeper.

Here is a program that performs a plus 2 operation:

int main(int argc, char **argv) {
    int number = argv[1][0] - '0';
    return number + 2;
}

It assumes a single digit number is passed as the first argument. Then it returns the answer in the exit code:

$ ./plustwo 4
$ echo $?
6
$ ./plustwo 7
$ echo $?
9

The equivalent C function is this:

int plus_two(int number) {
    return number + 2;
}

Then I measured how long they took respectively using my rlprofiler. Here is the measurement code:

void measure() {
    unsigned int index;
    RLPROFILER_ZONE_BEGIN("plus_two_spawn");
    for (index = 0; index < NUM_LOOPS; index++) {
        assert(plus_two_spawn(3) == 5);
    }
    RLPROFILER_ZONE_END("plus_two_spawn");
    RLPROFILER_ZONE_BEGIN("plus_two");
    for (index = 0; index < NUM_LOOPS; index++) {
        assert(plus_two(4) == 6);
    }
    RLPROFILER_ZONE_END("plus_two");
}

The plustwo program is wrapped like this:

int plus_two_spawn(int number) {
    int result = 0;
    int status;
    char number_arg[2];
    number_arg[0] = '0' + number;
    number_arg[1] = '\0';
    pid_t pid;
    pid = fork();
    assert(pid != -1);
    if (pid == 0) {
        assert(execlp("./plustwo", "./plustwo", number_arg, NULL) != -1);
    } else {
        wait(&status);
        result = WEXITSTATUS(status);
    }
    return result;
}

That is, it does a fork+exec and obtains the result from the status code.

When I run this with NUM_LOOPS set to 100000, I get this:

========================================================================
Profiler
========================================================================
system clock frequency        = 1000000Hz
estimated cpu clock frequency = 2688015791Hz
elapsed time                  = 38786.33ms
------------------------------------------------------------------------
label          | hit count | exclusive            | total
---------------+-----------+----------------------+---------------------
plus_two_spawn |         1 | 100.00% (38786.07ms) | 100.00% (38786.07ms)
plus_two       |         1 |   0.00% (    0.25ms) |   0.00% (    0.25ms)
========================================================================

This means, that on average, the overhead of fork+exec is (38786.07-0.25)/100000 = 0.3878582 (~0.39 ms).

So if I need to brute-force check something 1 million times, the overhead of doing it via fork+exec is (0.3878582*1000000)/1000/60 = 6.4643033333333335 (6.46 minutes).

This was a fun exercise.