IF-free conception.

Discussion in 'C Programming' started by Evgeney Knyazhev, Feb 15, 2013.

  1. Good Time to all, Amici(Friends).

    Here, i'd like to discuss how to reduce conditional branches in the code. 1st of the all, i would like to share some tricks. Their description is here (http://alg0z.blogspot.ru/2013/02/if-or-no-if.html).
    -----------------------
    Thanks in Advance for attention of Yours.
    Evgeney Knyazhev, Feb 15, 2013
    #1
    1. Advertising

  2. Evgeney Knyazhev

    Eric Sosman Guest

    On 2/15/2013 3:51 PM, Evgeney Knyazhev wrote:
    > Good Time to all, Amici(Friends).
    >
    > Here, i'd like to discuss how to reduce conditional branches in the code. 1st of the all, i would like to share some tricks. Their description is here (http://alg0z.blogspot.ru/2013/02/if-or-no-if.html).
    > -----------------------
    > Thanks in Advance for attention of Yours.


    The blog illustrates the transformation of

    if(a[root]<a[child]){
    swap(a, root, child);
    root=child;
    }

    into the if-less "equivalent" (quotes because it isn't)

    int *p0, *p1, a[], i1, i2, empty, *pEmpty, root, child;
    (Aside: Looks like `a' should be `extern', or should be a function
    parameter, or should have dimension.)
    p0=&a[root];
    p1=&a[child];
    i2=(*p0<*p1);
    i1=(i2+1) AND 1;
    (Aside: Have you learned about the `!' operator yet?)
    p0=i2*p0 + pEmpty*i1;
    p1=i2*p1 + pEmpty*i1;

    .... and my first question is: "Where did you send the compiler's
    error messages?" Pointer arithmetic in C is defined for pointer
    plus-or-minus integer and for pointer minus pointer (both in
    suitable ranges), but does not define pointer times integer -- no,
    not even when the integer must be zero or one. The transformed
    code is meaningless in C, and the compiler should have complained.

    Later, you offer a pointer-less variant

    empty=a[root];
    a[root]=i2*a[child]+i1*a[root];
    a[child]=i2*empty+i1*a[child];

    .... and this one is not required to produce error messages. Note
    that it still leaves `root' at its original value (the if-full
    version changed it). Fixing this bug, while writing out the
    booleans again gives

    i2 = a[root] < a[child];
    i1 = !i2;
    empty = a[root];
    a[root] = i1 * empty + i2 * a[child];
    a[child] = i2 * empty + i1 * a[child];
    empty = root;
    root = i1 * empty + i2 * child;
    child = i2 * empty + i1 * child;

    (The last line corrects what looks like an oversight in the original
    code; just delete it if the original was really intended to do
    what it says.)

    It seems to me you must really *hate* branches if you're
    willing to go to such lengths to avoid them. (And only "maybe"
    to avoid them, since `i2 = a[root] < a[child];' may require a
    few branches itself.) You start with an `if' block containing
    four or five (fleshing out the `swap'), and wind up with seven
    or eight assignments, six or eight multiplications, three or four
    additions, and a non-negligible increase in obfuscation. That
    doesn't strike me as a good trade -- and I'm the child of a father
    who so disliked waiting at traffic signals that he would drive
    two miles out of his way to avoid them!

    Your technique will also run into trouble if you try to
    apply it to `a' elements for which multiplication is not
    defined. For example, try your transformation on

    char *a[42] = ...;
    int root = ...;
    int child = ...;
    if (strcmp(a[root], a[child]) < 0) {
    char *tmp = a[root];
    a[root] = a[child];
    a[child] = tmp;
    root = child;
    }

    .... and see how far you get. Surprises are also likely if `a'
    holds `double' values, some of which are infinities or NaNs
    or negative zeroes.

    In summary: I don't like your technique, not at all.

    --
    Eric Sosman
    d
    Eric Sosman, Feb 15, 2013
    #2
    1. Advertising

  3. Evgeney Knyazhev <> wrote:
    > Good Time to all, Amici(Friends).


    > Here, i'd like to discuss how to reduce conditional branches in
    > the code. 1st of the all, i would like to share some tricks.


    (snip)

    Some processors now have a conditional load instruction. It is up to
    the compiler to figure out when to use it, unless you are doing
    assembly coding. (In the latter case, you are in the wrong group.)

    There is a slight chance that a compiler might figure out the
    conditional operator when it wouldn't the conditional branch,
    but pretty slight.

    -- glen
    glen herrmannsfeldt, Feb 15, 2013
    #3
  4. Eric, thanks for reply. mostly, code, posted in the blog, is schematic ;D full code has been in source.
    Evgeney Knyazhev, Feb 16, 2013
    #4
  5. "i1 = !i2;" will be not working because i1 & i2 are integers. yes, you can set them as booleans, but i chose that way + it's question which variant is more quick.
    Evgeney Knyazhev, Feb 16, 2013
    #5
  6. ----------------------------------------------
    It seems to me you must really *hate* branches if you're
    willing to go to such lengths to avoid them. (And only "maybe"
    to avoid them, since `i2 = a[root] < a[child];' may require a
    few branches itself.)
    -------------------------------------------------
    Eric, it Just looks too lengthy because it takes more symbols to write, butgenerated code runs faster than with branches. i don't argue we have many algorithms not suitable to fight against branches, because w/o branching large bulk of code will be running absolutely for Nothing. But heap sort is better w/ no IFs. ;-)
    Evgeney Knyazhev, Feb 16, 2013
    #6
  7. Evgeney Knyazhev

    Eric Sosman Guest

    On 2/15/2013 7:53 PM, Evgeney Knyazhev wrote:
    > "i1 = !i2;" will be not working because i1 & i2 are integers. yes, you can set them as booleans, but i chose that way + it's question which variant is more quick.


    You are mistaken. `i2' is the result of an `<' operator,
    hence either zero or one. `!0' is 1, `!1' is zero. `!i2' is
    well-defined.

    But if you don't like `!i2', consider `1 - i2' -- still a
    simpler construct than your original `(i2 + 1) AND 1'.

    --
    Eric Sosman
    d
    Eric Sosman, Feb 16, 2013
    #7
  8. Evgeney Knyazhev

    Eric Sosman Guest

    On 2/15/2013 8:04 PM, Evgeney Knyazhev wrote:
    > ----------------------------------------------
    > It seems to me you must really *hate* branches if you're
    > willing to go to such lengths to avoid them. (And only "maybe"
    > to avoid them, since `i2 = a[root] < a[child];' may require a
    > few branches itself.)
    > -------------------------------------------------
    > Eric, it Just looks too lengthy because it takes more symbols to write, but generated code runs faster than with branches. i don't argue we have many algorithms not suitable to fight against branches, because w/o branching large bulk of code will be running absolutely for Nothing. But heap sort is better w/ no IFs. ;-)


    Thanks for submitting your measurements to support the
    "faster" claim. One question, though: Since the code you
    offered will not even compile, how did you measure it?

    --
    Eric Sosman
    d
    Eric Sosman, Feb 16, 2013
    #8
  9. Eric, you can download the source & app as well, so it will "heal" your questions.
    Evgeney Knyazhev, Feb 16, 2013
    #9
  10. -----------------------
    You are mistaken. `i2' is the result of an `<' operator,
    hence either zero or one. `!0' is 1, `!1' is zero. `!i2' is
    well-defined.
    ----------------------------------
    well, let's assume

    int i=0;
    i=!i;
    // then output: 0xffff
    Evgeney Knyazhev, Feb 16, 2013
    #10
  11. Evgeney Knyazhev

    James Kuyper Guest

    On 02/15/2013 08:23 PM, Evgeney Knyazhev wrote:
    > -----------------------
    > You are mistaken. `i2' is the result of an `<' operator,
    > hence either zero or one. `!0' is 1, `!1' is zero. `!i2' is
    > well-defined.
    > ----------------------------------
    > well, let's assume
    >
    > int i=0;
    > i=!i;
    > // then output: 0xffff


    "The result of the logical negation operator ! is 0 if the value of its
    operand compares unequal to 0, 1 if the value of its operand compares
    equal to 0. The result has type int. The expression !E is equivalent to
    (0==E)." (6.5.3.3p5)

    Therefore, 0xFFFF is not a legal value for a logical negation
    expression. I think that what you're thinking of is the bitwise
    complement operator, "~"

    i = ~i;

    What value 'i' will have after that expression is executed depends upon
    whether it's 2's complement, 1's complement, or sign-magnitude, but
    regardless of which case applies, it's guaranteed to be negative, which
    is not the case for 0xFFFF. Therefore, I assume you're also thinking as
    if 'i' had the type 'unsigned int', and UINT_MAX == 0xFFFF.

    --
    James Kuyper
    James Kuyper, Feb 16, 2013
    #11
  12. Thanks, James, ye're correct. my mind shaded to confuse "!" & "~" operations :D
    Evgeney Knyazhev, Feb 16, 2013
    #12
  13. anyway, "i1=!i2" ain't suited because we need inversion ;D
    i1=0; // then i2==1
    i1=1; // then i2==0
    Evgeney Knyazhev, Feb 16, 2013
    #13
  14. Evgeney Knyazhev <> writes:
    > -----------------------
    > You are mistaken. `i2' is the result of an `<' operator,
    > hence either zero or one. `!0' is 1, `!1' is zero. `!i2' is
    > well-defined.
    > ----------------------------------
    > well, let's assume
    >
    > int i=0;
    > i=!i;
    > // then output: 0xffff


    "!" is the logical "not" operator; it yields 1 if its operand is 0, 0
    otherwise.

    "~" is the bitwise "not" operator. `~0` is 0xffff only if int is 16
    bits.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Working, but not speaking, for JetHead Development, Inc.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Feb 16, 2013
    #14
  15. Evgeney Knyazhev <> writes:
    > Eric, you can download the source & app as well, so it will "heal"
    > your questions.


    I downloaded your source via the URL buried at the bottom of the
    site you mentioned in your first post in this thread. I got a file
    called "IF free sorting.7z". Once I figured out how to unpack it,
    it included a source file called "IF-free sorting.cpp". (Yes, both file
    names had spaces in them.)

    The code is (a) Windows-specific, and (b) writtin in C++, not C.

    If you want to discuss the ideas represented in the code in the
    context of C, preferably portable C, feel free to do so. Otherwise,
    I'm suggest this is not the place.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Working, but not speaking, for JetHead Development, Inc.
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Feb 16, 2013
    #15
  16. ----------------
    Also * can be a more expensive operation than &.
    -----------------
    Howard, perhaps you're right, but we multiply only "1" & "0", so it could be negligible.
    -------------------------
    Whether any of these tricks help really depends on the machine and compiler. A
    delayed branch or speculative branch hardware with a compiler that can pack
    delay slots can implement branches as fast or faster than the non-branch code
    and keep the source code readable.
    --------------------------
    branches are very reason to idle processor for data receiving.
    Evgeney Knyazhev, Feb 16, 2013
    #16
  17. Keith, yes, i've done it on windows-based ground. but i don't think people would have insuperable problems to fit solution to another grounds.

    P.S.

    Thanks for reply.
    Evgeney Knyazhev, Feb 16, 2013
    #17
  18. Evgeney Knyazhev <> writes:

    > Eric, thanks for reply. mostly, code, posted in the blog, is schematic
    > ;D full code has been in source.


    The code is C++ (there's another group for that) and non-standard C++ so
    it won't compiler here without much editing. However I did take your
    if-avoiding factorial function and timed it compared to

    (a) one that was the same but written without all the extra bother of a
    pointer argument, automatic arrays, and the subtract one/add one dance
    you do; and

    (b) one written with a simple conditional; and

    (c) one that is written as a plain condition + iterative loop.

    My (a) was a little faster than yours (1.3 vs 1.9). My (b) was faster
    still (1.1 vs 1.9) and (c) was the fastest of the lot (0.7 vs 1.9).
    These are with no optimisation. with more optimisation turned on, the
    differences become more dramatic. I.e. the compiler can optimise the
    simpler code more easily than it can your complex code.

    These are crude tests, with one compiler, on one architecture so they
    may not be representative but do you have any data to support writing
    these messy alternatives?

    --
    Ben.
    Ben Bacarisse, Feb 16, 2013
    #18
  19. Ben, factorial was written Just for fun :D Actually, recursive functions are the Evil. About performance, Just compare two codes:

    1st. if(a<b)a++;
    2nd. a+=(a<b);
    ---
    Thanks for reply.
    Evgeney Knyazhev, Feb 16, 2013
    #19
  20. Evgeney Knyazhev

    James Kuyper Guest

    On 02/15/2013 09:46 PM, Evgeney Knyazhev wrote:
    > Keith, yes, i've done it on windows-based ground. but i don't think
    > people would have insuperable problems to fit solution to another
    > grounds.


    I haven't bothered to go through the trouble that Keith did to locate
    your code - but if he felt that the code was sufficiently
    Windows-specific to justify commenting on the fact, I suspect it would
    require significant conversion to work in other environments.

    The other point, which you seem to have ignored, is that the code is
    C++. As such, it should be discussed in a C++ forum, not a C forum.
    --
    James Kuyper
    James Kuyper, Feb 16, 2013
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. PHILIPPE

    Conception question

    PHILIPPE, Jun 17, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    291
    PHILIPPE
    Jun 17, 2004
  2. mutant
    Replies:
    0
    Views:
    423
    mutant
    Nov 27, 2005
  3. westhood
    Replies:
    5
    Views:
    616
    Lionel B
    Jun 20, 2007
  4. george
    Replies:
    0
    Views:
    1,086
    george
    Aug 29, 2008
  5. mohammed_a_o
    Replies:
    0
    Views:
    260
    mohammed_a_o
    Nov 30, 2010
Loading...

Share This Page