Velocity Reviews > IF-free conception.

# IF-free conception.

Ian Collins
Guest
Posts: n/a

 02-18-2013
Evgeney Knyazhev wrote:
> 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

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!

--
Ian Collins

Evgeney Knyazhev
Guest
Posts: n/a

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

 02-18-2013
On 02/18/2013 02:37 PM, Evgeney Knyazhev wrote:
> 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

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

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

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

--
Ben.

Evgeney Knyazhev
Guest
Posts: n/a

 02-18-2013
On Tuesday, February 19, 2013 12:20:55 AM UTC+3, James Kuyper wrote:

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

 02-18-2013
On Tuesday, February 19, 2013 12:35:50 AM UTC+3, Ben Bacarisse wrote:

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

 02-18-2013
On 02/18/2013 04:39 PM, Evgeney Knyazhev wrote:
> On Tuesday, February 19, 2013 12:20:55 AM UTC+3, James Kuyper wrote:
>
>> 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 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
Guest
Posts: n/a

 02-18-2013
On 02/18/2013 04:44 PM, Evgeney Knyazhev wrote:
> On Tuesday, February 19, 2013 12:35:50 AM UTC+3, Ben Bacarisse wrote:
>
>> 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.

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

 02-18-2013
Evgeney Knyazhev wrote:
> 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);

--
Ian Collins

Ben Bacarisse
Guest
Posts: n/a

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

> On Tuesday, February 19, 2013 12:35:50 AM UTC+3, Ben Bacarisse wrote:
>
>> 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.

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?

--
Ben.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

Advertisments