Yes, we'll have the freedom to choose and compare.

Andrei

On 2/2/12 3:19 PM, Martin Nowak wrote:
>>> I _suspect_ that if we try this, we'll find it isn't yet possible to do library AAs. Are we able to generate error messages at compile time when the same key is used twice? Maybe, maybe not. For sure we'll have to deal with template bloat.
> No template bloat needed if the implementation would use an untyped
> implementation
> with comparison/hash callbacks. But this making them templated might be
> a performance win.
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals

Ok, I've made https://github.com/D-Programming-Language/dmd/pull/688 and https://github.com/D-Programming-Language/druntime/pull/143 to remove AssociateArray from dmd, and moved the extensions into ufcs methods in object.d/di.

(I left byKey/byValue -> ranges out, because this was broken in ctfe and required duplicating the implementation)

Please review and test if you can.  Don, I hope I haven't mangled the interpreter too much.  Do you know how to force an AA ref variable into an AA literal?

On Fri, Feb 3, 2012 at 10:35 AM, Andrei Alexandrescu <andrei at erdani.com> wrote:
> Yes, we'll have the freedom to choose and compare.
>
> Andrei
>
>
> On 2/2/12 3:19 PM, Martin Nowak wrote:
>>>>
>>>> I _suspect_ that if we try this, we'll find it isn't yet possible to do library AAs. Are we able to generate error messages at compile time when the same key is used twice? Maybe, maybe not. For sure we'll have to deal with template bloat.
>>
>> No template bloat needed if the implementation would use an untyped
>> implementation
>> with comparison/hash callbacks. But this making them templated might be
>> a performance win.
>> _______________________________________________
>> dmd-internals mailing list
>> dmd-internals at puremagic.com
>> http://lists.puremagic.com/mailman/listinfo/dmd-internals
>
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals

As someone who's actually developed a hashmap in D2, I'd agree with Don that there are still some things that cannot fully implement how builtin AA's work (most glaring example is lack of constructor that takes literal values).? But it's better to have this part of the system pluggable.? Not only does it allow one to utilize D's power to work on something intrinsic like this, but it makes things simpler to understand from a maintenance perspective.? Not to mention, I could make AA's into dcollections hashmaps with some simple changes to the runtime :)


I agree with the approach below except for 2 things:

1. D1 AA's used a tree to handle bucket collisions, I don't think we should roll back that far (not sure what the state of D1 AAs are today).
2. This conversion:  [a:b, c:d] -->? AALiteral([a, c], [b, d]) should *NOT* use the heap for the two array literals.? I'm not sure how you can declare AALiteral such that this doesn't happen, but this needs to be solved.


-Steve



----- Original Message -----
> From: Andrei Alexandrescu <andrei at erdani.com>
> To: Don Clugston <dclugston at googlemail.com>; Discuss the internals of DMD <dmd-internals at puremagic.com>
> Cc:
> Sent: Thursday, February 2, 2012 5:11 PM
> Subject: Re: [dmd-internals] AssociativeArray in druntime should go before the next release
> 
> +dmd-internals back with Don's approval
> 
> Love this idea (below). If you folks bring things to a stable state for this release, I'll personally work on a library associative array implementation.
> 
> 
> Thanks!
> 
> Andrei
> 
> On 2/2/12 12:55 PM, Don Clugston wrote:
>>  On 2 February 2012 20:39, Andrei Alexandrescu<andrei at erdani.com>?
> wrote:
>>>  Ouch. We definitely need to fix this, apologies for unknowingly
> breaking so
>>>  much stuff.
>>> 
>>>  Long term we must adjust the compiler to simply lower special AA
> notation
>>>  into "regular" D code so we can rely on the library
> implementation. I'm not
>>>  sure what the best route would be for CTFE (special-case AAs vs.
>>>  interpreting the implementation in object.d).
>>> 
>>>  BTW what's the awful thing you mention in object.di? You mean the
> cast must
>>>  be interpreted during compilation?
>> 
>>  No. In that code, we're in an AA value[key] syntax that has been
>>  changed to an AssocArray!(key, value) struct.
>>  Now, we cast the first element of that struct into an AA. What it's
> doing is
>>  cast(typeof(this))this.
>>  but the two 'this'es are not the same. The original this is
> AssocArray
>>  template, while the typeof(this) is the compiler representation that
>>  corresponds to.
>>  They should be the same, but the 'in' syntax only works for the
>>  compiler 'this', not the runtime 'this'. Then, the poor
> compiler has
>>  to change it back into AssocArray!(). The really fun bit for CTFE is
>>  that with -inline, it all disappears; all you see is a void** getting
>>  cast to an template struct called 'AssociativeArray'. And that
> needs
>>  to work with array literals!!
>> 
>>  My feeling is, that the whole approach is doomed to failure. It is
>>  intrinsic fragile. I would suggest rolling back to the original D1
>>  AAs, which worked.
>>  Then, develop the new AA from scratch, _as if the built-in ones did
>>  not exist_. That includes, no AA literal syntax. Do it in a seperate,
>>  free-standing module.
>>  Once that is completely working, connect it up. Compilers role is
>>  simply to translate
>> 
>>  value[key] --->? AssocArray!(key, value)
>>  [a:b, c:d] -->? AALiteral([a, c], [b, d])?  or whatever the chosen
> syntax is.
>>  The compiler must not do anything more than that. No semantics, no
>>  error messages, nothing. Pure syntax sugar, no semantic sugar. The
>>  type 'Taarray' (Associative array)? and ArrayLiteralExp? should not
>>  exist except in the parser.
>> 
>>  The compiler must either know everything about AAs, or nothing. There
>>  is no middle ground.
>> 
>>  I _suspect_ that if we try this, we'll find it isn't yet possible
> to
>>  do library AAs. Are we able to generate error messages at compile time
>>  when the same key is used twice? Maybe, maybe not. For sure we'll have
>>  to deal with template bloat.
> _______________________________________________
> dmd-internals mailing list
> dmd-internals at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/dmd-internals
> 

On Sat, Feb 4, 2012 at 2:31 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:
> As someone who's actually developed a hashmap in D2, I'd agree with Don that there are still some things that cannot fully implement how builtin AA's work (most glaring example is lack of constructor that takes literal values).? But it's better to have this part of the system pluggable.? Not only does it allow one to utilize D's power to work on something intrinsic like this, but it makes things simpler to understand from a maintenance perspective.? Not to mention, I could make AA's into dcollections hashmaps with some simple changes to the runtime :)
>
>
> I agree with the approach below except for 2 things:
>
> 1. D1 AA's used a tree to handle bucket collisions, I don't think we should roll back that far (not sure what the state of D1 AAs are today).

Nowhere near that far.  All that's getting rolled back is the AssociativeArray templated struct in object.d, which basically just forwards to the druntime functions (_aaGet, _aaRehash, etc)  The most prominent effect of this struct is the multitude of AA ice bugs.

> 2. This conversion: ?[a:b, c:d] -->? AALiteral([a, c], [b, d]) should *NOT* use the heap for the two array literals.? I'm not sure how you can declare AALiteral such that this doesn't happen, but this needs to be solved.
>

It's not about how AALiteral is declared, it's how the compiler calls
it.  For a lot of druntime calls it currently does something along the
lines of:
Key[dim] keys;
... store the keys ...
Value[dim] values;
... store the values ...
aa = AAliteral(key, value);

We'll need to define an interface, but that's just the point - the current half-language/half-runtime solution doesn't have this.

>________________________________
> From: Daniel Murphy <yebblies at gmail.com>
>On Sat, Feb 4, 2012 at 2:31 AM, Steve Schveighoffer <schveiguy at yahoo.com> wrote:
>> 2. This conversion: ?[a:b, c:d] -->? AALiteral([a, c], [b, d]) should *NOT* use the heap for the two array literals.? I'm not sure how you can declare AALiteral such that this doesn't happen, but this needs to be solved.
>>
>
>It's not about how AALiteral is declared, it's how the compiler calls
>it.? For a lot of druntime calls it currently does something along the
>lines of:
>Key[dim] keys;
>... store the keys ...
>Value[dim] values;
>... store the values ...
>aa = AAliteral(key, value);
>
>We'll need to define an interface, but that's just the point - the current half-language/half-runtime solution doesn't have this.

Right, the point I was bringing is that if the new method is to do a simple lowering using the above translation, today that means heap allocations.? If that means we need to invent some new syntax, I'm all for it, or if it means the compiler needs to do a translation more like what you said than a simple expression change, then so be it.
I just don't want to move from the current method to something that unnecessarily heap-allocates, we already have enough of that.

-Steve

On Fri, 03 Feb 2012 20:11:18 +0100, Steve Schveighoffer <schveiguy at yahoo.com> wrote:

>> ________________________________
>> From: Daniel Murphy <yebblies at gmail.com>
>> On Sat, Feb 4, 2012 at 2:31 AM, Steve Schveighoffer
>> <schveiguy at yahoo.com> wrote:
>>> 2. This conversion:  [a:b, c:d] -->  AALiteral([a, c], [b, d]) should *NOT* use the heap for the two array literals.  I'm not sure how you can declare AALiteral such that this doesn't happen, but this needs to be solved.
>>>
>>
>> It's not about how AALiteral is declared, it's how the compiler calls
>> it.  For a lot of druntime calls it currently does something along the
>> lines of:
>> Key[dim] keys;
>> ... store the keys ...
>> Value[dim] values;
>> ... store the values ...
>> aa = AAliteral(key, value);
>>
>> We'll need to define an interface, but that's just the point - the current half-language/half-runtime solution doesn't have this.
>
> Right, the point I was bringing is that if the new method is to do a
> simple lowering using the above translation, today that means heap
> allocations.  If that means we need to invent some new syntax, I'm all
> for it, or if it means the compiler needs to do a translation more like
> what you said than a simple expression change, then so be it.
> I just don't want to move from the current method to something that
> unnecessarily heap-allocates, we already have enough of that.
>
> -Steve
What is allocating?
Are you referring to this
http://d.puremagic.com/issues/show_bug.cgi?id=2356?

----- Original Message -----
> From: Martin Nowak <dawg at dawgfoto.de>

> <schveiguy at yahoo.com> wrote:
> 
>>  I just don't want to move from the current method to something that
> unnecessarily heap-allocates, we already have enough of that.
>> 
> What is allocating?
> Are you referring to this http://d.puremagic.com/issues/show_bug.cgi?id=2356?

Yes.? Except this would be yet another case to add.

What I am saying is, if we go with the lowering of:

[a:b, c:d] => AALiteral([a,c], [b,d]);

I would like to have this not needlessly allocate the arrays [a, c] and [b, d] on the heap, since those arrays will be unused after that call.? To use the heap would be a step backwards, since the current AA literal code does not use it.

-Steve

On 2/3/12 2:28 PM, Steve Schveighoffer wrote:
> What I am saying is, if we go with the lowering of:
>
> [a:b, c:d] =>  AALiteral([a,c], [b,d]);
>
> I would like to have this not needlessly allocate the arrays [a, c] and [b, d] on the heap, since those arrays will be unused after that call.  To use the heap would be a step backwards, since the current AA literal code does not use it.
>
> -Steve

I think the language is powerful enough to afford us the rewrite:

[a:b, c:d] => aaLiteral(a, b, c, d)


Andrei

I'd much rather fix implicit storage of literals than incur both template bloat and have to deal with type deduction.? Besides the heap allocation issue, the rewrite that Don put forth already uses the compiler to type deduce the array types (and therefore the key and value types) without any excessive template bloat.? I'm assuming you meant something like:

SomeRecursiveTemplateToDeduceKeyAndValue!(T) AALiteral(T...)(T vals) if (vals.length % 2 == 0 && SomeRecursiveTemplateToEnsureKeyAndValueExist!(T))

What I was thinking is making something like:

void foo(scope int[]) {}
not allocate the argument to foo on the heap if it's a literal.


-Steve



----- Original Message -----
> From: Andrei Alexandrescu <andrei at erdani.com>
> To: Steve Schveighoffer <schveiguy at yahoo.com>; Discuss the internals of DMD <dmd-internals at puremagic.com>
> Cc:
> Sent: Friday, February 3, 2012 6:25 PM
> Subject: Re: [dmd-internals] AssociativeArray in druntime should go before the next release
> 
> On 2/3/12 2:28 PM, Steve Schveighoffer wrote:
>>  What I am saying is, if we go with the lowering of:
>> 
>>  [a:b, c:d] =>? AALiteral([a,c], [b,d]);
>> 
>>  I would like to have this not needlessly allocate the arrays [a, c] and [b,
> d] on the heap, since those arrays will be unused after that call.? To use the heap would be a step backwards, since the current AA literal code does not use it.
>> 
>>  -Steve
> 
> I think the language is powerful enough to afford us the rewrite:
> 
> [a:b, c:d] => aaLiteral(a, b, c, d)
> 
> 
> Andrei
> 

On 4 February 2012 00:56, Steve Schveighoffer <schveiguy at yahoo.com> wrote:
> I'd much rather fix implicit storage of literals than incur both template bloat and have to deal with type deduction.? Besides the heap allocation issue, the rewrite that Don put forth already uses the compiler to type deduce the array types (and therefore the key and value types) without any excessive template bloat.? I'm assuming you meant something like:
>
> SomeRecursiveTemplateToDeduceKeyAndValue!(T) AALiteral(T...)(T vals) if (vals.length % 2 == 0 && SomeRecursiveTemplateToEnsureKeyAndValueExist!(T))
>
> What I was thinking is making something like:
>
> void foo(scope int[]) {}
> not allocate the argument to foo on the heap if it's a literal.
>
>
> -Steve

Note that there is no urgency on this. It's more important to get it
right, and that includes avoiding unnecessary heap allocations.
It should not be tied into the compiler, until it's behaving perfectly
except for syntax sugar.