On Tuesday, 21 December 2021 at 17:06:04 UTC, Nick Treleaven wrote:

What it is conceptually, depends on how you conceptualize it. The most common conceptualization of "in" is as a set operation and you cannot represent a set with array indexes.

On Sunday, 19 December 2021 at 19:34:18 UTC, Ola Fosheim Grøstad wrote:

To guarantee amortized O(1) deletion, it is sufficient to ensure that shrink_threshold * growth_factor < growth_threshold. And if you look at the source code for D's built-in AAs, you will see that this is, in fact, ensured:

https://github.com/dlang/druntime/blob/v2.098.1/src/rt/aaA.d#L17-L27

So, we can safely put this discussion to rest, I think.

On Wednesday, 22 December 2021 at 14:27:32 UTC, Paul Backus wrote:

I haven't looked at the implementation of AAs or the allocator used, so I cannot tell whether it is O(1) amortized or not. You can test it by repeatedly adding/removing items near the thresholds.

A preliminary test suggests that the observed behaviour is rather wasteful, which should be a warning for anyone who considers using it in production.

It grows by a factor of 4, that is a lot of waste. It also appears to grow on deletion:

adding
changed 0 : 0
changed 6 : 8
changed 25 : 32
changed 102 : 128
changed 409 : 512
changed 1638 : 2048
changed 6553 : 8192

removing
changed 4095 : 32768
changed 1023 : 8192
changed 255 : 2048
changed 63 : 512
changed 15 : 128
changed 3 : 32

import std.stdio;

struct AA
{
    Impl* impl;
};

struct Impl {
    void*[] buckets;
};


void main(){
    immutable N = 6554;
    int[int] a;
    ulong nn = 0;
    writeln("adding");
    for(int i = 0; i<N; i++){
        auto b = a;
        a[i] = i;
    	auto aa = cast(AA*) &a;
    	auto n = aa.impl.buckets.length;
        if (n!=nn) {
            writeln("changed ", i, " : ", nn);
            nn = n;
        }
    }

    writeln("\nremoving");
    for(int i = N-1; i>=0; i--){
        auto b = a;
        a.remove(i);
    	auto aa = cast(AA*) &a;
    	auto n = aa.impl.buckets.length;
        if (n!=nn) {
            writeln("changed ", i, " : ", nn);
            nn = n;
        }
    }
}

On Wednesday, 29 December 2021 at 10:53:13 UTC, Ola Fosheim Grøstad wrote:

To put numbers on this, when deleting a long series of keys the hash table has consistently less than 13% filled slots, and right before shrinking it has 3% filled slots (1024/32768). That is a lot of wasted memory, 97%. Hash tables should not be worse than 75% waste as a rule of thumb.

With such high constant factors O(1) notation is of little value.

On Wednesday, 29 December 2021 at 11:26:48 UTC, Ola Fosheim Grøstad wrote:

Seems like an issue worth filing a bugzilla report about.

On Wednesday, 22 December 2021 at 12:43:26 UTC, Ola Fosheim Grøstad wrote:

in is defined for RedBlackTree, but it returns bool:
https://dlang.org/phobos/std_container_rbtree.html#.RedBlackTree.opBinaryRight

So aside from the complexity argument, element in arr could be defined if it returned bool, not a pointer (in order to be consistent with AAs not returning a pointer to the key). But due to time complexity it makes more sense to define index in arr.

On Wednesday, 29 December 2021 at 21:18:30 UTC, Paul Backus wrote:

Probably, I don't use AAs, but I can file an issue if nobody else has already.

On Tuesday, 21 December 2021 at 17:00:49 UTC, Steven Schveighoffer wrote:

Then maybe we in should be implemented; Have it check if you have it sorted (unless you do assumesorted template). If it is sorted naturally use BinarySearch, and if not it would probably do a linear search BUT give a warning message and file/line number so it can be fixed/traced? (Or just make it have to be Binary Search and asserts out if it isn't sorted)

As for bool vs pointer return... probably return a pointer as that can easily be tested as bool for no extra cost.