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.

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

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

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.

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

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

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

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.

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.

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.