You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by Dawid Weiss <da...@gmail.com> on 2010/01/25 14:26:41 UTC
Sorting invariants.
Hi Benson (and others),
Say, when you moved the code from Apache Harmony, did you modify it
along the way, or is it what's found in the Harmony's
source code? I'm asking because we're still hitting those array out of
bounds exceptions sometimes. They are tough to isolate, so I reverted
to white-box code inspection. There is a repeated snippet of code that
just isn't right to me, look here:
comparison = comp.compare(c, partitionIndex);
while (c >= b && comparison >= 0) {
if (comparison == 0) {
if (c == partitionIndex) {
partitionIndex = d;
} else if (d == partitionIndex) {
partitionIndex = c;
}
swap.swap(c, d);
d--;
}
c--;
comparison = comp.compare(c, partitionIndex);
}
doing eager comparison counting is wrong because variable c _can go
below _b_ (which can be the start index or zero). To keep
the invariants correct, the code should read as follows:
int comparison;
while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
if (comparison == 0) {
if (c == partitionIndex) {
partitionIndex = d;
} else if (d == partitionIndex) {
partitionIndex = c;
}
swap.swap(c, d);
d--;
}
c--;
}
Note that I did not analyze the whole logic flow of qsort in this
ported code, but just looking at the code above it seems
that c can indeed go beyond the marker limit.
What do you think? A bug or am I just being dim?
Dawid
Re: Sorting invariants.
Posted by Benson Margulies <bi...@gmail.com>.
I agree, based on my memory of thrashing around on this.
On Mon, Jan 25, 2010 at 10:21 AM, Dawid Weiss <da...@gmail.com> wrote:
> This looks like a bug, it's a different pattern everywhere else. See my patch.
>
> D.
>
> On Mon, Jan 25, 2010 at 4:16 PM, Benson Margulies <bi...@gmail.com> wrote:
>> Well,
>>
>> I deleted my Harmony tree, I'll refetch it tonight and check.
>>
>> --benson
>>
>>
>> On Mon, Jan 25, 2010 at 8:26 AM, Dawid Weiss <da...@gmail.com> wrote:
>>> Hi Benson (and others),
>>>
>>> Say, when you moved the code from Apache Harmony, did you modify it
>>> along the way, or is it what's found in the Harmony's
>>> source code? I'm asking because we're still hitting those array out of
>>> bounds exceptions sometimes. They are tough to isolate, so I reverted
>>> to white-box code inspection. There is a repeated snippet of code that
>>> just isn't right to me, look here:
>>>
>>> comparison = comp.compare(c, partitionIndex);
>>> while (c >= b && comparison >= 0) {
>>> if (comparison == 0) {
>>> if (c == partitionIndex) {
>>> partitionIndex = d;
>>> } else if (d == partitionIndex) {
>>> partitionIndex = c;
>>> }
>>> swap.swap(c, d);
>>>
>>> d--;
>>> }
>>> c--;
>>> comparison = comp.compare(c, partitionIndex);
>>> }
>>>
>>> doing eager comparison counting is wrong because variable c _can go
>>> below _b_ (which can be the start index or zero). To keep
>>> the invariants correct, the code should read as follows:
>>>
>>> int comparison;
>>> while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
>>> if (comparison == 0) {
>>> if (c == partitionIndex) {
>>> partitionIndex = d;
>>> } else if (d == partitionIndex) {
>>> partitionIndex = c;
>>> }
>>> swap.swap(c, d);
>>>
>>> d--;
>>> }
>>> c--;
>>> }
>>>
>>> Note that I did not analyze the whole logic flow of qsort in this
>>> ported code, but just looking at the code above it seems
>>> that c can indeed go beyond the marker limit.
>>>
>>> What do you think? A bug or am I just being dim?
>>>
>>> Dawid
>>>
>>
>
Re: Sorting invariants.
Posted by Dawid Weiss <da...@gmail.com>.
This looks like a bug, it's a different pattern everywhere else. See my patch.
D.
On Mon, Jan 25, 2010 at 4:16 PM, Benson Margulies <bi...@gmail.com> wrote:
> Well,
>
> I deleted my Harmony tree, I'll refetch it tonight and check.
>
> --benson
>
>
> On Mon, Jan 25, 2010 at 8:26 AM, Dawid Weiss <da...@gmail.com> wrote:
>> Hi Benson (and others),
>>
>> Say, when you moved the code from Apache Harmony, did you modify it
>> along the way, or is it what's found in the Harmony's
>> source code? I'm asking because we're still hitting those array out of
>> bounds exceptions sometimes. They are tough to isolate, so I reverted
>> to white-box code inspection. There is a repeated snippet of code that
>> just isn't right to me, look here:
>>
>> comparison = comp.compare(c, partitionIndex);
>> while (c >= b && comparison >= 0) {
>> if (comparison == 0) {
>> if (c == partitionIndex) {
>> partitionIndex = d;
>> } else if (d == partitionIndex) {
>> partitionIndex = c;
>> }
>> swap.swap(c, d);
>>
>> d--;
>> }
>> c--;
>> comparison = comp.compare(c, partitionIndex);
>> }
>>
>> doing eager comparison counting is wrong because variable c _can go
>> below _b_ (which can be the start index or zero). To keep
>> the invariants correct, the code should read as follows:
>>
>> int comparison;
>> while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
>> if (comparison == 0) {
>> if (c == partitionIndex) {
>> partitionIndex = d;
>> } else if (d == partitionIndex) {
>> partitionIndex = c;
>> }
>> swap.swap(c, d);
>>
>> d--;
>> }
>> c--;
>> }
>>
>> Note that I did not analyze the whole logic flow of qsort in this
>> ported code, but just looking at the code above it seems
>> that c can indeed go beyond the marker limit.
>>
>> What do you think? A bug or am I just being dim?
>>
>> Dawid
>>
>
Re: Sorting invariants.
Posted by Benson Margulies <bi...@gmail.com>.
Well,
I deleted my Harmony tree, I'll refetch it tonight and check.
--benson
On Mon, Jan 25, 2010 at 8:26 AM, Dawid Weiss <da...@gmail.com> wrote:
> Hi Benson (and others),
>
> Say, when you moved the code from Apache Harmony, did you modify it
> along the way, or is it what's found in the Harmony's
> source code? I'm asking because we're still hitting those array out of
> bounds exceptions sometimes. They are tough to isolate, so I reverted
> to white-box code inspection. There is a repeated snippet of code that
> just isn't right to me, look here:
>
> comparison = comp.compare(c, partitionIndex);
> while (c >= b && comparison >= 0) {
> if (comparison == 0) {
> if (c == partitionIndex) {
> partitionIndex = d;
> } else if (d == partitionIndex) {
> partitionIndex = c;
> }
> swap.swap(c, d);
>
> d--;
> }
> c--;
> comparison = comp.compare(c, partitionIndex);
> }
>
> doing eager comparison counting is wrong because variable c _can go
> below _b_ (which can be the start index or zero). To keep
> the invariants correct, the code should read as follows:
>
> int comparison;
> while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
> if (comparison == 0) {
> if (c == partitionIndex) {
> partitionIndex = d;
> } else if (d == partitionIndex) {
> partitionIndex = c;
> }
> swap.swap(c, d);
>
> d--;
> }
> c--;
> }
>
> Note that I did not analyze the whole logic flow of qsort in this
> ported code, but just looking at the code above it seems
> that c can indeed go beyond the marker limit.
>
> What do you think? A bug or am I just being dim?
>
> Dawid
>