On 06/10/12 18:02, Timon Gehr wrote:
> 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.

Implementation details. Would you like to forbid "unnecessary" allocations? Not doing this should be harmless as it only affects performance, but maybe the hidden heap allocations should indeed be disallowed. Any decent compiler won't be emitting them anyway.

>> and AFAICT this is how it's currently handled.
>>
> 
> It is not.
> 
> void main(){
>     int[0] x = [1];
> }

Try running that, in non-release mode. :)

The fact that the compiler accepts it even in the cases where it should be able to statically figure out that it will fail at runtime isn't ideal, but this is just a quality of implementation issue.


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

In a way - yes. But i think "static[...]" would be much better than "[...]S".


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

Obviously. I'm just showing a workaround that lets you avoid the useless heap allocation in certain cases, until the compiler learns to do the right thing.


>> 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])

I'm not sure what your point is here. Mine is that 'length' is
known in all these cases at compile time. Yet it's only possible
to retrieve it when the argument is a real static array. It should
also be possible when the function is called with a literal. Yes,
it's just for templates and would need (hidden) specialization/cloning.
Which sounds worse than it is - because it can happen after inlining.


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

> I don't see it helping optimization.

See above.

artur

On 06/10/2012 07:00 PM, Artur Skawina wrote:
> On 06/10/12 18:02, Timon Gehr wrote:
>> On 06/10/2012 04:54 PM, Artur Skawina wrote:
>>> ...
>>> 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.
>
> Implementation details. Would you like to forbid "unnecessary" allocations?
> Not doing this should be harmless as it only affects performance,

Wrong.

class S{
    ~this() {
        int[3] a = [1,2,3];
    }
}


> but maybe
> the hidden heap allocations should indeed be disallowed. Any decent compiler
> won't be emitting them anyway.
>
>>> and AFAICT this is how it's currently handled.
>>>
>>
>> It is not.
>>
>> void main(){
>>      int[0] x = [1];
>> }
>
> Try running that, in non-release mode. :)
>

(I never post valid D code that I haven't run.)

> The fact that the compiler accepts it even in the cases where it should
> be able to statically figure out that it will fail at runtime isn't ideal,
> but this is just a quality of implementation issue.
>

It is a bug. A static type system is pointless if it is not used for validating certain code properties.

>
>>>>>> 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.
>
> In a way - yes. But i think "static[...]" would be much better than "[...]S".
>

Obviously, none is much better than the other.

> ...
>>>
>>> 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])
>
> I'm not sure what your point is here.

A statically known length cannot be different in two identical instantiations.

> Mine is that 'length' is
> known in all these cases at compile time. Yet it's only possible
> to retrieve it when the argument is a real static array. It should
> also be possible when the function is called with a literal.

That is a case for introducing a dedicated static array literal syntax, not for butchering the template instantiation semantics. (if at all)

> Yes,
> it's just for templates and would need (hidden) specialization/cloning.
> Which sounds worse than it is - because it can happen after inlining.
>

It sounds bad because it is bad.

>
>>> would help when dealing
>>> with static arrays, and also allow more optimization opportunities.
>
>> I don't see it helping optimization.
>
> See above.
>
> artur

The optimizer can inline the call and use the additional information gained without language changes.

What you want to achieve is better left to macros.

On 06/10/12 19:32, Timon Gehr wrote:
> On 06/10/2012 07:00 PM, Artur Skawina wrote:
>> On 06/10/12 18:02, Timon Gehr wrote:
>>> On 06/10/2012 04:54 PM, Artur Skawina wrote:
>>>> ...
>>>> 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.
>>
>> Implementation details. Would you like to forbid "unnecessary" allocations? Not doing this should be harmless as it only affects performance,
> 
> Wrong.
> 
> class S{
>     ~this() {
>         int[3] a = [1,2,3];
>     }
> }

I'm sure we agree that no allocation should take place here, just a memcpy, which would often be optimized to only a few stores.

>> but maybe
>> the hidden heap allocations should indeed be disallowed. Any decent compiler
>> won't be emitting them anyway.

Your example is a good case for explicitly banning them, I agree.


>>>> and AFAICT this is how it's currently handled.
>>>>
>>>
>>> It is not.
>>>
>>> void main(){
>>>      int[0] x = [1];
>>> }
>>
>> Try running that, in non-release mode. :)
>>
> 
> (I never post valid D code that I haven't run.)

Then I'm not sure what you're trying to say; that program will throw an exception at runtime. That the compiler is buggy by compiling it?


>> The fact that the compiler accepts it even in the cases where it should be able to statically figure out that it will fail at runtime isn't ideal, but this is just a quality of implementation issue.
>>
> 
> It is a bug. A static type system is pointless if it is not used for validating certain code properties.

True. The way i see this --  there are so many large problems and holes in both the language and compiler that worrying about cases like this one not being caught at compile-time is premature. Sure, eventually it needs to be handled better, but right now there are bigger issues. And my comment wrt the compiler wasn't necessarily fair - it seems to do a very decent job in most cases, front-end wise; most issues are not with the implementation, but with the definition/specification.


>>>>>>> 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.
>>
>> In a way - yes. But i think "static[...]" would be much better than "[...]S".
>>
> 
> Obviously, none is much better than the other.
> 
>> ...
>>>>
>>>> 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])
>>
>> I'm not sure what your point is here.
> 
> A statically known length cannot be different in two identical instantiations.

Obviously. That's why I mentioned cloning them. This is done for
non-templated functions that are called with known arguments already;
all i'm suggesting is using a similar approach here.
The 'length' property of an array literal can be viewed as known
parameter. (and, yes, my solution requires for this be done at an
earlier stage)


>> Mine is that 'length' is
>> known in all these cases at compile time. Yet it's only possible
>> to retrieve it when the argument is a real static array. It should
>> also be possible when the function is called with a literal.
> 
> That is a case for introducing a dedicated static array literal syntax, not for butchering the template instantiation semantics. (if at all)

A solution that requires the programmer to always remember to mark literals in a special way is not the best approach. It should be possible to call a library functions with both a "real" array and a literal and the syntax shouldn't be different. Especially as that "array" could be an enum. Or immutable variable set at compile time.

Another approach would be using __traits, but the implications wouldn't really be much different...


> The optimizer can inline the call and use the additional information gained without language changes.

What if i'd like to use a different algorithm for a certain array size? Right now, I can, but have to assign the literal to a temporary static array, before calling the function. This is the main issue, everything else is just a consequence of my proposed solution, more of a side-effect actually.

The naive approach would be to convert the dynamic array literal to a static array, but that won't work, because static arrays are passed by value. Hmm, special-casing for const args and literals might work.

Anyway, can you think of a better solution? Ie one, that does not involve introducing a new literal syntax?

> What you want to achieve is better left to macros.

I'd love to have macros, they are necessary for things like attributes and pragmas. But if macros are required for generic programming then something is wrong.

artur

I honestly don't see the POINT of having a "dynamic array literal".

What's the point of making the literals dynamic?

They should all be static, and only converted to dynamic if necessary from the context.

But I really don't see the benefit of allocating them on the heap just because we can... perhaps someone can enlighten me?

On Sunday, June 10, 2012 23:23:57 Mehrdad wrote:
> I honestly don't see the POINT of having a "dynamic array literal".
> 
> What's the point of making the literals dynamic?
> 
> They should all be static, and only converted to dynamic if necessary from the context.
> 
> But I really don't see the benefit of allocating them on the heap just because we can... perhaps someone can enlighten me?

In the vast majority of cases where an array literal is used, it's assigned to a dynamic array. And if you do something like

auto arr = [1, 2, 3, 4, 5];

the expectation is that you'll get a dynamic array. So, it's quite natural to make array literals dynamic. Almost all arrays are dynamic.

As annoying is it may be upon occasion to not be able to simply pass a literal to a templated function which you want to be taking a static array, it would be _far_ more annoying if it assumed that the literal were static. Almost all functions (templated or otherwise) which take arrays take dynamic ones, not static ones.

And if an array literal were static, what would this do?

int[] func(int[] a)
{
    return a;
}

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

would it slice the static array literal and therefore return a slice of a now invalid temporary, or would it allocate the array on the heap as it would now? With all other static arrays, you'd get a slice, which would be very much the _wrong_ thing to do here. So, making the literal static and then slicing it wuold be very bad, but making it static and then converting it to a dynamic array would be completely inconsistent with the normal case.

About the only case where it's obvious what it should be doing is

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

Pretty much the only reason that this causes any problems is the case where you want to initialize a static array with a literal. In virtually _all_ other cases, what you want is a dynamic array, and making it a static one would just cause problems in many of them.

As such, this particular case should just be handled specially and optimize out the heap allocation rather than trying to alter how the literals themselves work. We already get that with strings. A string literal defaults to string, but you can pass it to a function taking wstring or dstring or assign it to a wstring or dstring variable. The compiler takes care of the conversion for you. So, assigning a static array with a literal would just be another case like that.

But since what you almost always want is a dynamic array, making the literal itself static would be asking for a heap of trouble.

- Jonathan M Davis

Ugh... you keep on saying "on occasion" and "particular case", making it seem like it's such a rarity that it's not worth mentioning.



Regarding your examples: the rule is quite simple:

- Literals are static by default
- If they are to be assigned to a dynamic array, then make them dynamic instead



But I really don't understand what benefit you get by making them dynamic by DEFAULT... and your answer didn't tell me anything, other than "most of the time you're assigning them to dynamic arrays" (which tells me nothing about the benefits).

On 06/11/2012 12:28 AM, Mehrdad wrote:
> Ugh... you keep on saying "on occasion" and "particular case", making it
> seem like it's such a rarity that it's not worth mentioning.
>
>
>
> Regarding your examples: the rule is quite simple:
>
> - Literals are static by default
> - If they are to be assigned to a dynamic array, then make them dynamic
> instead
>
>
>
> But I really don't understand what benefit you get by making them
> dynamic by DEFAULT... and your answer didn't tell me anything, other
> than "most of the time you're assigning them to dynamic arrays" (which
> tells me nothing about the benefits).

Type deduction.

On Monday, June 11, 2012 01:35:41 Timon Gehr wrote:
> On 06/11/2012 12:28 AM, Mehrdad wrote:
> > Ugh... you keep on saying "on occasion" and "particular case", making it seem like it's such a rarity that it's not worth mentioning.
> > 
> > 
> > 
> > Regarding your examples: the rule is quite simple:
> > 
> > - Literals are static by default
> > - If they are to be assigned to a dynamic array, then make them dynamic
> > instead
> > 
> > 
> > 
> > But I really don't understand what benefit you get by making them dynamic by DEFAULT... and your answer didn't tell me anything, other than "most of the time you're assigning them to dynamic arrays" (which tells me nothing about the benefits).
> 
> Type deduction.

Exactly. And if they need to be assigned to a static array, then the compiler can automatically do what it needs to do to avoid the extra heap allocation.

- Jonathan M Davis

>> Type deduction.
>
> Exactly. And if they need to be assigned to a static array, then the compiler
> can automatically do what it needs to do to avoid the extra heap allocation.
>
> - Jonathan M Davis


"Type deduction"?  o.O
I don't understand... could someone give me an example of what would break if we used the rule I suggested?

On Monday, June 11, 2012 02:08:53 Mehrdad wrote:
> >> Type deduction.
> > 
> > Exactly. And if they need to be assigned to a static array,
> > then the compiler
> > can automatically do what it needs to do to avoid the extra
> > heap allocation.
> > 
> > - Jonathan M Davis
> 
> "Type deduction"?  o.O
> I don't understand... could someone give me an example of what
> would break if we used the rule I suggested?

Pretty much anything involving templates would break. For instance,

auto found = find(arr, [1, 2]);

wouldn't compile, because [1, 2] would be considered a static array, which isn't a range.

- Jonathan M Davis