C bit twidders ... I'm in need of a dose of clever.

[user923005]

The purpose is for a shellsort.

I am experimenting with the increment for shellsort using a modified
version of Pete's 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.

[Kohn Emil Dan]

On Tue, 30 Jan 2007, user923005 wrote:

<snipped>

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.

Before trying to optimize, please make sure that that piece of code is the
one which is really eating up most of the time. You should use a profiling
tool for doing these timing measurements (e.g. vTune from Intel for
Windows or Linux on x86, or Quantify from Rational/IBM for other UNIX
platforms). Otherwise you will be surprised that despite your optimization
efforts you gain nothing. Detecting the "hotspots" in a piece of code
(i.e. the parts which eat up most of the time) can be an experience full
of surprises ;-)

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

Well, I'm not sure I have understood correctly your question. I think you
want to rewite the above piece of code without using "if" statements. You
can use the conditional operator ("?:") or exploit the fact that in C
logical expressions, such as "inc <= inversion && inc 1" yield an
integer value of 1 if their logical value is "true" and 0 otherwise. With
a little bit of simple arithmetics you can construct an expression that
replaces the "if" statement, for example:

int x;
..
..
if (<condition>)
x = a;
else
x = b;

can be rewritten as:

int cond;
..
..
..
cond = <condition>;
x = cond * a + !cond * b;

The reason for using the intermedirate "cond" variable to make sure that
<conditionis evaluated only once. It also improves the readability.
Notice however, that optimizing compilers are pretty smart at avoiding
unnecessary branches, (e.g. replacing them with conditional instructions
if the underlying processor supports them), so I think that unless you
have very serious reasons to do so, let the compiler optimize away the
"if" statement.
Emil

[user923005]

On Jan 30, 3:43 am, Kohn Emil Dan <[e-mail]:

On Tue, 30 Jan 2007, user923005 wrote:

<snipped>

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.

Before trying to optimize, please make sure that that piece of code is the
one which is really eating up most of the time. You should use a profiling
tool for doing these timing measurements (e.g. vTune from Intel for
Windows or Linux on x86, or Quantify from Rational/IBM for other UNIX
platforms). Otherwise you will be surprised that despite your optimization
efforts you gain nothing. Detecting the "hotspots" in a piece of code
(i.e. the parts which eat up most of the time) can be an experience full
of surprises ;-)

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

Well, I'm not sure I have understood correctly your question. I think you
want to rewite the above piece of code without using "if" statements. You
can use the conditional operator ("?:") or exploit the fact that in C
logical expressions, such as "inc <= inversion && inc 1" yield an
integer value of 1 if their logical value is "true" and 0 otherwise. With
a little bit of simple arithmetics you can construct an expression that
replaces the "if" statement, for example:

int x;
.
.

if (<condition>)
x = a;
else
x = b;

can be rewritten as:

int cond;
.
.
.
cond = <condition>;
x = cond * a + !cond * b;

The reason for using the intermedirate "cond" variable to make sure that
<conditionis evaluated only once. It also improves the readability.

Notice however, that optimizing compilers are pretty smart at avoiding
unnecessary branches, (e.g. replacing them with conditional instructions
if the underlying processor supports them), so I think that unless you
have very serious reasons to do so, let the compiler optimize away the
"if" statement.

That won't help. I think something akin to De Bruijn sequences might
help.

I'll ask my chess programming friends. They're pretty good at bit
twiddling.

[pete]

user923005 wrote:

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.

/* BEGIN s_sort defines */
#define NUMERATOR 3
#define DENOMINATOR 7
#define OFFSET (DENOMINATOR - 2 * NUMERATOR)
/* END s_sort defines */

inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;

If numerator and denominator are 3 and 8,
then you could have: inc = inc + inc + inc + 2 >3;

--
pete

[user923005]

On Jan 30, 12:56 pm, pete <[e-mail]:

user923005 wrote:

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.

/* BEGIN s_sort defines */
#define NUMERATOR 3
#define DENOMINATOR 7
#define OFFSET (DENOMINATOR - 2 * NUMERATOR)
/* END s_sort defines */

inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;

If numerator and denominator are 3 and 8,
then you could have: inc = inc + inc + inc + 2 >3;

--
pete

I don't understand how it is supposed to work. I get the increment
itself being affected, so obviously I am not using it right:

#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,
jnc = 1000000;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}
inc = jnc = 10009711;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}

return 0;
}
/*
inc=9582,jnc=310230
inc=2973,jnc=96242
inc=922,jnc=29857
inc=286,jnc=9262
inc=89,jnc=2873
inc=27,jnc=891
inc=8,jnc=276
inc=2,jnc=85
inc=1,jnc=26
inc=0,jnc=8
inc=12936,jnc=3105312
inc=4013,jnc=963360
inc=1245,jnc=298863
inc=386,jnc=92716
inc=120,jnc=28763
inc=37,jnc=8923
inc=11,jnc=2768
inc=3,jnc=858
inc=1,jnc=266
inc=0,jnc=82
*/

[user923005]

I probably just did not pose the problem clearly. Anyway, I 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;
}

[user923005]

Aargh -- this solutions is broken also due to integer modular math.
My increment is too large for 32 bit unsigned.
Maybe I will have to use float.
P.U.

[user923005]

/*
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);
}
}

[pete]

user923005 wrote:

>
On Jan 30, 12:56 pm, pete <[e-mail]:

user923005 wrote:

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.

/* BEGIN s_sort defines */
#define NUMERATOR 3
#define DENOMINATOR 7
#define OFFSET (DENOMINATOR - 2 * NUMERATOR)
/* END s_sort defines */

inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;

If numerator and denominator are 3 and 8,
then you could have: inc = inc + inc + inc + 2 >3;

--
pete

I don't understand how it is supposed to work. I get the increment
itself being affected, so obviously I am not using it right:

#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,
jnc = 1000000;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}
inc = jnc = 10009711;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}

return 0;
}
/*
inc=9582,jnc=310230
inc=2973,jnc=96242
inc=922,jnc=29857
inc=286,jnc=9262
inc=89,jnc=2873
inc=27,jnc=891
inc=8,jnc=276
inc=2,jnc=85
inc=1,jnc=26
inc=0,jnc=8
inc=12936,jnc=3105312
inc=4013,jnc=963360
inc=1245,jnc=298863
inc=386,jnc=92716
inc=120,jnc=28763
inc=37,jnc=8923
inc=11,jnc=2768
inc=3,jnc=858
inc=1,jnc=266
inc=0,jnc=82
*/

The increment algorithm has problems when
(size_t)-1 / NUMERATOR - OFFSET nmemb
is true and NUMERATOR is large.
I haven't decided how large "large" means,
but I think it's somewhere around ten or a hundred.

If I reduce the initial values of inc:
/* BEGIN new.c */

#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 = 100000,
jnc = 100000;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}
inc = jnc = 100097;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}

return 0;
}

/* END new.c */

Then I get:
inc=31023,jnc=31023
inc=9624,jnc=9624
inc=2986,jnc=2985
inc=926,jnc=926
inc=287,jnc=287
inc=89,jnc=89
inc=27,jnc=27
inc=8,jnc=8
inc=2,jnc=2
inc=1,jnc=0
inc=0,jnc=0
inc=31053,jnc=31053
inc=9633,jnc=9633
inc=2988,jnc=2988
inc=927,jnc=926
inc=287,jnc=287
inc=89,jnc=89
inc=27,jnc=27
inc=8,jnc=8
inc=2,jnc=2
inc=1,jnc=0
inc=0,jnc=0

To make the Shellsort work with large DENOMINATOR and large nmemb also,
I had to hybridize the sorting function for an integer math part
and a floating point part:

void shsort(e_type *array, size_t nmemb)
{
e_type *i, *j, *k, *after, temp;

after = array + nmemb;
if (((size_t)-1 - OFFSET) / NUMERATOR nmemb) {
nmemb = (nmemb * NUMERATOR + OFFSET) / DENOMINATOR;
} else {
nmemb *= (double)NUMERATOR / DENOMINATOR;
}
while (nmemb ((size_t)-1 - OFFSET) / NUMERATOR) {
i = array + nmemb;
do {
j = i - nmemb;
if (GT(j, i)) {
k = i;
temp = *k;
do {
*k = *j;
k = j;
if (nmemb + array j) {
break;
}
j -= nmemb;
} while (GT(j, &temp));
*k = temp;
}
++i;
} while (i != after);
nmemb *= (double)NUMERATOR / DENOMINATOR;
}
while (nmemb != 0) {
i = array + nmemb;
do {
j = i - nmemb;
if (GT(j, i)) {
k = i;
temp = *k;
do {
*k = *j;
k = j;
if (nmemb + array j) {
break;
}
j -= nmemb;
} while (GT(j, &temp));
*k = temp;
}
++i;
} while (i != after);
nmemb = (nmemb * NUMERATOR + OFFSET) / DENOMINATOR;
}
}
--
pete

[user923005]

Here is what I ended up with:
/* For C++ do this:
#include <cstdlib>
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);
}
}

Try it in your harness, it really smokes. I am going to do a bit more
increment hunting, but I am very happy with this one.

[pete]

user923005 wrote:

>
Here is what I ended up with:
/* For C++ do this:
#include <cstdlib>
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;

Should shell_ratio be a double instead of a float?

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

Try it in your harness, it really smokes. I am going to do a bit more
increment hunting, but I am very happy with this one.

It's not bad on my machine.

/* BEGIN e_driver.c program output */

Timing 6 different sorting functions.
Sorting arrays of N number of elements.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N s2sort s3sort s8sort shsort dcss spsort
1999998 2.516000 2.156000 2.094000 2.172000 2.047000 1.860000
1999999 2.532000 2.157000 2.079000 2.172000 2.078000 1.891000
Total times:
s2sort: 5.048000 e_type Shellsort, 1 / 2 increment ratio
s3sort: 4.313000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 4.173000 e_type Shellsort, 3 / 8 increment ratio
shsort: 4.344000 e_type Shellsort, 5 / 11 increment ratio
dcss: 4.125000 e_type Shellsort, dcorbit's latest
spsort: 3.751000 e_type Shellsort, Sedgewick numbers

/* END e_driver.c program output */

--
pete

[Thad Smith]

user923005 wrote:

On Jan 30, 12:56 pm, pete <[e-mail]:

>>user923005 wrote:

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

/* BEGIN s_sort defines */
#define NUMERATOR 3
#define DENOMINATOR 7
#define OFFSET (DENOMINATOR - 2 * NUMERATOR)
/* END s_sort defines */

inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;

If numerator and denominator are 3 and 8,
then you could have: inc = inc + inc + inc + 2 >3;

I don't understand how it is supposed to work. I get the increment
itself being affected, so obviously I am not using it right:

#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,
jnc = 1000000;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}
inc = jnc = 10009711;
while (inc 0) {
inc = (inc * NUMERATOR + OFFSET) / DENOMINATOR;
jnc *= .31023;
printf("inc=%u,jnc=%u\n", inc, jnc);
}

return 0;
}
/*
inc=9582,jnc=310230
inc=2973,jnc=96242

You are apparently getting overflow in the first adjustment. In
general, you should not need such large values to get a useable ratio
for Shell sort. Try the 3/7 and 3/8 suggested by Pete.

--
Thad

[CBFalconer]

user923005 wrote:

>
/*
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);
}
}

So? This appears to be code to do something to something. No
purpose is evident. It won't even compile as is, lacking a main,
etc. See below:

--
If you want to post a followup via groups.google.com, ensure
you quote enough for the article to make sense. Google is only
an interface to Usenet; it's not Usenet itself. Don't assume
your readers can, or ever will, see any previous articles.
More details at: <http://cfaj.freeshell.org/google/>

[Richard Heathfield]

CBFalconer said:

<snip>

It won't even compile as is, lacking a main,
etc.

It doesn't need a main to compile. It may not even need a main to link (on
freestanding implementations).

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[pete]

CBFalconer wrote:

>
user923005 wrote:

/*
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);
}
}

So? This appears to be code to do something to something. No
purpose is evident. It won't even compile as is, lacking a main,
etc. See below:

All it needs to be able to compile
are definitions for e_type, size_t and GT(a,b).

--
pete

[user923005]

Compilable header file:
/*
// This is a C++ template for shellsort.
// It can also be called form C, if e_type has a typedef.
// Modification of code by Pete Pfilander by Dann Corbit.
// Use it however you like.
// Send comments and curses to: dc*****@connx.com
*/
#ifdef __cplusplus
#include <cstdlib/* for definition of size_t */
template <class e_type>
#else
#include <stdlib.h/* for definition of size_t */
#endif
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);
}
}

Compilable test driver:
#ifdef __cplusplus
#include <cstdio>
#else
#include <stdio.h/* for definition of size_t */
#endif

#include "shellsort.h"

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

Output of Pete's program on my machine:
/* BEGIN e_driver.c program output */

Timing 9 different sorting functions.
Sorting arrays of N number of elements,
in 14 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.704000 0.735000 0.641000 0.672000 0.767000 0.673000
0.641000 0.642000 0.657000
0x200000 0.687000 0.749000 0.641000 0.671000 0.749000 0.671000
0.641000 0.624000 0.656000
Total times:
dcss: 1.391000 0.31023 float ratio Shellsort (a)
DCsort2c: 1.484000 0.31023 float ratio Shellsort (c)
DCsort2b: 1.282000 0.31023 float ratio Shellsort (b)
s3sort: 1.343000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 1.516000 e_type Shellsort, 3 / 8 increment ratio
spsort: 1.344000 e_type Shellsort, Sedgewick numbers
DCsort: 1.282000 Gonnet Shellsort
Sesort: 1.266000 Sedgewick Shellsort
optisort: 1.313000 Marcin Ciura increment shellsort

Distribution #2: Reverse sorted
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.187000 0.265000 0.188000 0.203000 0.218000 0.250000
0.250000 0.265000 0.249000
0x200000 0.188000 0.251000 0.189000 0.219000 0.219000 0.235000
0.266000 0.266000 0.235000
Total times:
dcss: 0.375000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.516000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.377000 0.31023 float ratio Shellsort (b)
s3sort: 0.422000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.437000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.485000 e_type Shellsort, Sedgewick numbers
DCsort: 0.516000 Gonnet Shellsort
Sesort: 0.531000 Sedgewick Shellsort
optisort: 0.484000 Marcin Ciura increment shellsort

Distribution #3: Ramp, Drives center pivot qsorts, quadratic
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.172000 0.220000 0.188000 0.204000 0.204000 0.204000
0.266000 0.220000 0.250000
0x200000 0.172000 0.204000 0.204000 0.203000 0.203000 0.188000
0.266000 0.235000 0.235000
Total times:
dcss: 0.344000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.424000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.392000 0.31023 float ratio Shellsort (b)
s3sort: 0.407000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.407000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.392000 e_type Shellsort, Sedgewick numbers
DCsort: 0.532000 Gonnet Shellsort
Sesort: 0.455000 Sedgewick Shellsort
optisort: 0.485000 Marcin Ciura increment shellsort

Distribution #4: Two values, Badly written qsorts choke on this
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.156000 0.172000 0.234000 0.172000 0.172000 0.156000
0.297000 0.234000 0.266000
0x200000 0.157000 0.219000 0.220000 0.172000 0.172000 0.157000
0.297000 0.235000 0.281000
Total times:
dcss: 0.313000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.391000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.454000 0.31023 float ratio Shellsort (b)
s3sort: 0.344000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.344000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.313000 e_type Shellsort, Sedgewick numbers
DCsort: 0.594000 Gonnet Shellsort
Sesort: 0.469000 Sedgewick Shellsort
optisort: 0.547000 Marcin Ciura increment shellsort

Distribution #5: Already sorted
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.063000 0.063000 0.157000 0.110000 0.110000 0.063000
0.235000 0.157000 0.219000
0x200000 0.063000 0.063000 0.157000 0.095000 0.079000 0.063000
0.235000 0.157000 0.220000
Total times:
dcss: 0.126000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.126000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.314000 0.31023 float ratio Shellsort (b)
s3sort: 0.205000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.189000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.126000 e_type Shellsort, Sedgewick numbers
DCsort: 0.470000 Gonnet Shellsort
Sesort: 0.314000 Sedgewick Shellsort
optisort: 0.439000 Marcin Ciura increment shellsort

Distribution #6: Constant
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.063000 0.063000 0.157000 0.094000 0.095000 0.063000
0.235000 0.157000 0.220000
0x200000 0.079000 0.063000 0.157000 0.094000 0.079000 0.064000
0.235000 0.157000 0.220000
Total times:
dcss: 0.142000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.126000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.314000 0.31023 float ratio Shellsort (b)
s3sort: 0.188000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.174000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.127000 e_type Shellsort, Sedgewick numbers
DCsort: 0.470000 Gonnet Shellsort
Sesort: 0.314000 Sedgewick Shellsort
optisort: 0.440000 Marcin Ciura increment shellsort

Distribution #7: 32 bit RAND
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.704000 0.750000 0.626000 0.673000 0.751000 0.672000
0.641000 0.626000 0.641000
0x200000 0.703000 0.734000 0.624000 0.671000 0.766000 0.671000
0.640000 0.624000 0.656000
Total times:
dcss: 1.407000 0.31023 float ratio Shellsort (a)
DCsort2c: 1.484000 0.31023 float ratio Shellsort (c)
DCsort2b: 1.250000 0.31023 float ratio Shellsort (b)
s3sort: 1.344000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 1.517000 e_type Shellsort, 3 / 8 increment ratio
spsort: 1.343000 e_type Shellsort, Sedgewick numbers
DCsort: 1.281000 Gonnet Shellsort
Sesort: 1.250000 Sedgewick Shellsort
optisort: 1.297000 Marcin Ciura increment shellsort

Distribution #8: Five values
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.234000 0.265000 0.281000 0.234000 0.265000 0.249000
0.343000 0.327000 0.312000
0x200000 0.235000 0.267000 0.282000 0.235000 0.266000 0.251000
0.329000 0.329000 0.314000
Total times:
dcss: 0.469000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.532000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.563000 0.31023 float ratio Shellsort (b)
s3sort: 0.469000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.531000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.500000 e_type Shellsort, Sedgewick numbers
DCsort: 0.672000 Gonnet Shellsort
Sesort: 0.656000 Sedgewick Shellsort
optisort: 0.626000 Marcin Ciura increment shellsort

Distribution #9: Ten values
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.282000 0.329000 0.329000 0.267000 0.329000 0.298000
0.360000 0.360000 0.329000
0x200000 0.281000 0.312000 0.327000 0.281000 0.313000 0.281000
0.375000 0.422000 0.359000
Total times:
dcss: 0.563000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.641000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.656000 0.31023 float ratio Shellsort (b)
s3sort: 0.548000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.642000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.579000 e_type Shellsort, Sedgewick numbers
DCsort: 0.735000 Gonnet Shellsort
Sesort: 0.782000 Sedgewick Shellsort
optisort: 0.688000 Marcin Ciura increment shellsort

Distribution #10: Twenty values
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.313000 0.376000 0.360000 0.297000 0.407000 0.329000
0.392000 0.407000 0.391000
0x200000 0.313000 0.360000 0.360000 0.297000 0.360000 0.344000
0.376000 0.391000 0.391000
Total times:
dcss: 0.626000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.736000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.720000 0.31023 float ratio Shellsort (b)
s3sort: 0.594000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.767000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.673000 e_type Shellsort, Sedgewick numbers
DCsort: 0.768000 Gonnet Shellsort
Sesort: 0.798000 Sedgewick Shellsort
optisort: 0.782000 Marcin Ciura increment shellsort

Distribution #11: 0x7fff values
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.641000 0.689000 0.563000 0.610000 0.688000 0.626000
0.610000 0.610000 0.610000
0x200000 0.656000 0.703000 0.578000 0.609000 0.687000 0.641000
0.593000 0.609000 0.594000
Total times:
dcss: 1.297000 0.31023 float ratio Shellsort (a)
DCsort2c: 1.392000 0.31023 float ratio Shellsort (c)
DCsort2b: 1.141000 0.31023 float ratio Shellsort (b)
s3sort: 1.219000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 1.375000 e_type Shellsort, 3 / 8 increment ratio
spsort: 1.267000 e_type Shellsort, Sedgewick numbers
DCsort: 1.203000 Gonnet Shellsort
Sesort: 1.219000 Sedgewick Shellsort
optisort: 1.204000 Marcin Ciura increment shellsort

Distribution #12: Camel, for floating types
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.094000 0.125000 0.156000 0.110000 0.094000 0.110000
0.251000 0.173000 0.219000
0x200000 0.079000 0.094000 0.157000 0.110000 4.360000 0.095000
0.251000 0.172000 0.219000
Total times:
dcss: 0.173000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.219000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.313000 0.31023 float ratio Shellsort (b)
s3sort: 0.220000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 4.454000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.205000 e_type Shellsort, Sedgewick numbers
DCsort: 0.502000 Gonnet Shellsort
Sesort: 0.345000 Sedgewick Shellsort
optisort: 0.438000 Marcin Ciura increment shellsort

Distribution #13: Perverse
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.344000 0.360000 0.360000 0.329000 0.376000 0.344000
0.391000 0.376000 0.391000
0x200000 0.343000 0.359000 0.359000 0.359000 0.374000 0.359000
0.406000 0.390000 0.406000
Total times:
dcss: 0.687000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.719000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.719000 0.31023 float ratio Shellsort (b)
s3sort: 0.688000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 0.750000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.703000 e_type Shellsort, Sedgewick numbers
DCsort: 0.797000 Gonnet Shellsort
Sesort: 0.766000 Sedgewick Shellsort
optisort: 0.797000 Marcin Ciura increment shellsort

Distribution #14: card_shuffle
N dcss DCsort2c DCsort2b s3sort s8sort
spsort DCsort Sesort optisort
0x1fffff 0.204000 0.250000 0.188000 0.391000 0.235000 0.204000
0.297000 0.204000 0.266000
0x200000 0.204000 0.282000 0.188000 0.407000 4.469000 0.172000
0.282000 0.204000 0.251000
Total times:
dcss: 0.408000 0.31023 float ratio Shellsort (a)
DCsort2c: 0.532000 0.31023 float ratio Shellsort (c)
DCsort2b: 0.376000 0.31023 float ratio Shellsort (b)
s3sort: 0.798000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 4.704000 e_type Shellsort, 3 / 8 increment ratio
spsort: 0.376000 e_type Shellsort, Sedgewick numbers
DCsort: 0.579000 Gonnet Shellsort
Sesort: 0.408000 Sedgewick Shellsort
optisort: 0.517000 Marcin Ciura increment shellsort

accumulator sums = 8.321000, 9.322000, 8.871000
/* END e_driver.c program output */

[user923005]

P.S.
For C, the algorithm still needs a typedef of int for e_type.

P.P.S.
If this message makes no sense to you, get a threading newsreader.

[Flash Gordon]

user923005 wrote, On 31/01/07 19:14:

P.S.
For C, the algorithm still needs a typedef of int for e_type.

P.P.S.
If this message makes no sense to you, get a threading newsreader.

That does not help if the message you are responding to never arrive, of
if it arrives some time after this message or if someone reads the
message after the response has expired, of if the news reader is set not
to show read messages and it is some time since they read the message
you are replying to.

If that is not enough to encourage you to post properly then consider
than most of the knowledgeable people here are likely to either kill
file you or ignore you so you will find the group of no use when you
need help.
--
Flash Gordon

[Richard Heathfield]

Flash Gordon said:

user923005 wrote, On 31/01/07 19:14:

>P.S.
For C, the algorithm still needs a typedef of int for e_type.

P.P.S.
If this message makes no sense to you, get a threading newsreader.

That does not help if the message you are responding to never arrive, of
if it arrives some time after this message or if someone reads the
message after the response has expired, of if the news reader is set not
to show read messages and it is some time since they read the message
you are replying to.

If that is not enough to encourage you to post properly then consider
than most of the knowledgeable people here are likely to either kill
file you or ignore you so you will find the group of no use when you
need help.

Most of the knowledgeable people in this newsgroup know who user923005 is.
They know that it would be silly to killfile or ignore him. They know that,
on the rare occasions that he asks for help, it's likely to be for
extremely interesting reasons. (And yes, they also know that he ought to
know better than to post a contextless reply.)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[CBFalconer]

user923005 wrote:

>
P.S.
For C, the algorithm still needs a typedef of int for e_type.

P.P.S.
If this message makes no sense to you, get a threading newsreader.

It has nothing to do with the newsreader, it has to do with the
mechanism of usenet. All articles should stand by themselves.

--
If you want to post a followup via groups.google.com, ensure
you quote enough for the article to make sense. Google is only
an interface to Usenet; it's not Usenet itself. Don't assume
your readers can, or ever will, see any previous articles.
More details at: <http://cfaj.freeshell.org/google/>

[Default User]

Richard Heathfield wrote:

Most of the knowledgeable people in this newsgroup know who
user923005 is. They know that it would be silly to killfile or
ignore him. They know that, on the rare occasions that he asks for
help, it's likely to be for extremely interesting reasons. (And yes,
they also know that he ought to know better than to post a
contextless reply.)

I can certainly make a guess, but I don't see any reason to give him a
pass from standard usenet etiquette. What if he decided next that
top-posting was the cat's meow?

I try to plonk consistently. If continues to post that way, especially
if he's obnoxious about it, then he'll certainly gain a deserved spot
in the old killfile.


Brian

[Richard Heathfield]

Default User said:

Richard Heathfield wrote:

>Most of the knowledgeable people in this newsgroup know who
user923005 is. They know that it would be silly to killfile or
ignore him. They know that, on the rare occasions that he asks for
help, it's likely to be for extremely interesting reasons. (And yes,
they also know that he ought to know better than to post a
contextless reply.)

I can certainly make a guess, but I don't see any reason to give him a
pass from standard usenet etiquette.

Neither do I. I suspect that he's just having a bad hair day.

What if he decided next that top-posting was the cat's meow?

The amount of slack I give people tends to depend on their S/N ratio (signal
to noise, sense to nonsense, skill to nuisance, whatever fits). This tiny
increase in N from user923005 doesn't significantly reduce his S/N ratio,
but obviously top-posting would increase N still further, and eventually
there would come a point... but I don't think that point is now. YMMV, of
course.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Lane Straatman]

"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:S6******************************@bt.com...

Flash Gordon said:

>user923005 wrote, On 31/01/07 19:14:

>>P.S.
For C, the algorithm still needs a typedef of int for e_type.

P.P.S.
If this message makes no sense to you, get a threading newsreader.

That does not help if the message you are responding to never arrive, of
if it arrives some time after this message or if someone reads the
message after the response has expired, of if the news reader is set not
to show read messages and it is some time since they read the message
you are replying to.

If that is not enough to encourage you to post properly then consider
than most of the knowledgeable people here are likely to either kill
file you or ignore you so you will find the group of no use when you
need help.

Most of the knowledgeable people in this newsgroup know who user923005 is.
They know that it would be silly to killfile or ignore him. They know
that,
on the rare occasions that he asks for help, it's likely to be for
extremely interesting reasons. (And yes, they also know that he ought to
know better than to post a contextless reply.)

Before he gets a disintegration ray, would he comment on how he came up with
the theoretical worst case performance in Figs. 13.7 and 13.8 without
handpicking "bad" initial sets? LS

[Default User]

Richard Heathfield wrote:

Default User said:

Richard Heathfield wrote:

Most of the knowledgeable people in this newsgroup know who
user923005 is. They know that it would be silly to killfile or
ignore him. They know that, on the rare occasions that he asks for
help, it's likely to be for extremely interesting reasons. (And

yes, >they also know that he ought to know better than to post a

contextless reply.)

I can certainly make a guess, but I don't see any reason to give
him a pass from standard usenet etiquette.

Neither do I. I suspect that he's just having a bad hair day.

What if he decided next that top-posting was the cat's meow?

The amount of slack I give people tends to depend on their S/N ratio
(signal to noise, sense to nonsense, skill to nuisance, whatever
fits). This tiny increase in N from user923005 doesn't significantly
reduce his S/N ratio, but obviously top-posting would increase N
still further, and eventually there would come a point... but I don't
think that point is now. YMMV, of course.

I just can't agree with that sort of evaluation. I try to be as
consistent as I can, as I think "rules" such as they are in an
unmoderated group should apply as equally as possible. Allowing the
"regulars" to flout the rules that we hammer newbies about sends
exactly the wrong message, and gives fuel to the trolls who maintain
that that's the norm here.

The fact that someone has made useful contributions historically
doesn't hold a lot of weight with me. Some, I guess, maybe as you say,
let one bad day slide. However, if it's appearing to be a continuing
policy, then I'm not going to calculate some S/N ratio.

Brian

[Richard Heathfield]

Default User said:

<snip>

I just can't agree with that sort of evaluation. I try to be as
consistent as I can, as I think "rules" such as they are in an
unmoderated group should apply as equally as possible.

So do I. I cut *everybody* slack in proportion to their S/N ratio.

Allowing the
"regulars" to flout the rules that we hammer newbies about sends
exactly the wrong message,

You're not *allowing* him to do anything. He can do what he likes, without
regard to your opinion or mine or anyone else's. The only control you have
is over *your* behaviour - your reaction to what he posts.

and gives fuel to the trolls who maintain
that that's the norm here.

Trolls don't need fuel. They just make stuff up.

>
The fact that someone has made useful contributions historically
doesn't hold a lot of weight with me. Some, I guess, maybe as you say,
let one bad day slide. However, if it's appearing to be a continuing
policy, then I'm not going to calculate some S/N ratio.

Well, neither am I. If someone posts a great many superb articles a day and
top-posts one or two from time to time, and forgets to quote context in
another handful, is it truly sensible to reprimand them for that? On the
other hand, if someone posts a handful of rather mediocre articles a day,
and top-posts in most of them, and fails to quote context in nearly all of
them, is it truly sensible *not* to?

At some point, you strike a balance. You don't need to dig out a pocket
calculator to know when someone "gets" it and when they don't.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.