IF-free conception.

[Evgeney Knyazhev]

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]

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
eso...@comcast-dot-net.invalid

[glen herrmannsfeldt]

Evgeney Knyazhev <z0dc...@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]

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

[Evgeney Knyazhev]

"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]

----------------------------------------------

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

[Eric Sosman]

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
eso...@comcast-dot-net.invalid

[Eric Sosman]

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
eso...@comcast-dot-net.invalid

[Evgeney Knyazhev]

Eric, you can download the source & app as well, so it will "heal" your questions.

[Evgeney Knyazhev]

-----------------------

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

[James Kuyper]

"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

[Evgeney Knyazhev]

Thanks, James, ye're correct. my mind shaded to confuse "!" & "~" operations :D

[Evgeney Knyazhev]

anyway, "i1=!i2" ain't suited because we need inversion ;D
i1=0; // then i2==1
i1=1; // then i2==0

[Keith Thompson]

"!" 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) ks...@mib.org <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]

Evgeney Knyazhev <z0dc...@gmail.com> 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.

[Evgeney Knyazhev]

----------------
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]

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.

[Ben Bacarisse]

Evgeney Knyazhev <z0dc...@gmail.com> 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.

[Evgeney Knyazhev]

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.

[James Kuyper]

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

[Eric Sosman]

Not in C. Perhaps you have confused `!' with `~' -- they
are entirely different operators.

I suspect that either (1) you are not using C but some
C-inspired other language, or (2) you have not actually tried
your code before making claims about it.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[Evgeney Knyazhev]

James, this code about IF-issues, but not about whatever programming language. if you haven't bothered, it doesn't mean Others have no interest of. ;D

----
Thanks for reply.

[Ben Bacarisse]

Evgeney Knyazhev <z0dc...@gmail.com> writes:

> Ben, factorial was written Just for fun :D Actually, recursive
> functions are the Evil.

That may be, but your code was also slower than the simple recursive
version.

> About performance, Just compare two codes:
>
> 1st. if(a<b)a++;
> 2nd. a+=(a<b);

That was not the example you gave. Here it can be argued that the
second version is simpler and clearer, but your blog suggests complex
versions of simple code. If you don't have any data supporting the
changes, why post them?

--
Ben.

[Ben Bacarisse]

Evgeney Knyazhev <z0dc...@gmail.com> writes:

> anyway, "i1=!i2" ain't suited because we need inversion ;D

So why is ! unsuitable?

> i1=0; // then i2==1
> i1=1; // then i2==0

Did you mean "when" in place of "then"? "Then" does not make sense here
because i1 = !i2 has no effect on t2.

--
Ben.

[Evgeney Knyazhev]

Eric, you can test solution, if you want + i'm here to answer how beast runs :D
-------
Thanks for reply.

[Eric Sosman]

How did *you* compare them, and what numbers did *you* get?

Stop making silly claims without evidence to support them.
Also, when (if!) you ever get around to making any measurements,
keep in mind that your measurements are valid only for the system
on which they were made, and only in the context in which they
were made. The fact that snippet S1 is faster/slower than S2 in
some micro-benchmark on Machine A implies little or nothing about
the state of affairs on B -- It doesn't even say much about how
S1 and S2 will perform on A in slightly different circumstances.

--
Eric Sosman
eso...@comcast-dot-net.invalid

[James Kuyper]

On 02/15/2013 10:36 PM, Evgeney Knyazhev wrote:
> James, this code about IF-issues, but not about whatever programming language. if you haven't bothered, it doesn't mean Others have no interest of. ;D

Well, so far the only results you've gotten is corrections to your
mistakes about C, expressions of disgust, reported timings that
contradict the supposed speed advantages, and redirection to more
appropriate windows/C++ forums. I haven't seen any positive expressions
of interest in the idea.
--
James Kuyper

[Evgeney Knyazhev]

------------------

That was not the example you gave. Here it can be argued that the
second version is simpler and clearer

--------------------
Ben, blog gives only the very idea, but whole code is in the source.

that's from source:
----------------------------
dv=(child+1<end);
dv=(a[child]<a[child+1])*dv;
child+=dv;
----------------------------

+ a mess with pointers like from blog was done for experiment's sake only :D
pointer arithmetic needs to cast types, thereby it's severely wrong way for everything. :-)
----
Thanks for reply

[Evgeney Knyazhev]

---------------

Stop making silly claims without evidence to support them.
Also, when (if!) you ever get around to making any measurements,
keep in mind that your measurements are valid only for the system
on which they were made, and only in the context in which they
were made. The fact that snippet S1 is faster/slower than S2 in
some micro-benchmark on Machine A implies little or nothing about
the state of affairs on B -- It doesn't even say much about how
S1 and S2 will perform on A in slightly different circumstances.

-----------------
Eric, you did ans your question :-) Everyone, who wants, can make own tests. + i've not claimed method as panacea ;D

[Evgeney Knyazhev]

---------------------------------

Well, so far the only results you've gotten is corrections to your
mistakes about C, expressions of disgust, reported timings that
contradict the supposed speed advantages, and redirection to more
appropriate windows/C++ forums. I haven't seen any positive expressions
of interest in the idea.

---------------------------------
James, take it easy, Please :D no solution can be absolutely Ideal + i did explain where if-lessness could be preferable.

[Geoff]

On Fri, 15 Feb 2013 12:51:47 -0800 (PST), Evgeney Knyazhev <z0dc...@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. Their description is here (http://alg0z.blogspot.ru/2013/02/if-or-no-if.html).
>-----------------------
>Thanks in Advance for attention of Yours.

Your code is OK as far as it goes but you appear to be using a lot of
Microsoft-isms and somewhat obsolete code, not the least of which is getch(). I
suspect you are using an older version of Microsoft C++. Publishing platform
dependent code in a language group is never a good idea since it generates more
noise about that issue than it generates about the technique you are trying to
get across.

You also failed to include stdafx.h that was in your Microsoft project but it
appears to be irrelevant anyway. The original code would not compile in VC++
2010.

Your style also leaves some things to be desired. I wouldn't publish code
looking like yours and encourage people to use it or follow it as an example.
Ugly code doesn't encourage serious consideration but leads viewers to believe
the author isn't serious or organized. Eliminate the use of comma operators in
your declarations of variables, it's a bad habit. Use more white space. Cramped
code is hard to read and maintain. Learn the standard language and code for it
and keep platform dependencies to a minimum. Break your printf lines up into
shorter segments, preferably at the newlines since the presentation in the code
will be more similar to the actual output of the program. Don't be in such a
rush to publish and share that you present an un-polished work.

Your C++ templates were about the only portable lines in your download package
and there were a few potential bugs in a couple of them with respect to argument
types and return values. I took the liberty of improving them.

You also published C++ in a C language group. A better venue would be
comp.lang.c++ or comp.lang.programming.

I offer the below in the hope that you will consider improving your style and
fixing your "main" function. The following code compiles correctly in VC++ 2010
on a PC and clang 3.0 in Xcode on a MacBook pro.

I broke your main function by using the standard getchar() instead of
Microsoft's _getch() but it's late night here and I simply didn't care to
continue on this anymore. I would also suggest writing your test code to drive
your algorithmic functions with a standard suite of arguments without user
input. I got tired of trying to thread my way through your main function to make
it perform a valid test.

---------------------------------------------------------------------------

// IF-free sorting.cpp : Defines the entry point for the console application.
// (C) 2013 Evgeney Knyazhev
// app name: IF-free Alg0Z
// ver: I.0

#ifdef _WIN32
#include <windows.h>
#include <process.h>
#include <conio.h>
#include <tchar.h>
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

template <class T>
void modExp(T &mod, T &seed, T &exp)
{
int root = 1;

for(int i = 0; exp >> (i + 1) > 0; i++)
{
if(((exp >> i) & 1) == 1)
{
root *= seed;
root %= mod;
}
seed = (seed * seed) % mod;
}
seed = root;
return;
}

template <class T, class T1>
void pseudoRND(T *arr, int &num0fItems, T1 &mod, T1 &seed, T1 &exp)
{
int size0fT1 = sizeof(T1) * 8 - 1;
T1 sign = 0;

for(int i = 0; i < num0fItems; i++)
{
modExp<T1>(mod, seed, exp);
sign = (seed >> size0fT1);
arr[i] = -1 * seed * sign + seed * ((sign + 1) & 1);
}
}

template <class T>
void IsArrSorted(T *arr, T I)
{
bool bOrder;
bool bWellOrdered;
bWellOrdered = true;
int i = 1;

while(arr[i] == arr[i-1]) i++;
if(arr[i] > arr[i-1])
{
for(; i < I; i++)
{
if(arr[i] == arr[i-1])
continue;
if(arr[i] < arr[i-1])
{
bWellOrdered = false;
goto ret;
}
}
bOrder = false;
goto ret;
}
bWellOrdered = true;
for(; i < I; i++)
{
if(arr[i] == arr[i-1])
continue;
if(arr[i] > arr[i-1])
{
bWellOrdered = false;
break;
}
}
if(bWellOrdered)
bOrder = true;

ret:
if(bWellOrdered)
{
if(!bOrder)
printf("\n\nAscending Order\n\n");
else
printf("\n\nDescending Order\n\n");
}
else
{
printf("\n\nNot Ordered at %d\n\n", i);
}
return;
}

// Return number of bad compares, or zero if arrays are equal
template <class T>
int compareArrays(T *arr1, T *arr2, T num)
{
int number0fwrongNested = 0;

for(int i = 0; i < num; i++)
{
if(arr1[i] != arr2[i])
number0fwrongNested++;
}
printf("\n\n%d numbers were nested wrong.\n\n", number0fwrongNested);
return number0fwrongNested;
}

#define chosenT uint64_t

/*********************** HeapSort ********************************/
template <class T>
inline void swp(T *p0, T *p1)
{
T empty;
empty = *p0;
*p0 = *p1;
*p1 = empty;
return;
}

template <class T, class adr>
inline T le(T *p0, T *p1)
{
T i1, i2, empty, *pEmpty;
pEmpty = &empty;
i2 = (*p0 < *p1);
i1 = (i2 + 1) & 1;
p1 = (T*)(i2 * (adr)p1 + i1 * (adr)pEmpty);
p0 = (T*)(i2 * (adr)p0 + i1 * (adr)pEmpty);
empty = *p0;
*p0 = *p1;
*p1 = empty;
return i2;
}

template <class T, class adr>
inline int siftDown(T *a, int root, int end)
{
int child;
int count = 0;
T dv;
child = root << 1;
child++;
while(child < end)
{
dv = (child + 1 < end);
dv = (a[child] < a[child+1]) * dv;
child += dv;
dv = le<T, adr>(&a[root], &a[child]);
root = child;
end *= dv;
child = root << 1;
child++;
count++;
}
return count;
}

template <class T, class adr>
inline int Heapify(T *a, int end)
{
int root = (end-1) >> 1;
int cnt = 0;
while(root > -1)
{
cnt += siftDown<T, adr>(a, root--, end);
}
return cnt;
}

template <class T, class adr>
inline int heapSort(T *arr, int end)
{
int count = Heapify<T, adr>(arr, end);
while(end > 0)
{
swp<T>(&arr[0], &arr[end - 1]);
count += siftDown<T, adr>(arr, 0, end-1);
end--;
}
return count;
}
/*********************** HeapSort ********************************/

/****************** factorial ***********************************/
#define I64 long long
typedef I64 (*TIMES)(I64*) ;
#define adr unsigned long long

//template <class T>
I64 ret(I64 *n)
{
return (*n>-1);
}

//template<class T, class adr>
I64 factorial(I64 *n)
{
// int64_t(*times)(__int64*);
//T (*times)(T*);
//T (*unit)(T*);
TIMES /*times, unit,*/ p[2];
// TIMES times;
int dv = (*n > 1);//, ndv;
//ndv=(dv+1) & 1;
// times=&factorial;
//unit=&ret;
// --------------------------------------------
p[0] = &ret;
p[1] = &factorial;
//times=p[dv];
// --------------------------------------------
// times=reinterpret_cast<TIMES>(((adr)times)*dv+ndv*((adr)unit));
// times=times*dv+ndv*unit;
*n -= (*n > 0);
return (*n + 1) * (p[dv])(n);
}
/****************** factorial ***********************************/

/****************** main ******************/

#ifdef _WIN32
int _tmain(int argc, _TCHAR* argv[])
#else
int main(int argc, char* argv[])
#endif
{
#ifdef _WIN32
SetConsoleTitleA("IF-free Alg0Z (ver I.0).");
#endif
printf("(C) 2013 Evgeney Knyazhev.\n\n");

int size0fInt = sizeof(int64_t) * 8 - 1;
int N0fItems = 100000;
int N0I;
int bottom = 0;
int DownThe;
int UpThe = 1;
int i1;
int i2;
int64_t deltaV;
int64_t *array2sort;
int64_t *unsortedArr;
int64_t *p0;
int64_t *p1;
int64_t *pEmpty;
int64_t empty;
char StopThe = 0;
char GV; /*greater value*/
char unit = 0;
pEmpty = &empty;
chosenT seed = 613;
chosenT exp = 259;
chosenT mod = 91477361;
chosenT countIteration;
bool onceRun = false;

main:
printf("\n\nPlease, choose tasks:\n\n");
printf(">>Sorting algos -- s.\n");
printf(">>Compute factorial -- press f.\n\n");
int gch = getchar();

switch(gch)
{
case 'f':
long long *n;
long long t;

n = &t;
printf("\nN: ");
scanf("%lld", n);

*n = factorial(n);
char msg[2048];
strcpy(msg, "Value is undefined");
size_t len = strlen(msg) + 1;
sprintf(msg + len, "n! == %lld\n\n", *n);
*n = (*n > 0) * len;
printf("%s", &msg[*n]);
goto main;
}

Enter:
printf("Generate the array of pseudorandom numbers ((seed^exp)modN)");
printf("\nDo you want the default values? (y/n)");

if(getchar() == 'y')
{
printf("\nPlease, enter a seed: ");
scanf("%lld", &seed);
printf("\nPlease, enter an exp: ");
scanf("%lld", &exp);
printf("\nPlease, enter a N: ");
scanf("%lld", &mod);
printf("\nPlease, enter a number of items of array to generate: ");
scanf("%d", &N0fItems);
onceRun = false;
}

if(!onceRun)
{
array2sort = (int64_t*)malloc(N0fItems * size0fInt);
unsortedArr = (int64_t*)malloc(N0fItems * size0fInt);

if(array2sort == NULL || unsortedArr == NULL)
{
printf("Not enough memory for array\n");
return 0;
}
pseudoRND<int64_t, chosenT>(array2sort, N0fItems, mod, seed, exp);
for(unsigned int p = 0; p < (unsigned)N0fItems; p++)
unsortedArr[p] = array2sort[p];
}

DownThe = N0fItems - 1;
countIteration = 0;
bottom = 0;
N0I = N0fItems;
StopThe = 0;

if(onceRun)
{
printf("\nWould ye like to generate new array? (y/n)\n");
if(getchar() == 'y')
{
free(array2sort);
free(unsortedArr);
goto Enter;
}
}

printf("\n\nPlease, choose a method to sort\n");
printf("Binary Heap -- press b.\n");
printf("Two-way Tides -- press t.\n\n");
gch = getchar();

switch(gch)
{
case 'b':
countIteration = heapSort < int64_t, chosenT >(array2sort,
N0fItems);
break;

case 't':
/***********************************
IF-free Sorting two-way tides
************************************/
while(StopThe != 1)
{
p1 = &array2sort[DownThe];
p0 = &array2sort[DownThe - 1];
deltaV = *p1 - *p0;
GV = ((uint64_t)deltaV) >> size0fInt;
if(*p0 > *p1)
i2 = 1;
i1 = (GV + 1) & 1;
i2 = GV & 1;
p1 = (int64_t*)(i2 * (chosenT)p1 + i1 * (chosenT)pEmpty);
p0 = (int64_t*)(i2 * (chosenT)p0 + i1 * (chosenT)pEmpty);
empty = *p1;
*p1 = *p0;
*p0 = empty;
unit = i2 + i1 * unit;
p1 = &array2sort[UpThe];
p0 = &array2sort[UpThe - 1];
deltaV = *p1 - *p0;
GV = ((uint64_t)deltaV) >> size0fInt;
i1 = (GV + 1) & 1;
i2 = GV & 1;
p1 = (int64_t*)(i2 * (chosenT)p1 + i1 * (chosenT)pEmpty);
p0 = (int64_t*)(i2 * (chosenT)p0 + i1 * (chosenT)pEmpty);
empty = *p1;
*p1 = *p0;
*p0 = empty;
unit = i2 + unit * i1;
UpThe++;
deltaV = UpThe - N0fItems;
GV = ((uint64_t)deltaV) >> size0fInt;
i1 = (GV + 1) & 1;
i2 = GV & 1;
bottom += i1;
UpThe = i2 * UpThe + i1 * bottom;
DownThe--;
/*deltaV=bottom-DownThe;
GV=((unsigned int)deltaV)>>size0fInt;
i1=(GV+1)&1;
i2=GV&1;*/
N0fItems -= i1;
DownThe = i2 * DownThe + i1 * (N0fItems - 1);
StopThe = i1 & (unit + 1);
unit &= i2;
countIteration++;
}
/**************************************
IF-free Sorting two-way tides
***************************************/
break;
}
countIteration /= N0I;
N0fItems = N0I;
onceRun = true;
printf("\n\n%llu iterations were gotten.\nP.S.\n", countIteration);
printf("Number of iterations was taken by formula: \n");
printf("total number of loops)/(length of array)\n\n");

menu:
printf("To test the order of array, please, press a.\n");
printf("To compare sorted & unsorted arrays, please, press c.\n");
printf("To swap items of sorted arrays, please, press s.\n");
printf("To repeat sorting, please, press r.\n");
gch = getchar();

switch(gch)
{

case 'a':
IsArrSorted<int64_t>(array2sort, N0I);
goto menu;

case 'c':
compareArrays<int64_t>(array2sort, unsortedArr, N0fItems);
goto menu;

case 's':
int64_t item1, item2, tmp;
printf("\nPlease, say me an item:");
scanf("%lld", &item1);
printf("\nNow, please, 2nd one:");
scanf("%lld", &item2);
tmp = array2sort[item1];
array2sort[item1] = array2sort[item2];
array2sort[item2] = tmp;
goto menu;

case 'r':
goto main;
}

return 0;
}

---------------------------------------------------------------------------

[Noob]

Evgeney Knyazhev wrote:

> chine.bleu wrote:
>
>> Also [multiplication] can be a more expensive operation
>> than [logical and].
>
> Perhaps you're right, but we multiply only "1" & "0", so it could be negligible.

Can you name two modern micro-architectures for which multiplication
(not division) has input-dependent latency?

Regards.

[Öö Tiib]

On what Microsoft compiler you get '65535' as result of '!0' ?
You probably mean '~0' that gives '-1' that is '0xffffffff' on all
currently supported MS compilers.

[BartC]

"Keith Thompson" <ks...@mib.org> wrote in message
news:lnvc9tm...@nuthaus.mib.org...

> Evgeney Knyazhev <z0dc...@gmail.com> 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, ...

That makes a change from the majority of open-source C code that appears to
be Unix-oriented, in its distribution format and tool-chains expected to be
used to build it, just for a start!

--
Bartc

[Dr Nick]

You have to use some tool-chain though. And it's a lot easier to port
Unix tool-chains to Windows than vv (cygwin/bash takes you a long way
there).

[Keith Thompson]

Evgeney Knyazhev <z0dc...@gmail.com> writes:
> James, this code about IF-issues, but not about whatever programming
> language. if you haven't bothered, it doesn't mean Others have no
> interest of. ;D

If it's not about "whatever programming language", then it doesn't
belong here. This newsgroup specifically discusses the C programming
language. There are other newsgroups, and other forums outside
Usenet, that discuss more general programming topics.

And when you post here, it would be helpful if you'd follow the
conventions that have evolved for formatting your posts. Quote enough
of the article to which you're replying so that your reply makes sense
in context; it's not always easy to find the parent of a given article.
Your newsreader software should do this for you; if it doesn't, please
find something that does. See most of the articles posted here for
examples.

[Keith Thompson]

Evgeney Knyazhev <z0dc...@gmail.com> writes:
[...]

> + a mess with pointers like from blog was done for experiment's sake
> only :D pointer arithmetic needs to cast types, thereby it's severely
> wrong way for everything. :-)

If you're suggesting that pointer arithmetic *always* implies the need
to perform casts, you're mistaken.

[Keith Thompson]

Evgeney Knyazhev <z0dc...@gmail.com> writes:
[...]

> Eric, you did ans your question :-) Everyone, who wants, can make own
> tests. + i've not claimed method as panacea ;D

But *you're* the one making (rather vague) claims about increased
performance. It's up to you to support those claims. I, for one,
am not going to do that work for you.

I can believe that replacing conditional code with non-conditional
("if-free") code can sometimes result in performance improvements.
If so, modern optimizing compilers are sophisticated enough to
perform such tranformations themselves. Do they? (I don't know the
answer to that). And I think that speculative execution avoids at
least some of the performance problems of conditional code; have you
looked into whether that might make your if-less code unnecessary?

[Keith Thompson]

Certainly a lot of open-source C code is Unix-specific.
Such code would be no more appropriate here in comp.lang.c than
Windows-specific code.

I don't suggest that Windows-specific code is necessarily a bad
thing, nor is C++ code, just that comp.lang.c is not the best place
to discuss either.

Taking another quick look at the source, I don't think the
Windows-specificity is really necessary; probably the same program
*could* have been written in purely portable C++. Writing it in
C might be more difficult, given its heavy use of templates.

(I might take a closer look at it, but I'd have to be convinced that
it's useful first.)

[glen herrmannsfeldt]

ￜￜ Tiib <oot...@hot.ee> wrote:
> On Saturday, 16 February 2013 03:23:50 UTC+2, 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

> On what Microsoft compiler you get '65535' as result of '!0' ?
> You probably mean '~0' that gives '-1' that is '0xffffffff' on all
> currently supported MS compilers.

Are there any C compilers for ones-complement machines?

I remember learning about ones complement in the 1960's, but not
which machines used it then.

-- glen

[Joe Pfeiffer]

glen herrmannsfeldt <g...@ugcs.caltech.edu> writes:

CDC was the famous one. There is a story that when Seymour Cray
switched to 2's complement for the Cray-1 somebody asked him why he'd
used 1's before. He said he'd only just learned about 2's complement.

[Robert Wessel]

On Sat, 16 Feb 2013 20:41:27 +0000 (UTC), glen herrmannsfeldt
<g...@ugcs.caltech.edu> wrote:

Unisys' Clearpath IX* line still implements the old UNIVAC 1100/2200
36 bit, ones-complement architecture. There is a C compiler available
for OS 2200, and it certainly appears to be one-complement. See
section 4.3 (page 4-8) of:

http://public.support.unisys.com/2200/docs/cp12.0/pdf/78310422-010.pdf

"int -- 36 bits -- (-2**35)+1 to (2**35)-1 "

I believe they have an option for generating a twos-complement program
as well.


*Or whatever they're calling it this week.

[Ian Collins]

Sums up the platform cultures....

--
Ian Collins

[glen herrmannsfeldt]

Keith Thompson <ks...@mib.org> wrote:
> Evgeney Knyazhev <z0dc...@gmail.com> writes:
> [...]
>> Eric, you did ans your question :-) Everyone, who wants, can make own
>> tests. + i've not claimed method as panacea ;D

> But *you're* the one making (rather vague) claims about increased
> performance. It's up to you to support those claims. I, for one,
> am not going to do that work for you.

> I can believe that replacing conditional code with non-conditional
> ("if-free") code can sometimes result in performance improvements.
> If so, modern optimizing compilers are sophisticated enough to
> perform such tranformations themselves. Do they? (I don't know the
> answer to that). And I think that speculative execution avoids at
> least some of the performance problems of conditional code; have you
> looked into whether that might make your if-less code unnecessary?

I believe that some now have conditional load, which allows for a
conditional without the execution path uncertainty of a branch.

IA32 has CMOVxx (where xx is the condition) which can replace some
branch instructions. It might not go all the way back to the 386,
and it might be that compilers generating 32 bit code still stay
with instructions from the 386 (at least by default).

Between branch prediction and speculative execution, much of the
cost of branches is reduced.

-- glen

[glen herrmannsfeldt]

Joe Pfeiffer <pfei...@cs.nmsu.edu> wrote:

(snip, I wrote)

>> Are there any C compilers for ones-complement machines?

>> I remember learning about ones complement in the 1960's, but not
>> which machines used it then.

> CDC was the famous one. There is a story that when Seymour Cray
> switched to 2's complement for the Cray-1 somebody asked him why he'd
> used 1's before. He said he'd only just learned about 2's complement.

I did use some CDC machines in the 1980's, but I don't remember if
they had C compilers. About the time I learned C, I had enough other
computers to use.

Unisys produced ones complement machines more recently, but again
I don't know about C compilers.

-- glen

[Evgeney Knyazhev]

1st & foremost, my Friends, my dozen of Thanks for reply of Yours. at the 2nd moment, i'd like to put some things clear:

*my very goal to verify one idea or another.
*i'm too lazy to polish code (yes, i know it's extremely bad :D ).
*i'd like to move on Linux, but no time + too lazy again.
* branch prediction is very reason to slow processor down, so it's really good idea to avoid if-statements at some cases as much as possible. (heap sort has been one of such representative examples).
-----------------------
let's compare two type of codes in the heap sort.

IF-based:
------------------------------------
if(child+1<end){
if(a[child]<a[child+1])child++;
}
------------------------------------

IF-free:
-----------------------------------

dv=(child+1<end);
dv=(a[child]<a[child+1])*dv;
child+=dv;

-----------------------------------

IF-free(another version):
-----------------------------------
dv=(child+1<end);
dv&=(a[child]<a[child+1]);
child+=dv;
-----------------------------------

So, simple question: why'd we need to use if-structure at given situation? :D

[Evgeney Knyazhev]

http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/

Good explanation of IF-Disaster :D

[Ian Collins]

Evgeney Knyazhev wrote:
> 1st & foremost, my Friends, my dozen of Thanks for reply of Yours. at the 2nd moment, i'd like to put some things clear:
>
> *my very goal to verify one idea or another.
> *i'm too lazy to polish code (yes, i know it's extremely bad :D ).
> *i'd like to move on Linux, but no time + too lazy again.
> * branch prediction is very reason to slow processor down, so it's really good idea to avoid if-statements at some cases as much as possible. (heap sort has been one of such representative examples).
> -----------------------
> let's compare two type of codes in the heap sort.

If you are so sure, post two *working C* examples and your benchmark
results. Otherwise this looks like yet another attempt at a pointless
premature micro-optimisation.

--
Ian Collins

[Evgeney Knyazhev]

Ian, ye have code -- you can do it yourself for yourself :D i don't see any reason why i need to do it for you. http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
learn the problem, learn the experiences & you'll figure out why i'm confident of it ;D

[Ben Bacarisse]

Evgeney Knyazhev <z0dc...@gmail.com> writes:

> 1st & foremost, my Friends, my dozen of Thanks for reply of Yours. at
> the 2nd moment, i'd like to put some things clear:
>
> *my very goal to verify one idea or another.

But you don't do any verification! In fact when asked if you have any
evidence to support your claims you tell the asker to do it. When I did
that (me) you say that the example I was foolish enough to waste my time
on was just for fun.

> *i'm too lazy to polish code (yes, i know it's extremely bad :D ).
> *i'd like to move on Linux, but no time + too lazy again.
> * branch prediction is very reason to slow processor down, so it's
> really good idea to avoid if-statements at some cases as much as
> possible.

Why, then, did it not work for the code of yours that I tried?

> (heap sort has been one of such representative examples).
> ----------------------- let's compare two type of codes in the heap
> sort.
>
> IF-based:
> ------------------------------------
> if(child+1<end){
> if(a[child]<a[child+1])child++;
> }
> ------------------------------------
>
> IF-free:
> -----------------------------------
> dv=(child+1<end);
> dv=(a[child]<a[child+1])*dv;
> child+=dv;
> -----------------------------------
>
> IF-free(another version):
> -----------------------------------
> dv=(child+1<end);
> dv&=(a[child]<a[child+1]);
> child+=dv;
> -----------------------------------
>
> So, simple question: why'd we need to use if-structure at given
> situation? :D

Simple answer: you might need it for the code to work: your re-write is
not the same as the original. It is possible (likely, I'd say) that the
child + 1 < end test is there to prevent accessing a[child + 1] when
that element is out-of-bounds.

--
Ben.

[James Kuyper]

On 02/15/2013 11:06 PM, Evgeney Knyazhev wrote:
> ---------------------------------
> Well, so far the only results you've gotten is corrections to your
> mistakes about C, expressions of disgust, reported timings that
> contradict the supposed speed advantages, and redirection to more
> appropriate windows/C++ forums. I haven't seen any positive expressions
> of interest in the idea.
> ---------------------------------
> James, take it easy, Please :D no solution can be absolutely Ideal

True, but this doesn't even come close. The costs to the clarity and
maintainability of the code are enormous. You've ignored requests to
provide test results measuring the supposed benefits, and other people
have produced test results that seem to suggest that your approach
actually makes things worse. Even if there were actual benefits, this
would constitute micro-optimization of the worst sort.
--
James Kuyper

[Evgeney Knyazhev]

----------------------------------

Simple answer: you might need it for the code to work: your re-write is
not the same as the original. It is possible (likely, I'd say) that the
child + 1 < end test is there to prevent accessing a[child + 1] when
that element is out-of-bounds.

----------------------------------
Ben, it's the code from original source:

[Ian Collins]

Evgeney Knyazhev wrote:

Please fix your quoting!

> Ian, ye have code -- you can do it yourself for yourself :D i don't
> see any reason why i need to do it for you.
> http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

As the answer there says, at least two common compilers can optimise
away the branch (I tried gcc and the sort made no difference).

Prefer simple code over obscure hacks unless you have a very specific
need for one.

--
Ian Collins

[Evgeney Knyazhev]

well, James, perhaps later i'll get gcc to re-write code to it, or shall do it on Java. about readability: high-performance code frequently ain't good readable. Automatic Optimization with such technique would be preferable, but AO is too closely related with ATP (automated theorem proving). to avoid IFs ain't easy-go Beast at many cases. :D

[Evgeney Knyazhev]

Ian, what a kind of optimization ye're saying?

[James Kuyper]

The original code never accesses a[child+1] when child+1>=end. There are
other possibilities, but one of the most common reasons for writing code
like that is that for larger values of 'child', the expression
a[child+1] has undefined behavior, because it refers to a non-existent
element of an array.

Your re-write always evaluates the expression a[child+1], regardless of
the value of 'child', before multiplying by 0. Thus, it fails to avoid
the undefined behavior that the original version successfully avoided.
--
James Kuyper

[James Kuyper]

So far. several people have reported timing results suggesting that the
compilers they were using took the simple, clear, if-based code, and
automatically optimized it to run as fast as, or even faster than, your
obscure and unreadable if-free code. Do you know of any compiler for
which this is NOT the case? Could you identify that compiler, the
platform you were using it on, and the results of your timing tests?
--
James Kuyper

[Ian Collins]

Evgeney Knyazhev wrote:
> Ian, what a kind of optimization ye're saying?

Optimising your quoting stile would be a good start!

I'm saying the (completely off topic C++) code you referred to ran just
a fast with or without the sort when compiled with gcc -O3.

Which just goes to show that micro-optimisations are best left to the
compiler.

--
Ian Collins

[glen herrmannsfeldt]

James Kuyper <james...@verizon.net> wrote:

(snip on avoiding branches)

> True, but this doesn't even come close. The costs to the clarity and
> maintainability of the code are enormous. You've ignored requests to
> provide test results measuring the supposed benefits, and other people
> have produced test results that seem to suggest that your approach
> actually makes things worse. Even if there were actual benefits, this
> would constitute micro-optimization of the worst sort.

You might look at:

http://ondioline.org/mail/cmov-a-bad-idea-on-out-of-order-cpus

Written by Linus Torvalds, it seems to indicate that CMOV isn't
all that useful compared to branches.

Well, more specifically, on the P4 it isn't all that good, but
then mispredicted branches aren't either. On Core 2, both CMOV
and branches are better.

The discussion relates to out-of-order execution, which is done
by many of the more recent processors, and the effect of different
instructions on it.

Seems that for a truly unpredicable branch that CMOV might be
better. (A test on the result of a random number generator.)

Compilers might not be so good at knowing which ones are more
predicatable and which less.

-- glen

[Robert Wessel]

Predication (or If Conversion) has a long history, and has always been
used heavily with vector operations. It's also been studied
extensively for scalar code for many years, and there's considerable
literature on the subject.

But while very small sequences of code are (sometimes) usefully
predicated, it stops working for larger sequences. If the two
operations are relatively long, executing both of them be less
efficient that whatever instruction rewind process is needed to make
up for the mispredicted branch. Second, executing both haves often
takes more power (that what kills multi-branch execution at the
hardware level, not to mention the explosion in required hardware).

But for very short sequences, predication can be useful. OTOH, for
very short sequences is exactly where I'd expect the compiler to be
able to do it for me automatically, although I've usually only seen
compilers do that in significant amounts for IPF and (to a lesser
extent) ARM. MSVC used to generate the occasional CMOV a few versions
ago, but they seem to be much rarer these days.

Here's a trivial example from MSVC/IPF:


int f(int a, int b)
{
int t;

if (a)
t = b + 2;
else
t = b + 3;

return t;
}


// Begin code for function: f:
.proc f#
.align 32
f:
// a$ = r32
// b$ = r33
// Output regs: None
// File g:\wessel\test150.c
{ .mii //R-Addr: 0X00
adds r8=3, r33 //10.R
cc:0
cmp4.eq.unc p0,p15=r0, r32;; //7. cc:0
(p15) adds r8=2, r33 //8.R cc:1
}
{ .mmb //R-Addr: 0X010
nop.m 0
nop.m 0
br.ret.sptk.many b0;; //13 cc:1
}
// End code for function:
.endp f#


And this is Usenet. Please quote properly.

[pete]

Robert Wessel wrote:

> Second, executing both haves

ITYM "halves"

> often takes more power (that what kills multi-branch execution at the
> hardware level,

--
pete

[Robert Wessel]

On Sun, 17 Feb 2013 07:51:23 -0500, pete <pfi...@mindspring.com>
wrote:

>Robert Wessel wrote:
>
>> Second, executing both haves
>
>ITYM "halves"

Of course. Darn spill chucker!

[88888 Dihedral]

Evgeney Knyazhev於 2013年2月16日星期六UTC+8上午4時51分47秒寫道：
> 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

I'll give an example that will work to reduce the if part.

a= a&1; // integer for reducing to the 0,1 system

Invoke functor[a] immediately.

a=a | 0xffffffff ;// 0, 0xffffffff system for 32 bits
a2 = a ^ 0xffffffff;
y=(a&z1)| ( a2&z2); // if a y=z1 else z2 ;;
// good for very slow branching HW only

[Bart van Ingen Schenau]

Hight performance code does not have to be unreadable.
In fact, with modern optimizing compilers, it is far from obvious to hand-
optimize code, because any optimization you make might inhibit the
compiler from performing further optimizations, in effect rendering the
result *less* optimized.

As a point in fact, here are some measurements of your if-less sort
algorithms:

Optimised version (-O3):
(C) 2013 Evgeney Knyazhev.

Start No-IF heapsort
No-IF heapsort: 100000 ticks (100.000000 msec)
Start qsort
qsort: 20000 ticks (20.000000 msec)
Start std::sort
std::sort: 20000 ticks (20.000000 msec)
Start std::make_heap + std::sort_heap
std::make_heap + std::sort_heap: 60000 ticks (60.000000 msec)
Start No-IF two-way tides
No-IF two-way tides: 122200000 ticks (122200.000000 msec)

Debug version (-O0):
(C) 2013 Evgeney Knyazhev.

Start No-IF heapsort
No-IF heapsort: 140000 ticks (140.000000 msec)
Start qsort
qsort: 20000 ticks (20.000000 msec)
Start std::sort
std::sort: 30000 ticks (30.000000 msec)
Start std::make_heap + std::sort_heap
std::make_heap + std::sort_heap: 100000 ticks (100.000000 msec)
Start No-IF two-way tides
No-IF two-way tides: 221790000 ticks (221790.000000 msec)

As you can see, the No-IF algorithms are the two slowest ones (the two-
way tides might even be outperformed by a bogo-sort).

The code that generated the results (removed most of the C++ specific
stuff to keep it on topic here):

// IF-free sorting.cpp : Defines the entry point for the console
application.
// (C) 2013 Evgeney Knyazhev
// app name: IF-free Alg0Z
// ver: I.0

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <algorithm>

void modExp(uint64_t mod, uint64_t *seed, uint64_t exp)
{
int root = 1;
uint64_t lseed = *seed;

for(int i = 0; exp >> (i + 1) > 0; i++)
{
if(((exp >> i) & 1) == 1)
{
root *= lseed;
root %= mod;
}
lseed = (lseed * lseed) % mod;
}
*seed = root;
return;
}

void pseudoRND(int64_t *arr, int num0fItems, uint64_t mod, uint64_t seed,
uint64_t exp)
{
int size0fT1 = sizeof(uint64_t) * 8 - 1;
uint64_t sign = 0;

for(int i = 0; i < num0fItems; i++)
{
modExp(mod, &seed, exp);
sign = (seed >> size0fT1);
arr[i] = -1 * seed * sign + seed * ((sign + 1) & 1);
}
}

#define chosenT uint64_t

/*********************** HeapSort ********************************/
inline void swp(int64_t *p0, int64_t *p1)
{
int64_t empty;
empty = *p0;
*p0 = *p1;
*p1 = empty;
return;
}

inline int64_t le(int64_t *p0, int64_t *p1)
{
int64_t i1, i2, empty, *pEmpty;
pEmpty = &empty;
i2 = (*p0 < *p1);
i1 = (i2 + 1) & 1;
p1 = (int64_t*)(i2 * (chosenT)p1 + i1 * (chosenT)pEmpty);
p0 = (int64_t*)(i2 * (chosenT)p0 + i1 * (chosenT)pEmpty);
empty = *p0;
*p0 = *p1;
*p1 = empty;
return i2;
}

inline int siftDown(int64_t *a, int root, int end)
{
int child;
int count = 0;
int64_t dv;
child = root << 1;
child++;
while(child < end)
{
dv = (child + 1 < end);
dv = (a[child] < a[child+1]) * dv;
child += dv;
dv = le(&a[root], &a[child]);
root = child;
end *= dv;
child = root << 1;
child++;
count++;
}
return count;
}

inline int Heapify(int64_t *a, int end)
{
int root = (end-1) >> 1;
int cnt = 0;
while(root > -1)
{
cnt += siftDown(a, root--, end);
}
return cnt;
}

inline int heapSort(int64_t *arr, int end)
{
int count = Heapify(arr, end);
while(end > 0)
{
swp(&arr[0], &arr[end - 1]);
count += siftDown(arr, 0, end-1);
end--;
}
return count;
}
/*********************** HeapSort ********************************/

int comp(const void* a, const void* b)
{
const int64_t* lhs = (const int64_t*)a;
const int64_t* rhs = (const int64_t*)b;
return lhs - rhs;
}

/****************** main ******************/

int main(int argc, char* argv[])
{
printf("(C) 2013 Evgeney Knyazhev.\n\n");

int size0fInt = sizeof(int64_t) * 8 - 1;
int N0fItems = 100000;
int bottom = 0;
int DownThe;
int UpThe = 1;
int i1;
int i2;
int64_t deltaV;
int64_t *array2sort;
int64_t *unsortedArr;
int64_t *p0;
int64_t *p1;
int64_t *pEmpty;
int64_t empty;
char StopThe = 0;
char GV; /*greater value*/
char unit = 0;
pEmpty = &empty;
chosenT seed = 613;
chosenT exp = 259;
chosenT mod = 91477361;
chosenT countIteration;

array2sort = (int64_t*)malloc(N0fItems * size0fInt);
unsortedArr = (int64_t*)malloc(N0fItems * size0fInt);

if(array2sort == NULL || unsortedArr == NULL)
{
printf("Not enough memory for array\n");
return 0;
}
pseudoRND(unsortedArr, N0fItems, mod, seed, exp);
for(unsigned int p = 0; p < (unsigned)N0fItems; p++)
array2sort[p] = unsortedArr[p];

DownThe = N0fItems - 1;
countIteration = 0;
bottom = 0;
StopThe = 0;

printf("Start No-IF heapsort\n");
clock_t start = clock();
countIteration = heapSort(array2sort,N0fItems);
clock_t stop = clock();
printf("No-IF heapsort: %ld ticks (%f msec)\n", stop-start, (1000.0*
(stop-start)/CLOCKS_PER_SEC));

for(unsigned int p = 0; p < (unsigned)N0fItems; p++)
array2sort[p] = unsortedArr[p];

printf("Start qsort\n");
start = clock();
qsort(array2sort, N0fItems, sizeof(array2sort[0]), comp);
stop = clock();
printf("qsort: %ld ticks (%f msec)\n", stop-start, (1000.0*(stop-start)/
CLOCKS_PER_SEC));

for(unsigned int p = 0; p < (unsigned)N0fItems; p++)
array2sort[p] = unsortedArr[p];

printf("Start std::sort\n");
start = clock();
std::sort(array2sort, array2sort+N0fItems);
stop = clock();
printf("std::sort: %ld ticks (%f msec)\n", stop-start, (1000.0*(stop-
start)/CLOCKS_PER_SEC));

for(unsigned int p = 0; p < (unsigned)N0fItems; p++)
array2sort[p] = unsortedArr[p];

printf("Start std::make_heap + std::sort_heap\n");
start = clock();
std::make_heap(array2sort, array2sort+N0fItems);
std::sort_heap(array2sort, array2sort+N0fItems);
stop = clock();
printf("std::make_heap + std::sort_heap: %ld ticks (%f msec)\n", stop-
start, (1000.0*(stop-start)/CLOCKS_PER_SEC));

for(unsigned int p = 0; p < (unsigned)N0fItems; p++)
array2sort[p] = unsortedArr[p];

printf("Start No-IF two-way tides\n");
start = clock();
/***********************************
IF-free Sorting two-way tides
************************************/
while(StopThe != 1)
{
p1 = &array2sort[DownThe];
p0 = &array2sort[DownThe - 1];
deltaV = *p1 - *p0;
GV = ((uint64_t)deltaV) >> size0fInt;
if(*p0 > *p1)
i2 = 1;
i1 = (GV + 1) & 1;
i2 = GV & 1;
p1 = (int64_t*)(i2 * (chosenT)p1 + i1 * (chosenT)pEmpty);
p0 = (int64_t*)(i2 * (chosenT)p0 + i1 * (chosenT)pEmpty);
empty = *p1;
*p1 = *p0;
*p0 = empty;
unit = i2 + i1 * unit;
p1 = &array2sort[UpThe];
p0 = &array2sort[UpThe - 1];
deltaV = *p1 - *p0;
GV = ((uint64_t)deltaV) >> size0fInt;
i1 = (GV + 1) & 1;
i2 = GV & 1;
p1 = (int64_t*)(i2 * (chosenT)p1 + i1 * (chosenT)pEmpty);
p0 = (int64_t*)(i2 * (chosenT)p0 + i1 * (chosenT)pEmpty);
empty = *p1;
*p1 = *p0;
*p0 = empty;
unit = i2 + unit * i1;
UpThe++;
deltaV = UpThe - N0fItems;
GV = ((uint64_t)deltaV) >> size0fInt;
i1 = (GV + 1) & 1;
i2 = GV & 1;
bottom += i1;
UpThe = i2 * UpThe + i1 * bottom;
DownThe--;
/*deltaV=bottom-DownThe;
GV=((unsigned int)deltaV)>>size0fInt;
i1=(GV+1)&1;
i2=GV&1;*/
N0fItems -= i1;
DownThe = i2 * DownThe + i1 * (N0fItems - 1);
StopThe = i1 & (unit + 1);
unit &= i2;
countIteration++;
}
/**************************************
IF-free Sorting two-way tides
***************************************/
stop = clock();
printf("No-IF two-way tides: %ld ticks (%f msec)\n", stop-start,
(1000.0*(stop-start)/CLOCKS_PER_SEC));

return 0;
}

Bart v Ingen Schenau

[Noob]

glen herrmannsfeldt wrote:

> IA32 has CMOVxx (where xx is the condition) which can replace some
> branch instructions. It might not go all the way back to the 386,

Indeed not.

Intel introduced CMOVcc with the Pentium Pro (so -march=i686 in gcc).

The availability of CMOVcc is signaled by bit 15 of EDX after
executing CPUID with EAX=1.

https://en.wikipedia.org/wiki/X86_instruction_listings#Added_with_Pentium_Pro
https://en.wikipedia.org/wiki/Processor_supplementary_capability#IA-32
http://www.sandpile.org/x86/opc_2.htm
http://www.sandpile.org/x86/cpuid.htm

Regards.

[Noob]

Evgeney Knyazhev wrote:

> branch prediction is very reason to slow processor down, so it's
> really good idea to avoid if-statements at some cases as much as
> possible. (heap sort has been one of such representative examples).

I think you need to read a book or three on computer architecture.
In comp arch, there are no universal truths. Even if one considers
several processors implementing the SAME instruction set, different
micro-architectures have different performance characteristics.

So what is "true" for one micro-arch may no longer hold for the next!
Case in point: the characteristics of Intel's P4 were wildly different
from what came before and after "Netbust".

Please read this discussion:

http://ondioline.org/mail/cmov-a-bad-idea-on-out-of-order-cpus

Regards.

[Evgeney Knyazhev]

----------------------------------

Start No-IF heapsort
No-IF heapsort: 100000 ticks (100.000000 msec)
Start qsort
qsort: 20000 ticks (20.000000 msec)
Start std::sort
std::sort: 20000 ticks (20.000000 msec)
Start std::make_heap + std::sort_heap
std::make_heap + std::sort_heap: 60000 ticks (60.000000 msec)
Start No-IF two-way tides
No-IF two-way tides: 122200000 ticks (122200.000000 msec)

----------------------------------
Bart, it was Great :-) qsort can be faster than heap one (it has been known). i think No-IF heap sort is slower because this piece of code:
---------------------------
T i1, i2, empty, *pEmpty;
pEmpty=&empty;
i2=(*p0<*p1);
i1=(i2+1)&1;
p1=(T*)(i2*(adr)p1+i1*(adr)pEmpty);
p0=(T*)(i2*(adr)p0+i1*(adr)pEmpty);
empty=*p0;
*p0=*p1;
*p1=empty;
return i2;
---------------------------
superfluous casting definitely makes stuff slower.
we can use scheme w/o pointers:
----------------------
empty=a[root];
a[root]=i2*a[child]+i1*a[root];
a[child]=i2*empty+i1*a[child];
----------------------

+ yet another room to speed-up could be to avoid multiplication.

As Glen mentioned, modern processors allow the way with CMOV to gain comparable performance. But it ain't available for all processors & compilers.

P.S.

two-way tides is O(n^2) time sort, but if array have small number of wrong-placed items, it'd run faster than heap-sort.

[Evgeney Knyazhev]

----------------------

I think you need to read a book or three on computer architecture.
In comp arch, there are no universal truths. Even if one considers
several processors implementing the SAME instruction set, different
micro-architectures have different performance characteristics.

So what is "true" for one micro-arch may no longer hold for the next!
Case in point: the characteristics of Intel's P4 were wildly different
from what came before and after "Netbust".

Please read this discussion:

http://ondioline.org/mail/cmov-a-bad-idea-on-out-of-order-cpus

-----------------------------
Noob, Thanks for reply. i know it has no sense to say about absolute solution & i no've (haven't) said such way. :D

[Öö Tiib]

On Sunday, 17 February 2013 07:01:28 UTC+2, Ian Collins wrote:
> Evgeney Knyazhev wrote:
> > Ian, what a kind of optimization ye're saying?
>
> Optimising your quoting stile would be a good start!
>
> I'm saying the (completely off topic C++) code you referred to
> ran just a fast with or without the sort when compiled with
> gcc -O3.

True. What Evgeney Knyazhev is doing here (removing branches)
is often done in massively parallel computing and there it
gives major benefits. That means code that should run on
thousands of cores (like in modern GPU). It does not indeed
matter for modern desktop CPU.

> Which just goes to show that micro-optimisations are best left
> to the compiler.

Yes. Or for code-generator that is specially for GPU. It is anyway
worthy idea to discuss ... even with C++ for Windows examples.
C is usually expected to be among the first languages optimized
for whatever particular purpose hardware. ;-)

[Evgeney Knyazhev]

------------------------

int64_t i1, i2, empty;

i2 = (*p0 < *p1);
i1 = (i2 + 1) & 1;

empty = *p0;
*p0 = *p1*i2+*p0*i1;
*p1 = empty*i2+*p1*i1;

return 0;
}
------------------------------

Results:
--------------------------------
Start No-IF heapsort
No-IF heapsort: 312 ticks (312.000000 msec)
Start qsort
qsort: 94 ticks (94.000000 msec)
Start std::sort
std::sort: 297 ticks (297.000000 msec)

Start std::make_heap + std::sort_heap

std::make_heap + std::sort_heap: 343 ticks (343.000000 msec)
---------------------------------
So, messy pointers have been truly chosen culprit :D but we have yet another one, i.e. "*".

[Evgeney Knyazhev]

i did change only "dv = (a[child] < a[child+1]) * dv;" to "dv = (a[child] < a[child+1]) & dv;"

gotten results:
--------------------
Start No-IF heapsort
No-IF heapsort: 297 ticks (297.000000 msec)
Start qsort
qsort: 110 ticks (110.000000 msec)
Start std::sort
std::sort: 343 ticks (343.000000 msec)

Start std::make_heap + std::sort_heap

std::make_heap + std::sort_heap: 375 ticks (375.000000 msec)
--------------------
So, culprit is proven -- multiplication must be substituted with only logical operations.

[Ian Collins]

Evgeney Knyazhev wrote:
> i did change only "dv = (a[child] < a[child+1]) * dv;" to "dv = (a[child] < a[child+1]) & dv;"

In what context? You really should get to grips with Usenet quoting.

--
Ian Collins

[Evgeney Knyazhev]

Ian, sorry, i don't get your question.

[Ian Collins]

Evgeney Knyazhev wrote:
> ------------------------
> // app name: IF-free Alg0Z
> // ver: I.0
>

<snip>

> ------------------------------
>
> Results:
> --------------------------------
> Start No-IF heapsort
> No-IF heapsort: 312 ticks (312.000000 msec)
> Start qsort
> qsort: 94 ticks (94.000000 msec)
> Start std::sort
> std::sort: 297 ticks (297.000000 msec)
> Start std::make_heap + std::sort_heap
> std::make_heap + std::sort_heap: 343 ticks (343.000000 msec)
> ---------------------------------
> So, messy pointers have been truly chosen culprit :D but we have yet another one, i.e. "*".

So you have proved your hackery is by far the slowest solution?

With optimisation enabled, your "No-IF heapsort" is off by almost an
order of magnitude...

--
Ian Collins

[Evgeney Knyazhev]

Ian, you say about qsort? :D qsort can be faster than heap-sort, but qsort ain't stable -- some data throws it to quadratic. i'm supporter of stable sorts :D

[Ian Collins]

Evgeney Knyazhev wrote:
> On Sunday, February 17, 2013 11:05:31 PM UTC+3, Ian Collins wrote:
>> Evgeney Knyazhev wrote:
>>
>>> i did change only "dv = (a[child] < a[child+1]) * dv;" to "dv = (a[child] < a[child+1]) & dv;"
>>
>> In what context? You really should get to grips with Usenet quoting.
>

> Ian, sorry, i don't get your question.
>

http://www.netmeister.org/news/learn2quote.html

--
Ian Collins

[Ian Collins]

Evgeney Knyazhev wrote:
> On Sunday, February 17, 2013 11:13:15 PM UTC+3, Ian Collins wrote:
>>
>> So you have proved your hackery is by far the slowest solution?
>>
>> With optimisation enabled, your "No-IF heapsort" is off by almost an
>> order of magnitude...
>

> Ian, you say about qsort? :D qsort can be faster than heap-sort, but qsort ain't stable -- some data throws it to quadratic. i'm supporter of stable sorts :D
>

I'm saying that with optimisation, your "No-IF heapsort" is almost an
order of magnitude slower than qsort or C++'s std::sort; I had to
increase the array sizes by 100 to get meaningful data:

g++ -m64 -O3 s.cc && ./a.out
Start No-IF heapsort
No-IF heapsort: 3940000 ticks (3940.000000 msec)
Start qsort
qsort: 590000 ticks (590.000000 msec)
Start std::sort
std::sort: 480000 ticks (480.000000 msec)


--
Ian Collins

[Evgeney Knyazhev]

what version did you use?????? with pointers?????

[Shao Miller]

On 2/15/2013 15:51, 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.
>

That web-page includes:
> ...at some cases) to gain practical benefits...

What practical benefits?

> ...Actually, IF-free code ain't panacea to speed-up...

Is speed one of the practical benefits? If so, C doesn't define the
speed of a program, so it'll always be relative to a particular instance
of a program, or sometimes even to particular input or even to the state
of system the program executes within.

> ... Here dead turns become faster than branching. ...

I'd suggest revising that statement to say something like "I measured
the performance of this program once and it took XXX amount of time,
whereas an 'if' counterpart took YYY amount of time. I tested with
such-and-such C compiler on such-and-such platform with such-and-such
compiler options." Otherwise, it looks like a universal claim, which I
find to be a turn-off.

I bet CHAR_BIT bits that you won't answer the following question: Why
did you choose to post to comp.lang.c?

What does this have to do with C? In C, 'if' can be used if you need to
conditionally execute a statement. If you only need expressions, then
you don't need 'if'. Are you familiar with the so-called "conditional"
operator?

expr1 ? expr2 : expr3

If 'expr1 == 0', then 'expr2' is evaluated, otherwise 'expr3' is evaluated.

Programming can be exciting. It's nice that you've found something
interesting. So what kind of discussion are you hoping for? :)

--
- Shao Miller
--
"Thank you for the kind words; those are the kind of words I like to hear.

Cheerily," -- Richard Harter

[Shao Miller]

On 2/17/2013 15:53, Shao Miller wrote:
>
> What does this have to do with C? In C, 'if' can be used if you need to
> conditionally execute a statement. If you only need expressions, then
> you don't need 'if'. Are you familiar with the so-called "conditional"
> operator?
>
> expr1 ? expr2 : expr3
>
> If 'expr1 == 0', then 'expr2' is evaluated, otherwise 'expr3' is evaluated.
>

Oops, I meant:

> If 'expr1 == 0', then 'expr3' is evaluated, otherwise 'expr2' is evaluated.

Sorry about that.

[Öö Tiib]

On Sunday, 17 February 2013 22:49:39 UTC+2, Evgeney Knyazhev wrote:
> what version did you use?????? with pointers?????

Whatever he uses, he is right. You apparently measure not optimized code.
Everywhere optimized std::sort tends to be tiny bit faster than qsort.
If you see it to be noticeably slower then that means you have
compiler optimizations turned off.

[Keith Thompson]

*Please* learn how to post here.

Quoted text is marked by a leading "> " on each line, not by
surrounding it with rows of '-' characters. Quoted text should
also be preceded by an attribution line, such as the "Evgeney
Knyazhev <z0dc...@gmail.com> writes:" line above. Your own text
should be wrapped to about 72 colums so it's easy to read in an
80-column window, leaving room for a few "> " prefixes when it's
quoted in followups.

Any decent newsreader program will do this for you automatically.

For examples of the right way to quote and cite other articles, see the
vast majority of the articles in this newsgroup, including this one.

--
Keith Thompson (The_Other_Keith) ks...@mib.org <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]

Öö Tiib <oot...@hot.ee> writes:
[...]

> Yes. Or for code-generator that is specially for GPU. It is anyway
> worthy idea to discuss ... even with C++ for Windows examples.

Examples using Windows-specific C++ code may well be worthy of
discussion -- but not here, please.

[Evgeney Knyazhev]

Shao, Thanks for reply. i've shared code for people to test solution in different environments. Actually, last variant of no-if heap-sort wins classic heap-sort in my case. qsort runs faster about 2X-4X.

[Noob]

Evgeney Knyazhev wrote:

> superfluous casting definitely makes stuff slower.

Such peremptory (and incorrect) claims make baby Jesus cry.

How much C programming experience do you have?

[Keith Thompson]

Evgeney Knyazhev <z0dc...@gmail.com> writes:
[...]
> #include <algorithm>
[...]

> printf("Start std::sort\n");
> start = clock();
> std::sort(array2sort, array2sort+N0fItems);
> stop = clock();
> printf("std::sort: %ld ticks (%f msec)\n", stop-start, (1000.0*(stop-
> start)/CLOCKS_PER_SEC));

[...]

Eveney, seriously, what part of the name "comp.lang.c" do you
not understand? There's an active comp.lang.c++ newsgroup.
Your articles might be considered off-topic there as well, for
different reasons, but why would you post C++ code in a newsgroup
dedicated to discussing C? They're two different languages.

[Öö Tiib]

On Sunday, 17 February 2013 23:04:37 UTC+2, Keith Thompson wrote:
> Öö Tiib <oot...@hot.ee> writes:
>
> [...]
> > Yes. Or for code-generator that is specially for GPU. It is anyway
> > worthy idea to discuss ... even with C++ for Windows examples.
>
> Examples using Windows-specific C++ code may well be worthy of
> discussion -- but not here, please.

Most of his code is written in C. C++ is used to compare timings with
C++ standard library. Parts of C++ standard library work more
efficiently than anything in standard C ... so dodging such benchmarks
equals hiding your head under sand.

[Keith Thompson]

Evgeney Knyazhev <z0dc...@gmail.com> writes:
[...]

> Ian, you say about qsort? :D qsort can be faster than heap-sort, but
> qsort ain't stable -- some data throws it to quadratic. i'm supporter
> of stable sorts :D

C's qsort function doesn't necessarily use the QuickSort algorithm.

[Keith Thompson]

Öö Tiib <oot...@hot.ee> writes:
> On Sunday, 17 February 2013 23:04:37 UTC+2, Keith Thompson wrote:
>> Öö Tiib <oot...@hot.ee> writes:
>>
>> [...]
>> > Yes. Or for code-generator that is specially for GPU. It is anyway
>> > worthy idea to discuss ... even with C++ for Windows examples.
>>
>> Examples using Windows-specific C++ code may well be worthy of
>> discussion -- but not here, please.
>
> Most of his code is written in C.

All of his code is written in C++. (Most of it is written in the common
subset of the two languages.)

> C++ is used to compare timings with
> C++ standard library. Parts of C++ standard library work more
> efficiently than anything in standard C ... so dodging such benchmarks
> equals hiding your head under sand.

I'm not hiding my head anywhere. I'm not saying the comparisons aren't
useful or interesting, merely that if they're not about C, they belong
somewhere other than comp.lang.c.

[Öö Tiib]

On Sunday, 17 February 2013 23:31:09 UTC+2, Keith Thompson wrote:
> Öö Tiib <oot...@hot.ee> writes:
> > On Sunday, 17 February 2013 23:04:37 UTC+2, Keith Thompson wrote:
> >> Öö Tiib <oot...@hot.ee> writes:
> >> [...]
> >> > Yes. Or for code-generator that is specially for GPU. It is anyway
> >> > worthy idea to discuss ... even with C++ for Windows examples.
> >>
> >> Examples using Windows-specific C++ code may well be worthy of
> >> discussion -- but not here, please.
>
> > Most of his code is written in C.
>
> All of his code is written in C++. (Most of it is written in the common
> subset of the two languages.)

We seem to say the same thing? The original work that he compares with C++
standard library is useful as C (being common subset between the languages).

> > C++ is used to compare timings with
> > C++ standard library. Parts of C++ standard library work more
> > efficiently than anything in standard C ... so dodging such benchmarks
> > equals hiding your head under sand.
>
> I'm not hiding my head anywhere.

I did not say that you hide. It was metaphor.

> I'm not saying the comparisons aren't
> useful or interesting, merely that if they're not about C, they belong
> somewhere other than comp.lang.c.

He is about C. Performance is very important for C. Attempts to
write C that competes well with other well-performers belongs exactly
to comp.lang.c. The whole point of his work is to achieve well-performing
C code by reducing if() branches. Why it is wrong in comp.lang.c?

[Ben Bacarisse]

Evgeney Knyazhev <z0dc...@gmail.com> writes:

> ------------------------
> // app name: IF-free Alg0Z
> // ver: I.0

<snip rest of C++ program>

Before you post in comp.lang.c++ you might want to correct the program.
As I said before, it accesses the array outside of the array bounds.
Its behaviour is undefined so the timing is, for the moment, irrelevant.

--
Ben.

[Ben Bacarisse]

It still contains a bug, though.

--
Ben.

[Evgeney Knyazhev]

Ben, it cannot go out of bounds:

code:

dv = (child + 1 < end);

dv = (a[child] < a[child+1]) & dv;
child += dv;
------
variable "end" is number of items of array, last item has index end-1.

[Evgeney Knyazhev]

Start No-IF heapsort
No-IF heapsort: 14969 ticks (14969.000000 msec)
Start qsort
qsort: 1703 ticks (1703.000000 msec)
Start std::sort
std::sort: 1250 ticks (1250.000000 msec)

Start std::make_heap + std::sort_heap

std::make_heap + std::sort_heap: 5765 ticks (5765.000000 msec)
--------
So, classic heap-sort in optimized shape beats no-if up to 3X. heh, here it needs to dig into assembler codes. :D

[Ben Bacarisse]

Evgeney Knyazhev <z0dc...@gmail.com> writes:

> On Monday, February 18, 2013 1:59:58 AM UTC+3, Ben Bacarisse wrote:
>> Evgeney Knyazhev <z0dc...@gmail.com> writes:
>>
>> > ------------------------
>> > // app name: IF-free Alg0Z
>> > // ver: I.0
>>
>> <snip rest of C++ program>
>>
>> Before you post in comp.lang.c++ you might want to correct the program.
>> As I said before, it accesses the array outside of the array bounds.
>> Its behaviour is undefined so the timing is, for the moment, irrelevant.
>

> Ben, it cannot go out of bounds:
>
> code:
> dv = (child + 1 < end);
> dv = (a[child] < a[child+1]) & dv;
> child += dv;
> ------
> variable "end" is number of items of array, last item has index end-1.

There is so much wrong with that. 'end' is not the number of items in
the array -- the code you cite is in a loop that modifies 'end' so it
takes lots of values. However, that's not really the issue. The
problem is that 'child+1' can be equal to the size of the array.

--
Ben.

[Evgeney Knyazhev]

> There is so much wrong with that. 'end' is not the number of items in
>
> the array -- the code you cite is in a loop that modifies 'end' so it
>
> takes lots of values. However, that's not really the issue. The
>
> problem is that 'child+1' can be equal to the size of the array.
>
>
>
> --
>

Ben, end can be set to zero only when siftdown() must be finished.

[Ben Bacarisse]

Evgeney Knyazhev <z0dc...@gmail.com> writes:

>> There is so much wrong with that. 'end' is not the number of items in
>> the array -- the code you cite is in a loop that modifies 'end' so it
>> takes lots of values. However, that's not really the issue. The
>> problem is that 'child+1' can be equal to the size of the array.
>>

> Ben, end can be set to zero only when siftdown() must be finished.

You keep replying by stating things that have no bearing on the issue.

If you want to understand this bug you can (a) run the program under a
memory checker like valgrind; (b) use a debugger to trap when child + 1
is equal to the array size; or (c) put 'assert(child + 1 < 100000);'
above the code in question. I'm suggesting practical thing because you
don't seem to like thinking about the code.

--
Ben.

[James Kuyper]

On 02/17/2013 01:50 PM, Evgeney Knyazhev wrote:
...

> superfluous casting definitely makes stuff slower.

I wonder - what makes you so certain about that? Have you had the
misfortune of using a compiler so badly implemented that this is
actually true? If so, could you identify the compiler, and provide us
with evidence supporting that claim?
Alternatively, are you just making very bad guesses about what would
happen if you tried this?

--
James Kuyper

[James Kuyper]