On 02/11/16 05:36, Andrei Alexandrescu wrote:
> Cons:
>
> * Built-in hashtables are a convenience facility more than a
> high-performance one, so providing an efficiency-oriented primitive
> seems a bit odd.
>

I think that, in itself, is a mistake. A language that thinks of itself as a system programming language cannot, I think, provide hash functions that are designed to be "convenience over performance".

I also think the basic approach is flawed. If we're talking about GC backs storage for everything, then "reserve" should not attempt to pre-allocate memory to the values. Instead, "reserve" should set the hash table size.

In other words, if I call "hash.reserve(10_000)", and then insert 10,000 elements, I'm less concerned with allocations for the values (especially if it's defined to be GC controlled and non-contiguous anyways), and more concerned about it not rehashing while I insert due to the table getting full.

To me, "reserve" is more about preventing copying data around due to the data structure being surprised from the number of elements it needs to handle than it is about preventing any allocations during the insert. If the values are stored in a linked list, and do not need to be copied no matter what, then reserve need not do anything about them at all.

Lastly, if "reserve" doesn't do anything under a certain implementation because it makes no sense, that is not a problem as far as I'm concerned. If an implementation does not gain performance from calling "reserve", that is not a reason not to have the function. It can just be a no-op, and I'm fine with calling it an "implementation detail". As such, I don't think it is a problem for future changes to the underlying structure.

Shachar

On 03/11/16 23:00, Yuxuan Shui wrote:
> On Wednesday, 2 November 2016 at 03:36:42 UTC, Andrei Alexandrescu wrote:
>> [snip]
>>
>> * The implementation cannot use Phobos' allocator because it's in
>> druntime.
>
> How about let the user provide the memory block when they calls reserve()?
>

I think that's just a halfhearted attempt at introducing STL's allocators.

Shachar

On Friday, 4 November 2016 at 09:37:39 UTC, Shachar Shemesh wrote:
> On 03/11/16 23:00, Yuxuan Shui wrote:
>> On Wednesday, 2 November 2016 at 03:36:42 UTC, Andrei Alexandrescu wrote:
>>> [snip]
>>>
>>> * The implementation cannot use Phobos' allocator because it's in
>>> druntime.
>>
>> How about let the user provide the memory block when they calls reserve()?
>>
>
> I think that's just a halfhearted attempt at introducing STL's allocators.

I see this topic started a clash of opinions regarding the future of AAs. After Andrei suggested a free-list implementation I had a good idea of how to proceed but now I am not so sure since this discussion isn't converging to a single idea/implementation.

On Sunday, 6 November 2016 at 02:12:12 UTC, Alexandru Caciulescu wrote:
> On Friday, 4 November 2016 at 09:37:39 UTC, Shachar Shemesh wrote:
>> On 03/11/16 23:00, Yuxuan Shui wrote:
>>> On Wednesday, 2 November 2016 at 03:36:42 UTC, Andrei Alexandrescu wrote:
>>>> [snip]
>>>>
>>>> * The implementation cannot use Phobos' allocator because it's in
>>>> druntime.
>>>
>>> How about let the user provide the memory block when they calls reserve()?
>>>
>>
>> I think that's just a halfhearted attempt at introducing STL's allocators.
>
> I see this topic started a clash of opinions regarding the future of AAs. After Andrei suggested a free-list implementation I had a good idea of how to proceed but now I am not so sure since this discussion isn't converging to a single idea/implementation.
>
To make a concrete proposal - For near-term, against current AAs, add a 'reserve()' function that pre-allocates the bucket array, but not the memory for elements. This would be consistent with the current implementation. It looks like it could be done via a call to the 'resize()' function. It would be similar to the 'rehash()' function (see _aaRehash() in aaA.d). Memory allocation and management for inserted elements is unchanged, it continues to operate as current. This approach would be similar to how the C++ std::unordered_map::reserve() function works.

This still permits a longer term approach adding template-based hash tables in the future, with various options for memory management, etc.

I think this suggestion is consistent with Steve Schveighoffer's suggestion earlier in the thread.

--Jon

On Sunday, 6 November 2016 at 03:28:20 UTC, Jon Degenhardt wrote:
> On Sunday, 6 November 2016 at 02:12:12 UTC, Alexandru Caciulescu wrote:
>>
>> I see this topic started a clash of opinions regarding the future of AAs. After Andrei suggested a free-list implementation I had a good idea of how to proceed but now I am not so sure since this discussion isn't converging to a single idea/implementation.
>>
> [Snip]
>
> I think this suggestion is consistent with Steve Schveighoffer's suggestion earlier in the thread.
>
> --Jon

I agree with what Jon Degenhardt said. It also seems to be in agreement with what Shachar Shemesh and Steven Schveighoffer wrote regarding the implementation of a reserve function for the built in AAs.

On Sunday, 6 November 2016 at 09:32:33 UTC, safety0ff wrote:
> On Sunday, 6 November 2016 at 03:28:20 UTC, Jon Degenhardt wrote:
>> On Sunday, 6 November 2016 at 02:12:12 UTC, Alexandru Caciulescu wrote:
>>>
>>> I see this topic started a clash of opinions regarding the future of AAs. After Andrei suggested a free-list implementation I had a good idea of how to proceed but now I am not so sure since this discussion isn't converging to a single idea/implementation.
>>>
>> [Snip]
>>
>> I think this suggestion is consistent with Steve Schveighoffer's suggestion earlier in the thread.
>>
>> --Jon
>
> I agree with what Jon Degenhardt said. It also seems to be in agreement with what Shachar Shemesh and Steven Schveighoffer wrote regarding the implementation of a reserve function for the built in AAs.

Alex, Andrei - Any updates on pursuing this?

On Wednesday, 4 January 2017 at 08:00:14 UTC, Jon Degenhardt wrote:
> Alex, Andrei - Any updates on pursuing this?

https://github.com/dlang/druntime/pull/1929#pullrequestreview-67691304