Velocity Reviews > IF-free conception.

# IF-free conception.

Evgeney Knyazhev
Guest
Posts: n/a

 02-15-2013
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.

Eric Sosman
Guest
Posts: n/a

 02-15-2013
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
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
http://www.velocityreviews.com/forums/(E-Mail Removed)d

glen herrmannsfeldt
Guest
Posts: n/a

 02-15-2013
Evgeney Knyazhev <(E-Mail Removed)> 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

Evgeney Knyazhev
Guest
Posts: n/a

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

Evgeney Knyazhev
Guest
Posts: n/a

 02-16-2013
"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
Guest
Posts: n/a

 02-16-2013
----------------------------------------------
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.

Eric Sosman
Guest
Posts: n/a

 02-16-2013
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
(E-Mail Removed)d

Eric Sosman
Guest
Posts: n/a

 02-16-2013
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
(E-Mail Removed)d

Evgeney Knyazhev
Guest
Posts: n/a

 02-16-2013

Evgeney Knyazhev
Guest
Posts: n/a

 02-16-2013
-----------------------
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