View mode: basic / threaded / horizontal-split · Log in · Help
March 07, 2012
0 < negative loop condition bug or misunderstanding on my part
I'm writing my first basic algorithms, this one is merge sort. 
This version throws an exception when array.length - setSize is 
negative (which should be fine, the rest of my function would 
deal with it):

template mergeSort(T)
{
	void mergeSort(ref T[] array, const T setSize = 100)
	{
		T[][] merge;
		merge.length = array.length / setSize;
		T ii, jj;
		for(ii = 0, jj = 0;ii < array.length - setSize;ii += setSize, 
++jj)
			merge[jj] = array[ii..ii + setSize];

...

If I make the seemingly pointless change to this:

template mergeSort(T)
{
	void mergeSort(ref T[] array, const T setSize = 100)
	{
		T[][] merge;
		merge.length = array.length / setSize;
		T ii, jj;
		T temp2 = array.length - setSize;
		for(ii = 0, jj = 0;ii < temp2;ii += setSize, ++jj)
			merge[jj] = array[ii..ii + setSize];

Where it's a temporary variable then it works perfectly well.
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
On 03/06/2012 09:11 PM, ixid wrote:
> I'm writing my first basic algorithms, this one is merge sort. This
> version throws an exception when array.length - setSize is negative
> (which should be fine, the rest of my function would deal with it):
>
> template mergeSort(T)
> {
> void mergeSort(ref T[] array, const T setSize = 100)
> {
> T[][] merge;
> merge.length = array.length / setSize;
> T ii, jj;
> for(ii = 0, jj = 0;ii < array.length - setSize;ii += setSize, ++jj)

We don't know what T is, but I assume a signed type like int.

array.length is size_t, i.e. an unsigned type. Unsigned types have this 
nasty habit of converting the entire expression to unsigned (that is a 
rule since C). So array.length - setSize above is size_t.

In other words, it is never negative.

> merge[jj] = array[ii..ii + setSize];
>
> ...
>
> If I make the seemingly pointless change to this:
>
> template mergeSort(T)
> {
> void mergeSort(ref T[] array, const T setSize = 100)
> {
> T[][] merge;
> merge.length = array.length / setSize;
> T ii, jj;
> T temp2 = array.length - setSize;

There, you are setting temp2's size to be T (e.g. int), so temp2 can be 
negative.

> for(ii = 0, jj = 0;ii < temp2;ii += setSize, ++jj)
> merge[jj] = array[ii..ii + setSize];
>
> Where it's a temporary variable then it works perfectly well.

Ali
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
On Wed, Mar 07, 2012 at 06:11:18AM +0100, ixid wrote:
> I'm writing my first basic algorithms, this one is merge sort. This
> version throws an exception when array.length - setSize is negative
> (which should be fine, the rest of my function would deal with it):
[...]

array.length is of type size_t, which is an *unsigned* integer type. If
setSize > array.length, then array.length - setSize will underflow and
become a large positive number.


T

-- 
They say that "guns don't kill people, people kill people." Well I think
the gun helps. If you just stood there and yelled BANG, I don't think
you'd kill too many people. -- Eddie Izzard, Dressed to Kill
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
Ah, thank you, so it's wrapping. That seems like a bad idea, what 
is the benefit to size being unsigned rather than signed? This 
case would seem like one where allowing negatives is clearly 
better and more intuitive.
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
On 03/06/2012 10:05 PM, ixid wrote:
> Ah, thank you, so it's wrapping. That seems like a bad idea, what is the
> benefit to size being unsigned rather than signed? This case would seem
> like one where allowing negatives is clearly better and more intuitive.

There are probably hundreds of discussions about that over the years on 
many different language newsgroups and forums. :) There is no clear 
winner: Both sides of the arguments seem to have good points.

Ali
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
> On 03/06/2012 10:05 PM, ixid wrote:
> > Ah, thank you, so it's wrapping. That seems like a bad idea, what is
> > the benefit to size being unsigned rather than signed?

Because it doesn't make sense to have something with a negative size?


> > This case would seem like one where allowing negatives is clearly
> > better and more intuitive.

Not necessarily. For example, int.max+1 is a very large negative number,
and -int.min is still a very large negative number. :-)


T

-- 
Be in denial for long enough, and one day you'll deny yourself of things you wish you hadn't.
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
On 7 March 2012 19:30, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:
>> On 03/06/2012 10:05 PM, ixid wrote:
>> > Ah, thank you, so it's wrapping. That seems like a bad idea, what is
>> > the benefit to size being unsigned rather than signed?
>> > This case would seem like one where allowing negatives is clearly
>> > better and more intuitive.

Because you don't describe things as -5 metres tall, so you don't
describe things as -1024 bytes long. size_t makes sense unsigned
because negatives make no sense for size.

However, if you cast array.length to an int, it may work, haven't tested it.

--
James Miller
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
On 03/07/2012 07:05 AM, ixid wrote:
> Ah, thank you, so it's wrapping. That seems like a bad idea, what is the
> benefit to size being unsigned rather than signed? This case would seem
> like one where allowing negatives is clearly better and more intuitive.

The problem is not that length is unsigned. The issue is the implicit 
conversion from signed to unsigned. The right thing would be to disallow 
signed -> unsigned and unsigned -> signed implicit conversion unless 
value range propagation can prove it safe, and to make comparison 
between signed and unsigned actually work by translating it to more than 
one machine instruction.
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
On 03/07/2012 11:01 AM, Timon Gehr wrote:
> On 03/07/2012 07:05 AM, ixid wrote:
>> Ah, thank you, so it's wrapping. That seems like a bad idea, what is the
>> benefit to size being unsigned rather than signed? This case would seem
>> like one where allowing negatives is clearly better and more intuitive.
>
> The problem is not that length is unsigned. The issue is the implicit
> conversion from signed to unsigned. The right thing would be to disallow
> signed -> unsigned and unsigned -> signed implicit conversion unless
> value range propagation can prove it safe, and to make comparison
> between signed and unsigned actually work by translating it to more than
> one machine instruction.

Furthermore, bitwise boolean operators should still accept arguments of 
arbitrary signedness but the result should implicitly convert to both 
signed and unsigned.
March 07, 2012
Re: 0 < negative loop condition bug or misunderstanding on my part
On 3/7/12, Timon Gehr <timon.gehr@gmx.ch> wrote:
> The problem is not that length is unsigned. The issue is the implicit
> conversion from signed to unsigned.

You bet. I've once had this hard to spot bug where I've used a call
that was something like max(0, min(10, <expression>)), and this ended
up returning a negative int because <expression> was combining an
integer with a .length property of some array (I don't recall the
exact call though). It was truly a WTF moment.
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home