Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   IF-free conception. (http://www.velocityreviews.com/forums/t957661-if-free-conception.html)

Evgeney Knyazhev 02-15-2013 08:51 PM

IF-free conception.
 
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 02-15-2013 09:48 PM

Re: IF-free conception.
 
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
esosman@comcast-dot-net.invalid

glen herrmannsfeldt 02-15-2013 11:21 PM

Re: IF-free conception.
 
Evgeney Knyazhev <z0dchiy8@gmail.com> 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 02-16-2013 12:39 AM

Re: IF-free conception.
 
Eric, thanks for reply. mostly, code, posted in the blog, is schematic ;D full code has been in source.

Evgeney Knyazhev 02-16-2013 12:53 AM

Re: IF-free conception.
 
"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 02-16-2013 01:04 AM

Re: IF-free conception.
 
----------------------------------------------
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 02-16-2013 01:09 AM

Re: IF-free conception.
 
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
esosman@comcast-dot-net.invalid

Eric Sosman 02-16-2013 01:11 AM

Re: IF-free conception.
 
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
esosman@comcast-dot-net.invalid

Evgeney Knyazhev 02-16-2013 01:19 AM

Re: IF-free conception.
 
Eric, you can download the source & app as well, so it will "heal" your questions.

Evgeney Knyazhev 02-16-2013 01:23 AM

Re: IF-free conception.
 
-----------------------
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


All times are GMT. The time now is 09:24 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.