Why?

I posted a bug report yesterday, thinking it was just some accidentally left over code.
But I noticed this statement in the documentation today. And, frankly, I don't understand why that limitation is there.

The problem with this restriction comes when using multi-dimensional arrays. Branched dynamic arrays are MUCH slower than rectangular/cubic/etc. static arrays - and this is a severe limitation for anyone wanting to work with large amounts of data (e.g. game maps). Of course I could work around this by calculating the positions manually using x*width+y, but I'd like to know the reason why this limitation was put there in the first place, and what's the reasoning behind it. No other compiled language that I used (C/C++/Delphi) has such a limitation.

The check is in mtype.c, line 1835 (DMD 1.021).

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com

Vladimir Panteleev wrote:
> Why?
> 
> I posted a bug report yesterday, thinking it was just some accidentally left over code.
> But I noticed this statement in the documentation today. And, frankly, I don't understand why that limitation is there.
> 
> The problem with this restriction comes when using multi-dimensional arrays. Branched dynamic arrays are MUCH slower than rectangular/cubic/etc. static arrays - and this is a severe limitation for anyone wanting to work with large amounts of data (e.g. game maps). Of course I could work around this by calculating the positions manually using x*width+y, but I'd like to know the reason why this limitation was put there in the first place, and what's the reasoning behind it. No other compiled language that I used (C/C++/Delphi) has such a limitation.
> 
> The check is in mtype.c, line 1835 (DMD 1.021).

This is a reply from Walter last year:

http://www.digitalmars.com/d/archives/digitalmars/D/37038.html#N37071


-- 
Oskar

On Tue, 02 Oct 2007 09:20:29 +0300, Vladimir Panteleev <thecybershadow@gmail.com> wrote:

> Why?
>
> I posted a bug report yesterday, thinking it was just some accidentally left over code.
> But I noticed this statement in the documentation today. And, frankly, I don't understand why that limitation is there.
>
> The problem with this restriction comes when using multi-dimensional arrays. Branched dynamic arrays are MUCH slower than rectangular/cubic/etc. static arrays - and this is a severe limitation for anyone wanting to work with large amounts of data (e.g. game maps). Of course I could work around this by calculating the positions manually using x*width+y, but I'd like to know the reason why this limitation was put there in the first place, and what's the reasoning behind it. No other compiled language that I used (C/C++/Delphi) has such a limitation.
>
> The check is in mtype.c, line 1835 (DMD 1.021).

I think I found the cause of this limitation - OPTLINK hangs, crashes and/or generates corrupt data if I try to force it such input. It works if I use a pointer to a huge static array, but DMD wouldn't accept that as input anyway. I thought that putting the array in a struct or class would prevent the linker from generating a >16MB data segment, but I forgot that D needs(!) to have an initial value for every type, even if it's completely null. Once again, I'll mention that Borland and Microsoft's linkers don't have such a limitation, and they can generate data segments over 16 MB with no problems.

So, suggestions for fixing this:

1) fix or rewrite OPTLINK
   ("rewrite" because I keep hearing about how OPTLINK holds D back for one reason or another; I know it's no small task, however D doesn't need a multi-purpose linker, just one that can handle what the DMD compiler generates)
2) if a type doesn't contain any non-0 initial values, instead of generating a big block of zeroes for the initializer, initialize it with a memset (rep stosd/stosb).

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com

On Tue, 02 Oct 2007 09:44:22 +0300, Oskar Linde <oskar.lindeREM@ovegmail.com> wrote:

> This is a reply from Walter last year:
>
> http://www.digitalmars.com/d/archives/digitalmars/D/37038.html#N37071

If you ask me, most of those reasons are excuses for 6). Putting restrictions on things which MAY hurt you IF you do things you're never going to do is, to put it softly, not a very good idea. A static array in the uninitialized part of the data segment allows me to randomly access any part of it very quickly, because its address and the address of every of its elements is predetermined at compile time, so - unlike with the case of dynamic arrays or pointers to static arrays - you do not need to dereference pointers every time. I'll say it again, D is the only compiled language that has such a limitation.

As for point 5) - well, the executable grows by the size of the array regardless if the array has any initialization. Heck, it adds initialization data even if I use "=void".

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com

Reply to Vladimir,

> Why?
> 
> I posted a bug report yesterday, thinking it was just some
> accidentally left over code.
> 
> But I noticed this statement in the documentation today. And, frankly,
> I don't understand why that limitation is there.
> 
> The problem with this restriction comes when using multi-dimensional
> arrays. Branched dynamic arrays are MUCH slower than
> rectangular/cubic/etc. static arrays - and this is a severe limitation
> for anyone wanting to work with large amounts of data (e.g. game
> maps). Of course I could work around this by calculating the positions
> manually using x*width+y, but I'd like to know the reason why this
> limitation was put there in the first place, and what's the reasoning
> behind it.

just new the array.

On Tue, 02 Oct 2007 10:16:25 +0300, BCS <ao@pathlink.com> wrote:

> Reply to Vladimir,
>
>> Why?
>>
>> I posted a bug report yesterday, thinking it was just some accidentally left over code.
>>
>> But I noticed this statement in the documentation today. And, frankly, I don't understand why that limitation is there.
>>
>> The problem with this restriction comes when using multi-dimensional arrays. Branched dynamic arrays are MUCH slower than rectangular/cubic/etc. static arrays - and this is a severe limitation for anyone wanting to work with large amounts of data (e.g. game maps). Of course I could work around this by calculating the positions manually using x*width+y, but I'd like to know the reason why this limitation was put there in the first place, and what's the reasoning behind it.
>
> just new the array.

If you mean that I do something like:
	int[4096][4096]* arr = (new int[4096][4096][1]).ptr;
1) the compiler still (normally) doesn't let me do it
2) it's slower for random access due to having to dereference a pointer.

But, yes, this is the sanest workaround so far.

-- 
Best regards,
 Vladimir                          mailto:thecybershadow@gmail.com

On 10/2/07, Vladimir Panteleev <thecybershadow@gmail.com> wrote:
> If you mean that I do something like:
>         int[4096][4096]* arr = (new int[4096][4096][1]).ptr;

Why not just
class Array2D(T)
{
    this(int width, int height)
    {
        this.width = width;
        a = new T(width * height);
    }

    T opIndex(int x, int y)
    {
        return a[x * width + y];
    }

    void opIndexAssign(T n, int x, int y)
    {
        a[x * width + y] = n;
    }

    T[] a;
    int width;
}

Then
    arr = new Array2D(4096,4096);

On 10/2/07, Janice Caron <caron800@googlemail.com> wrote:
> Then
>     arr = new Array2D(4096,4096);

Sorry. That should be

    arr = new Array!(int)(4096,4096);

then you just refer to the elements as arr[x,y] as you'd expect.

On 10/2/07, Janice Caron <caron800@googlemail.com> wrote:
> Sorry. That should be
>
>     arr = new Array!(int)(4096,4096);

Gaah! That's too many typos for one morning!

arr = new Array2D!(int)(4096,4096);

Anyway, hopefully you get the idea. I'm going for more coffee before I mistype anything else!

Janice Caron Wrote:
> Anyway, hopefully you get the idea. I'm going for more coffee before I mistype anything else!
Thanks - this indeed makes the code more readable, however now accessing an element involves two dereferences (the class, and the array pointer) - and, possibly, a function call if the compiler won't inline it. My main concern is the speed, otherwise I wouldn't be complaining and just use dynamic arrays :P

-- Vladimir