IF-free conception.

[Piotr Kalinowski]

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

Stable sort is a sorting algorithm that does not change order of items
in the sequence that compare as equal to each other. While quicksort is
not stable, this is not the description you wanted to use.

You wanted to note that quicksort has O(n * log n) complexity only in
average case, whereas heapsort maintains such characteristic in worst
case scenario as well.

Regards,
Piotr Kalinowski

 

[James Kuyper]

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

On 02/18/2013 08:05 AM, Ben Bacarisse wrote:
....

seem to be disputed by anyone (which is good because it's true!). What
Evgeney Knyazhev seems to be disputing is that child+1 is ever equal to
the length of the array just before it used as an array index.

If that's what he's asserting (which is not exactly clear), that leads
to a different problem. The first statement which calculates dv is
immediately followed by the statement which evaluates the expression
a[child+1] - the execution of the first statement will always be
immediately followed by execution of the second. If the expression
a[child+1] would never be executed when child+1 >= end, then it would
follow that the first expression which sets dv would never set it to any
value other than 1. That would render that entire statement pointless;
if that were true, the code could have been simplified considerably:

child += a[child] < a[child+1];

I don't think he thought the first calculation of dv was pointless. I
think he thought (and presumably still does) that evaluation of
a[child+1] is perfectly safe, even if child+1 >= end. I'm not sure why
he thinks that, because he's said things suggesting that he understands
that going outside the bounds of an array is problem. Possible he's
thinking that because nothing has gone wrong in his testing so far, that
the code must be safe?

 

[Ben Bacarisse]

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

On 02/18/2013 08:05 AM, Ben Bacarisse wrote:
...

seem to be disputed by anyone (which is good because it's true!). What
Evgeney Knyazhev seems to be disputing is that child+1 is ever equal to
the length of the array just before it used as an array index.

If that's what he's asserting (which is not exactly clear),

There is only one thing that is clear: he disputes that there is an
out-of-bounds bug. Since the bug is due to executing a[child+1] when
child is equal to the size of the array 'a', it seems reasonable to
imagine that he's disputing that fact.

that leads
to a different problem. The first statement which calculates dv is
immediately followed by the statement which evaluates the expression
a[child+1] - the execution of the first statement will always be
immediately followed by execution of the second. If the expression
a[child+1] would never be executed when child+1 >= end, then it would
follow that the first expression which sets dv would never set it to any
value other than 1. That would render that entire statement pointless;
if that were true, the code could have been simplified considerably:

child += a[child] < a[child+1];

I don't think he thought the first calculation of dv was pointless.

I am not sure what your point is. He certainly does not think it's
pointless, but I don't think he know what the point is. He's simply
translated the usual heap sort code that says something like:

if (child + 1 < end && a[child] < a[child + 1])
child += 1;

into code that uses multiplication by 0/1 without taking into account
that the short-circuit && operator protects the otherwise undefined
array access.

I
think he thought (and presumably still does) that evaluation of
a[child+1] is perfectly safe, even if child+1 >= end. I'm not sure why
he thinks that, because he's said things suggesting that he understands
that going outside the bounds of an array is problem.

Maybe, but that seems staggeringly unlikely. He does seem to know the
valid range of indexes, and I've spelt it out at least once (at least I
thought I'd spelt it out). All his "defences" of the code have
referenced variables other than child, so my guess is he does not think
that child is ever one less than the array size. It's almost equally
odd, but I can't make any other sense of it.

 

[James Kuyper]

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

On 02/18/2013 08:05 AM, Ben Bacarisse wrote:
...

seem to be disputed by anyone (which is good because it's true!). What
Evgeney Knyazhev seems to be disputing is that child+1 is ever equal to
the length of the array just before it used as an array index.

If that's what he's asserting (which is not exactly clear),

There is only one thing that is clear: he disputes that there is an
out-of-bounds bug. Since the bug is due to executing a[child+1] when
child is equal to the size of the array 'a', it seems reasonable to
imagine that he's disputing that fact.

Of course - the issue is, why does he think that won't happen? I don't I
have any better answers to that question than you do. However, the
initial calculation of dv implies that he does expect it to happen -
otherwise dv could simply be replaced with 1. Unless, of course, he
simply mechanically translated the code without thinking about it hard
enough to form any such expectations. I'm just pointing out that
discrepancy.

that leads
to a different problem. The first statement which calculates dv is
immediately followed by the statement which evaluates the expression
a[child+1] - the execution of the first statement will always be
immediately followed by execution of the second. If the expression
a[child+1] would never be executed when child+1 >= end, then it would
follow that the first expression which sets dv would never set it to any
value other than 1. That would render that entire statement pointless;
if that were true, the code could have been simplified considerably:

child += a[child] < a[child+1];

I don't think he thought the first calculation of dv was pointless.

I am not sure what your point is. He certainly does not think it's
pointless, but I don't think he know what the point is. ...

That seems quite likely. I'm just trying to guide his thinking toward
figuring it out. It's like trying to herd cats, but I thought I'd give
it a try.

... He's simply
translated the usual heap sort code that says something like:

if (child + 1 < end && a[child] < a[child + 1])
child += 1;

into code that uses multiplication by 0/1 without taking into account
that the short-circuit && operator protects the otherwise undefined
array access.

I'm just pointing out the discrepancy between that translation, and his
belief that a[child+1] will never be evaluated with child + 1 >= end.

 

[Evgeney Knyazhev]

while(child < end)

{

dv = (child + 1 < end);

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

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

Ben, it's not full code.

dv = (child + 1 < end);
dv = (a[child] < a[child+1]) & dv;
child += dv;
dv = le(&a[root], &a[child]); // here is crucial moment -- it says
// whether we need new loop or not
//("Not" sets dv to zero)
end*= dv; // So, end==end or end==0
****

Anyway, i decided to use Asm inserts -- AO (automatic optimization) is crappy joke

 

[James Kuyper]

On 02/18/2013 02:15 PM, Evgeney Knyazhev wrote:
....

Ben, it's not full code.

dv = (child + 1 < end);

Does dv ever get set to 0? If so, then the following line evaluates
a[child+1] when child+1 >= end. If that happens your program has
undefined behavior, and nothing that happens afterwards matters.

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

 

[Evgeney Knyazhev]

On 02/18/2013 02:15 PM, Evgeney Knyazhev wrote:

...

Ben, it's not full code.

dv = (child + 1 < end);

Does dv ever get set to 0? If so, then the following line evaluates

a[child+1] when child+1 >= end. If that happens your program has

undefined behavior, and nothing that happens afterwards matters.

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

James, out there is entire code, you can test it as much as you want. give me array to fail this scheme -- that would be useful ;D

 

[Keith Thompson]

On 02/18/2013 02:15 PM, Evgeney Knyazhev wrote:
...

Ben, it's not full code.

dv = (child + 1 < end);

Does dv ever get set to 0? If so, then the following line evaluates
a[child+1] when child+1 >= end. If that happens your program has
undefined behavior, and nothing that happens afterwards matters.

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

James, out there is entire code, you can test it as much as you
want. give me array to fail this scheme -- that would be useful ;D

Undefined behavior doesn't mean that the program will necessarily fail;
it means that its behavior is undefined. A very common symptom of
undefined behavior is that the program behaves just as you'd expect it
to.

A simple example:

int main(void) {
char arr[7];
arr[7] = 0;
return arr[7];
}

This program's behavior is undefined because it attempts to access
an element of arr outside its bounds -- but on my system it "works"
just fine, and I'd be surprised to see it fail on any implementation
that doesn't perform deliberate array bound checking.

 

[Ben Bacarisse]

while(child < end)

{

dv = (child + 1 < end);

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

Yes, it was full code. I showed exactly the full sequence that leads to
the error.

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

The error occurs here.

child += dv;
dv = le(&a[root], &a[child]); // here is crucial moment -- it says
// whether we need new loop or not
//("Not" sets dv to zero)

That moment may be crucial to you, but the program has already gone
wrong by this point. Nothing that happens here can correct what
happened before -- the program's behaviour has become undefined.

I am going to hazard a guess as to why you don't see this as a bug. I
am pretty sure that you do see that the array access is out-of-bounds,
but since it is only a read and not a write, you think it's OK; and
anyway the '& dv' means that value of the comparison is ignored when the
index is out-of-bounds. So, in summary, you might a junk value but you
ignore the result when the index is too large so all's well. Is that
how you see it?

That's not how the language works. Once you access an element beyond
the end of an array, the language standard washes its hands of you
program -- the program is undefined as far as C (or C++) is concerned.
The fact that you can seem to get away with it does not make it OK --
you should be aiming to write code whose meaning is well-defined by the
language you are using.

 

[Ben Bacarisse]

I'm just pointing out the discrepancy between that translation, and his
belief that a[child+1] will never be evaluated with child + 1 >= end.

I don't think that's his belief, but in cases like this one never knows.

I've tried to get my head round what his misunderstanding is because
I've become intrigued by it and I hazard a guess in a direct reply
elsewhere in this thread. In summary, I think he does not regard the
access as an error because (a) it's only a read access, and (b) the
value accessed is ignored (in the sense of having no effect on the logic
of the algorithm) when the index is out of bounds. In other words he
does not know (or maybe does not care) about the behaviour being
undefined as far as the language goes.

 

[Ian Collins]

On 02/18/2013 02:15 PM, Evgeney Knyazhev wrote:

...

Ben, it's not full code.

dv = (child + 1 < end);

Does dv ever get set to 0? If so, then the following line evaluates

a[child+1] when child+1 >= end. If that happens your program has

undefined behavior, and nothing that happens afterwards matters.

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

James, out there is entire code, you can test it as much as you want. give me array to fail this scheme -- that would be useful ;D

Please please please learn the very simple art of quoting before you reply!

Then run the code you posted under a memory checker to see where the
problem lies. Don't bother posting back until you do!

 

[Evgeney Knyazhev]

well, we have simple & clear method to check algo about out-of-bound access: after sorting, order of numbers must be verified ;D it's too unlikely to have well-ordered array with such trouble + etalon array could be used too.

 

[James Kuyper]

On 02/18/2013 02:15 PM, Evgeney Knyazhev wrote:
...

Ben, it's not full code.

dv = (child + 1 < end);

Does dv ever get set to 0? If so, then the following line evaluates
a[child+1] when child+1 >= end. If that happens your program has
undefined behavior, and nothing that happens afterwards matters.

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

James, out there is entire code, you can test it as much as you want. give me array to fail this scheme -- that would be useful ;D

I'm curious. How do you think I could determine that the behavior is
defined by testing it? "Undefined behavior" means that the standard
imposes no requirements on the behavior of your program. The only way to
prove that code has defined behavior is to analyze the code and compare
it to the requirements imposed by the standard. There's no behavior that
could be produced by such a test program that would be inconsistent with
the requirements imposed by the standard on code with undefined
behavior, because there are NO such requirements. When I perform the
appropriate analysis on your code, I find that it violates requirements
imposed by the standard, for which the behavior is undefined.

If you mistakenly believe that a particular piece of code with undefined
behavior is required to produce a particular output, it's entirely
possible that it will. That's actually bad luck for you, because it
prevents you from noticing the defect in your code. This is actually a
disproportionately likely event, because your mistaken certainty about
the behavior will often reflect undue familiarity with the way one
particular system works, and ignorance of the fact that other systems
can, and often do, work differently. You can even get different behavior
just by running the same exact program with the same inputs a second
time. It might even have failed THIS time - it might have done precisely
what you thought it was required to do, and ALSO something else you
didn't think it could do, and you just haven't noticed the other part of
it's behavior yet. Those are the possibilities that makes sane
programmers avoid writing code with undefined behavior.

You should write such code only when something other than the standard
guarantees what the actual behavior will be, and only if you never
intend to port the code to platforms where that guarantee applies. Even
if all of those conditions are met, you still shouldn't write such code
unless you have to.

Can you identify any document that defines what the behavior of your
code should be? If so, what kind of platforms does that document apply
to? Are you sure you'll never want to port this code to any platforms
not on that list?

 

[Ben Bacarisse]

well, we have simple & clear method to check algo about out-of-bound
access: after sorting, order of numbers must be verified ;D

No, the best way is to check the accesses! You haven't done that. I
suggested various ways and I think you've ignored them all.

My preferred method: looking at the code, does not seem to work for you.

it's too
unlikely to have well-ordered array with such trouble + etalon array
could be used too.

Ah, I see that my attempt to grasp your misunderstanding was wrong: you
actually think that there is no out-of-bounds access.

 

[Evgeney Knyazhev]

Can you identify any document that defines what the behavior of your

code should be? If so, what kind of platforms does that document apply

to? Are you sure you'll never want to port this code to any platforms

not on that list?

James, absolutely portable code doesn't exist, even java code could providesurprises, if virtual machine got some bugs. So, i don't see an issue here after Asm inserts, it could be s!cko-portable, but it will run at due speeds. ;D Trade-off is everywhere

 

[Evgeney Knyazhev]

Ah, I see that my attempt to grasp your misunderstanding was wrong: you

actually think that there is no out-of-bounds access.

Ben, sample of step-by-step execution of >entire< code would be helpful.

 

[James Kuyper]

James, absolutely portable code doesn't exist, even java code could provide surprises, if virtual machine got some bugs. So, i don't see an issue here after Asm inserts, it could be s!cko-portable, but it will run at due speeds. ;D Trade-off is everywhere

I'm not insisting on absolutely portable code (though non-portable code
is more usefully discussed in forums that are dedicated to the kinds of
systems where it's guaranteed to work). There's nothing wrong with code
that is only guaranteed to have the behavior you want it to have when
you compile it for certain platforms - at least, there's nothing wrong
with it so long as you're certain that you'll never want it to work
anywhere else. Note: such certainly is usually a self-delusion.

However, there should be at least one such platform. Do you know of any
such platform? This particular program appears to work as you expected
it to on the platform where you tested it - but do you know of any
document anywhere that guarantees that it will work on that platform?
Without such guarantees, you can't be sure that it won't fail the very
next time you run it. Unless you know precisely what is happening to
make your program work, despite the fact that the standard allows it to
fail, how can you be sure it won't fail when you make a small
modification to the program?

 

[James Kuyper]

Ben, sample of step-by-step execution of >entire< code would be helpful.

Execution of the entire code is unnecessary, if you truly understand
what the problem is. All that's really needed is to demonstrate that the
following line:

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

is actually reached with child == 99999, at a time when 'a' points at an
array containing only 100000 elements. I can demonstrate that quite
easily, but it won't do any good unless you're willing to accept such a
demonstration as proof that your code has undefined behavior. Would you?

I can also demonstrate the same thing by going step-by-step, as you
request, but that would be a lot of work, and I don't want to do that
much work unless you insist on it; even then, I'm only willing to bother
if you agree in advance that demonstrating that child==99999 on that
line is sufficient. Otherwise it would just be a waste of my time.

If you don't think that would be sufficient, please identify what you
think we'd have to do to prove, to your satisfaction, that your code has
undefined behavior.

 

[Ian Collins]

well, we have simple & clear method to check algo about out-of-bound
access: after sorting, order of numbers must be verified ;D it's too
unlikely to have well-ordered array with such trouble + etalon array
could be used too.

Seeing as you are unwilling to learn, or even try, here's the proof:

(dbx 1) check -all
access checking - ON
memuse checking - ON
(dbx 2) run
Start No-IF heapsort
Read from uninitialized (rui):
Attempting to read 8 bytes at address 0x4dff68
which is 800000 bytes into a heap block of size 6300000 bytes at
0x41ca68
This block was allocated from:
[1] main() at line 143 in "s.cc"

stopped in siftDown at line 73 in file "s.cc"
73 dv = (a[child] < a[child+1]) & dv;
(dbx 3) print end
end = 100000
(dbx 4) up
Current function is Heapify
91 cnt += siftDown(a, root--, end);
(dbx 5) up
Current function is heapSort
98 int count = Heapify(arr, end);
(dbx 6) up
Current function is main
162 countIteration = heapSort(array2sort,N0fItems);

 

[Ben Bacarisse]

Ben, sample of step-by-step execution of >entire< code would be
helpful.

No, I don't think it would be. I've shown you how and when the problem
occurs, and I traced the sequence of steps from main the statement in
question. How could the rest of the execution path help? Just in case,
please answer this question: do you think that there is no out-of-bounds
access or do you think the because the program works, the out-of-bounds
access is not a problem?

I gave you three practical ways to assure yourself of the problem and I
don't think you've taken up any of them. I've included the output of
your program with the critical condition marked with an "assert"
statement.

Another try? Here is your posted code running under gdb:

$ gdb -q esort
Reading symbols from /home/ben/play/esort...done.
(gdb) break 76
Breakpoint 1 at 0x400fa1: file esort.cc, line 76.
(gdb) run
Starting program: /home/ben/play/esort
(C) 2013 Evgeney Knyazhev.

Start No-IF heapsort

Breakpoint 1, siftDown (a=0x7ffff6c03010, root=49999, end=100000)
at esort.cc:76
76 dv = (a[child] < a[child+1]) * dv;
(gdb) print child+1
$1 = 100000
(gdb)

I'm beginning to feel foolish wasting time on this. I really don't care
if you accept it or not. After all, the code is not real code that is
used (or likely to be used) for any purpose, so what does it matter?