Velocity Reviews > IF-free conception.

# IF-free conception.

Piotr Kalinowski
Guest
Posts: n/a

 02-18-2013
Evgeney Knyazhev <(E-Mail Removed)> writes:

> On Sunday, February 17, 2013 11:13:15 PM UTC+3, Ian Collins wrote:
> Ian, you say about qsort? 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

--
Intelligence is like a river: the deeper it is, the less noise it makes.

James Kuyper
Guest
Posts: n/a

 02-18-2013
On 02/17/2013 02:42 PM, Evgeney Knyazhev wrote:
> 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
Guest
Posts: n/a

 02-18-2013
James Kuyper <(E-Mail Removed)> writes:

> On 02/17/2013 02:42 PM, Evgeney Knyazhev wrote:
>> 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.

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

> Possible he's
> thinking that because nothing has gone wrong in his testing so far, that
> the code must be safe?
>
>

--
Ben.

James Kuyper
Guest
Posts: n/a

 02-18-2013
On 02/18/2013 01:33 PM, Ben Bacarisse wrote:
> James Kuyper <(E-Mail Removed)> writes:
>
>> On 02/17/2013 02:42 PM, Evgeney Knyazhev wrote:
>>> 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.

>> 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
Guest
Posts: n/a

 02-18-2013
> 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
Guest
Posts: n/a

 02-18-2013
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
Guest
Posts: n/a

 02-18-2013
On Monday, February 18, 2013 10:27:43 PM UTC+3, James Kuyper wrote:
> 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
Guest
Posts: n/a

 02-18-2013
Evgeney Knyazhev <(E-Mail Removed)> writes:
> On Monday, February 18, 2013 10:27:43 PM UTC+3, James Kuyper wrote:
>> 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.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <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"

Ben Bacarisse
Guest
Posts: n/a

 02-18-2013
Evgeney Knyazhev <(E-Mail Removed)> writes:

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

> ------------
>
> Ben, it's not full code.

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.

> end*= dv; // So, end==end or end==0
> ****

--
Ben.

Ben Bacarisse
Guest
Posts: n/a

 02-18-2013
James Kuyper <(E-Mail Removed)> writes:

<snip>

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

--
Ben.