June 09, 2012
(apologies for cross-posting here, I feel this is a better place to ask than in my original post where I only received 1 answer that seemed in favor of this:
http://d.puremagic.com/issues/show_bug.cgi?id=8008 which was 2 months ago).

Please see to the original post above to see the proposal for the new syntax for static array litterals
(but please reply here).

Running some simple tests show that this is not just cosmetics and ease of use but would also lead to significantly reduced overhead when dealing with static array litterals vs raw C array litterals, as currently D static array litterals perform costly heap allocation as intermediate step (as shown in the resulting assembly).

Here's 2 identical programs in C and D, which, compiled with all optimization flags, result in 20x speedup for the C version (D takes 17 sec with dmd -O -release -inline -noboundscheck main).

-----
//main.d
import std.stdio,std.conv;
void main(){
	size_t n=100000000,z=0;i=0,j=0;
	for(i=0;i<n;i++){
		size_t[10] a=[i,i+1,i+2,i+3,i+4,i+5,i+6,i+7,i+8,i+9];
		for(j=0;j<9;j++){z+=a[j];}
	}
	writeln(z);
}
-----
//main.c
#include <stdio.h>
int main(){
	size_t n=100000000,z=0;i=0,j=0;
	for(i=0;i<n;i++){
		size_t a[10]={i,i+1,i+2,i+3,i+4,i+5,i+6,i+7,i+8,i+9};
		for(j=0;j<9;j++){z+=a[j];}
	}
	printf("%lu\n",z);
	return 0;
}
-----
Note, the same D program modified as follows runs about as fast as the C program:
size_t[10] a=void; a[0]=i; a[1]=i+1; a[2]=i+2;a[3]=i+3;a[4]=i+4;a[5]=i+5;a[6]=i+6;a[7]=i+7;a[8]=i+8;a[9]=i+9;

Having the new syntax auto a=[i,i+1,i+2,i+3,i+4,i+5,i+6,i+7,i+8,i+9]S would prevent the intermediate heap allocation and should be at least as fast as the C version, possibly faster if SSE instructions are used.

Finally, someone suggested somewhere else (http://www.digitalmars.com/d/archives/digitalmars/D/bugs/Issue_8008_New_static_array_literal_syntax_request_auto_x_1_2_3_S_39709.html) that this could be done in library code:
auto a = [1, 2, 3].toStatic;
however I don't see how that could be achieved, as by the time the array reaches the toStatic function, it is a dynamic array whose length is not known at compile time.
Also, his suggested syntax auto[$] a=[1,2,3] is not as good in my opinion as it prevents one from directly passing an (anonymous) static array to a function, eg my_fun([1,2,3]S) vs: auto[$] a=[1,2,3]; my_fun(a);

Thanks for your comments!

June 09, 2012
On 06/10/2012 12:05 AM, timotheecour wrote:
> (apologies for cross-posting here, I feel this is a better place to ask
> than in my original post where I only received 1 answer that seemed in
> favor of this:
> http://d.puremagic.com/issues/show_bug.cgi?id=8008 which was 2 months ago).
>
> Please see to the original post above to see the proposal for the new
> syntax for static array litterals
> (but please reply here).
>
> Running some simple tests show that this is not just cosmetics and ease
> of use but would also lead to significantly reduced overhead when
> dealing with static array litterals vs raw C array litterals, as
> currently D static array litterals perform costly heap allocation as
> intermediate step (as shown in the resulting assembly).
> ...

D static array literals don't perform a costly heap allocation. It is simply a bug in the implementation. This is not a compelling reason to add new syntax.
June 09, 2012
On Sunday, June 10, 2012 00:15:01 Timon Gehr wrote:
> D static array literals don't perform a costly heap allocation. It is simply a bug in the implementation. This is not a compelling reason to add new syntax.

D doesn't _have_ static array literals. It only has dynamic array literals.

int[5] a = [1, 2, 3, 4, 5];

should definitely be optimized such that it doesn't do any heap allocations, but the array literal itself is dynamic regardless, as typeof indicates. The other place that this causes problems is templated functions. e.g.

void func(A)(A array)
    if(isStaticArray!A)
{}

func([1, 2, 3, 4, 5]);

will fail to compile. You're forced to create one on the stack first.

int[5] array = [1, 2, 3, 4, 5];
func(array);

That _might_ merit adding a syntax for indicating that an array literal is static.

However, in general, it's definitely true that the additional heap allocations that we currently see should just be optimized out by the compiler, and if that's all that we're trying to solve, then that's a matter of fixing the optimizer, not the language.

- Jonathan M Davis
June 09, 2012
On 06/10/2012 12:34 AM, Jonathan M Davis wrote:
> On Sunday, June 10, 2012 00:15:01 Timon Gehr wrote:
>> D static array literals don't perform a costly heap allocation. It is
>> simply a bug in the implementation. This is not a compelling reason to
>> add new syntax.
>
> D

DMD

> doesn't _have_ static array literals. It only has dynamic array literals.
>
> int[5] a = [1, 2, 3, 4, 5];
>

This is a static array literal.

> should definitely be optimized such that it doesn't do any heap allocations,
> but the array literal itself is dynamic regardless, as typeof indicates.

I don't see a typeof there. The array literal is a static array literal if it is assigned/converted to a static array.


> The
> other place that this causes problems is templated functions. e.g.
>
> void func(A)(A array)
>      if(isStaticArray!A)
> {}
>
> func([1, 2, 3, 4, 5]);
>
> will fail to compile. You're forced to create one on the stack first.
>
> int[5] array = [1, 2, 3, 4, 5];
> func(array);
>

func(cast(int[5])[1,2,3,4,5]);

> That _might_ merit adding a syntax for indicating that an array literal is
> static.
>

Yes, certainly. I was simply pointing out that arguing about performance makes a poor case here.

> However, in general, it's definitely true that the additional heap allocations
> that we currently see should just be optimized out by the compiler, and if
> that's all that we're trying to solve, then that's a matter of fixing the
> optimizer, not the language.
>

This is not about optimization. Allocating is simply incorrect. It is a 'wrong code' bug.
June 10, 2012
On 10-06-2012 01:02, Timon Gehr wrote:
> On 06/10/2012 12:34 AM, Jonathan M Davis wrote:
>> On Sunday, June 10, 2012 00:15:01 Timon Gehr wrote:
>>> D static array literals don't perform a costly heap allocation. It is
>>> simply a bug in the implementation. This is not a compelling reason to
>>> add new syntax.
>>
>> D
>
> DMD
>
>> doesn't _have_ static array literals. It only has dynamic array literals.
>>
>> int[5] a = [1, 2, 3, 4, 5];
>>
>
> This is a static array literal.
>
>> should definitely be optimized such that it doesn't do any heap
>> allocations,
>> but the array literal itself is dynamic regardless, as typeof indicates.
>
> I don't see a typeof there. The array literal is a static array literal
> if it is assigned/converted to a static array.
>
>
>> The
>> other place that this causes problems is templated functions. e.g.
>>
>> void func(A)(A array)
>> if(isStaticArray!A)
>> {}
>>
>> func([1, 2, 3, 4, 5]);
>>
>> will fail to compile. You're forced to create one on the stack first.
>>
>> int[5] array = [1, 2, 3, 4, 5];
>> func(array);
>>
>
> func(cast(int[5])[1,2,3,4,5]);
>
>> That _might_ merit adding a syntax for indicating that an array
>> literal is
>> static.
>>
>
> Yes, certainly. I was simply pointing out that arguing about performance
> makes a poor case here.
>
>> However, in general, it's definitely true that the additional heap
>> allocations
>> that we currently see should just be optimized out by the compiler,
>> and if
>> that's all that we're trying to solve, then that's a matter of fixing the
>> optimizer, not the language.
>>
>
> This is not about optimization. Allocating is simply incorrect. It is a
> 'wrong code' bug.

I'd have to agree. There needs to be strong guarantees about this, not just "the compiler can/might optimize this".

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org
June 10, 2012
On Sunday, June 10, 2012 01:02:40 Timon Gehr wrote:
> On 06/10/2012 12:34 AM, Jonathan M Davis wrote:
> > On Sunday, June 10, 2012 00:15:01 Timon Gehr wrote:
> >> D static array literals don't perform a costly heap allocation. It is simply a bug in the implementation. This is not a compelling reason to add new syntax.
> > 
> > D
> 
> DMD
> 
> > doesn't _have_ static array literals. It only has dynamic array literals.
> > 
> > int[5] a = [1, 2, 3, 4, 5];
> 
> This is a static array literal.
> 
> > should definitely be optimized such that it doesn't do any heap allocations, but the array literal itself is dynamic regardless, as typeof indicates.
> I don't see a typeof there. The array literal is a static array literal if it is assigned/converted to a static array.

Just do

writlen(typeof([1, 2, 3, 4, 5]).stringof);

It'll be int[], not int[5]. I don't believe that there is _any_ case where an array literal is considered static. The closest that you get is that it will implicitly conert them to static arrays in statements such as

int[5] a = [1, 2, 3, 4, 5];

but as evidenced by the extra heap allocation, it still creates the dynamic array before doing the conversion, and that exact same assignment works if the dynamic array isn't a literal.

int[] a = [1, 2, 3, 4, 5];
int[5] b = a;

I think that it's quite clear that the type system always considers array literals to be dynamic, which is why we're getting that extra heap allocation, and why in no case are they inferred to be static.

> This is not about optimization. Allocating is simply incorrect. It is a 'wrong code' bug.

As far as I can tell, there's nothing wrong about it as far as the type system is concerned. Certainly, the compiler considers array literals to be dynamic, and that's why we're getting these issues. This behavior is _not_ desirable from the standpoint of efficiency, but as for as the type system goes, I don't see anything incorrect about it.

- Jonathan M Davis
June 10, 2012
Am 10.06.2012 01:02, schrieb Timon Gehr:
> On 06/10/2012 12:34 AM, Jonathan M Davis wrote:
>> On Sunday, June 10, 2012 00:15:01 Timon Gehr wrote:
>>> D static array literals don't perform a costly heap allocation. It is simply a bug in the implementation. This is not a compelling reason to add new syntax.
>>
>> D
> 
> DMD
> 
>> doesn't _have_ static array literals. It only has dynamic array literals.
>>
>> int[5] a = [1, 2, 3, 4, 5];
>>
> 
> This is a static array literal.
> 
>> should definitely be optimized such that it doesn't do any heap
>> allocations,
>> but the array literal itself is dynamic regardless, as typeof indicates.
> 
> I don't see a typeof there. The array literal is a static array literal if it is assigned/converted to a static array.
> 
> 
>> The
>> other place that this causes problems is templated functions. e.g.
>>
>> void func(A)(A array)
>>      if(isStaticArray!A)
>> {}
>>
>> func([1, 2, 3, 4, 5]);
>>
>> will fail to compile. You're forced to create one on the stack first.
>>
>> int[5] array = [1, 2, 3, 4, 5];
>> func(array);
>>
> 
> func(cast(int[5])[1,2,3,4,5]);
> 
>> That _might_ merit adding a syntax for indicating that an array
>> literal is
>> static.
>>
> 
> Yes, certainly. I was simply pointing out that arguing about performance makes a poor case here.
> 
>> However, in general, it's definitely true that the additional heap
>> allocations
>> that we currently see should just be optimized out by the compiler,
>> and if
>> that's all that we're trying to solve, then that's a matter of fixing the
>> optimizer, not the language.
>>
> 
> This is not about optimization. Allocating is simply incorrect. It is a 'wrong code' bug.

Yes, you're right. And you've also shown that we don't need a new syntax to accomplish this.
June 10, 2012
On 06/10/12 10:47, mta`chrono wrote:
> Am 10.06.2012 01:02, schrieb Timon Gehr:
>> On 06/10/2012 12:34 AM, Jonathan M Davis wrote:
>>> On Sunday, June 10, 2012 00:15:01 Timon Gehr wrote:
>>>> D static array literals don't perform a costly heap allocation. It is simply a bug in the implementation. This is not a compelling reason to add new syntax.
>>>
>>> D
>>
>> DMD
>>
>>> doesn't _have_ static array literals. It only has dynamic array literals.
>>>
>>> int[5] a = [1, 2, 3, 4, 5];
>>>
>>
>> This is a static array literal.
>>
>>> should definitely be optimized such that it doesn't do any heap
>>> allocations,
>>> but the array literal itself is dynamic regardless, as typeof indicates.
>>
>> I don't see a typeof there. The array literal is a static array literal if it is assigned/converted to a static array.

An array literal is a dynamic array with a known constant length that implicitly converts to a static array of the same size and element type. That's a sane definition, and AFAICT this is how it's currently handled.

>>> The
>>> other place that this causes problems is templated functions. e.g.
>>>
>>> void func(A)(A array)
>>>      if(isStaticArray!A)
>>> {}
>>>
>>> func([1, 2, 3, 4, 5]);
>>>
>>> will fail to compile. You're forced to create one on the stack first.
>>>
>>> int[5] array = [1, 2, 3, 4, 5];
>>> func(array);
>>>
>>
>> func(cast(int[5])[1,2,3,4,5]);
>>
>>> That _might_ merit adding a syntax for indicating that an array
>>> literal is
>>> static.

I wasn't kidding about overloading 'static' for this; it would certainly be better that inventing yet another literal syntax.

>> Yes, certainly. I was simply pointing out that arguing about performance makes a poor case here.
>>
>>> However, in general, it's definitely true that the additional heap
>>> allocations
>>> that we currently see should just be optimized out by the compiler,
>>> and if
>>> that's all that we're trying to solve, then that's a matter of fixing the
>>> optimizer, not the language.
>>>
>>
>> This is not about optimization. Allocating is simply incorrect. It is a 'wrong code' bug.
> 
> Yes, you're right. And you've also shown that we don't need a new syntax to accomplish this.

When you want to avoid the heap allocation, you can always use hacks such as:

   template static_array(alias da) {
      typeof(da[0])[da.length] static_array = da;
   }
   f(...) {
      int[3] a = static_array!([1,2,3]);
      ...
   }

But the compiler should do this automatically in these cases, right now it doesn't. This hack won't of course work for the program mentioned in this thread.

The isStaticArray!A problem is partially related to how the compiler handles arrays.

   auto f(T)(T a) { enum l = a.length; return l; }

works with

   int[3] a = [1,2,3];
   f(a);

but fails with

   f([1,2,3]);

And cases like

   auto f(E)(E[] a) { enum l = a.length; return l; }

don't work at all.

Making these things work, which should be possible, would help when dealing with static arrays, and also allow more optimization opportunities.

artur
June 10, 2012
writefln(typeof([1, 2, 3, 4, 5]).stringof) is int[5u] in D1 haha.


June 10, 2012
On 06/10/2012 04:54 PM, Artur Skawina wrote:
> On 06/10/12 10:47, mta`chrono wrote:
>> Am 10.06.2012 01:02, schrieb Timon Gehr:
>>> On 06/10/2012 12:34 AM, Jonathan M Davis wrote:
>>>> On Sunday, June 10, 2012 00:15:01 Timon Gehr wrote:
>>>>> D static array literals don't perform a costly heap allocation. It is
>>>>> simply a bug in the implementation. This is not a compelling reason to
>>>>> add new syntax.
>>>>
>>>> D
>>>
>>> DMD
>>>
>>>> doesn't _have_ static array literals. It only has dynamic array literals.
>>>>
>>>> int[5] a = [1, 2, 3, 4, 5];
>>>>
>>>
>>> This is a static array literal.
>>>
>>>> should definitely be optimized such that it doesn't do any heap
>>>> allocations,
>>>> but the array literal itself is dynamic regardless, as typeof indicates.
>>>
>>> I don't see a typeof there. The array literal is a static array literal
>>> if it is assigned/converted to a static array.
>
> An array literal is a dynamic array with a known constant length that
> implicitly converts to a static array of the same size and element type.
> That's a sane definition,

It is not. It does not specify if/when allocations take place, for example.

> and AFAICT this is how it's currently handled.
>

It is not.

void main(){
    int[0] x = [1];
}


>>>> The
>>>> other place that this causes problems is templated functions. e.g.
>>>>
>>>> void func(A)(A array)
>>>>       if(isStaticArray!A)
>>>> {}
>>>>
>>>> func([1, 2, 3, 4, 5]);
>>>>
>>>> will fail to compile. You're forced to create one on the stack first.
>>>>
>>>> int[5] array = [1, 2, 3, 4, 5];
>>>> func(array);
>>>>
>>>
>>> func(cast(int[5])[1,2,3,4,5]);
>>>
>>>> That _might_ merit adding a syntax for indicating that an array
>>>> literal is
>>>> static.
>
> I wasn't kidding about overloading 'static' for this; it would certainly
> be better that inventing yet another literal syntax.
>

Using 'static' is "inventing yet another literal syntax" as well.

>>> Yes, certainly. I was simply pointing out that arguing about performance
>>> makes a poor case here.
>>>
>>>> However, in general, it's definitely true that the additional heap
>>>> allocations
>>>> that we currently see should just be optimized out by the compiler,
>>>> and if
>>>> that's all that we're trying to solve, then that's a matter of fixing the
>>>> optimizer, not the language.
>>>>
>>>
>>> This is not about optimization. Allocating is simply incorrect. It is a
>>> 'wrong code' bug.
>>
>> Yes, you're right. And you've also shown that we don't need a new syntax
>> to accomplish this.
>
> When you want to avoid the heap allocation, you can always use hacks such as:
>
>     template static_array(alias da) {
>        typeof(da[0])[da.length] static_array = da;
>     }
>     f(...) {
>        int[3] a = static_array!([1,2,3]);
>        ...
>     }
>
> But the compiler should do this automatically in these cases,

The compiler should do the right thing, not automatically apply a hack that only works for CTFEable right hand sides.

> right now it
> doesn't. This hack won't of course work for the program mentioned in this
> thread.
>
> The isStaticArray!A problem is partially related to how the compiler handles
> arrays.
>
>     auto f(T)(T a) { enum l = a.length; return l; }
>
> works with
>
>     int[3] a = [1,2,3];
>     f(a);
>
> but fails with
>
>     f([1,2,3]);
>
> And cases like
>
>     auto f(E)(E[] a) { enum l = a.length; return l; }
>
> don't work at all.
>
> Making these things work, which should be possible,

f([1,2,3]);               // f!(int[])
f([1,2,3,4]);             // f!(int[])

int[3] a = [1,2,3];
f(a);                     // f!(int[3])
f(cast(int[3])[1,2,3]);   // f!(int[3])
f(cast(int[4])[1,2,3,4]); // f!(int[4])

> would help when dealing
> with static arrays, and also allow more optimization opportunities.
>
> artur

I don't see it helping optimization.
« First   ‹ Prev
1 2 3 4
Top | Discussion index | About this forum | D home