View mode: basic / threaded / horizontal-split · Log in · Help
June 09, 2012
static array literal syntax request: auto x=[1,2,3]S;
(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
Re: static array literal syntax request: auto x=[1,2,3]S;
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
Re: static array literal syntax request: auto x=[1,2,3]S;
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
Re: static array literal syntax request: auto x=[1,2,3]S;
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
Re: static array literal syntax request: auto x=[1,2,3]S;
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
Re: static array literal syntax request: auto x=[1,2,3]S;
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
Re: static array literal syntax request: auto x=[1,2,3]S;
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
Re: static array literal syntax request: auto x=[1,2,3]S;
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
Re: static array literal syntax request: auto x=[1,2,3]S;
writefln(typeof([1, 2, 3, 4, 5]).stringof) is int[5u] in D1 haha.
June 10, 2012
Re: static array literal syntax request: auto x=[1,2,3]S;
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