On 4/7/15 4:18 PM, Walter Bright wrote:
> On 4/7/2015 3:59 PM, Andrei Alexandrescu wrote:
>> On 4/7/15 3:56 PM, Walter Bright wrote:
>>> On 4/7/2015 3:14 PM, Andrei Alexandrescu wrote:
>>>> Arrays would need to move data. Current hashtables rely on values
>>>> staying put.
>>>
>>> If the array of buckets were enhanced to include the hashes, the
>>> key/value objects could stay untouched when the AA is grown. The
>>> key/value objects would only be dereferenced if the hashes matched.
>>
>> Not sure I understand. What if the collision array needs to grow? That
>> might
>> move it. -- Andrei
>
> The collision array is an array of pairs:
>
>      KeyValue *kv;
>      Hash_t hash;
>
> growing the array moves those around, but the locations of the array
> elements are never exposed to the users. The addresses of kv are
> exposed, but those don't move.

Ah, I thought the array embeds KeyValue directly. Thx! -- Andrei

On 4/7/15 7:01 PM, Walter Bright wrote:
> On 4/7/2015 3:33 PM, Steven Schveighoffer wrote:
>> Until that point, all these discussions on AA updates are useless.
>
> The data structure has changed before (used to be a binary tree) without
> disruption and can change again.
>

Sure but there are so many gotchas to this thing. Multiple very smart, very competent developers set out to change the AA and failed. I would rather effort be spent focusing on getting it into a full-fledged library type with simple lowering for syntax, and then we can play with everything we want to do. At least at that point, there aren't special considerations to worry about.

-Steve

On Tue, Apr 07, 2015 at 07:47:37PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
> On 4/7/15 7:01 PM, Walter Bright wrote:
> >On 4/7/2015 3:33 PM, Steven Schveighoffer wrote:
> >>Until that point, all these discussions on AA updates are useless.
> >
> >The data structure has changed before (used to be a binary tree) without disruption and can change again.
> >
> 
> Sure but there are so many gotchas to this thing. Multiple very smart, very competent developers set out to change the AA and failed. I would rather effort be spent focusing on getting it into a full-fledged library type with simple lowering for syntax, and then we can play with everything we want to do. At least at that point, there aren't special considerations to worry about.
[...]

Didn't somebody check in a whole bunch of PRs already in this direction? IIRC, there are only 1 or 2 more pieces left before AA's can be fully implemented as a library type.


T

-- 
People say I'm indecisive, but I'm not sure about that. -- YHL, CONLANG

On 4/7/2015 4:47 PM, Steven Schveighoffer wrote:
> On 4/7/15 7:01 PM, Walter Bright wrote:
>> On 4/7/2015 3:33 PM, Steven Schveighoffer wrote:
>>> Until that point, all these discussions on AA updates are useless.
>>
>> The data structure has changed before (used to be a binary tree) without
>> disruption and can change again.
>>
>
> Sure but there are so many gotchas to this thing. Multiple very smart, very
> competent developers set out to change the AA and failed. I would rather effort
> be spent focusing on getting it into a full-fledged library type with simple
> lowering for syntax, and then we can play with everything we want to do. At
> least at that point, there aren't special considerations to worry about.

Conform to the existing interface and it'll work.

"Steven Schveighoffer"  wrote in message news:mg1m0g$91e$1@digitalmars.com...

> The correct way forward is to implement the AA in the library in the safest way possible. Then, make the library implementation customizable for specialized situations. But it needs to be fully in the library, not partly in the compiler as it is now. Until that point, all these discussions on AA updates are useless.

I mostly agree, except I think we only need _an_ AA in the library, not necessarily _the_ AA. 

On Tuesday, 7 April 2015 at 19:09:21 UTC, deadalnix wrote:
> Food for thought :
>
> http://codecapsule.com/2013/11/11/robin-hood-hashing/
> http://people.csail.mit.edu/shanir/publications/disc2008_submission_98.pdf
>
> Also it is probably worthwhile to adopt various strategy depending on element types characteristics.

More food, D implementation and benchmark results (default AAs vs. Vibe.d linear probing vs. Robin Hood) :
http://www.infognition.com/blog/2014/on_robin_hood_hashing.html

On Tuesday, 7 April 2015 at 19:07:01 UTC, w0rp wrote:
> On Tuesday, 7 April 2015 at 18:35:27 UTC, Martin Nowak wrote:
> One thing I was wondering about, which you might know more about, is that I had to set my load factor to be half the size of the array, as quadratic probing seems to fail when more than half the buckets are filled. Is that correct, or did I make a mistake?

You made a mistake somewhere, the sweet spot should be in the range of 0.6-0.8. Quadratic probing with triangular numbers is guaranteed to fail only when your buckets are completely full.

On Tuesday, 7 April 2015 at 23:38:21 UTC, Andrei Alexandrescu wrote:
> Ah, I thought the array embeds KeyValue directly. Thx! -- Andrei

It should if they are relatively small compared to the pointer, or at least store the key inline. As we recently discussed about the freeing bug in the AA, it should be fine to store values inline, as long as the bucket array is never deleted.

On Tuesday, 7 April 2015 at 22:33:52 UTC, Steven Schveighoffer wrote:
> Until that point, all these discussions on AA updates are useless.

I really don't that all or nothing attitude, it condemns an important step, just because something better might be possible. It's also very comfortable, because this way nobody will ever have to do anything.

Improving the AA implementation has a big immediate effect, and will also help anyone writing a library implementation, because any candidate up to this date was still based on that crappy bucket list implementation.

The biggest problems in writing an AA library implementation sorted by difficulty are:
- deprecation of all magic AA behaviors (attributes, as[i][j]++)
- get the lowering right
- efficient construction and value insertion (rvalue moving)

On Wednesday, 8 April 2015 at 09:12:00 UTC, Martin Nowak wrote:
> The biggest problems in writing an AA library implementation sorted by difficulty are:

There is a clear acceptance list for a good AA here.
https://github.com/D-Programming-Language/druntime/pull/934#issuecomment-65916801