4
\$\begingroup\$

The four parameters a, b, c and d can be -1 (meaning it's not set) or a random one of {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}. If they are different from -1, they are guaranteed to be distinct.

The code looks at the four least significant bits of the four ints and tests if they all have a bit in common:

1101
1110
0100
0101

have the second left bit 1.

1001
1010
0000
0001

all have the second left bit 0.

1000
0110
0101
1101

have no common bit.

The following is possible:

a = -1, b = -1, c = 15, d =  4; //sim(a, b, c, d) == 0, because at least one is -1
a = -1, b = -1, c = -1, d = -1; //sim(a, b, c, d) == 0, because all are -1
a =  9, b =  1, c =  3, d =  5; //sim(a, b, c, d) == 1, because all values have a bit in common (a & 1, b & 1, c & 1 and d & 1 are all 1)
a =  8, b =  1, c =  2, d =  4; //sim(a, b, c, d) == 0, because there is no bit that is equal for a, b, c and d

The following will never happen:

a = 1, b = 1, c = 2, d = 5; // a == b, which is guaranteed to never happen because a == b

The code is meant to be as fast as possible on x86, readability would be a plus but is not necessary.


The code:

int sim(int a, int b, int c, int d)
{
    return ((a != -1) && (b != -1) && (c != -1) && (d != -1)) &&
    ((((a & 8) == (b & 8)) && ((a & 8) == (c & 8)) && ((a & 8) == (d & 8))) ||
     (((a & 4) == (b & 4)) && ((a & 4) == (c & 4)) && ((a & 4) == (d & 4))) ||
     (((a & 2) == (b & 2)) && ((a & 2) == (c & 2)) && ((a & 2) == (d & 2))) ||
     (((a & 1) == (b & 1)) && ((a & 1) == (c & 1)) && ((a & 1) == (d & 1))));
}

Are there obvious ways to speed up the code?

\$\endgroup\$
3
  • \$\begingroup\$ It's really not clear what you are asking here. \$\endgroup\$
    – pacmaninbw
    Commented Jun 11, 2016 at 12:52
  • \$\begingroup\$ @JanKorous This case is documented in the second line of the "The following is possible" section. It should return 0. \$\endgroup\$
    – bot47
    Commented Jun 11, 2016 at 12:55
  • \$\begingroup\$ @pacmaninbw Added a question to it. \$\endgroup\$
    – bot47
    Commented Jun 11, 2016 at 12:56

5 Answers 5

8
\$\begingroup\$

The code isn't bad, but it's a little more verbose than it needs to be. Consider that we don't really need to check one bit at a time; we can check four simultaneously.

The key here is that we're looking for bits that are the same in all four numbers. If we wanted to look for ones that were shared, we could do this:

a & b & c & d & 0xf

If we want to look for zeroes, we can simply invert:

~a & ~b & ~c & ~d & 0xf

If we put those together with the -1 part, it might look like this:

return a != -1 && b != -1 && c != -1 && d != -1 &&
    ((a & b & c & d) || (~a & ~b & ~c & ~d & 0xf));

However, the problem with this is that even though it's parallel, it still requires more operations than might be required.

If we consider the exclusive or function, it effectively return a 1 whenever the bits differ. So if there were only two numbers, we could do:

return (a ^ b) ^ 0xf;

The expression would only be false if all of the bits were different. We can use a similar strategy for three numbers.

return ((a ^ b) | (b ^ c)) ^ 0xf;

For this one, (a ^ b) returns 1 for every bit that is not the same between a and b, and the expression (b ^ c) returns 1 for every bit that is not the same between b and c. When we do a bitwise or of those quantities, only the the bits that are the same for all three quanties remain zeroes. When we do ^ 0xf we invert the bottom 4 bits so that only bits that are the same are ones.

Extrapolating this to four quantities,

return ((a ^ b) | (b ^ c) | (c ^ d)) ^ 0xf;

This is good but not sufficient since we still need to deal with the possible -1 quantities that may be among the inputs. One obvious way to do this is this:

return a != -1 && b != -1 && c != -1 && d != -1 &&
    (((a ^ b) | (b ^ c) | (c ^ d)) ^ 0xf);

To compare this routine which I'll call "Edward" to the one above, which I'll call "naive" to the original and the other three proposals so far, I used this code:

testcode.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>

bool sim(int a, int b, int c, int d)
{
    return ((a != -1) && (b != -1) && (c != -1) && (d != -1)) &&
    ((((a & 8) == (b & 8)) && ((a & 8) == (c & 8)) && ((a & 8) == (d & 8))) ||
     (((a & 4) == (b & 4)) && ((a & 4) == (c & 4)) && ((a & 4) == (d & 4))) ||
     (((a & 2) == (b & 2)) && ((a & 2) == (c & 2)) && ((a & 2) == (d & 2))) ||
     (((a & 1) == (b & 1)) && ((a & 1) == (c & 1)) && ((a & 1) == (d & 1))));
}

bool naive(int a, int b, int c, int d)
{
    return a != -1 && b != -1 && c != -1 && d != -1 &&
        ((a & b & c & d) || (~a & ~b & ~c & ~d & 0xf));
}

bool edward(int a, int b, int c, int d)
{
    return a != -1 && b != -1 && c != -1 && d != -1 &&
        (((a ^ b) | (b ^ c) | (c ^ d)) ^ 0xf);
}

bool BitsInCommon(int a, int b, int c, int d)
{
    if (a == -1 || b == -1 || c == -1 || d == -1)
        return false;

    int rslt = 0;
    rslt = (a & 15) & (b & 15) & (c & 15) & (d & 15);
    if (rslt != 0)
        return true;

    //check for zero bits in common???  if needed?
    rslt = ((a ^ -1) & 15) & ((b ^ -1) & 15) & ((c ^ -1) & 15) & ((d ^ -1) & 15);

    return rslt != 0;
}

bool jan_korous(int a, int b, int c, int d) {

    if( a == -1 || b == -1 || c == -1 || d == -1 ) { return 0; }

    const unsigned int diff = (a ^ b) | (c ^ d) | (a ^ c);

    return 
        ( (diff & 1) == 0 ) || 
        ( (diff & 2) == 0 ) || 
        ( (diff & 4) == 0 ) || 
        ( (diff & 8) == 0 );

}

bool scottbb(int a, int b, int c, int d) {
    if (a == -1 || b == -1 || c == -1 || d == -1) {
        return 0;
    }
    else {
        unsigned int all_1 = (unsigned int)a & (unsigned int)b &
                             (unsigned int)c & (unsigned int)d;
        unsigned int all_0 = ~((unsigned int)a | (unsigned int)b |
                               (unsigned int)c | (unsigned int)d);
        return (all_1 | (all_0 & 0xF)) ? 1 : 0;
    }
}

int main()
{
    bool troubleshoot = false;
    struct {
        const char *name;
        bool (*func)(int, int, int, int);
        double elapsed;
        bool isCorrect;
    } tests[] = {
        { "original", sim, 0, true },
        { "naive", naive, 0, true },
        { "Edward", edward, 0, true },
        { "dbasnett", BitsInCommon, 0, true },
        { "Jan Korous", jan_korous, 0, true },
        { "scottbb", scottbb, 0, true},
        { NULL, NULL, 0, false}
    };
    // see if they're all correct
    for (int a = -1; a < 16; ++a) {
        for (int b = -1; b < 16; ++b) {
            for (int c = -1; c < 16; ++c) {
                for (int d = -1; d < 16; ++d) {
                    for (size_t i = 1; tests[i].func; ++i) {
                        if (tests[i].func(a,b,c,d) != tests[0].func(a,b,c,d)) {
                            if (troubleshoot) {
                                printf("%s failed! [%d, %d, %d, %d] => %d, should have been %d\n",
                                    tests[i].name, a, b, c, d, 
                                    tests[i].func(a, b, c, d), 
                                    tests[0].func(a, b, c, d) 
                                );
                            }
                            tests[i].isCorrect = false;
                            if (troubleshoot) 
                                return -1;
                        }
                    }
                }
            }
        }
    }

    puts("All functions checked for accuracy; checking timing...");
    for (int iterations = 100; iterations; --iterations) {
        for (size_t i = 0; tests[i].func; ++i) {
            if (tests[i].isCorrect) {
                for (int a = -1; a < 16; ++a) {
                    for (int b = -1; b < 16; ++b) {
                        for (int c = -1; c < 16; ++c) {
                            for (int d = -1; d < 16; ++d) {
                                clock_t start = clock();
                                tests[i].func(a,b,c,d);
                                tests[i].elapsed += clock() - start;
                            }
                        }
                    }
                }
            }
        }
    }
    // print results
    for (size_t i = 0; tests[i].func; ++i) {
        if (tests[i].isCorrect) {
            printf("%12s\t%.10f\t%f%% %s than %s\n", tests[i].name, tests[i].elapsed,
                100.0*fabs(tests[i].elapsed-tests[0].elapsed)/tests[0].elapsed, 
                (tests[i].elapsed > tests[0].elapsed ? "slower" : "faster"),
                tests[0].name
            );
        } else {
            printf("%12s\twas not correct; no time recorded\n", tests[i].name);
        }
    }
}

Results:

Note: I've updated the results to include everybody's correct versions and to include the two solutions proposed by @js1 although I didn't bother duplicating the source code for those solutions in the code above.

All functions checked for accuracy; checking timing...
    original    1052389.0000000000  0.000000% faster than original
       naive    1034792.0000000000  1.672100% faster than original
      Edward    1024637.0000000000  2.637048% faster than original
    dbasnett    1032151.0000000000  1.923053% faster than original
  Jan Korous    1028349.0000000000  2.284326% faster than original
     scottbb    1026372.0000000000  2.472185% faster than original
         JS1    1035062.0000000000  1.646444% faster than original
  JS1 Lookup    1023049.0000000000  2.787942% faster than original

So in my tests, on a quad-core x86_64 machine, the Edward and Jan Korous routines are nearly identical in time and both are a small improvement (approximately 2%) over the original. There was a slight but persistent speed advantage to the "JS1 Lookup" version on this machine.

Compile command (Linux) was:

gcc -O2 -std=c99 testcode.c -o testcode && ./testcode

On a quad core ARM7, I got this result with the same code:

All functions checked for accuracy; checking timing...
    original    17302157.0000000000 0.000000% faster than original
       naive    17211229.0000000000 0.525530% faster than original
      Edward    17231692.0000000000 0.407261% faster than original
    dbasnett    17255411.0000000000 0.270174% faster than original
  Jan Korous    17115011.0000000000 1.081634% faster than original
     scottbb    17120390.0000000000 1.050545% faster than original
         JS1    17267606.0000000000 0.199692% faster than original
  JS1 Lookup    17118642.0000000000 1.060648% faster than original

I also tested on Windows under Cygwin, but found that the variability in timing on that platform was so large as to render the test results meaningless. As an example, here are four successive runs on that platform:

All functions checked for accuracy; checking timing...
    original    1902.0000000000 0.000000% faster than original
       naive    2124.0000000000 11.671924% slower than original
      Edward    2182.0000000000 14.721346% slower than original
    dbasnett    2091.0000000000 9.936909% slower than original
  Jan Korous    1980.0000000000 4.100946% slower than original
     scottbb    2144.0000000000 12.723449% slower than original
         JS1    2276.0000000000 19.663512% slower than original
  JS1 Lookup    2075.0000000000 9.095689% slower than original
All functions checked for accuracy; checking timing...
    original    2174.0000000000 0.000000% faster than original
       naive    2121.0000000000 2.437902% faster than original
      Edward    2088.0000000000 3.955842% faster than original
    dbasnett    2055.0000000000 5.473781% faster than original
  Jan Korous    2136.0000000000 1.747930% faster than original
     scottbb    2109.0000000000 2.989880% faster than original
         JS1    1855.0000000000 14.673413% faster than original
  JS1 Lookup    2149.0000000000 1.149954% faster than original
All functions checked for accuracy; checking timing...
    original    2073.0000000000 0.000000% faster than original
       naive    2154.0000000000 3.907381% slower than original
      Edward    1960.0000000000 5.451037% faster than original
    dbasnett    2288.0000000000 10.371442% slower than original
  Jan Korous    2032.0000000000 1.977810% faster than original
     scottbb    2091.0000000000 0.868307% slower than original
         JS1    2245.0000000000 8.297154% slower than original
  JS1 Lookup    2138.0000000000 3.135552% slower than original
All functions checked for accuracy; checking timing...
    original    2158.0000000000 0.000000% faster than original
       naive    2277.0000000000 5.514365% slower than original
      Edward    1840.0000000000 14.735867% faster than original
    dbasnett    2081.0000000000 3.568119% faster than original
  Jan Korous    2135.0000000000 1.065802% faster than original
     scottbb    2228.0000000000 3.243744% slower than original
         JS1    1969.0000000000 8.758109% faster than original
  JS1 Lookup    2010.0000000000 6.858202% faster than original
\$\endgroup\$
14
  • \$\begingroup\$ Well, crap. +100 for excellent test code. The error in my suggestion was a typo (mask with 0xFF in my return statement should have been 0xF). Fixing / commenting mine now. However... \$\endgroup\$
    – scottbb
    Commented Jun 12, 2016 at 2:42
  • \$\begingroup\$ -1 for performance conclusion. For ordered inputs, all of the implementations are similar. But what about for randomly-generated datasets? One thing I touched on (but didn't test or control for at all) is the frequency of -1 input values. At a certain point (not sure what that point is), that will have a big impact on performance. \$\endgroup\$
    – scottbb
    Commented Jun 12, 2016 at 2:45
  • \$\begingroup\$ @scottbb: I've also updated my answer and results. \$\endgroup\$
    – Edward
    Commented Jun 12, 2016 at 2:48
  • \$\begingroup\$ @scottbb: Evenly distributed randomly generated datasets should have similar results because each individual trial is timed separately (i.e. order doesn't matter). If we don't have to check for -1 inputs, I would anticipate that all implementations would see a speed increase. \$\endgroup\$
    – Edward
    Commented Jun 12, 2016 at 2:52
  • 1
    \$\begingroup\$ @MaxRied: Yes, it's a Raspberry Pi 2 model B. \$\endgroup\$
    – Edward
    Commented Jun 12, 2016 at 19:26
5
\$\begingroup\$

This is one of those happy instances where optimization will increase performance, maintainability, and readability. But first,

Analyzing your specification

With what you have described, the example outputs you have provided, and the code submitted, if I had to back-derive specifications for sim(), this is the best I could do:

  1. A return value of 0 indicates that
    • one or more inputs' values was -1; OR that
    • none of bits 0-3 were identical across all of the inputs
  2. A return value of 1 indicates that
    • none of the input's values were -1; AND that
    • all of the inputs share an identical bit (in bits 0-3); however only 1 common bit was detected (because the code returned as soon as the first commonality was detected), and which bit was common is unknown from the return value (i.e., further work on the part of the caller is required to determine which bit(s) is/are common).

Now maybe your use case does not care about which bit(s) is/are common. But one of the nice things about C's design, and most idioms in C, is that truth is reduced not to 0 and 1; but to 0 and anything but 0.

I will come back to this point in my suggestion.

Recognize the opportunity to work in parallel

C's bitwise operators are just parallel 1-bit logic functions, so there's no need to check for individual bit positions one at a time; bitwise operations do not "interact with" neighboring bits (unlike mathematical operators, which have carry / overflow).

So, to check if any of the "bit columns" in {a, b, c, d} are all 1:

int all_1 = (a & b & c & d);

Not only does this tell us if any "bit columns" are all 1, it also tells us which bit column is all 1 (any bits that are 1 in all of the input variables are set in all_1). Note that there are no logical operators here (i.e., ||, &&, ==). This is important for algorithmic optimization because logical operations can "stall" pipelining or cause branch mispredictions, which can kill performance.

For checking for "bit columns" of all 0, we could use the same concept (but with inverted inputs) as such: int all_0 = (~a & ~b & ~c & ~d). But that's not taking advantage of our knowledge of Boolean logic.

Recall from De Morgan's laws that (A')·(B') ≣ (A+B)' (that is, "(not A) and (not B)" is equivalent to "not (A or B)". Thus, we can calculate all_0 as:

int all_0 = ~(a | b | c | d) & 0xFF 0x0F;

Note that unlike in the case for all_1, we must mask with 0xFF 0x0F (because assuming bits 4-(num bits in int) aren't set in the inputs, bits >4 will always match as "all zeros").

Below is the rewritten sim() which matches the specifications (i.e., it returns strictly 0 or 1 as described above):

int sim(int a, int b, int c, int d) {
    if (a == -1 || b == -1 || c == -1 || d == -1) {
        return 0;
    }
    else {
        unsigned int all_1 = (unsigned int)a & (unsigned int)b &
                             (unsigned int)c & (unsigned int)d;
        unsigned int all_0 = ~((unsigned int)a | (unsigned int)b |
                               (unsigned int)c | (unsigned int)d);
        return (all_1 | (all_0 & 0x0F)) ? 1 : 0;
    }
}

Edit: Original code masked all_0 with 0xFF, which was erroneous. Mask (corrected above) should be 0x0F.

Note: I have use (unsigned int) casts because per the C11 standard, §6.5, para. 4 (emphasis mine):

[Bitwise] operators return values that depend on the internal representations of integers, and thus have implementation-defined and undefined aspects for signed types.

Thus, for ultimate portability, and to satisfy pedantic compilers / analyzers, use unsigned types/casts with bitwise operators.

Providing more information (return value)

If you have the leeway to change the specification, you could make a couple changes to the function to increase the information it provides to the caller:

  1. Return -1 if any of the inputs are -1.
  2. Let the output value tell you which "bit columns" were found identical. Even if you don't need that knowledge currently, calls to the function like such,

    if (x = sim(a, b, c, d) && x != -1) {
        ...
    }
    

    provide the same logical information as calling sim() as you originally posted it like: if (sim(a, b, c, d)) { ... }. But with this suggestion, the following information is available:

    if (x = sim(a, b, c, d) != -1) {
        unsigned int bits_with_1s = (unsigned int)x & (unsigned int)a;
        unsigned int bits_with_0s = (unsigned int)x & ~(unsigned int)a;
    }
    

Answering your real question (i.e. Performance) (finally!)

Are there obvious ways to speed up the code?

Let's compare your implementation of sim() to my functionally equivalent implementation. For testing, I created 2 datasets for input. One dataset ("Permutations") is just all the permutations of a, b, c, d (non- -1 inputs, values 0-15) (that's 164 = 65,536). The other dataset ("Randomization") is 65,536 randomly-generated sets of {a, b, c, d}, about 50% of numbers are -1, the rest are more-or-less evenly distributed between 0 and 16. I ran these datasets through our implementations 10,000 times. Here are the process's CPU times (in seconds):

As spec'd (checking for -1)
---- Permutations:
    CPU Time, your sim: 9.363161
    CPU Time, my sim  : 7.896544
---- Randomization:
    CPU Time, your sim: 12.981316
    CPU Time, my sim  : 12.601381
  1. When the data doesn't have any -1 values, my algorithm appears to be about 15% faster.
  2. When the data has lots of -1 values, there is not an appreciable difference. This makes sense, because most of the time, every set of {a, b, c, d} statistically should contain two -1 values. This shortcuts the differences between our algorithms, leaving only (in those cases), just checking for -1.

Edit: I lost track of your statement in the problem statement,

If they are different from -1, they are guaranteed to be distinct.

That means there are (16 choose 4) combination = 1820 possible input combinations, much less than 65,536 (or 16 * 15 * 14 * 13 = 43,680 permutations if order matters). However, that knowledge does not change the algorithm or opportunity to improve the performance.

But what about the differences between the algorithms?

I ran the same test inputs (including identical random data) against 3 other functions: your sim() (but sans checking for -1); my sim() (sans checking for -1); and finally, my sim() (also sans checking for -1) but following my suggestion and returning more than just 0 or 1. Here are the CPU times (in seconds):

No checking for -1
---- Permutations:
    CPU Time, your sim: 7.549818
    CPU Time, my sim  : 6.585851
    CPU Time, my sugg.: 6.326155
---- Randomization:
    CPU Time, your sim: 20.233936
    CPU Time, my sim  : 6.596144
    CPU Time, my sugg.: 6.257887

All of the masking with individual bits and logically comparing values really eats up your performance on the randomized data. For the ordered permutation runs, it's likely that some compiler optimizations in conjunction with branch prediction helped out your times (because every group of 16 calls to sim() had a, b, and c identical, varying d.

This is evident because for the randomized data runs, your original algorithm suffers a 3x performance penalty compared to my implementation.

The Takeaway

This is probably one of those cases where, if performance is really important because you're operating on a lot of data, or you need hard real-time performance, that it pays to take a step back, and reconsider the data flow. If at all possible, removing the cases where you're checking the inputs {a, b, c, d} for -1 will yield 2x-3x improvement in the algorithm computations. Alternately, if there's another way to handle those cases (mathematically, instead of conditional-logically), then you can just operate around the issue.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I'd like to accept two answers... \$\endgroup\$
    – bot47
    Commented Jun 12, 2016 at 8:00
5
\$\begingroup\$

First alternative solution

As mentioned in several other answers already, you can do many of the computations in parallel 4 bits at a time. To check whether all four numbers have a 1-bit in the same column, you can use:

if (a & b & c & d)
    return true;

To check whether all four numbers have a 0-bit in the same column, you can use:

if ((a | b | c | d) ^ 0xf)
    return true;

One trick that no one else has mentioned yet is that you can detect if any number is -1 in parallel as well, like this:

if ((a | b | c | d) == -1)
    return false;

Since there is a common expression between this and the previous check, you can save time by computing that expression once. Therefore, the complete solution is:

bool js1(int a, int b, int c, int d)
{
    int totalOr = a | b | c | d;

    return (totalOr != -1) && ((totalOr ^ 0xf) || (a & b & c & d));
}

Actually I found after doing timing tests that this ordering seems to be faster, probably because the if statement short circuits more often:

bool js1_reordered(int a, int b, int c, int d)
{
    int totalOr = a | b | c | d;

    return ((totalOr ^ 0xf) || (a & b & c & d)) && (totalOr != -1);
}

Second alternative solution

Another thing that I haven't seen mentioned yet is that the problem is small enough that you can construct a lookup table that holds every answer. In total, there are 16*16*16*16 = 65536 possibilities, which only requires an 8 KB table to store the answers (1 bit per answer). Assuming your computer's L1 cache is larger than 8 KB, you may be able to achieve faster speeds with a lookup table.

Here is my solution using a lookup table:

static uint16_t js1_table[0x1000];

void build_table(void)
{
    for (int a=0; a<16; a++) {
        for (int b=0; b<16; b++) {
            for (int c=0; c<16; c++) {
                for (int d=0; d<16; d++) {
                    if (((a | b | c | d) ^ 0xf) || (a & b & c & d)) {
                        unsigned int index = (a << 8) | (b << 4) | c;
                        js1_table[index] |= (1 << d);
                    }
                }
            }
        }
    }
}

bool js1_lookup(int a, int b, int c, int d)
{
    unsigned int index = (a << 8) | (b << 4) | c;

    if (index >= 0x1000)
        return false;

    return js1_table[index] & (1 << d);
}

The -1 detection works in a tricky way:

  1. If any of a, b, or c is -1, then the index computed will have high bits set and will be greater than 0x1000, thus causing the function to return false. This also doubles as a bounds check to prevent accessing past the end of the lookup table.
  2. If d is -1, then 1 << d will be 0, and anything anded with 0 will become 0, so the function will return false.

Timings

I used Edward's timing program but I modified the timing loop to reduce jitter by moving the call to clock() to the outermost loop so that it is called only once per test instead of once per function call. The drawback is that the loop overhead shows up in the final time, but since this overhead is the same for all tests, the relative speed of each solution is preserved. The absolute speed could theoretically be determined by measuring and subtracting the loop overhead, but I didn't bother to do that.

Here is the complete test program for reference:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>

bool sim(int a, int b, int c, int d)
{
    return ((a != -1) && (b != -1) && (c != -1) && (d != -1)) &&
    ((((a & 8) == (b & 8)) && ((a & 8) == (c & 8)) && ((a & 8) == (d & 8))) ||
     (((a & 4) == (b & 4)) && ((a & 4) == (c & 4)) && ((a & 4) == (d & 4))) ||
     (((a & 2) == (b & 2)) && ((a & 2) == (c & 2)) && ((a & 2) == (d & 2))) ||
     (((a & 1) == (b & 1)) && ((a & 1) == (c & 1)) && ((a & 1) == (d & 1))));
}

bool naive(int a, int b, int c, int d)
{
    return a != -1 && b != -1 && c != -1 && d != -1 &&
        ((a & b & c & d) || (~a & ~b & ~c & ~d & 0xf));
}

bool edward(int a, int b, int c, int d)
{
    return a != -1 && b != -1 && c != -1 && d != -1 &&
        (((a ^ b) | (b ^ c) | (c ^ d)) ^ 0xf);
}

bool js1(int a, int b, int c, int d)
{
    int totalOr = a | b | c | d;

    return (totalOr != -1) && ((totalOr ^ 0xf) || (a & b & c & d));
}

bool js1_reordered(int a, int b, int c, int d)
{
    int totalOr = a | b | c | d;

    return ((totalOr ^ 0xf) || (a & b & c & d)) && (totalOr != -1);
}

static uint16_t js1_table[0x1000];

void build_table(void)
{
    for (int a=0; a<16; a++) {
        for (int b=0; b<16; b++) {
            for (int c=0; c<16; c++) {
                unsigned int index = (a << 8) | (b << 4) | c;
                for (int d=0; d<16; d++) {
                    if (((a | b | c | d) ^ 0xf) || (a & b & c & d))
                        js1_table[index] |= (1 << d);
                }
            }
        }
    }
}

bool js1_lookup(int a, int b, int c, int d)
{
    unsigned int index = (a << 8) | (b << 4) | c;

    if (index >= 0x1000)
        return false;

    return js1_table[index] & (1 << d);
}

bool BitsInCommon(int a, int b, int c, int d)
{
    if (a == -1 || b == -1 || c == -1 || d == -1)
        return false;
    if (((a & b & c & d) & 0xf) != 0)
        return true;
    return (((a ^ -1) & (b ^ -1) & (c ^ -1) & (d ^ -1)) & 0xf) != 0;
}

bool jan_korous(int a, int b, int c, int d) {

    if( a == -1 || b == -1 || c == -1 || d == -1 ) { return 0; }

    const unsigned int diff = (a ^ b) | (c ^ d) | (a ^ c);

    return
        ( (diff & 1) == 0 ) ||
        ( (diff & 2) == 0 ) ||
        ( (diff & 4) == 0 ) ||
        ( (diff & 8) == 0 );

}

bool scottbb(int a, int b, int c, int d) {
    if (a == -1 || b == -1 || c == -1 || d == -1) {
        return 0;
    }
    else {
        unsigned int all_1 = (unsigned int)a & (unsigned int)b &
                             (unsigned int)c & (unsigned int)d;
        unsigned int all_0 = ~((unsigned int)a | (unsigned int)b |
                               (unsigned int)c | (unsigned int)d);
        return (all_1 | (all_0 & 0xF)) ? 1 : 0;
    }
}

int main()
{
    bool troubleshoot = false;
    struct {
        const char *name;
        bool (*func)(int, int, int, int);
        double elapsed;
        bool isCorrect;
    } tests[] = {
        { "original", sim, 0, true },
        { "naive", naive, 0, true },
        { "Edward", edward, 0, true },
        { "JS1", js1, 0, true },
        { "JS1 Reordered", js1_reordered, 0, true },
        { "JS1 Lookup", js1_lookup, 0, true },
        { "dbasnett", BitsInCommon, 0, true },
        { "Jan Korous", jan_korous, 0, true },
        { "scottbb", scottbb, 0, true},
        { NULL, NULL, 0, false}
    };

    build_table();

    // see if they're all correct
    for (int a = -1; a < 16; ++a) {
        for (int b = -1; b < 16; ++b) {
            for (int c = -1; c < 16; ++c) {
                for (int d = -1; d < 16; ++d) {
                    for (size_t i = 1; tests[i].func; ++i) {
                        if (tests[i].func(a,b,c,d) != tests[0].func(a,b,c,d)) {
                            if (troubleshoot) {
                                printf("%s failed! [%d, %d, %d, %d] => %d, should have been %d\n",
                                    tests[i].name, a, b, c, d,
                                    tests[i].func(a, b, c, d),
                                    tests[0].func(a, b, c, d)
                                );
                            }
                            tests[i].isCorrect = false;
                            if (troubleshoot)
                                return -1;
                        }
                    }
                }
            }
        }
    }

    puts("All functions checked for accuracy; checking timing...");
    for (size_t i = 0; tests[i].func; ++i) {
        if (tests[i].isCorrect) {
            clock_t start = clock();
            for (int iterations = 10000; iterations; --iterations) {
                for (int a = -1; a < 16; ++a) {
                    for (int b = -1; b < 16; ++b) {
                        for (int c = -1; c < 16; ++c) {
                            for (int d = -1; d < 16; ++d) {
                                tests[i].func(a,b,c,d);
                            }
                        }
                    }
                }
            }
            tests[i].elapsed = clock() - start;
        }
    }
    // print results
    for (size_t i = 0; tests[i].func; ++i) {
        if (tests[i].isCorrect) {
            printf("%12s\t%.10f\t%f%% %s than %s\n", tests[i].name, tests[i].elapsed,
                100.0*fabs(tests[i].elapsed-tests[0].elapsed)/tests[0].elapsed,
                (tests[i].elapsed > tests[0].elapsed ? "slower" : "faster"),
                tests[0].name
            );
        } else {
            printf("%12s\twas not correct; no time recorded\n", tests[i].name);
        }
    }
}

And here is the output when run on my computer (built with gcc -O2 on 64-bit Linux). Note: I originally had run these tests on 32-bit Cygwin, but it appears that the timings run more accurately on Linux:

All functions checked for accuracy; checking timing...
    original    4680000.0000000000      0.000000% faster than original
       naive    2580000.0000000000      44.871795% faster than original
      Edward    2380000.0000000000      49.145299% faster than original
         JS1    2530000.0000000000      45.940171% faster than original
JS1 Reordered   2240000.0000000000      52.136752% faster than original
  JS1 Lookup    1920000.0000000000      58.974359% faster than original
    dbasnett    2610000.0000000000      44.230769% faster than original
  Jan Korous    2340000.0000000000      50.000000% faster than original
     scottbb    2530000.0000000000      45.940171% faster than original

Frequency distribution affects algorithm

You didn't mention anything about the frequency distribution in the problem statement. For example, how often does -1 appear? Do the numbers 0..15 all appear with equal frequency? The "fastest" algorithm could depend on the answers to the above questions. For example, if -1 appears very often, then the check that determines if any of the four numbers is -1 becomes very important and may need adjusting. For example, the straightforward method

if (a == -1 || b == -1 || c == -1 || d == -1)
    return false;

might be the best because it will likely short circuit early and return quicker than something like this which has to always do three ORs:

if ((a | b | c | d) == -1)
    return false;
\$\endgroup\$
6
  • \$\begingroup\$ You grabbed my function before the typo was fixed. The mask with 0xFF in my return statement should be 0x0F. That will make my function return the correct values. \$\endgroup\$
    – scottbb
    Commented Jun 12, 2016 at 11:42
  • \$\begingroup\$ @scotbb I have fixed the program and I reran the timings. You can see the updated results above. \$\endgroup\$
    – JS1
    Commented Jun 12, 2016 at 17:11
  • \$\begingroup\$ thanks. BTW, excellent catch on the direct lookup table, nice optimization. \$\endgroup\$
    – scottbb
    Commented Jun 12, 2016 at 17:38
  • \$\begingroup\$ I tried the lookup table and it was actually about ~8% slower than the @Edward function. I tested it on an old i7, OS X, clang (llvm 7.3). I would buy all of you a beer... \$\endgroup\$
    – bot47
    Commented Jun 12, 2016 at 19:28
  • \$\begingroup\$ @MaxRied I tried with OS X, old Core i5, clang -O2, and I got JS1 fastest, JS1_Lookup 2nd fastest, Edward 3rd fastest, so I can't explain why it varies so much from machine to machine. Were you using my program to test? \$\endgroup\$
    – JS1
    Commented Jun 13, 2016 at 1:34
4
\$\begingroup\$

Alternative - instead of doing a lot of compares just do the boolean operations and single compare. This will provide consistent performance.

public bool BitsInCommon(int a, int b, int c, int d)
{
    if (a == -1 || b == -1 || c == -1 || d == -1) {
        return false;
        }
    int rslt = 0;
    rslt = (a & 15) & (b & 15) & (c & 15) & (d & 15);
    if (rslt != 0)
        return true;

    //check for zero bits in common???  if needed?
    rslt = ((a ^ -1) & 15) & ((b ^ -1) & 15) & ((c ^ -1) & 15) & ((d ^ -1) & 15);

    return rslt != 0;
}

Condensed version of above

private bool BitsInCommon(int a, int b, int c, int d)
{
    if (a == -1 || b == -1 || c == -1 || d == -1)
        return false;
    if (((a & b & c & d) & 0xf) != 0)
        return true;
    return (((a ^ -1) & (b ^ -1) & (c ^ -1) & (d ^ -1)) & 0xf) != 0;
}
\$\endgroup\$
8
  • 1
    \$\begingroup\$ I guess your last if/else could be simplified as return rslt != 0;. \$\endgroup\$
    – Jan Korous
    Commented Jun 11, 2016 at 13:31
  • 1
    \$\begingroup\$ @JanKorous Or just as return rslt;? \$\endgroup\$
    – bot47
    Commented Jun 11, 2016 at 13:38
  • \$\begingroup\$ @MaxRied Exactly :-) \$\endgroup\$
    – Jan Korous
    Commented Jun 11, 2016 at 13:39
  • \$\begingroup\$ My C skills aren't good. \$\endgroup\$
    – dbasnett
    Commented Jun 11, 2016 at 13:53
  • 1
    \$\begingroup\$ @pacmaninbw - I had the check for -1 as a comment. For us really old guys 15 = 0xf = o17 :) You'd probably write 0xffffffff instead of -1. \$\endgroup\$
    – dbasnett
    Commented Jun 11, 2016 at 14:54
2
\$\begingroup\$

I am not an expert for such low level things, but I would try to avoid repetition of operations by using one variable and (left-to-right evaluated) OR operator ('||'):

int sim(int a, int b, int c, int d) {

    if( a == -1 || b == -1 || c == -1 || d == -1 ) { return 0; }

    const unsigned int diff = (a ^ b) | (c ^ d) | (a ^ c);

    return 
        ( (diff & 1) == 0 ) || 
        ( (diff & 2) == 0 ) || 
        ( (diff & 4) == 0 ) || 
        ( (diff & 8) == 0 );

}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.