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).
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.
