Non chess programming bit twiddling question

[Dann Corbit]

The newsgroup news:comp.lang.c was {so far} unable to come up with a solution. I want to be able to do a branchless calculation of a last increment for shellsort that does not use if checks.

I am experimenting with the increment for shellsort using a modified version of Pete Pfilander's sorting driver and this bit of code (shell_ratio is a floating point number for the time being during my search):

void ssort2b(e_type array[], size_t count)
{
size_t i,
inc,
j;
e_type tmp;
int inversion = 1.0 / shell_ratio;


for (inc = count; inc > 0;) {
for (i = inc; i < count; i++) {
j = i;
tmp = array[i];
while (j >= inc && (GT(array + j - inc, &tmp))) {
array[j] = array[j - inc];
j -= inc;
}
array[j] = tmp;
}
if (inc <= inversion && inc > 1) {
inc = 1;
} else
inc *= shell_ratio;
}
}


At any rate, the bit at the end with:
if (inc <= inversion && inc > 1) {
inc = 1;
} else
inc *= shell_ratio;

really gives me the heebie-jeebies (imagining missed branch predictions). Eventually, I am going to use a rational increment and I also would like to change the calculation for the last increment so it is totally branchless.

So what I am wondering is:
"Is there a way to modify an integer so that there is no change if it is larger to a certain value and so that it gets truncated to 1 if it is less than or equal to a certain value?"


It also needs to get clobbered on the final pass so that it becomes zero, so the bitwise operations would also have to take that into account.

[Dann Corbit]

I figured it out and came up with this solution:
#include <stdio.h>

/* BEGIN s_sort defines */
#define NUMERATOR 31023
#define DENOMINATOR 100000
#define OFFSET (DENOMINATOR - 2 * NUMERATOR)
/* END s_sort defines */

int main(void)
{
size_t inc = 1000000;
double dinvert = DENOMINATOR * 1.0 / NUMERATOR;
size_t stinvert = (size_t) dinvert;
int danger_danger=0 ;
while (inc > 0) {
inc *= 31023;
inc /= 100000;
inc += danger_danger;
danger_danger = (inc <= stinvert && inc > 1);
printf("inc=%u\n", inc);
}
inc = 10009711;
danger_danger=0 ;
while (inc > 0) {
inc *= 31023;
inc /= 100000;
inc += danger_danger;
danger_danger = (inc <= stinvert && inc > 1);
printf("inc=%u\n", inc);
}

return 0;
}

[Dann Corbit]

This overflows too easily (but my increment has to be very precise) so I guess I will have to use floating point for the increment calculations.

[Dann Corbit]

/*
Here is what I ended up with:
*/
void dcss(e_type * array, size_t h)
{
e_type *i,
*j,
*k,
*after,
temp;
static const float shell_ratio = 0.31023;
size_t inversion = (size_t) (1.0f / shell_ratio);
size_t danger_danger = 0;
after = array + h;
h *= shell_ratio;
while (h != 0) {
i = array + h;
do {
j = i - h;
if (GT(j, i)) {
k = i;
temp = *k;
do {
*k = *j;
k = j;
if (h + array > j) {
break;
}
j -= h;
} while (GT(j, &temp));
*k = temp;
}
++i;
} while (i != after);
h *= shell_ratio;
h += danger_danger;
danger_danger = (h <= inversion && h > 1);
}
}

[Dann Corbit]

Let's try that again (with proper code formatting):

Code: Select all

void            dcss(e_type * array, size_t h)
{
    e_type         *i,
                   *j,
                   *k,
                   *after,
                    temp;
    static const float shell_ratio = 0.31023;
    size_t          inversion = (size_t) (1.0f / shell_ratio);
    size_t          danger_danger = 0;
    after = array + h;
    h *= shell_ratio;
    while (h != 0) {
        i = array + h;
        do {
            j = i - h;
            if (GT(j, i)) {
                k = i;
                temp = *k;
                do {
                    *k = *j;
                    k = j;
                    if (h + array > j) {
                        break;
                    }
                    j -= h;
                }   while (GT(j, &temp));
                *k = temp;
            }
            ++i;
        }   while (i != after);
        h *= shell_ratio;
        h += danger_danger;
        danger_danger = (h <= inversion && h > 1);
    }
}


[Dann Corbit]

Last word on this, I promise! Here's the header and test driver I eventually came up with:

Code: Select all


// File: shellsort.h -- a shellsort driver with special increment:

#include <cstdlib> /* for definition of size_t */
template <class e_type>
void            dcss(e_type * array, size_t h)
{
    e_type         *i,
                   *j,
                   *k,
                   *after,
                    temp;
    static const float shell_ratio = 0.31023;
    size_t          inversion = 3;
    size_t          danger_danger = 0;
    after = array + h;
    h *= shell_ratio;
    while (h != 0) {
        i = array + h;
        do {
            j = i - h;
            if ((*(j) > *(i))) {
                k = i;
                temp = *k;
                do {
                    *k = *j;
                    k = j;
                    if (h + array > j) {
                        break;
                    }
                    j -= h;
                }   while ((*(j) > *(&temp)));
                *k = temp;
            }
            ++i;
        }   while (i != after);
        h *= shell_ratio;
        h += danger_danger;
        danger_danger = (h <= inversion && h > 1);
    }
}



Code: Select all

#include "shellsort.h"

#include <cstdio>

int             testvector[1000000];

int             main(void)
{
    size_t          vdim = sizeof testvector / sizeof testvector[0];
    size_t          index;
    for (index = 0; index < vdim; index++) {
        testvector[index] = rand();
    }
    dcss(testvector, vdim);
    size_t          i;
    for (i = 0; i < vdim - 1; i++) {
        if (testvector[i] > testvector[i + 1]) {
            printf("testvector is out of sort at %u (%d,%d)\n", (unsigned) i, testvector[i], testvector[i + 1]);
        }
    }
    return 0;
}


[Zach Wegner]

What about

Code: Select all

((inc - 1) & (inc <= X) - 1) + 1

:?:
If I understand you properly, you will follow that with inc *= shell_ratio, with shell_ratio being < 1? If so, then integer multiplication will make that 0 on the last pass. Otherwise you can throw in an ^ (inc == 1).

[Dann Corbit]

That's an interesting alternative.
It's fun for me to think about this kind of thing.

[H.G.Muller]

At any rate, the bit at the end with:
if (inc <= inversion && inc > 1) {
inc = 1;
} else
inc *= shell_ratio;

really gives me the heebie-jeebies (imagining missed branch predictions).

Why do you assume that the translation of this would involve any branches at all? It seems a simple conditional move would suffice here. This would be even more likely if you used & in stead of &&, just in case the compiler is not smart enough to realize that inc>1 has no side effects, and can thus better be executed always than conditionally skipped.