Index » General » hashed array? (page 4)

November 12, 2012
On 11/12/12, Andrej Mitrovic <andrej.mitrovich@gmail.com> wrote:
> Otherwise people use workarounds like "alias
> void[0][string] StringSet", and wrap such a type in a struct with
> operator overloads to emulate the built-in hash syntax.

Unfortunately this is also problematic with libraries which don't handle this type. For example serialization libraries can choke on such a type, and probably any routine that isn't specifically designed to work with void[0] will choke.
November 14, 2012
On 12/11/12 20:42, Jonathan M Davis wrote:
> On Monday, November 12, 2012 11:36:38 H. S. Teoh wrote:
>> I contend that the problem with built-in AA's is their implementation,
>> not the fact that they're built-in.
>
> Oh, I agree, but we, as a group, have obviously failed to handle the
> implementation of the built-in AAs properly, and I think that the indications
> are definitely that it's harder to get the built-in AAs right that it would be
> to create a library solution.

I disagree with that 100%.
Built-in AAs in D1 work fine (They could use a lot of improvement, but there's nothing wrong with the basic approach, it's quite simple). It was the idea that they could be seamlessly moved to a library type that was an unmitigated disaster.

And for some reason, there has been a refusal to roll it back to the old method which worked.

The thing that really really should change is the bizarre 'magic null' semantics of AAs.
November 14, 2012
On Wed, Nov 14, 2012 at 10:25:53AM +0100, Don Clugston wrote:
> On 12/11/12 20:42, Jonathan M Davis wrote:
> >On Monday, November 12, 2012 11:36:38 H. S. Teoh wrote:
> >>I contend that the problem with built-in AA's is their implementation, not the fact that they're built-in.
> >
> >Oh, I agree, but we, as a group, have obviously failed to handle the implementation of the built-in AAs properly, and I think that the indications are definitely that it's harder to get the built-in AAs right that it would be to create a library solution.
> 
> I disagree with that 100%.
> Built-in AAs in D1 work fine (They could use a lot of improvement,
> but there's nothing wrong with the basic approach, it's quite
> simple).

I don't know how AA's worked in D1, but the current codebase does not handle complex value types correctly. For one thing, it uses bitwise comparison of *arbitrary types*, as opposed to using opEquals or some such built-in language capability. This is the source of a good number of AA bugs.


> It was the idea that they could be seamlessly moved to a library type that was an unmitigated disaster.

The problem is with making byKey and byValue return ranges, which is a Phobos concept. That is the source of the schizophrenic code duplication in object_.d, which probably hides a subtle bug or two. Basically, it's the conflict between making AA's built-in, and making them compatible with a Phobos concept.

Either we make it built-in, and if ranges are required then we add new functions to aaA.d that return ranges, or we make it library-level code, which means we move it out of aaA.d and add lowerings in the compiler to map it to a library type. Trying to straddle the two only leads to disaster.


> And for some reason, there has been a refusal to roll it back to the old method which worked.
> 
> The thing that really really should change is the bizarre 'magic null' semantics of AAs.

Agreed.


T

-- 
May you live all the days of your life. -- Jonathan Swift
November 14, 2012
On 11/14/12 1:25 AM, Don Clugston wrote:
> On 12/11/12 20:42, Jonathan M Davis wrote:
>> On Monday, November 12, 2012 11:36:38 H. S. Teoh wrote:
>>> I contend that the problem with built-in AA's is their implementation,
>>> not the fact that they're built-in.
>>
>> Oh, I agree, but we, as a group, have obviously failed to handle the
>> implementation of the built-in AAs properly, and I think that the
>> indications
>> are definitely that it's harder to get the built-in AAs right that it
>> would be
>> to create a library solution.
>
> I disagree with that 100%.
> Built-in AAs in D1 work fine (They could use a lot of improvement, but
> there's nothing wrong with the basic approach, it's quite simple). It
> was the idea that they could be seamlessly moved to a library type that
> was an unmitigated disaster.
>
> And for some reason, there has been a refusal to roll it back to the old
> method which worked.

I think it is an absolute must that we move forward with a library implementation.

> The thing that really really should change is the bizarre 'magic null'
> semantics of AAs.

This is new! What does this mean?


Andrei
November 14, 2012
11/14/2012 9:44 PM, Andrei Alexandrescu пишет:
> On 11/14/12 1:25 AM, Don Clugston wrote:
>> On 12/11/12 20:42, Jonathan M Davis wrote:
>>> On Monday, November 12, 2012 11:36:38 H. S. Teoh wrote:
>>>> I contend that the problem with built-in AA's is their implementation,
>>>> not the fact that they're built-in.
>>>
>>> Oh, I agree, but we, as a group, have obviously failed to handle the
>>> implementation of the built-in AAs properly, and I think that the
>>> indications
>>> are definitely that it's harder to get the built-in AAs right that it
>>> would be
>>> to create a library solution.
>>
>> I disagree with that 100%.
>> Built-in AAs in D1 work fine (They could use a lot of improvement, but
>> there's nothing wrong with the basic approach, it's quite simple). It
>> was the idea that they could be seamlessly moved to a library type that
>> was an unmitigated disaster.
>>
>> And for some reason, there has been a refusal to roll it back to the old
>> method which worked.
>
> I think it is an absolute must that we move forward with a library
> implementation.
>
>> The thing that really really should change is the bizarre 'magic null'
>> semantics of AAs.
>
> This is new! What does this mean?
>

I'm sure it is nothing new. Basically AA is a reference type but it is auto-magically created on the first insertion. This is called magic null behavior.

void foo(int[int] aa){
//aa here is null
	aa[1] = 1;
//now the local aa points to a new hash-map
}

void main(){
	int[int] map;
	foo(map);
	//map in this scope is still null
	assert(1 in map); // fails
}


I'm in favor of implicitly allocating an AA on definition that'll make it a proper reference type.

-- 
Dmitry Olshansky
November 14, 2012
On 11/14/2012 7:20 PM, Dmitry Olshansky wrote:
> 11/14/2012 9:44 PM, Andrei Alexandrescu пишет:
>>
>> This is new! What does this mean?
>>
>
> I'm sure it is nothing new. Basically AA is a reference type but it is
> auto-magically created on the first insertion. This is called magic null
> behavior.
>
> void foo(int[int] aa){
> //aa here is null
>      aa[1] = 1;
> //now the local aa points to a new hash-map
> }
>
> void main(){
>      int[int] map;
>      foo(map);
>      //map in this scope is still null
>      assert(1 in map); // fails
> }
>
>
> I'm in favor of implicitly allocating an AA on definition that'll make
> it a proper reference type.
>

I don't like the "magic null behaviour", but I see issues with this straight forward implementation: how can you define a statically initialized struct value (including init) that contains an associative array? It will have to run a default constructor to allocate the AA root object, introducing something like the often rejected user-defined default constructor for structs.
November 14, 2012
On 14.11.2012 20:15, Rainer Schuetze wrote:
>
> On 11/14/2012 7:20 PM, Dmitry Olshansky wrote:
>> 11/14/2012 9:44 PM, Andrei Alexandrescu пишет:
>>>
>>> This is new! What does this mean?
>>>
>>
>> I'm sure it is nothing new. Basically AA is a reference type but it is
>> auto-magically created on the first insertion. This is called magic null
>> behavior.
>>
>> void foo(int[int] aa){
>> //aa here is null
>> aa[1] = 1;
>> //now the local aa points to a new hash-map
>> }
>>
>> void main(){
>> int[int] map;
>> foo(map);
>> //map in this scope is still null
>> assert(1 in map); // fails
>> }
>>
>>
>> I'm in favor of implicitly allocating an AA on definition that'll make
>> it a proper reference type.
>>
>
> I don't like the "magic null behaviour", but I see issues with this
> straight forward implementation: how can you define a statically
> initialized struct value (including init) that contains an associative
> array? It will have to run a default constructor to allocate the AA root
> object, introducing something like the often rejected user-defined
> default constructor for structs.

It doesn't need to allocate any keys or values. It just needs to allocate whatever structure it needs to keep track of how many items it has. As if you added an element, and then removed it.


November 14, 2012
On Wednesday, November 14, 2012 20:29:03 Don wrote:
> It doesn't need to allocate any keys or values. It just needs to allocate whatever structure it needs to keep track of how many items it has. As if you added an element, and then removed it.

Except that that doesn't play nicely with init. Instead of using init, it would have to be default constructed, which goes against how every other type works and risks causing problems outside of the case where you simply declare an AA as a local variable. For instance, it wouldn't work at all when an AA is a member variable of a struct.

I understand wanting to get rid of the magic initialization nonsense, but what it does is completely consistent with how dynamic arrays work, and making it work otherwise would make it inconsistent with every other type in D with regards to default-initiliazation.

We _do_ need a way to indicate that an AA should be properly initialized without inserting anything into it (having to insert and then remove something to do that is atrocious), but I don't think that default constructing AAs will fly.

- Jonathan M Davis
November 14, 2012
On 14.11.2012 16:39, H. S. Teoh wrote:
> On Wed, Nov 14, 2012 at 10:25:53AM +0100, Don Clugston wrote:
>> On 12/11/12 20:42, Jonathan M Davis wrote:
>>> On Monday, November 12, 2012 11:36:38 H. S. Teoh wrote:
>>>> I contend that the problem with built-in AA's is their
>>>> implementation, not the fact that they're built-in.
>>>
>>> Oh, I agree, but we, as a group, have obviously failed to handle the
>>> implementation of the built-in AAs properly, and I think that the
>>> indications are definitely that it's harder to get the built-in AAs
>>> right that it would be to create a library solution.
>>
>> I disagree with that 100%.
>> Built-in AAs in D1 work fine (They could use a lot of improvement,
>> but there's nothing wrong with the basic approach, it's quite
>> simple).
>
> I don't know how AA's worked in D1, but the current codebase does not
> handle complex value types correctly. For one thing, it uses bitwise
> comparison of *arbitrary types*, as opposed to using opEquals or some
> such built-in language capability. This is the source of a good number
> of AA bugs.
>
>
>> It was the idea that they could be seamlessly moved to a library type
>> that was an unmitigated disaster.
>
> The problem is with making byKey and byValue return ranges, which is a
> Phobos concept. That is the source of the schizophrenic code duplication
> in object_.d, which probably hides a subtle bug or two. Basically, it's
> the conflict between making AA's built-in, and making them compatible
> with a Phobos concept.

Yeah, that's from the library point view. From the compiler side, the problem is that this is a type which the compiler knows far too much about.
I cannot see any way that the coupling between compiler and library can be less than we started with. The compiler has to relinquish control over most of the semantics, but cannot get rid of it all.

>
> Either we make it built-in, and if ranges are required then we add new
> functions to aaA.d that return ranges, or we make it library-level code,
> which means we move it out of aaA.d and add lowerings in the compiler to
> map it to a library type. Trying to straddle the two only leads to
> disaster.
>
>
>> And for some reason, there has been a refusal to roll it back to the
>> old method which worked.
>>
>> The thing that really really should change is the bizarre 'magic
>> null' semantics of AAs.
>
> Agreed.
>
>
> T
>

November 14, 2012
On 11/14/12 10:20 AM, Dmitry Olshansky wrote:
> 11/14/2012 9:44 PM, Andrei Alexandrescu пишет:
>> On 11/14/12 1:25 AM, Don Clugston wrote:
>>> The thing that really really should change is the bizarre 'magic null'
>>> semantics of AAs.
>>
>> This is new! What does this mean?
>>
>
> I'm sure it is nothing new. Basically AA is a reference type but it is
> auto-magically created on the first insertion. This is called magic null
> behavior.

Oh I see. Well it's not that magic because it can be done in library code.

Andrei
Next ›   Last »
1 2 3 4
Top | Discussion index | About this forum | D home