Velocity Reviews > IF-free conception.

# IF-free conception.

Evgeney Knyazhev
Guest
Posts: n/a

 02-19-2013
On Tuesday, February 19, 2013 3:18:52 AM UTC+3, Ben Bacarisse wrote:
> 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
>

Ben, so let's take code again:
while(child<end){
dv = (child + 1 < end);
dv = (a[child] < a[child+1])*dv;
child += dv;
dv = le(&a[root], &a[child]);
end*= dv;
}
> (gdb) print child+1
>
> \$1 = 100000

why'd you need that???? yes, child+1==end, but our very point is control 'child' value itself ;D
dv = (child + 1 < end);
this line controls a bound, thereby child<end (always that way).

Evgeney Knyazhev
Guest
Posts: n/a

 02-19-2013
frankly, this code has a potential problem

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

too intellectual memory management can abort this line as illegal access. actually, such policy would be quite wise. however, solution is simple: we could use buffer item to avoid ambiguities like that.

Ben Bacarisse
Guest
Posts: n/a

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

> On Tuesday, February 19, 2013 3:18:52 AM UTC+3, Ben Bacarisse wrote:
>> 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
>>

> Ben, so let's take code again:
> while(child<end){
> dv = (child + 1 < end);
> dv = (a[child] < a[child+1])*dv;
> child += dv;
> dv = le(&a[root], &a[child]);
> end*= dv;
> }
>> (gdb) print child+1
>>
>> \$1 = 100000

> why'd you need that????

Because I'm trying to understand what it is you are missing. Obviously
you agree that child+1 == 100000. We agree on one thing at least.

> yes, child+1==end, but our very point is control 'child' value itself ;D
> dv = (child + 1 < end);
> this line controls a bound, thereby child<end (always that way).

That line does not "control a bound", it simply sets dv to 0. The
problem (the out-of-bounds access) is in the next line:

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

This line has no defined meaning in C (or C++) because it accesses an
element of 'a' that does not exist. The previous statement does not
stop this statement from being executed, even though the value of dv
means that you or I could work out what the result is without that
out-of-bounds access.

--
Ben.

Keith Thompson
Guest
Posts: n/a

 02-19-2013
Evgeney Knyazhev <(E-Mail Removed)> writes:
> On Tuesday, February 19, 2013 3:18:52 AM UTC+3, Ben Bacarisse wrote:
>> 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
>>

> Ben, so let's take code again:
> while(child<end){
> dv = (child + 1 < end);
> dv = (a[child] < a[child+1])*dv;
> child += dv;
> dv = le(&a[root], &a[child]);
> end*= dv;
> }
>> (gdb) print child+1
>>
>> \$1 = 100000

> why'd you need that???? yes, child+1==end, but our very point is control 'child' value itself ;D
> dv = (child + 1 < end);
> this line controls a bound, thereby child<end (always that way).

Your program evaluates the expression `a[child+1]` when `child+1 ==
100000`. Since the array `a` has no element 100000, the evaluation of
that expression has undefined behavior.

Multiplying the result by 0 doesn't change that.

--
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-19-2013
Evgeney Knyazhev <(E-Mail Removed)> writes:

> frankly, this code has a potential problem
>
> dv = (a[child] < a[child+1])*dv;
>
> too intellectual memory management can abort this line as illegal
> access. actually, such policy would be quite wise. however, solution
> is simple: we could use buffer item to avoid ambiguities like that.

At last!

--
Ben.

James Kuyper
Guest
Posts: n/a

 02-19-2013
On 02/18/2013 08:07 PM, Evgeney Knyazhev wrote:
> frankly, this code has a potential problem
>
> dv = (a[child] < a[child+1])*dv;
>
> too intellectual memory management can abort this line as illegal access. actually, such policy would be quite wise. however, solution is simple: we could use buffer item to avoid ambiguities like that.

Ben's first message pointing out that problem was nearly two days ago.
76 messages have been posted since them, a large fraction of them
discussing this one issue. I'm glad you finally understand, but more
than a little annoyed that it took so long and so many words to achieve
that result.
By the way, "too intellectual memory management" sounds a bit
dismissive. Reading past the end of an array runs a real risk of reading
outside the section of memory that the operating system has made
available to your program. There are systems that strictly enforce
memory access limitations, by aborting processes that violate them. I
wouldn't call them "too intellectual", I'd call them "safer" or "more
secure".
--
James Kuyper

glen herrmannsfeldt
Guest
Posts: n/a

 02-19-2013
James Kuyper <(E-Mail Removed)> wrote:

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

(snip)
> Ben's first message pointing out that problem was nearly two days ago.
> 76 messages have been posted since them, a large fraction of them
> discussing this one issue. I'm glad you finally understand, but more
> than a little annoyed that it took so long and so many words to achieve
> that result.
> By the way, "too intellectual memory management" sounds a bit
> dismissive. Reading past the end of an array runs a real risk of reading
> outside the section of memory that the operating system has made
> available to your program. There are systems that strictly enforce
> memory access limitations, by aborting processes that violate them. I
> wouldn't call them "too intellectual", I'd call them "safer" or "more
> secure".

For a paging MMU with 4K pages, it isn't so likely that you end exactly
at the end of a page.

On the 80286 with OS/2, I was once allocating segments directly
from OS/2, instead of with malloc(), with the segment limit exactly
at the end of the array. But no-one does that with current systems,
though segments are still there.

-- glen

Evgeney Knyazhev
Guest
Posts: n/a

 02-19-2013
On Tuesday, February 19, 2013 5:00:27 AM UTC+3, James Kuyper wrote:
> On 02/18/2013 08:07 PM, Evgeney Knyazhev wrote:
>
> > frankly, this code has a potential problem

>
> >

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

>
> >

>
> > too intellectual memory management can abort this line as illegal access. actually, such policy would be quite wise. however, solution is simple: we could use buffer item to avoid ambiguities like that.

>
>
>
> Ben's first message pointing out that problem was nearly two days ago.
>
> 76 messages have been posted since them, a large fraction of them
>
> discussing this one issue. I'm glad you finally understand, but more
>
> than a little annoyed that it took so long and so many words to achieve
>
> that result.
>
> By the way, "too intellectual memory management" sounds a bit
>
> dismissive. Reading past the end of an array runs a real risk of reading
>
> outside the section of memory that the operating system has made
>
> available to your program. There are systems that strictly enforce
>
> memory access limitations, by aborting processes that violate them. I
>
> wouldn't call them "too intellectual", I'd call them "safer" or "more
>
> secure".
>
> --
>
> James Kuyper

James, C never been safe programming language. most of C-code no's (hasn't)been safe up to now it has been known since not 2 days ago ;D In short, for me, it no'w (wasn't) issue at all. real issue for me is idiotic optimization of compiler: no-if C-code becomes if-fy Asm output. Such an irony all-around. XD

BartC
Guest
Posts: n/a

 02-19-2013
"Evgeney Knyazhev" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> On Tuesday, February 19, 2013 5:00:27 AM UTC+3, James Kuyper wrote:

>> Reading past the end of an array runs a real risk of reading
>>
>> outside the section of memory that the operating system has made
>>

> James, C never been safe programming language. most of C-code no's
> (hasn't) been safe up to now it has been known since not 2 days ago ;D

You're proposing to replace if-statements with alternatives might be faster,
but might crash. That's not really acceptable. It can also be considered
cheating. It's also seems to be debatable whether they are actually faster.
They are also unreadable, harder to maintain, and likely to introduce extra,
even more subtle bugs.

In short, you're not really selling your proposal very well! Your
devil-may-care attitude doesn't help either..

--
Bartc

Öö Tiib
Guest
Posts: n/a

 02-19-2013
On Tuesday, 19 February 2013 03:27:18 UTC+2, Ben Bacarisse wrote:
> Evgeney Knyazhev <(E-Mail Removed)> writes:
> > frankly, this code has a potential problem
> >
> > dv = (a[child] < a[child+1])*dv;
> >
> > too intellectual memory management can abort this line as illegal
> > access. actually, such policy would be quite wise. however, solution
> > is simple: we could use buffer item to avoid ambiguities like that.

You have one iteration too lot. That dv is to remove effects of last
iteration. Better may be to iterate one less at first place. Less
code often (not always) results with better efficiency.

> At last!

Congrats Ben. You deserve gold medal of stubborn mentor.