IF-free conception.

[Eric Sosman]

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

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.

 

[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

 

[Ben Bacarisse]

Ben, factorial was written Just for fun 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 Bacarisse]

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.

 

[Evgeney Knyazhev]

Eric, you can test solution, if you want + i'm here to answer how beast runs

 

[Eric Sosman]

Ben, factorial was written Just for fun Actually, recursive functions are the Evil. About performance, Just compare two codes:

1st. if(a<b)a++;
2nd. a+=(a<b);

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.

 

[James Kuyper]

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.

 

[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:

 

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

 

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

 

[Geoff]

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

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 = -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 == arr[i-1]) i++;
if(arr > arr[i-1])
{
for(; i < I; i++)
{
if(arr == arr[i-1])
continue;
if(arr < arr[i-1])
{
bWellOrdered = false;
goto ret;
}
}
bOrder = false;
goto ret;
}
bWellOrdered = true;
for(; i < I; i++)
{
if(arr == arr[i-1])
continue;
if(arr > 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 != arr2)
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]

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]

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

 

[BartC]

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!

 

[Keith Thompson]

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]

+ a mess with pointers like from blog was done for experiment's sake
only 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]

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]

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!

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]

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]

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.